Slide 1MenuProblem SetsPS2: Question 3PS2: Question 8, 9Can we do better?Hmmm....find-bestestfind-best-handPS3: Lindenmayer System FractalsL-SystemsL-System RewritingSlide 13Slide 14Slide 15Slide 16Pegboard PuzzleSolving the Pegboard PuzzleRemoving a PegAdding a PegRemove HoleFilterFilter RemoveSolving the Peg Board GameChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 10:Puzzling Pegboards2Lecture 10: Pegboard PuzzleMenu•Problem Sets 2 and 3•Pegboard Puzzler3Lecture 10: Pegboard PuzzleProblem Sets•Not just meant to review stuff you should already know–Get you to explore new ideas–Motivate what is coming up in the class•The main point of the PSs is le arning, not evalua tion–Don’t give up if you can’t find the answer in the book (you won’t solve many problems this way)–Do discuss with other students4Lecture 10: Pegboard PuzzlePS2: Question 3Why is (define (higher-card? card1 card2) (> (card-rank card1) (card-rank card2)better than (define (higher-card? card1 card2) (> (car card1) (car card2))?5Lecture 10: Pegboard PuzzlePS2: Question 8, 9•Predict how long it will take•Identify ways to make it fasterMost of next week and much of many later classes will be focused on how computer scientists predict how long programs will take, and on how to make them faster.6Lecture 10: Pegboard PuzzleCan we do better?(define (find-best-hand hole-cards community-cards) (car (sort (possible-hands hole-cards community-cards)) higher-hand?))7Lecture 10: Pegboard PuzzleHmmm....(define (find-closest goal lst closeness) (if (= 1 (length lst)) (car lst) (pick-closest closeness goal (car lst) (find-closest goal (cdr lst) closeness))))(define (pick-closest closeness goal num1 num2) (if (< (closeness goal num1) (closeness goal num2)) num1 num2))8Lecture 10: Pegboard Puzzlefind-bestest(define (find-bestiest lst bestiness) (if (= 1 (length lst)) (car lst) (pick-bestier bestiness (car lst) (find-bestiest goal (cdr lst) bestiness))))(define (pick-bestier bestiness num1 num2) (if (bestiness num1 num2) num1 num2))9Lecture 10: Pegboard Puzzlefind-best-hand(define (find-bestiest lst bestiness) (if (= 1 (length lst)) (car lst) (pick-bestier bestiness (car lst) (find-bestiest (cdr lst) bestiness))))(define (pick-bestier bestiness num1 num2) (if (bestiness num1 num2) num1 num2))(define (find-best-hand lst) (find-bestest lst higher-hand?))Next week: how much better is this?10Lecture 10: Pegboard PuzzlePS3:Lindenmayer System Fractals11Lecture 10: Pegboard PuzzleL-SystemsCommandSequence ::= ( CommandList )CommandList ::= Command CommandListCommandList ::=Command ::= FCommand ::= RAngleCommand ::= OCommandSequence12Lecture 10: Pegboard PuzzleL-System RewritingStart: (F)Rewrite Rule: F (F O(R30 F) F O(R-60 F) F)Work like BNF replacement rules, except replace all instances at once!Why is this a better model for biological systems?CommandSequence ::= ( CommandList )CommandList ::= Command CommandListCommandList ::=Command ::= FCommand ::= RAngleCommand ::= OCommandSequenceLevel 0(F) Level 1F (F O(R30 F) F O(R-60 F) F)Start: (F)(F O(R30 F) F O(R-60 F) F)14Lecture 10: Pegboard PuzzleLevel 2Level 315Lecture 10: Pegboard PuzzleThe Great Lambda Treeof Ultimate Knowledgeand Infinite Power(Level 5 with color)16Lecture 10: Pegboard PuzzleRose Bush by Jacintha Henry and Rachel Kay Tie Dye by Bill Ingram17Lecture 10: Pegboard PuzzlePegboard Puzzle 1,1 2,1 2,2 3,1 3,2 3,3 4,1 4,2 4,3 4,4 5,1 5,2 5,3 5,4 5,518Lecture 10: Pegboard PuzzleSolving the Pegboard Puzzle•How to represent the state of the board?–Which holes have pegs in them•How can we simulate a jump?–board state, jump positions board state•How can we generate a list of all possible jumps on a given board?•How can we find a winning sequence of jumps?19Lecture 10: Pegboard PuzzleRemoving a Peg;;; remove-peg evaluates to the board you get by removing a ;;; peg at posn from the passed board (removing a peg adds a ;;; hole)(define (remove-peg board posn) (make-board (board-rows board) (cons posn (board-holes board))))20Lecture 10: Pegboard PuzzleAdding a Peg;;; add-peg evaluates to the board you get by ;;; adding a peg at posn to board (adding a ;;; peg removes a hole)(define (add-peg board posn) (make-board (board-rows board) (remove-hole (board-holes board) posn)))21Lecture 10: Pegboard PuzzleRemove Hole(define (remove-hole lst posn) (if (same-position (car lst) posn) (cdr lst) (cons (car lst) (remove-hole (cdr lst) posn))))What if we had a procedure (filter proc lst) that removes fromlst all elements for which proc (applied to that element) is false?Could we define remove-hole using map?No. (length (map f lst)) is always the same as (length lst), but remove-hole needs to remove elements from the list.22Lecture 10: Pegboard PuzzleFilter(define (filter proc lst) (if (null? lst) null (if (proc (car lst)) ; proc is true, keep it (cons (car lst) (filter proc (cdr lst))) (filter proc (cdr lst))))) ; proc is false, drop it> (filter (lambda (x) (> x 0)) (list 1 4 -3 2))(1 4 2)23Lecture 10: Pegboard PuzzleFilter Remove(define (filter proc lst) (if (null? lst) null (if (proc (car lst)) ; proc is true, keep it (cons (car lst) (filter proc (cdr lst))) (filter proc (cdr lst))))) ; proc is false, drop it(define (remove-hole lst posn) (filter (lambda (pos) (not (same-position pos posn))) lst))24Lecture 10: Pegboard PuzzleSolving the Peg Board Game•Try all possible moves on the board•Try all possible moves from the positions you get after each possible first move•Try all possible moves from the positions you get after trying each possible move from the positions you get after each possible first move•…25Lecture 10: Pegboard PuzzleCharge•Next class: we’ll finish a pegboard puzzle solver and find out if how hard it is to be “genius”•I have office hours now•Make progress on
View Full Document
Unlocking...