CS 5 Today CS 5 alien on strike! Fractals and Turtles More Eyes! Photograph of CS 5 co-worker accused of burnination. How random! hw2 due Monday Lots of tutoring https://www.youtube.com/watch?v=TfrAf1a9Qhs 1:00-1:30 CS 5's three-eyed spokesalien has walked off the job, according to an AFL-CIO (Alien Federation of Labor and Congress of
Interplanetary Organizations) lifeform. "I can't work under these conditions when I arrived this morning, I was immediately and indecorously - burninated by a new coworker," sources reported hearing as the trinocular terrestrial stormed off. No word yet on who this reputed co-worker might be, though picket lines consumed by flames, p. 42 Cyriak: conceptually disruptive recursion Baaa Recursion's 80/20: def dot( L, K ): if len(L) == 0 or len(K) == 0: return 0.0 Basic? if len(L) != len(K): return 0.0 combine else:
return L[0]*K[0] + dot(L[1:],K[1:]) handle the FIRST of L handle the FIRST of K handle the REST of L firsts, as appropriate first handle the REST of K recursion w/the rest rest def dot( L, K ): if len(L) == 0 or len(K) == 0:
return 0.0 if len(L) != len(K): return 0.0 else: return L[0]*K[0] + dot(L[1:],K[1:]) dot dot([3,2,4],[4,7,4]) 3*4 + dot([2,4],[7,4]) 2*7 + dot([4],[4]) 4*4 + dot([],[]) 0.0 16.0 30.0 42.0 L = [3,2,4] and K = [4,7,4] L = [2,4] and K = [7,4]
L = [4] and K = [4] L = [ ] and K = [ ] pythontutor.com There are four different values of L and four different values of M all alive, simultaneously, in the stack Seeing the "stack" ... Some random asides import random from random import * allows use of dir(random) and help(random) all random functions are now available! chooses 1 element from the sequence L choice( L ) ... or 1 character from a string choice('mudd')
choice(['cmc','scripps','pitzer','pomona']) list(range(1,5)) [1,2,3,4] How would you get a random integer from 0 to 99 inclusive? uniform(low,hi) chooses a random float from low to hi floats have 16 places of precision Aargh so close! A random function from random import * def guess( hidden ): Remember, this is [0,1,,99] """ tries to guess our "hidden" # """ compguess = choice( list(range(100)) )
if compguess == hidden: print('I got it!') else: guess( hidden ) # at last! Suspicious? I am! print the guesses ? slow down return the number of guesses ? investigate expected # of guesses?!?? Recursive guess-counting from random import * import time c o de av in hw ailable 2pr2
def guess( hidden ): """ guessing game """ compguess = choice( list(range(100)) ) # print('I choose', compguess) # time.sleep(0.05) if compguess == hidden: # at last! # print('I got it!') return 1 else: return 1 + guess( hidden ) Quiz Name(s): from random import * choice( [1,2,3,2] ) A few random thoughts What are the chances this returns a 2 ?
choice( list(range(1,5))+[4,2,4,2] ) [1,2,3,4] What are the chances of this returning a 4 ? choice( '1,2,3,4' ) What's the most likely return value here? choice( ['1,2,3,4'] ) What's the most likely return value here? choice( '[1,2,3,4]' ) What's the most likely return value here? choice(list(range(5))) Carefu
l! Is this more likely to be even or odd (or same)? [0,1,2,3,4] uniform( -20.5, 0.5 ) choice(0,1,2,3,4) choice([list(range(5))]) choice[list(range(5))] What're the chances of this being > 0? Extra! Which two of these 3 are syntax errors? Also, what does the third one the one syntactically correct actually do? and how likely is each of these?
Syntax corner Data is in black. Probabilities are in blue. Team up and tr y this on the backpage fi rst from random import * choice( [1,2,3,2] ) choice( list(range(1,5))+[4,2,4,2] ) [1,2,3,4] 2/4 or 50% What are the chances this returns a 2 ? What are the chances of this returning a 4 ?
3/8 [1,2,3,4,4,2,4,2] choice( '1,2,3,4' ) What's the most likely return value here? ',' 3/7 choice( ['1,2,3,4'] ) What's the most likely return value here? '1,2,3,4' 1/1 choice( '[1,2,3,4]' )
What's the most likely return value here? ',' 3/9 choice(list(range(5))) [0,1,2,3,4] uniform( -20.5, 0.5 ) Is this more likely to be even or odd (or same)? even What're the chances of this being > 0? 1/42 choice(0,1,2,3,4) syntax error: needs [...] or '...' choice([list(range(5))])
correct: always returns [0,1,2,3,4] choice[list(range(5))] syntax error: needs choice( ... ) 3/5 and how likely are all these? 1/1 chance Data is in black. Probabilities are in blue. Team up and tr y this on the backpage fi rst from random import * choice( [1,2,3,2] )
2/4 or 50% What are the chances this returns a 2 ? choice( list(range(1,5))+[4,2,4,2] ) What are the chances of this returning a 4 ? e s e h t s Pas ! d r a w t
s e w [1,2,3,4] 3/8 [1,2,3,4,4,2,4,2] choice( '1,2,3,4' ) What's the most likely return value here? ',' 3/7 choice( ['1,2,3,4'] ) What's the most likely return value here? '1,2,3,4'
1/1 choice( '[1,2,3,4]' ) What's the most likely return value here? ',' 3/9 choice(list(range(5))) [0,1,2,3,4] uniform( -20.5, 0.5 ) Is this more likely to be even or odd (or same)? even What're the chances of this being > 0? 1/42 choice(0,1,2,3,4)
syntax error: needs [...] or '...' choice([list(range((5))]) correct: always returns [0,1,2,3,4] choice[list(range(5))] syntax error: needs choice( ... ) 3/5 and how likely are all these? 1/1 chance The two Monte Carlos and their denizens
Insights via random trials Monte Carlo casino, Monaco Monte Carlo methods, Math/CS The two Monte Carlos and their denizens Ulam, Stan Stanislaw UlamUlam (Los Alamos badge) Insights via random trials Bond, James Bond
Monte Carlo casino, Monaco Monte Carlo methods, Math/CS Monte Carlo in action How many doubles will you get in N rolls of 2 dice? N is the total number of rolls def countDoubles( N ): """ input: the # of dice rolls to make output: the # of doubles seen """ if N == 0: return 0 # zero rolls, zero doubles else: two dice from d1 = choice( [1,2,3,4,5,6] ) 1-6 inclusive
d2 = choice( list(range(1,7)) ) if d1 != d2: return 0+countDoubles( N-1 ) else: return 1+countDoubles( N-1 ) # don't count it # COUNT IT! where and how is the check for doubles? Another Monty ? inspiring the Monty Hall paradox Let's make a deal Monty '63-'86 inspiring the Monty Hall paradox Monte Carlo Monty Hall
Suppose you always switch to the other door... What are the chances that you will win the prize ? Let's play (randomly) 300 times and see! Monte Carlo Monty Hall 'switch' or 'stay' Your initial choice! number of times to play def MCMH( init, sors, N ): """ plays the "Let's make a deal" game N times returns the number of times you win the *Spam!* """ if N == 0: return 0 # don't play, can't win przDoor = choice([1,2,3]) # where the spam (prize) is if init == przDoor and sors == 'stay': result elif init == przDoor and sors == 'switch': result
elif init != przDoor and sors == 'switch': result else: result = = = = 'Spam!' 'pmfp.' 'Spam!' 'pmfp.' print 'You get the', result if result == 'Spam!': else: return 1 + MCMH( init, sors, N-1 ) return 0 + MCMH( init, sors, N-1 ) 0
A B C D E F G H 1 2 3 4 5 6 7
8 9 0 A B C D E F G H 1 2 3 4
5 6 7 8 9 Let's make a deal: XKCD's take Monty inspiring the Monty Hall paradox but what if you considered the goat the grand prize!? An example closer to home start ...
class (W) 0 ... S 22 23 24 25 hw2pr2 26 27 28 Dorm (E) 50 An overworked 5C student (S) leaves H/S after their "late-night" breakfast or lunch. Each moment, they
randomly stumble toward class (W) or the dorm (E) Once the student arrives at the dorm or classroom, the trip is complete. The program should then print the total number of steps taken. Write a program to model and analyze! this scenario... rwpos(s,nsteps) take nsteps random steps starting at s rwsteps(s,low,hi) take random steps starting at s until you reach either low or hi An example closer to home start ... class (W) 0
... S 22 23 24 25 hw2pr2 26 27 28 Dorm (E) 50 s i h t e t a
e r c ? e n w o i d t l a u o m i c n a w "
o I I H C S A " n a s Write a a program to model and analyze! this scenario... An overworked 5C student (S) leaves H/S after their "late-night" breakfast or lunch. Each moment, they randomly stumble toward class (N) or the Dorm (S) Once the student arrives at the dorm or classroom, the trip is complete. The program should then print the total number of steps taken. rwpos(s,nsteps) take nsteps random
steps starting at s rwsteps(s,low,hi) take random steps starting at s until you reach either low or hi Etch-a-Sketch ? No way this is real but it is ! www.gvetchedintime.com more usual etch-a-sketch work... No way this is real but it is ! Python's Etch-a-Sketch import time from turtle import * the turtle's canvas
# run it and done! draw(); done() sets if the pen animates or not (42,42) window_height() def draw(): # define it! shape('turtle') # pause time.sleep(2) # drawing width(5) left(90) forward(50) pixels! right(90) degrees! backward(50) down() or up() is the pen on the "paper"?
color('darkgreen') tracer(1) or tracer(0) width(5) (0,0) window_width() http://docs.python.org/library/turtle.html Turtle happiness? you can always run done() after turtle drawing This releases control of the turtle window to the computer (the operating system). ur o y n i
t i e don't us er v e w o h s, function To be honest, it seems that not every machine needs this Single-path recursion (1) Let's tri this with recursion: def tri(): # define it! """ a triangle! """ forward(100) left(120)
forward(100) left(120) forward(100) left(120) # run + done tri(); done() I don't know about tri, but there sure is NO return ! def tri( n ): """ draws a triangle """ if n == 0: return else: forward(100) # one side left(120) # turn 360/3 tri( n-1 ) # draw rest (2) How about any regular N-gon? def poly(n, N): """ draws a triangle """
if n == 0: return else: forward(100) # one side left(360.0/N) # turn 360/N poly(n-1, N) # draw rest Be the turtle ! (1) Have rwalk draw a "stock-market" path: (2) What would chai(100) draw? one possible result of rwalk(20) N steps of 10 pixels each. Use recursion. from random import * def rwalk(N):
""" make N 10-pixel steps, NE or SE """ def chai(dist): """ mystery fn! """ if dist < 5: return if N == 0: return elif choice(['left','right']) == 'left': left(45) forward(10) forward(dist) left(90) forward(dist/2.0) right(90) ? else: right(90) forward(dist) left(90) left(90)
forward(dist/2.0) right(90) backward(dist) # this handles 'right' ? Extra! How could you make this a bull (or a bear) market? Extra #2! What if the line chai(dist/2) were placed between the two right(90) lines? And/or between the two left(90) lines? from random import * rwalk(N) is a random "stock market" walk... def rwalk(N): """ make N 10-px steps, NE or SE """ if N == 0: return elif choice(['left','right'])=='left': left(45)
forward(10) right(45) rwalk( N-1 ) What if we didn't turn back to face east each time? else: # 'right' right(45) forward(10) left(45) rwalk( N-1 ) Single-path (or counting) recursion Cyriak: conceptually disruptive recursion handfingers is the branching, not the single-path variety. Single-path recursion What does chai(100) do here?
def chai(dist): """ mystery! """ if dist<5: return forward(dist) left(90) forward(dist/2.0) right(90) right(90) forward(dist) left(90) left(90) forward(dist/2.0) right(90) backward(dist) How could you add more to each T's tips? Why are there two identical commands in a row ~ twice!? Branching recursion Now, what does chai(100) do?
def chai(dist): """ mystery! """ if dist<5: return forward(dist) left(90) forward(dist/2.0) right(90) chai(dist/2) right(90) forward(dist) left(90) chai(dist/2) left(90) forward(dist/2.0) right(90) backward(dist) lab ~ hw2pr1 64
fractal art 80 spiral(100,90,0.8) 100 spiral( initLength, angle, multiplier ) lab ~ hw2pr1 spiral(80,90,0.8) 64 fractal art 80 spiral(100,90,0.8) 100 spiral( initLength, angle, multiplier )
svtree( trunkLength, levels ) svtree( 100, 5 ) levels == 5 levels == 4 levels == 3 levels == 2 levels == 1 levels == 0 (no drawing) svtree( trunkLength, levels ) svtree( 75, 4 ) svtree( 100, 5 ) levels == 5 levels == 4 levels == 3
What steps does the turtle need to take before recursing? levels == 2 levels == 1 levels == 0 (no drawing) svtree( trunkLength, levels ) step #3: draw a smaller svtree! svtree( 100, 5 ) step #2: turn a bit step #1: go forward levels == 5 step #6: get back to the start by turning and
moving! levels == 4 step #4: turn to another heading Be sure the turtle always returns to its starting position! levels == 3 levels == 2 levels == 1 step #5: draw another smaller svtree! levels == 0 (no drawing) svtree( trunkLength, levels ) svtree( 75, 4 )
svtree( 100, 5 ) Be sure the turtle always returns to its starting position! levels == 5 levels == 4 that means it will finish the recursive levels == 3 call right here! levels == 2 so that it can change heading and draw another one levels == 1 levels == 0 (no drawing) The Koch curve
snowflake(100, 0) snowflake(100, 1) snowflake(100, 2) snowflake(100, 3) snowflake(100, 4) snowflake(100, 5) Recursive art? Create your own seven-cornered confetti Happy turtling i n lab! What? Way too happy to be art My recursive compositions burninate even Cyriak's brain!
Using a Euro, Yuan the deadline comes next time I'll try to make the Mark. I'm Pounding it into my brain, but I have to Peso much attention to other deadlines in the classes I Currency have - but if this keeps up, my grade will be demolished to Ruble. hw0 highlights depending which way one's facing, perhaps! Dafna Bimstein For example, when someone coughs, in English there is not really an appropriate response, while after a sneeze, someone would normally say "Bless you". In arabic however, one commonly says "suh-huh" after someone coughs. ... two grueling days of learning where N, E, W, and S are in relation to each other. ... I need to trick myself into thinking that the brackets are commas. programmers approach a problem as a series of functions (often arithmetic operations) in order to convey their ideas to a computer. A normal person might perceive a fractal design as a beautiful drawing, but all a programmer sees in that design is a series of numbers. Using a Euro, Yuan the deadline comes next time I'll try to make the Mark. I'm Pounding it into my brain, but I have to Peso much
attention to other deadlines in the classes I Currency have - but if this keeps up, my grade will be demolished to Ruble. hw0 highlights depending which way one's facing, perhaps! Liz H. For example, when someone coughs, in English there is not really an appropriate response, while after a sneeze, someone would normally say "Bless you". In Arabic however, one commonly says "suh-huh" after someone coughs. programmers approach a problem as a series of functions (often arithmetic operations) to convey their ideas to a computer. A normal person might perceive a fractal design as a beautiful drawing, but all a programmer sees in that design is a series of numbers. Using a Euro, Yuan the deadline comes next time I'll try to make the Mark. I'm Pounding it into my brain, but I have to Peso much attention to other deadlines in the classes I Currency have - but if this keeps up, my grade will be demolished to Ruble. hw0 highlights depending which way one's facing, perhaps!
Who a! For example, when someone coughs, in English there is not really an appropriate response, while after a sneeze, someone would normally say "Bless you". In arabic however, one commonly says "suh-huh" after someone coughs. ... two grueling days of learning where N, E, W, and S are in relation to each other. ... I need to trick myself into thinking that the brackets are commas. programmers approach a problem as a series of functions (often arithmetic operations) in order to convey their ideas to a computer. A normal person might perceiveBrendan a fractal design McL. as a beautiful drawing, but all a programmer sees in that design is a series of numbers. Using a Euro, Yuan the deadline comes next time I'll try to make the Mark. I'm Pounding it into my brain, but I have to Peso much attention to other deadlines in the classes I Currency have - but if this keeps up, my grade will be demolished to Ruble. hw0 highlights depending which way one's facing, perhaps!
CMS RPS! For example, when someone coughs, in English there is not really an appropriate response, while after a sneeze, someone would normally say "Bless you". In Arabic however, one commonly says "suh-huh" after someone coughs. programmers approach a problem as a series of functions (often arithmetic operations) in order to convey their ideas to a computer. A normal person might perceive a fractal design as a beautiful drawing, but all a programmer sees in that design is a series of numbers. Eliana K & Emily C Single-path recursiondef (1) What does chai(100) do? chai(size): """ mystery! """ if size<9: return forward(size) left(90) forward(size/2.0)
right(90) right(90) forward(size) left(90) left(90) forward(size/2.0) right(90) backward(size) How could you add more to each T-tip? Why are there two identical commands in a row ~ twice!? Etch-a-Sketch ? No way this is real but it is ! www.gvetchedintime.com Gel electrophoresis one of many applications for random walks
uses a basic random-walk model with unequal step probabilities Used to separate proteins and nucleic acids (DNA) from a biological sample. Molecules with different properties travel different distances. CS 5 green: Gel electrophoresis fire! Python's turtle graphics Sometimes you need to run Python from the command-line www.cs.hmc.edu/twiki/bin/view/CS5/RunningPythonFromTheCommandLine Mac instructions... Windows instructions... 0 A
B C D E F G H 1 2 3 4 5 6 7
8 9 0 1 42 3 4 5 6 A B C D
E F G H g n i d l i bu s k c o bl 7 8
9 ENIAC 1 Programming before stored-program computers Claremont residents report droplets of water falling down-ward from the sky: unexplained meteorological phenomenon details, causes p. panic 42 CS 5 Today hw2 due Mon. Fri. aft. office hours! Fractals and Turtles!
LAC tutoring hours all Other weekend! trogdor appearances how random CS 5 alien on strike! Consummate sketch of accused, bullying CS 5 coworker The three-eyed CS 5 spokesalien has walked off the job, according to an AFL-CIO (Alien Federation of Labor and Congress of Interplanetary Organizations) lifeform. "I can't work under these conditions -- I arrived at work this morning
and was immediately burninated by a new coworker," sources reported hearing as the trinocular terrestrial stormed off. No word yet on who this reputed coworker might be, though picket lines consumed by flames, p. 4 The Koch Curve 0 A B C D E F G H 1 2
3 4 5 6 7 8 42 Python's Etch-a-Sketch Be SURE to start IDLE with "no subprocess" Mac instructions... (Step 1) menus: Go Utilities Terminal Windows instructions... (Step 1) Go to the Start menu's search field
Start this! (Step 2) Type or paste the full path to IDLE If you used the standard install, it will be (Step 2) Enter idle n & C:\Python27\Lib\idlelib\idle.pyw -n Hit return; you'll see a console window and IDLE open. Then, you can type from turtle import * Reading this week... If all computation really consists of conditionals (if), data storage 'hi', and recursion (or loops) perhaps natural
interactions could be created, too? Joseph Weizenbaum's Eliza What's missing? Easy as p (1,1) pi via darts (-1,-1) print: Making programs talk to you! import time def countdown( num ): """ remarkably accurate sim. of 2006's final moments """ if num == 0:
return 'Hooray!' else: print 'Countdown is', num time.sleep(1) return countdown(num-1) you can slow things down, as well! Essential for debugging Randomness vs. Determinism Are there random numbers? Can a computer generate them? RNG Output A black box model of a
random number generator. Randomness vs. Determinism Are there random numbers? Yes Can a computer generate them? Not without help! The RNG revealed. Output http://en.wikipedia.org/wiki/Mersenne_twister Periodic! p = 219937-1 Some random history
True randomness is valuable! but not that valuable! http://www.rand.org/pubs/monograph_reports/MR1418/index.html True Randomness ! http://www.leapzine.com/hr/ random, but not! an enthusiastic endorser LavaRnds lava lamps using a chaotic physical system to seed random number generators (Patent 5,732,138: "Method for seeding a pseudorandom number generator with a cryptographic hash of a digitization of a chaotic system.") www.wired.com/wired/archive/11.08/random.html
This has since been improved Some random programs import random def guess( hidden ): """ guesses the user's #, "hidden" """ compguess = random.choice( range(10) ) if compguess == hidden: return 'I got it!' else: return guess( hidden ) print guesses ? num guesses ? "Quiz" (1) What should we do to improve this guesser? (2) How? import random def guess( hidden ):
""" guesses the user's #, "hidden" """ compguess = random.choice( range(10) ) if compguess == hidden: return 'I got it!' else: return guess( hidden ) print guesses ? num guesses ? Monte Carlo p An engineering challenge: to estimate p using everyday items... Quiz Design a strategy for estimating pi using random numbers ("dart throws") and this diagram ("dartboard"): Name(s): 1) Here is a dart-throwing function: (1,1)
What does this return? def throw(): return [ random.uniform(-1,1), random.uniform(-1,1) ] 2) Here is a dart-testing function: What does this return? def test(x,y): return (x**2 + y**2) < 1.0 3) What strategy could use the functions in (1) and (2) to estimate pi? (-1,-1) 4) Write a function to implement your strategy:
Notes from prior hwks Warnings! def rps(p1,p2): """ rock-paper-scissors judger """ if 'p1' == 'p2': return 0 def rps(p1,p2): if p1 == p2: return '0' def letterscore(let): if let in 'zq': return 10 (lots more) Notes from prior hwks Warnings! The string 'p1' is not the same as the variable p1 !
The string '0' is not the same as the number 0 ! def rps(p1,p2): """ rock-paper-scissors judger """ if 'p1' == 'p2': return 0 def rps(p1,p2): """ rock-paper-scissors judger """ if p1 == p2: return '0' no docstring! Capital letters count! (It should be letterScore.) def letterscore(let): if let in 'zq': return 10 (lots more)
Poetic Programming 1 My letters are eight (though I number much more) 2 And the first can start words such as 'file' and 'four.' 3 My four which begin form a word for stronghold 4 Like the one we call Knox where we keep all our gold. 5 My fifth is that letter our alphabet's got 6 Which can't choose if it will be a vowel or not. 7 My last three will come 'twixt a one and a three 8 And they are not a crowd, though they are company. 9 If you can't find my answer, please don't you despair. 10 Just come to CS class; it's everywhere there. #Poem: I find that eating pie makes me negative #1 I'll make the first clue easy: This list is composed of 16 digits. #2 Within these, the 4th through the 10th digits are a palindrome including four 8s and which sums to 37. #3 The 11th digit is the number of teams entering a semi-final. #4 The 13th digit is one of two single-digit Kaprekar numbers in base 10. #5 The 12th, 3rd, 16th, and 14th digits (in that order)
comprise the legal slang (refering to the California Welfare & Institutions Code) for when a person is considered a danger to him/herself or others as a redult of a mental disorder. #6 The 2nd and 1st digits (in that order) comprise the amount of time in hours such a person may be held in custody. #7 Lastly, the 15th digit is an exciting number of letters #1 Listen my children and you shall hear #2 The wonderful tales of Paul Revere #3 Of all the 8 letters he shall send #4 Number four is the middle of middle and the end of en #5 Letters five and eight are exactly the same #6 They are the end of Superman's real name #7 Letters one through four are opposite the sea #8 Number 6 completely refers to me! #9 Now fill in the letter 7 blank #10 Now that you have the majority on hand #11 Flip the sea to the back, #12 and get the costco brand!
1 2 3 4 First a riff, then a twang, then a howl, then a bang: Here?s a song that the Stones rocked real hard when they sang. With Sir Mick on the mic and ol Keef on the strings, There?s still some irony in the joy this song brings? 5 6 7 8 The first fourth of our song rhymes with cat and with hat. It?s the past tense of ?sit.? You can sit on a mat. (Though I?m sad I must say this clue gives it away To the fans of this band. I hope they?ll understand.) 9 The next sixth is a verb that is hard to avoid 10 (In the last line alone, you can find two employed!)
11 And in Spanish ? reversed ? with an accent, it?s ?yes!? 12 Do you know what this verb is? Come on, take a guess! 13 14 15 16 The next twelfth of the word used to look just like ?E.? But it lost his third limb; now he?s an amputee. Though they still live nearby, things were never the same He gets sad and self conscious and thinks he is lame. 17 18 19 20 The last half of this song is six letters, I?m told, And they certainly speak of demeanor quite bold. And intertially speaking, this thing is opposed By its equal and opposite twin, I suppose. 21 Of what song do I speak? I can hypothesize
22 That by now you?ve deciphered the code in my rhymes. Friday Homework Hints hw2pr3 : rwPos() is similar to the countdown example (from Wed.) rwSteps() is similar to the guess example (from Wed.) hw2pr4 : countStrings(s1,s2) is similar to the sajak example (last Fri.) except you will need to use slices instead of single characters s2[0:?] s2[0] removeAll(e,L) is similar to sajak (last Fri.) and range (from Wed.) it returns a list like L but with top-level elements e removed Two more functions, as well: spiral() and svTree() Recursion -- not just numbers Self-similarity elsewhere... Natural phenomena
Relationships What is an ancestor ? Names -- acronyms GNU == GNUs Not Unix how much here is leaf vs. stem? Recursion -- not just numbers Self-similarity elsewhere... Natural phenomena Relationships What is an ancestor ?
An ancestor is a parent OR an ancestor of a parent Names -- acronyms GNU == GNUs Not Unix all stem! Turtle Graphics You will need to have two files in your working folder (directory): csturtle.py csplot.py You will want to have this line in your hw2pr4.py file: import csturtle ; reload(csturtle) ; from csturtle import * Then you will be able to write functions using the csturtle commands:
www.cs.hmc.edu/twiki/bin/view/CS5/CsturtleDirections for csturtle help A place to start def tri(): """ draws a polygon """ forward(100) left(120) forward(100) left(120) forward(100) left(120) Window controls all that's left from the villagers' thatched cars http://www.cs.hmc.edu/twiki/bin/view/CS5/Lab2Part1
Recursive Graphics there is no tri def tri(): """ draws a polygon """ forward(100) left(120) forward(100) left(120) forward(100) left(120) I don't know about tri, but there sure's NO return ! (1) Could we tri this with recursion? (2) Could we create any regular n-gon? Name(s):
(1) What does chai draw? Turtle Graphics (2) "Quiz" Finish rwalk to draw a "stock-market-type" random path of nsteps steps. Use recursion! import random def rw(nsteps): """ moving for nsteps steps, randomly 45 deg. left (1) or right (-1) """ if nsteps == 0: return if random.choice([1,-1]) == 1: # left def chai(size): """ mystery! """ forward(size)
left(90) forward(size/2.0) right(90) right(90) forward(size) left(90) left(90) forward(size/2.0) right(90) backward(size) else: # it was -1, meaning right one possible result of rw(20) Ex Cr: How could you make it a bull (or a bear) market? (1) What does chai draw?
def chai(size): """ mystery! """ forward(size) left(90) forward(size/2.0) right(90) right(90) forward(size) left(90) left(90) forward(size/2.0) right(90) backward(size) Why are there two identical commands in a row? How could you add more to each end? (2) Finish rwalk to draw a "stock-market-type" random path of nsteps steps.
import random def rw(nsteps): """ moving for nsteps steps, randomly 45 deg. left (1) or right (-1) """ if nsteps == 0: return if random.choice([1,-1]) == 1: # 1 means left left(45) forward(20) right(45) else: # it was -1, meaning right right(45) forward(20) left(45) one possible result of rw(20) What if we didn't go back to the starting pose? Ex Cr: How could you make it a bull (or a bear) market?
hw2pr4 spiral 81 72.9 90 close-up of innermost part of the spiral spiral( 100, 90, 0.9 ) 100 spiral( initLength, angle, multiplier ) hw2pr4 svTree svTree( 100, 4 ) I wonder what happened to the leaves on that tree ?
svTree( trunkLength, levels ) and more! (if you Taking away def removeBs( s ): returns a string that is the same as s, except without any 'b's Examples: removeBs('hubbabubba') == 'huaua' Taking away def removeBs( s ) Base Case: returns a string that is the same as
s, except without any 'b's when there are no letters, the answer is _____________ if the first letter IS an B, the answer is ______________________ Recursive Step: if the first letter IS an B, the answer is __________________ Sorting def sort(L) Ideas? returns a list which has the same elements as L, but in sorted order! Sorting def sort(L)
returns a list which has the same elements as L, but in sorted order! Ideas? Let b be the biggest item in L Remove b from L to get a newL Add b to the end of what ?!? Sorting in only 4 lines of code! Name(s): (1) What does chai draw? Turtle Graphics (2) "Quiz" Finish rwalk to draw a "stock-market-type" random path of nsteps steps. Use recursion! import random
def rw(nsteps): """ moving for nsteps steps, randomly 45 deg. left (1) or right (-1) """ if nsteps == 0: return if random.choice([1,-1]) == 1: # left def chai(size): """ mystery! """ forward(size) left(90) forward(size/2.0) right(90) right(90) forward(size) left(90) left(90) forward(size/2.0) right(90) backward(size) else:
# it was -1, meaning right one possible result of rw(20) Ex Cr: How could you make it a bull (or a bear) market? Real visual recursion How many times has the light bounced before reaching the camera from various items here?? Quiz Write each of these functions using recursion Returns a string the same as s, but with no x characters in it. ( x, not 'x' ! ) remove('t','wait a minute') == 'wai a minue' def remove( x, s ):
Removes the characters in the string s2 from the string s. removeAll( 'gqz', 'quizzing' ) == 'uiin' def removeAll( s2, s ): Removes the characters in the string s2 at most once from the string s. (Hw problem!) removeOne( 'agqz', 'quizzing' ) == 'uizin' def removeOne( s2, s ): Drawing Recursively Any self-similarity here? 190 200 Drawing Recursively Designing any recursive program boils down to the same two pieces
Base Case: Recursive Step: Think about the SIMPLEST POSSIBLE case! Do ONLY ONE STEP, and let recursion do the rest Drawing Recursively Designing any recursive program boils down to the same two pieces Base Case Recursive Step def spiral(L):
if L < 1: return else: forward(L) left(90) spiral(L-10) What if we had forgotten the base case? Drawing Recursively Try writing these functions: def spiralTri( L ): Draws a triangular (equilateral) spiral. Try it! spiralTri(200) draws def spiralOct( L ): Draws an octagonal spiral. Try it! spiralOct(100) draws def spiralLim( L ): Draws a square spiral with only N segments! Try it! spiralLim(200,7) draws actually, a bit
larger than this More on sorting def isSorted(s) returns true if s is in order, false otherwise isSorted('BART') returns False isSorted('BERT') returns True isSorted('BEGIN') returns True isSorted([3,1,4]) returns
False isSorted([1,3,4]) returns True isSorted('LOOPY') returns ?? ties? Six-letter word? print: Making programs talk to you! Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs. - Maurice Wilkes
Programming: the art of debugging an empty file. - The Jargon File http://www.tuxedo.org/~esr/jargon/ EDSAC Cambridge U., 1949 EDSACs input: punched tape The most famous bug Grace Hopper from the UNIVAC 1 In the days they used oxen for heavy pulling, when one ox couldn't budge a log, they didn't try to grow a larger ox. We shouldn't be trying for bigger and better computers, but for better systems of computers. The Python shell
IDLE uses Python's graphics - but built-in shells do not "command window" "terminal window" c:\python25\python -i hw2pr1.py python -i hw2pr1.py Turtle Graphics You will need to have two files in your working folder (directory): csturtle.py csplot.py You will want to have this line in your hw2pr4.py file: from csturtle import * Then you will be able to write functions using the csturtle commands:
www.cs.hmc.edu/twiki/bin/view/CS5/CsturtleDirections for csturtle help A place to start def tri(): """ draws a polygon """ forward(100) left(120) forward(100) left(120) forward(100) left(120) Window controls all that's left from the villagers' thatched cars http://www.cs.hmc.edu/twiki/bin/view/CS5/Lab2Part1 CS 5 Today
Fractals and Turtles CS 5 alien on strike! More Eyes! hw2 due Mon. Fri. aft. office hrs! Lots of tutoring Photograph of CS 5 co-worker accused of burnination. random how! The three-eyed CS 5 spokesalien has walked off the job, according to an AFL-CIO (Alien Federation of Labor and Congress of Interplanetary Organizations) lifeform. "I can't work under these conditions -- I arrived at work this morning and was immediately burninated by a new co-worker," sources reported hearing as the trinocular terrestrial stormed off. No word yet on who this reputed
co-worker might be, though picket lines consumed by flames, p. 4 The Koch Curve Python's turtle graphics Running a turtle-friendly version of IDLE Mac instructions... (Step 1) menus: Go Utilities Terminal Windows instructions... (Step 1) Go to the Start menu's search field Start this! (Step 2) Type or paste the full path to IDLE If you used the standard install, it will be (Step 2) Enter idle n & C:\Python27\Lib\idlelib\idle.pyw -n Hit return; you'll see a console window and IDLE open.