blob: e483dc10157bda0ddd9c0907be437b7c5df1f598 (
plain)
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
|
(defmeth board depth-search (bo mincost cur goal gpath lpath depth)
(unless (or (memqual cur lpath)
(memqual cur gpath)
(minusp cur.x)
(minusp cur.y)
(>= cur.x bo.w)
(>= cur.y bo.h))
(push cur lpath)
(if (or (zerop (pdec depth)) (equal cur goal))
(let ((cost (sum lpath bo)))
(when (or (null mincost.val) (< cost mincost.val))
(set mincost.val cost
mincost.path lpath)))
(progn
bo.(depth-search mincost (new (coord cur.x (succ cur.y)))
goal gpath lpath depth)
bo.(depth-search mincost (new (coord (succ cur.x) cur.y))
goal gpath lpath depth)
bo.(depth-search mincost (new (coord cur.x (pred cur.y)))
goal gpath lpath depth)
bo.(depth-search mincost (new (coord (pred cur.x) cur.y))
goal gpath lpath depth)))))
(defmeth board search (bo gmincost cur goal gpath lookahead)
(unless (memqual cur gpath)
(if (equal cur goal)
(set gmincost.val (+ (sum gpath bo) (- [bo cur] [bo goal]))
gmincost.path gpath)
(let ((lmincost (new cost)))
bo.(depth-search lmincost cur goal gpath nil lookahead)
(whenlet ((next [lmincost.path -2]))
(prinl next)
bo.(search gmincost next goal (cons cur gpath) lookahead))))))
(defun solve-one (: (name :))
(let ((bo (read-input name))
(mincost (new cost)))
bo.(search mincost
(new (coord 0 0))
(new (coord (pred bo.w) (pred bo.h)))
nil
13)
mincost))
(defmeth board fill-costs (bo lim)
(let ((goal (new (coord (pred bo.w) (pred bo.h)))))
(labels ((rec (coo path xmin ymin xmax ymax)
(unless (or (memqual coo path)
(< coo.x xmin)
(< coo.y ymin)
(>= coo.x bo.w)
(>= coo.y bo.h))
(push coo path)
(placelet ((memo [bo.memo coo]))
(or memo
(if (equal coo goal)
(set memo (new cost
coo coo
val 0
path (list goal))))
(iflet ((next (flow
(vec (rec (new (coord coo.x (succ coo.y)))
path xmin ymin xmax ymax)
(rec (new (coord (succ coo.x) coo.y))
path xmin ymin xmax ymax)
(rec (new (coord coo.x (pred coo.y)))
path xmin ymin xmax ymax)
(rec (new (coord (pred coo.x) coo.y))
path xmin ymin xmax ymax))
(remq nil)))
(min [find-min next : .val]))
(set memo
(new cost
coo coo
val (+ [bo coo] min.val)
path (cons coo min.path)))))))))
(each ((k (max bo.w bo.h)..0))
(each ((y bo.h..k))
(let ((coo (new (coord k y)))
(xmin (max 0 (- k lim)))
(xmax (min bo.w (+ k lim))))
(prinl coo)
(set [bo.memo coo]
(rec coo nil xmin (max 0 (- y lim)) xmax (min bo.h (+ y lim))))))
(each ((x bo.w..k))
(let ((coo (new (coord x k)))
(ymin (max 0 (- k lim)))
(ymax (min bo.h (+ k lim))))
(prinl coo)
(set [bo.memo coo]
(rec coo nil (max 0 (- x lim)) ymin (min bo.w (+ x lim)) ymax))))))))
(defun solve-one-bad (: (name :))
(let ((bo (read-input name)))
bo.(fill-costs 0)
[bo.memo (new (coord 0 0))]))
|
