;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-advanced-reader.ss" "lang")((modname |32.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))))) ;A solitaire board (board) is a (vectorof (vectorof booleans)), where true represents a filled square, false an empty square. In particular, for any given board, the n-th element is a vector containing n booleans. We call a triangular board with n-pegs to a side a size-n triangle. For example, the representation of a size-4 equilaterial triangular board: ;(vector (vector false) ; (vector true true) ; (vector true true true) ; (vector true true true true)) ;enabled? : posn board -> boolean ;Determines whether or not the peg specified by aposn is enabled in aboard (enabled means that the peg is capable of jumping). The top position of the board has the index (make-posn 1 1). The vertical axis is denoted by y, the horizontal by x. ;next-peg-x represents the x-index where the peg will jump to if it jumps to the right ;next-peg-y represents the y-index where the peg will jump to if it jumps down ;prev-peg-x represents the x-index ... if the peg jumps to the left ;prev-peg-x represents the y-index ... if the peg jumps up ;need-length-x represents the necessary horizontal length of the board to jump to the right ;need-length-y represents the necessary vertical length of the board to jump down ;next-peg-x-removes represents the x-index of the peg that will be removed if the peg is jumped, etc. (define (enabled? aposn aboard) (local ((define peg-x (sub1 (posn-x aposn))) (define peg-y (sub1 (posn-y aposn))) (define next-peg-x-removes (+ peg-x 1)) (define next-peg-y-removes (+ peg-y 1)) (define prev-peg-x-removes (- peg-x 1)) (define prev-peg-y-removes (- peg-y 1)) (define next-peg-x (+ peg-x 2)) (define next-peg-y (+ peg-y 2)) (define prev-peg-x (- peg-x 2)) (define prev-peg-y (- peg-y 2))) (cond ;;first, is there even a peg? ;;if so, test jump down, jump right, jump up, jump left, jump diagonal (up), jump diagonal (down), in that order [(vector-ref (vector-ref aboard peg-y) peg-x) (or (jump? peg-x next-peg-y peg-x next-peg-y-removes aboard) (jump? next-peg-x peg-y next-peg-x-removes peg-y aboard) (jump? peg-x prev-peg-y peg-x prev-peg-y-removes aboard) (jump? prev-peg-x peg-y prev-peg-x-removes peg-y aboard) (jump? prev-peg-x prev-peg-y prev-peg-x-removes prev-peg-y-removes aboard) (jump? next-peg-x next-peg-y next-peg-x-removes next-peg-y-removes aboard))] [else false]))) ;jump? : N N N N board-> boolean ;Given new-peg-x, new-peg-y, remove-peg-x, remove-peg-y, and aboard, determine if it is possible to make a jump. All coordinates are in terms of vector indices. E.g, 0,0 represents the first element in the first vector. (define (jump? new-peg-x new-peg-y remove-peg-x remove-peg-y aboard) (local ((define need-length-x (add1 new-peg-x)) (define need-length-y (add1 new-peg-y))) (and (not (negative? new-peg-x)) (not (negative? new-peg-y)) (>= (vector-length aboard) need-length-y) (>= (vector-length (vector-ref aboard new-peg-y)) need-length-x) (not (vector-ref (vector-ref aboard new-peg-y) new-peg-x)) (vector-ref (vector-ref aboard remove-peg-y) remove-peg-x)))) ;jump : board posn -> (listof boards) ;Given aboard and aposn, (define trueboard (list (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true false true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true false) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector false true true true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true false) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true true true false true true)) (vector (vector true) (vector true true) (vector false true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true false false) (vector true false true true true true) (vector false false true false false false true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true true false) (vector true true true false true true) (vector false false true false false false true)))) (define falseboard (list (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true true false true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true false true true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true false true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true false true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true true true) (vector true false true true true true) (vector false false true true true true true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true false false) (vector true false false true true true) (vector false false true true true true true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true false false) (vector true false false false true true) (vector false false true false false false true)) (vector (vector true) (vector true true) (vector false true true) (vector true false false true) (vector true false true false false) (vector true true false false true true) (vector false false true false false false true)))) (define trueboard2 (list (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true false true false true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true false) (vector true true true true true true) (vector true true true true true true true)))) (define trueboard3 (list (vector (vector true) (vector true true) (vector false true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true false true false true true)) (vector (vector true) (vector true true) (vector true true false) (vector true true true true) (vector true true true true false) (vector true true true true true true) (vector true true true true true true true)))) (define trueboard4 (list (vector (vector true) (vector true true) (vector false true true) (vector true true true true) (vector true true true true true) (vector true true true true true true) (vector true true false true false true true)) (vector (vector true) (vector true true) (vector true true false) (vector true true true true) (vector false true true true false) (vector true true true true true true) (vector true true true true true true true)))) (define falseboard2 (list (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true true false true true true false)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true false true true true) (vector true true true true true true) (vector true true true true true false true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true true true true) (vector true true true true false true) (vector true false true true true true true)))) (define falseboard3 (list (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true true true true true true true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector true true false true true) (vector true true true true true true) (vector true false false true true true false)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector false false true true true) (vector false true true true true true) (vector true true true true true false true)) (vector (vector true) (vector true true) (vector true true true) (vector true true true true) (vector false true false true true) (vector false true false true false true) (vector true false false true true true true)))) (andmap (lambda (b) (enabled? (make-posn 3 5) b)) trueboard) (andmap (lambda (b) (not (enabled? (make-posn 3 5) b))) falseboard) (andmap (lambda (b) (enabled? (make-posn 7 7) b)) trueboard2) (andmap (lambda (b) (enabled? (make-posn 1 1) b)) trueboard3) (andmap (lambda (b) (enabled? (make-posn 1 7) b)) trueboard4) (andmap (lambda (b) (not (enabled? (make-posn 7 7) b))) falseboard2) (andmap (lambda (b) (not (enabled? (make-posn 1 7) b))) falseboard3)