1 2(module board racket 3 4 ;; color = (symbols 'blue 'green 'red 'yellow) 5 ;; color : color 6 ;; id : (union 0 1 2 3) 7 (define-struct pawn (color id index) #:inspector (make-inspector)) 8 9 ;; v : (vectorof loc) length is always 16 10 (define-struct board (v) #:inspector (make-inspector)) 11 12 ;; loc = (union 'start 'home number[main-loc] home-row-loc) 13 (define-struct home-row-loc (num color) #:inspector (make-inspector)) 14 15 (define color (symbols 'red 'green 'blue 'yellow)) 16 17 (provide/contract 18 (get-enter-pos (color . -> . number?)) 19 (get-exit-pos (color . -> . number?)) 20 (pawn-id (pawn? . -> . (integer-in 0 4))) 21 (pawn-color (pawn? . -> . color))) 22 23 (provide (rename-out [build-pawn make-pawn]) 24 pawn? 25 new-board 26 for-each-pawn/loc 27 28 (rename-out [make-old-style-board make-board]) 29 30 board-start 31 32 board-main-i 33 board-main-size 34 35 board-home-row-i 36 board-home-row-size 37 38 board-home 39 40 move-piece 41 move-piece2 42 43 safety? 44 45 find-blockades/color 46 make-blockade 47 blockade-loc 48 blockade-p1 49 blockade-p2 50 find-blockade/between 51 52 make-home-row-loc 53 home-row-loc-num 54 home-row-loc-color 55 home-row-loc?) 56 57 ;; inline with a macro? 58 (define (for-each-pawn/loc/proc board f) 59 (let ([v (board-v board)]) 60 (let loop ([i 16]) 61 (unless (zero? i) 62 (f (vector-ref all-pawns (- i 1)) (vector-ref v (- i 1))) 63 (loop (- i 1)))))) 64 65 (define-syntax (for-each-pawn/loc stx) 66 (syntax-case stx () 67 [(_ board (lambda (pawn loc) lam-body)) 68 (let loop ([i 0] 69 [lst '()]) 70 (cond 71 [(= i 16) (with-syntax ([(bodies ...) lst]) 72 (syntax 73 (let ([v (board-v board)]) 74 bodies ... 75 (void))))] 76 [else (loop (+ i 1) 77 (cons (with-syntax ([i i]) 78 (syntax (let ([loc (vector-ref v i)] 79 [pawn (vector-ref all-pawns i)]) 80 lam-body))) 81 lst))]))] 82 [(_ board f) (syntax (for-each-pawn/loc/proc board f))])) 83 84 (define (make-old-style-board start main home-rows home) 85 (let* ([board (new-board)] 86 [v (board-v board)]) 87 ;; can ignore start pawns 88 89 ;; main pawns 90 (let loop ([i 0]) 91 (cond 92 [(= i (vector-length main)) '()] 93 [else (for-each (lambda (pawn) (vector-set! v (pawn-index pawn) i)) 94 (vector-ref main i)) 95 (loop (+ i 1))])) 96 97 ;; home row pawns 98 (for-each 99 (lambda (hr) 100 (let ([vec (cdr hr)]) 101 (let loop ([i 0]) 102 (cond 103 [(= i (vector-length vec)) (void)] 104 [else 105 (for-each (lambda (pawn) 106 (vector-set! v 107 (pawn-index pawn) 108 (make-home-row-loc i (pawn-color pawn)))) 109 (vector-ref vec i)) 110 (loop (+ i 1))])))) 111 home-rows) 112 113 ;; home pawns 114 (for-each (lambda (home-pawn) (vector-set! v (pawn-index home-pawn) 'home)) home) 115 board)) 116 117 (define (new-board) (make-board (make-vector 16 'start))) 118 (define board-home-row-size 7) 119 (define board-main-size 68) 120 121 ; (matching-pawns <board-exp> <pawn-id> <loc-id> <test-exp>) 122 (define-syntax (matching-pawns stx) 123 (syntax-case stx () 124 [(_ board pawn loc test) 125 (and (identifier? (syntax pawn)) 126 (identifier? (syntax loc))) 127 (let loop ([i 16] 128 [sofar '()]) 129 (cond 130 [(zero? i) (with-syntax ([(body ...) sofar]) 131 (syntax 132 (let ([result '()] 133 [v (board-v board)]) 134 body ... 135 result)))] 136 [else (loop (- i 1) 137 (cons 138 (with-syntax ([i (- i 1)]) 139 (syntax 140 (let ([loc (vector-ref v i)] 141 [pawn (vector-ref all-pawns i)]) 142 (when test 143 (set! result (cons pawn result)))))) 144 sofar))]))])) 145 146 (define (board-main-i board i) (matching-pawns board pawn loc (equal? i loc))) 147 (define (board-home-row-i board color i) 148 (matching-pawns board 149 pawn 150 loc 151 (and (home-row-loc? loc) 152 (= (home-row-loc-num loc) i) 153 (eq? (home-row-loc-color loc) color)))) 154 (define (board-start board) (matching-pawns board pawn loc (eq? loc 'start))) 155 (define (board-home board) (matching-pawns board pawn loc (eq? loc 'home))) 156 157 ;; move-piece : board pawn loc -> board 158 (define (move-piece board pawn to) 159 (let ([new-board (copy-board board)]) 160 (vector-set! (board-v new-board) (pawn-index pawn) to) 161 new-board)) 162 163 ;; move-piece2 : board pawn loc pawn loc -> board 164 (define (move-piece2 board pawn to pawn2 to2) 165 (let ([new-board (copy-board board)]) 166 (vector-set! (board-v new-board) (pawn-index pawn) to) 167 (vector-set! (board-v new-board) (pawn-index pawn2) to2) 168 new-board)) 169 170 ;; copy-board : board -> board 171 (define (copy-board board) 172 (let ([v (board-v board)]) 173 (make-board (build-vector 16 (lambda (i) (vector-ref v i)))))) 174 175 ;; entry points for the four colors 176 (define enters '((green . 5) 177 (red . 22) 178 (blue . 39) 179 (yellow . 56))) 180 (define (get-enter-pos color) (cdr (assq color enters))) 181 182 ;; the points where the four colors go off into their 183 ;; own sections of the board. 184 (define exits '((green . 0) 185 (red . 17) 186 (blue . 34) 187 (yellow . 51))) 188 (define (get-exit-pos color) (cdr (assq color exits))) 189 190 (define safeties (append (map cdr enters) 191 (map cdr exits) 192 (list 12 193 (+ 12 17) 194 (+ 12 17 17) 195 (+ 12 17 17 17)))) 196 (define (safety? i) (memq i safeties)) 197 198 ;; find-blockade/between : board loc loc -> (union loc #f) 199 (define (find-blockade/between board start end) 200 (find-blockade/cases (find-blockades board) start end)) 201 202 ;; find-blockades : board -> (listof loc) 203 (define (find-blockades board) 204 (let ([ht (make-hash)] 205 [blockades '()]) 206 (for-each-pawn/loc 207 board 208 (lambda (pawn loc) 209 (when (hash-ref ht 210 loc 211 (lambda () 212 (hash-set! ht loc #t) 213 #f)) 214 (set! blockades (cons loc blockades))))) 215 blockades)) 216 217 ;; find-blockade/cases : (listof loc) loc loc -> (union loc #f) 218 (define (find-blockade/cases blockades start end) 219 (cond 220 [(and (number? start) (number? end)) 221 (if (<= start end) 222 (find-blockade/between-main blockades start end) 223 (or (find-blockade/between-main blockades start (- board-main-size 1)) 224 (find-blockade/between-main blockades 0 end)))] 225 [(and (number? start) (home-row-loc? end)) 226 (or (find-blockade/cases blockades start (get-exit-pos (home-row-loc-color end))) 227 (find-blockade/between-home-row blockades 228 (home-row-loc-color end) 229 0 230 (home-row-loc-num end)))] 231 [(and (home-row-loc? start) (home-row-loc? end)) 232 (find-blockade/between-home-row blockades 233 (home-row-loc-color start) 234 (home-row-loc-num start) 235 (home-row-loc-num end))] 236 [(not (loc<=? start end)) 237 (error 'find-blockade/between "expected locs in order, got ~e and ~e" start end)] 238 [(or (eq? start 'home) (eq? end 'home)) 239 (error 'find-blockade/between "cannot accept 'home as argument, got ~e and ~e" start end)] 240 [(or (eq? start 'start) (eq? end 'start)) 241 (error 'find-blockade/between "cannot accept 'start as argument, got ~e and ~e" start end)] 242 [else 243 (error 'find-blockade/between "unknown arguments ~e and ~e" start end)])) 244 245 (define (find-blockade/between-main blockades start end) 246 (ormap (lambda (blockade) (and (number? blockade) 247 (<= start blockade end) 248 blockade)) 249 blockades)) 250 251 (define (find-blockade/between-home-row blockades color start end) 252 (ormap (lambda (blockade) (and (home-row-loc? blockade) 253 (eq? color (home-row-loc-color blockade)) 254 (<= start (home-row-loc-num blockade) end) 255 blockade)) 256 blockades)) 257 258 ;; loc : loc 259 ;; p1 : pawn 260 ;; p2 : pawn 261 ;; (pawn<=? p1 p2) is true 262 (define-struct blockade (loc p1 p2) #:inspector (make-inspector)) 263 264 ;; find-blockades/color : board color -> (listof blockade) 265 (define (find-blockades/color board color) 266 (let ([ht (make-hash)] 267 [v (board-v board)] 268 [offset (find-pawn-index color 0)]) 269 (let loop ([i 0] 270 [blockades null]) 271 (cond 272 [(= i 4) blockades] 273 [else 274 (let ([loc (vector-ref v (+ offset i))]) 275 (cond 276 [(eq? loc 'start) (loop (+ i 1) blockades)] 277 [(eq? loc 'home) (loop (+ i 1) blockades)] 278 [(hash-ref ht loc (lambda () 279 (hash-set! ht loc i) 280 #f)) 281 => 282 (lambda (old-i) 283 (loop (+ i 1) 284 (cons (make-blockade loc 285 (vector-ref all-pawns (+ offset old-i)) 286 (vector-ref all-pawns (+ offset i))) 287 blockades)))] 288 [else (loop (+ i 1) blockades)]))])))) 289 290 (define (loc<=? l1 l2) (<= (loc->id l1) (loc->id l2))) 291 292 (define (loc->id loc) 293 (cond 294 [(eq? loc 'start) 0] 295 [(number? loc) (+ loc 1)] 296 [(eq? loc 'home) 1000] 297 [(home-row-loc? loc) (+ 100 298 (* (color->int (home-row-loc-color loc)) 299 100) 300 (home-row-loc-num loc))] 301 [else (error 'loc->id "expected a loc, got ~e" loc)])) 302 303 (define (build-pawn color id) (make-pawn color id (find-pawn-index color id))) 304 (define (find-pawn-index color id) (+ (* (color->int color) 4) id)) 305 306 (define (pawn<=? p1 p2) 307 (if (eq? (pawn-color p1) (pawn-color p2)) 308 (<= (pawn-id p1) (pawn-id p2)) 309 (color<= (pawn-color p1) (pawn-color p2)))) 310 311 (define (color<= c1 c2) 312 (<= (color->int c1) (color->int c2))) 313 314 (define (color->int c) 315 (case c 316 [(blue) 0] 317 [(green) 1] 318 [(red) 2] 319 [(yellow) 3] 320 [else (error 'color->int "unknown color ~e" c)])) 321 322 323 (define all-pawns 324 (vector (build-pawn 'blue 0) 325 (build-pawn 'blue 1) 326 (build-pawn 'blue 2) 327 (build-pawn 'blue 3) 328 (build-pawn 'green 0) 329 (build-pawn 'green 1) 330 (build-pawn 'green 2) 331 (build-pawn 'green 3) 332 (build-pawn 'red 0) 333 (build-pawn 'red 1) 334 (build-pawn 'red 2) 335 (build-pawn 'red 3) 336 (build-pawn 'yellow 0) 337 (build-pawn 'yellow 1) 338 (build-pawn 'yellow 2) 339 (build-pawn 'yellow 3))) 340 341 (let loop ([i 0]) 342 (unless (= i 16) 343 (unless (= i (pawn-index (vector-ref all-pawns i))) 344 (error 'mismatch "~s ~s" i (vector-ref all-pawns i))) 345 (loop (+ i 1))))) 346