Unformatted text preview:

1David Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 11: 1% Pure LuckMake-up lab hours: 4:30-6 today2Lecture 11: 1% LuckPegboard Puzzle1,12,1 2,23,1 3,2 3,34,1 4,2 4,3 4,45,1 5,2 5,3 5,4 5,53Lecture 11: 1% LuckSolving 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?4Lecture 11: 1% LuckData Abstractions(define (make-board rows holes)(cons rows holes))(define (board-holes board) (cdr board))(define (board-rows board) (car board))(define (make-position row col) (cons row col))(define (get-row posn) (car posn))(define (get-col posn) (cdr posn))(define (same-position pos1 pos2)(and (= (get-row pos1) (get-row pos2))(= (get-col pos1) (get-col pos2))))5Lecture 11: 1% LuckRemoving 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))))6Lecture 11: 1% LuckAdding a Peg;;; add-peg evaluates to the board you get by ;;; adding a peg at posn to board (adding a ;;; peg removesa hole)(define (add-peg board posn)(make-board (board-rows board) (remove-hole (board-holes board) posn)))27Lecture 11: 1% LuckRemove 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.8Lecture 11: 1% LuckFilter(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)9Lecture 11: 1% LuckFilter 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))10Lecture 11: 1% LuckJumps;;; move creates a list of three positions: a start (the posn that the ;;; jumping peg starts from), a jump (the posn that is being jumped;;; over), and end (the posn that the peg will end up in)(define (make-move start jump end) (list start jump end))(define (get-start move) (first move))(define (get-jump move) (second move))(define (get-end move) (third move));;; execute-move evaluates to the board after making move ;;; move on board.(define (execute-move board move)(add-peg (remove-peg (remove-peg board (get-start move))(get-jump move))(get-end move)))11Lecture 11: 1% LuckSolving 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• …12Lecture 11: 1% LuckFinding a Winning StrategyStartHow is winning 2-person games (e.g., chess, poker) different?...Winning position!313Lecture 11: 1% LuckPegboard Puzzle1,12,1 2,23,1 3,2 3,34,1 4,2 4,3 4,45,1 5,2 5,3 5,4 5,5How do we find all possible jumps that land in a given target hole?14Lecture 11: 1% LuckPegboard Puzzle1,12,1 2,23,1 3,2 3,34,1 4,2 4,3 4,45,1 5,2 5,3 5,4 5,5How do we find all possible jumps that land in a given target hole?15Lecture 11: 1% LuckPegboard Puzzle1,12,1 2,23,1 3,2 3,34,1 4,2 4,3 4,45,1 5,2 5,3 5,4 5,5How do we find all possible jumps that land in a given target hole?16Lecture 11: 1% LuckAll Moves into Target;;; generate-moves evaluates to all possible moves that move a peg into;;; the position target, even if they are not contained on the board.(define (generate-moves target)(map (lambda (hops)(let ((hop1 (car hops)) (hop2 (cdr hops)))(make-move (make-position (+ (get-row target) (car hop1)) (+ (get-col target) (cdr hop1)))(make-position (+ (get-row target) (car hop2)) (+ (get-col target) (cdr hop2)))target)))(list (cons (cons 2 0) (cons 1 0)) ;; right of target, hopping left(cons (cons -2 0) (cons -1 0)) ;; left of target, hopping right(cons (cons 0 2) (cons 0 1)) ;; below, hopping up(cons (cons 0 -2) (cons 0 -1)) ;; above, hopping down(cons (cons 2 2) (cons 1 1)) ;; above right, hopping down-left(cons (cons -2 2) (cons -1 1)) ;; above left, hopping down-right(cons (cons 2 -2) (cons 1 -1)) ;; below right, hopping up-left(cons (cons -2 -2) (cons -1 -1)))))) ;; below left, hopping up-right17Lecture 11: 1% LuckAll Possible Moves(define (all-possible-moves board)(append-all (map generate-moves (board-holes holes))))(define (append-all lst)(if (null? lst) null(append (car lst) (append-all (cdr lst)))))But…only legal if: start and end are positions on the board containing pegs!Note: could use (apply append ...) instead of append-all.18Lecture 11: 1% LuckLegal Move(define (legal-move? move);; A move is valid if:;; o the start and end positions are on the board;; o there is a peg at the start position;; o there is a peg at the jump position;; o there is not a peg at the end position(and (on-board? board (get-start move)) (on-board? board (get-end move))(peg? board (get-start move))(peg? board (get-jump move))(not (peg? board (get-end move)))))419Lecture 11: 1% LuckAll Legal Moves(define (legal-moves board)(filter legal-move? (all-possible-moves board)))(define (legal-move? move);; A move is valid if:;; o the start and end positions are on the board;; o there is a peg at the start position;; o there is a peg at the jump position;; o there is not a peg at the end position(and (on-board? board (get-start move)) (on-board? board (get-end move))(peg? board (get-start move))(peg? board (get-jump move))(not (peg? board (get-end move)))))(define (all-possible-moves board)(append-all(map generate-moves (board-holes holes))))20Lecture 11: 1% LuckBecoming a “Genius”!Start...Winning position!Try all


View Full Document

UVA CS 150 - Pegboard Puzzle

Documents in this Course
Objects

Objects

6 pages

Load more
Download Pegboard Puzzle
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pegboard Puzzle and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pegboard Puzzle 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?