| blob | ae3322a9ed7e7794e75096794626fa96660c206a |
1 divert(-1)dnl -*- m4 -*-
2 # Usage: m4 [-Dfile=day23.input] day23.m4
3 # Optionally use -Dverbose=1 to see some progress
5 # TODO: Ideas for optimization:
6 # * Square root of work. Instead of doing ~3^34 branches from start to end,
7 # do ~3^17 branches from start to mid, ~3^17 branches from end to mid,
8 # then search for best valid pair among the results. Requires storing
9 # path as a bitmap. A single int bitmap is possible: although there are 36
10 # nodes, our path must include start, end, and their two neighbors, which
11 # therefore don't need a bit in the map.
12 # * Early abort. The max path occupies at most n-1 edges, and we know the
13 # best score possible from all nodes. By comparing the potential possible
14 # contribution of all unvisited nodes (subtract the current node's
15 # contribution), we can kill any path that will not beat an already-known
16 # longer solution
17 # * DP solution, which considers the state of 6 nodes at a time (as no level
18 # of the graph is wider). There are at most 76 possible states for 6 nodes:
19 # https://www.reddit.com/r/adventofcode/comments/18ysozp/comment/kgdcc0p
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 # More importantly, any two rows of nodes can be collapsed into one, with
97 # a finite number of transitions to the next row that don't form a
98 # disconnected loop.
100 include(`common.m4')ifelse(common(23), `ok', `',
101 `errprint(`Missing common initialization
102 ')m4exit(1)')
104 define(`input', translit(include(defn(`file')), `#.>v'nl, `01234'))
105 define(`x', 0)define(`y', 0)define(`n', 1)
106 define(`check', `ifdef(`$1', `define(`c'$1, incr(defn(`c'$1)))1')')
107 define(`do0', `define(`x', incr($1))')
108 define(`do1', `define(`g$1_$2')do0($@)')
109 define(`do2', `ifelse(check(`n'decr($1)`_$2'), 1, `', check(`n'incr($1)`_$2'),
110 1, `', `define(`n'incr($1)`_$2', n)define(`c'n, 1)define(`n'n,
111 incr($1)`,$2')define(`n', incr(n))')do1($@)')
112 define(`do3', `ifelse(check(`n$1_'decr($2)), 1, `', `define(`n$1_'incr($2),
113 n)define(`c'n, 1)define(`n'n, `$1,'incr($2))define(`n', incr(n))')do1($@)')
114 define(`do4', `define(`maxx', $1)define(`x', 0)define(`y', incr($2))')
116 ifdef(`__gnu__', `
117 patsubst(defn(`input'), `.', `do\&(x, y)')
118 ',`
119 define(`chew', `ifelse($1, 1, `do$2(x, y)', `$0(eval($1/2), substr(
120 `$2', 0, eval($1/2)))$0(eval($1-$1/2), substr(`$2', eval($1/2)))')')
121 chew(len(defn(`input')), defn(`input'))
122 ')
124 # Assumption: all decision points are entered from top or left, and
125 # exit to bottom or right. Reduce the graph to just the distances between
126 # nodes of interest, for a much smaller problem to solve. In part 2, a
127 # naive brute force with no constraints on edges visits over 102 million
128 # edges, but given that we are a planar graph and cannot visit a node twice,
129 # any node with fewer than 4 neighbors is on a perimeter; edges between two
130 # perimeter nodes should always be directional to avoid cutting off a path
131 # to the end node. This change alone reduces work to 14.7 million edge visits.
132 ifdef(`g1_0', `', `fatal(`failed assumption about start point')')
133 ifdef(`g'decr(decr(maxx))`_'decr(y), `',
134 `fatal(`failed assumption about end point')')
135 define(`n0', `1,0')define(`c0', 1)
136 define(`n'n, decr(decr(maxx))`,'decr(y))define(`c'n, 1)
137 define(`n'decr(decr(maxx))`_'decr(y), n)
138 # pair(from_n, to_n, dist)
139 # Ep_n: list of neighbors for part p from node n
140 # en_m: weight of edge from node n to m
141 define(`pair', `ifelse($1, $2, `', `define(`E1_$1', defn(`E1_$1')`,$2')define(
142 `E2_$1', defn(`E2_$1')`,$2')ifelse(eval(c$1==4 || c$2==4), 1, `define(`E2_$2',
143 defn(`E2_$2')`,$1')')define(`e$1_$2', $3)define(`e$2_$1', $3)')')
144 # visit(x, y, from_n, dist)
145 define(`_visit', `ifdef(`g$1_$2', `popdef(`g$1_$2')visit(incr($1), $2, $3,
146 incr($4))visit($1, incr($2), $3, incr($4))visit(decr($1), $2, $3,
147 incr($4))visit($1, decr($2), $3, incr($4))')')
148 define(`visit', `ifdef(`n$1_$2', `pair($3, n$1_$2, $4)ifdef(`s$1_$2', `',
149 `define(`s$1_$2')_$0(incr($1), $2, n$1_$2, 1)_$0($1, incr($2), n$1_$2,
150 1)')', `_$0($@)')')
151 output(1, `...compressing graph')
152 define(`s1_0')_visit(1, 1, 0, 1)
154 # Create tN(dist) and TN(dist) for each node N
155 define(`_travel_', ``$2$3(eval($''1+e$1_$3``))'')
156 define(`_travel', `define(`$2$1', ifelse(eval(verbose > 0), 1,
157 ``show(p)'')`pushdef(`$2$1')'_foreach(`$0_($1, `$2', ', `)',
158 shift($@))`popdef(`$2$1')')')
159 define(`travel', `_$0($1, `t'E1_$1)_$0($1, `T'E2_$1)')
160 forloop_arg(0, decr(n), `travel')
161 define(`t'n, `ifelse(eval($1 > part1), 1, `define(`part1', $1)')')
162 define(`T'n, `ifelse(eval($1 > part2), 1, `define(`part2', $1)')')
164 define(`p', 0)
165 define(`rename', `define(`$2', defn(`$1'))popdef(`$1')')
166 define(`show0', `output(1, `...$1')rename(`show$1', `show'eval($1+500000))')
167 define(`show', `ifdef(`$0$1', `$0$1($1)')define(`p', incr($1))')
168 ifelse(eval(verbose > 0), 1, `define(`_travel', `show(p)'defn(`_travel'))')
170 define(`part1', 0)t0(0)
171 define(`part2', 0)T0(0)
173 divert`'part1
174 part2