-
Notifications
You must be signed in to change notification settings - Fork 0
/
walls.scm
201 lines (188 loc) · 5.87 KB
/
walls.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
(define (find-walls state x/y in-column?)
(define (p coord)
(and (= 1 (count unseen?
(filter valid-coord?
(let ((d (if in-column? '(1 0) '(0 1))))
(list (map + coord d)
(map - coord d))))))
(and (eq? 'none (square-color coord))
(member (square-char coord) '(#\| #\-)))))
(let ((ls (map (lambda (x/y2)
(let ((coord (if in-column?
(list x/y x/y2)
(list x/y2 x/y))))
(and (p coord) coord)))
(if in-column?
(reverse-range 20 4)
(reverse-range 78 3)))))
(let loop ((ls ls)
(cur '())
(acc '()))
(if (null? ls)
(if (>= (length cur) 3)
(cons cur acc)
acc)
(if (car ls)
(loop (cdr ls)
(cons (car ls) cur)
acc)
(loop (cdr ls)
'()
(if (>= (length cur) 3)
(cons cur acc)
acc)))))))
(define (grow-wall wall vert?)
(define (grow start dir)
(let loop ((c (map + start dir))
(acc '()))
(if (or (seen? c)
(not (valid-coord? c)))
acc
(loop (map + c dir)
(cons c acc)))))
(let ((dir (if vert? '(0 1) '(1 0))))
(append (grow (car wall) (map - dir))
wall
(reverse (grow (last wall) dir)))))
(define (unseen? c) (not (seen? c)))
(define (wall-dir wall vert?)
(let* ((d (if vert? '(1 0) '(0 1)))
(side (map (lambda (c) (map + c d)) wall)))
(cond ((every unseen? (map (lambda (c) (map + c d)) wall))
d)
((every unseen? (map (lambda (c) (map - c d)) wall))
(map - d))
(else #f))))
(define (wall-extend wall vert?)
(let ((dir (wall-dir wall vert?)))
(if (not dir)
0
(let loop ((i 2))
(let ((disp (map (specialize * i) dir)))
(if (or (not (valid-coord? (map + (car wall) disp)))
(not (every unseen? (map (lambda (c) (map + c disp))
wall))))
(- i 1)
(loop (+ i 1))))))))
; For squares, the score is the same as the area of the unexplored area
; extending out from the wall. We prefer rectangles that are closer
; to squares. To adjust the score, we multiply the area by the fourth root
; of the height/width ratio. So while 3x3 has a score of 9, 1x9 has a score
; of only (* 1 9 (expt (/ 1 9) 1/4)) = 5.20.
(define (wall-score wall vert?)
(let ((extend (wall-extend wall vert?)))
(if (zero? extend)
0
(let* ((len (length wall))
(ratio (if (< len extend)
(/ len extend)
(/ extend len)))
(penalty (expt ratio 1/4)))
(* len extend penalty)))))
(define (walls-to-search state)
(define (ranked-walls vert?)
(map (lambda (wall)
(list wall (wall-score (grow-wall wall vert?) vert?)))
(apply append
(map (lambda (x/y)
(find-walls state x/y vert?))
(if vert?
(range 1 80)
(range 2 22))))))
(map car
(list-sort (lambda (a b)
(> (cadr a) (cadr b)))
(append (ranked-walls #t)
(ranked-walls #f)))))
(define (wall-get-inner state wall)
(let* ((dir (map - (cadr wall) (car wall)))
(disp (map abs (reverse dir))))
(let ((side (map (lambda (c) (map + c disp)) wall)))
(if (every seen? side)
side
(let ((side (map (lambda (c) (map - c disp)) wall)))
(if (every seen? side)
side
'wall-get-inner-missed))))))
(define (search-walls state)
(let* ((current (get-state state 'wall-searching))
(walls (get-state state 'walls-to-search)))
(cond ((not walls)
(search-walls
(set-state state 'walls-to-search (walls-to-search state))))
((not current)
(if (null? walls)
(pop-action-go (set-state state 'searched-walls #t))
(let* ((inner (wall-get-inner state (car walls)))
(a (find-path-hard state (get-coord) (car inner)))
(b (find-path-hard state (get-coord) (last inner))))
(search-walls (set-state
state
'walls-to-search (cdr walls)
'wall-searching (if (< (length a) (length b))
inner
(reverse inner)))))))
((and (< (searched-for state (get-coord)) 23)
(member (get-coord) current))
(search state))
(else
(let ((rest (remove (specialize adjacent? (get-coord)) current))
(p (specialize find-path-to state (get-coord))))
(if (and (> (length rest) 1)
(p (cadr rest)))
(push-action-go (set-state state 'wall-searching rest)
(lambda (state) (go-to state (cadr rest))))
(let loop ((rest rest))
(cond ((null? rest)
(search-walls (set-state state 'wall-searching #f)))
((p (car rest))
(push-action-go
(set-state state 'wall-searching rest)
(lambda (state) (go-to state (car rest)))))
(else (loop (cdr rest)))))))))))
(define (wall-curved? coord)
(define (straight-neighbors c)
(filter wall?
(map (lambda (dir) (map + c dir))
'((0 -1) (1 0) (0 1) (-1 0)))))
(define (diagonal-neighbors c)
(filter wall?
(map (lambda (dir) (map + c dir))
'((1 -1) (1 1) (-1 1) (-1 -1)))))
(define (knights-move? a b)
(member (map abs (map - a b))
'((1 2) (2 1))))
(let ((char (square-char coord)))
(or (any (lambda (c)
(equal? (square-char c) char))
(diagonal-neighbors coord))
(let loop ((cur coord)
(last coord))
(let ((cur-char (square-char cur)))
(and (<= (min-distance cur coord) 2)
(or (and (knights-move? cur coord)
(char=? cur-char #\|)
(char=? char #\|))
(and (equal? (map abs (map - cur coord)) '(2 2))
(char=? cur-char #\-)
(char=? char #\-))
(let ((ls (delete last (straight-neighbors cur))))
(and (= (length ls) 1)
(loop (car ls)
cur))))))))))
(define (wc2? coord)
(define (straight-neighbors c)
(filter wall?
(map (lambda (dir) (map + c dir))
'((0 -1) (1 0) (0 1) (-1 0)))))
(define (diagonal-neighbors c)
(filter wall?
(map (lambda (dir) (map + c dir))
'((1 -1) (1 1) (-1 1) (-1 -1)))))
(define (knights-move? a b)
(member (map abs (map - a b))
'((1 2) (2 1))))
(let ((char (square-char coord)))
(any (lambda (c)
(equal? (square-char c) char))
(diagonal-neighbors coord))))