-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathd12p2.hoon
111 lines (101 loc) · 4.1 KB
/
d12p2.hoon
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
|= input=(list @t)
^- @ud
=<
=/ height=@ud (lent input)
=/ width=@ud (lent (trip +2:input))
=/ parsed-output=[(map (pair @ud @ud) @t) (pair @ud @ud) (pair @ud @ud)] (parse-input input)
=/ heightmap=(map (pair @ud @ud) @t) +2:parsed-output
=/ pairs=(list (pair @ud @ud)) (murn ~(tap by heightmap) |=([a=[@ud @ud] b=@t] ?:(=('a' b) (some a) ~)))
~& > (lent pairs)
=/ start=[@ud @ud] +2:+3:parsed-output
=/ end=[@ud @ud] +3:+3:parsed-output
=/ dk-raw=[(map (pair @ud @ud) @ud) (map (pair @ud @ud) (pair @ud @ud))] (dijkstra heightmap end width height)
(find-smallest heightmap +3:dk-raw end)
::
|%
++ find-smallest
|= [hm=(map (pair @ud @ud) @t) prev=(map (pair @ud @ud) (pair @ud @ud)) end=[@ud @ud]]
^- @ud
=/ minval=@ud 99.999
=/ pairs=(list (pair @ud @ud)) (murn ~(tap by hm) |=([a=[@ud @ud] b=@t] ?:(=('a' b) (some a) ~)))
|-
?~ pairs minval
=/ candidate=@ud (count-smallest-path prev i.pairs end)
?: (lth candidate minval) $(minval candidate, pairs t.pairs)
$(pairs t.pairs)
::
++ count-smallest-path
|= [prev=(map (pair @ud @ud) (pair @ud @ud)) end=[@ud @ud] goal=[@ud @ud]]
^- @ud
=| count=@ud
|-
?: =(end goal) count
?: ?!((~(has by prev) end)) 99.999
$(end (~(got by prev) end), count +(count))
++ get-smallest-dist
|= [hm=(map (pair @ud @ud) @ud) qr=(set (pair @ud @ud))]
^- [@ud @ud]
=/ q=(list (pair @ud @ud)) ~(tap in qr)
=| min-coord=[@ud @ud]
=/ min=@ud 999
?: =(0 ~(wyt by hm)) +2:q
|-
?~ q min-coord
?: (lth (~(gut by hm) i.q 999) min) $(min (~(gut by hm) i.q 999), min-coord i.q, q t.q)
$(q t.q)
::
++ dijkstra
|= [hm=(map (pair @ud @ud) @t) s=[@ud @ud] w=@ud h=@ud]
^- [(map (pair @ud @ud) @ud) (map (pair @ud @ud) (pair @ud @ud))]
=/ q=(set (pair @ud @ud)) ~(key by hm)
=| dist=(map (pair @ud @ud) @ud)
=| prev=(map (pair @ud @ud) (pair @ud @ud))
=. dist (~(put by dist) s 0)
=/ os=@ud 99.999
|-
?: =(os ~(wyt in q)) [dist prev]
=. os ~(wyt in q)
=/ n=[@ud @ud] (get-smallest-dist dist q)
=. q (~(del in q) n)
=/ top-coord=[@ud @ud] [999 999]
=/ bot-coord=[@ud @ud] [999 999]
=/ left-coord=[@ud @ud] [999 999]
=/ right-coord=[@ud @ud] [999 999]
=? top-coord (gte +((~(gut by hm) [+2:n +(+3:n)] 0)) (~(got by hm) n)) [+2:n +(+3:n)]
=? bot-coord
?: (gth +3:n 0) (gte +((~(gut by hm) [+2:n (sub +3:n 1)] 0)) (~(got by hm) n))
|
[+2:n (sub +3:n 1)]
=? left-coord
?: (gth +2:n 0) (gte +((~(gut by hm) [(sub +2:n 1) +3:n] 0)) (~(got by hm) n))
|
[(sub +2:n 1) +3:n]
=? right-coord (gte +((~(gut by hm) [+(+2:n) +3:n] 0)) (~(got by hm) n)) [+(+2:n) +3:n]
=? dist ?!(=(top-coord [999 999])) (~(put by dist) top-coord (min (~(gut by dist) top-coord 999) (add 1 (~(got by dist) n))))
=? prev ?!(=(top-coord [999 999])) ?:((lte (add 1 (~(got by dist) n)) (~(gut by dist) top-coord 999)) (~(put by prev) top-coord n) prev)
=? dist ?!(=(bot-coord [999 999])) (~(put by dist) bot-coord (min (~(gut by dist) bot-coord 999) (add 1 (~(got by dist) n))))
=? prev ?!(=(bot-coord [999 999])) ?:((lte (add 1 (~(got by dist) n)) (~(gut by dist) bot-coord 999)) (~(put by prev) bot-coord n) prev)
=? dist ?!(=(left-coord [999 999])) (~(put by dist) left-coord (min (~(gut by dist) left-coord 999) (add 1 (~(got by dist) n))))
=? prev ?!(=(left-coord [999 999])) ?:((lte (add 1 (~(got by dist) n)) (~(gut by dist) left-coord 999)) (~(put by prev) left-coord n) prev)
=? dist ?!(=(right-coord [999 999])) (~(put by dist) right-coord (min (~(gut by dist) right-coord 999) (add 1 (~(got by dist) n))))
=? prev ?!(=(right-coord [999 999])) ?:((lte (add 1 (~(got by dist) n)) (~(gut by dist) right-coord 999)) (~(put by prev) right-coord n) prev)
$(dist dist, prev prev, q q, os os)
::
++ parse-input
|= in=(list @t)
^- [(map (pair @ud @ud) @t) (pair @ud @ud) (pair @ud @ud)]
=| w=@ud
=| h=@ud
=| s=[@ud @ud]
=| e=[@ud @ud]
=| m=(map (pair @ud @ud) @t)
|-
?~ in [m s e]
=/ line=tape (trip i.in)
|-
?~ line ^$(in t.in, w 0, h +(h))
=/ val=@t i.line
?: =(val 'S') $(line t.line, w +(w), s [w h], m (~(put by m) [w h] 'a'))
?: =(val 'E') $(line t.line, w +(w), e [w h], m (~(put by m) [w h] 'z'))
$(line t.line, m (~(put by m) [w h] i.line), w +(w))
--