Art of Problem Solving
Chris Piech and Mehran Sahami
CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
First, a cool program
Piech and Sahami, CS106A, Stanford University
Today’s Goal
1. Decomposition: Be able to approach a problem “top down”
2. Stepwise Refinement: Balance testing while decomposing
Piech and Sahami, CS106A, Stanford University
Quick review
Piech and Sahami, CS106A, Stanford University
Karel the Robot
Piech and Sahami, CS106A, Stanford University
Functions
def main():
go_to_moon()
def go_to_moon():
build_spaceship()
# a few more steps
def build_spaceship():
# todo
put_beeper()
Piech and Sahami, CS106A, Stanford University
For Loops
def main():
# repeats the body 99 times
for i in range(99):
# the “body”
put_beeper()
Piech and Sahami, CS106A, Stanford University
While Loops
def main():
# while condition holds runs body
# checks condition after body completes
while front_is_clear():
move()
Piech and Sahami, CS106A, Stanford University
If Statement
def main():
# If the condition holds, runs body
if front_is_clear():
move()
Piech and Sahami, CS106A, Stanford University
If / Else Statement
def main():
# If the condition holds,
if beepers_present():
# do this
pick_beeper()
else :
# otherwise, do this
put_beeper()
Piech and Sahami, CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
End review
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
Make Pasta from Scratch
Piech and Sahami, CS106A, Stanford University
Make Pasta from Scratch
Piech and Sahami, CS106A, Stanford University
My helper is a 3 year old.
Like Karel, needs very clear
instructions
We are going to
need to decompose
the task
Piech and Sahami, CS106A, Stanford University
Make Pasta from Scratch
make_dough() shape_pasta() cook_pasta()
Piech and Sahami, CS106A, Stanford University
Make Pasta from Scratch
Piech and Sahami, CS106A, Stanford University
Mountain Karel
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
Mountain Karel
Piech and Sahami, CS106A, Stanford University
Mountain Karel
Muhammed ibn
Musa Al Kwarizmi
Piech and Sahami, CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
Pro Tips
A good function should do ”one conceptual thing”
Know what it does by looking at its name
Less than 10 lines, 3 levels of indentation
Reusable and easy to modify
Well commented
There are two types of programs.
One is so complex, there is nothing obvious wrong with it.
One is so clear, that
Piech andthis obviously
Sahami, nothing
CS106A, Stanford wrong with it.
University
Aside: Common Errors
Lather,
Rinse,
Repeat
Piech and Sahami, CS106A, Stanford University
Infinite Loop
def turn_to_wall():
while left_is_clear():
turn_left()
Piech and Sahami, CS106A, Stanford University
Infinite Loop
def turn_to_wall():
while left_is_clear():
turn_left()
Piech and Sahami, CS106A, Stanford University
Infinite Loop
def turn_to_wall():
while left_is_clear():
turn_left()
Piech and Sahami, CS106A, Stanford University
Infinite Loop
def turn_to_wall():
while left_is_clear():
turn_left()
Piech and Sahami, CS106A, Stanford University
Pre/Post that Don’t Match
What do you
def climb_mountain: assume here?
while front_is_clear():
# step up
move()
turn_left()
move()
Does the end condition of
the loop match the start
assumptions?
Piech and Sahami, CS106A, Stanford University
Rhoomba Karel
8 . . . . . . . .
7 . . . . . . . .
6 . . . . . . . .
5 . . . . . . . .
4 . . . . . . . .
3 . . . . . . . .
2 . . . . . . . .
1 . . . . . . . .
1 2 3 4 5 6 7 8 An actual Rhoomba Robot
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
Rhoomba Karel
• Write a Roomba Karel that sweeps the entire world of all
beepers.
8 . . . . . . . .
– Karel starts at (1,1) facing East.
– The world is rectangular, and 7 . . . . . . . .
some squares contain beepers.
– There are no interior walls. 6 . . . . . . . .
– When the program is done, the 5 . . . . . . . .
world should contain 0 beepers.
4 . . . . . . . .
– Karel's ending location
does not matter. 3 . . . . . . . .
2 . . . . . . . .
• How should we approach
this tricky problem? 1 . . . . . . . .
1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Possible Algorithm 1
. . . . . . . .
8
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . .
5
. . . . . . . .
4
. . . . . . . .
3
. . . . . . . .
2
1
. . . . . . . .
1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Possible Algorithm 2
. . . . . . . .
8
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . .
5
. . . . . . . .
4
. . . . . . . .
3
. . . . . . . .
2
1
. . . . . . . .
1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Possible Algorithm 3
. . . . . . . .
8
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . .
5
. . . . . . . .
4
. . . . . . . .
3
. . . . . . . .
2
1
. . . . . . . .
1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Possible Algorithm 4
. . . . . . . .
8
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . .
5
. . . . . . . .
4
. . . . . . . .
3
. . . . . . . .
2
1
. . . . . . . .
1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Which Algorithm???
. . . . . . . . . . . . . . . .
8
. . . . . . . . 8
. . . . . . . .
7
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . .
6
. . . . . . . .
5
. . . . . . . .
5
. . . . . . . .
4
. . . . . . . .
4
. . . . . . . .
3
. . . . . . . .
3
. . . . . . . .
2
. . . . . . . .
2
1
. . . . . . . .
1
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
. . . . . . . . . . . . . . . .
8
. . . . . . . .
8
. . . . . . . .
7
. . . . . . . .
7
. . . . . . . .
6
. . . . . . . . 6
. . . . . . . .
5
. . . . . . . . 5
. . . . . . . .
4
. . . . . . . . 4
. . . . . . . .
3
. . . . . . . . 3
. . . . . . . .
2
1
. . . . . . . . 2
1
. . . . . . . .
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
Piech and Sahami, CS106A, Stanford University
Rhoomba Karel
Piech and Sahami, CS106A, Stanford University
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
def art_of_problem_solving():
# lesson plan
decomposition()
mountain_karel()
rhoomba_karel()
if extra_time():
word_search_karel()
Piech and Sahami, CS106A, Stanford University
