| blob | 8016a57789081da2d34105fe8aaba4c7cbc900f3 |
1 divert(-1)dnl -*- m4 -*-
2 # Usage: m4 [-Dseed=NNN] [-Dfile=day10.input] day10.m4
3 # Optionally use -Dverbose=1 to see some progress
4 # Optionally use -Dalgo=full|sparse to choose an algorithm
6 include(`common.m4')ifelse(common(10, 131101), `ok', `',
7 `errprint(`Missing common initialization
8 ')m4exit(1)')
10 ifdef(`seed', `', `define(`seed', translit(include(defn(`file')), nl))')
11 ifdef(`algo', `', `define(`algo', `sparse')')
13 # Using http://www.se16.info/js/lands2.htm
14 define(`table', `
15 `1, H, `H', 22',
16 `2, He, `Hf,Pa,H,Ca,Li', 13112221133211322112211213322112',
17 `3, Li, `He', 312211322212221121123222112',
18 `4, Be, `Ge,Ca,Li', 111312211312113221133211322112211213322112',
19 `5, B, `Be', 1321132122211322212221121123222112',
20 `6, C, `B', 3113112211322112211213322112',
21 `7, N, `C', 111312212221121123222112',
22 `8, O, `N', 132112211213322112',
23 `9, F, `O', 31121123222112',
24 `10, Ne, `F', 111213322112',
25 `11, Na, `Ne', 123222112',
26 `12, Mg, `Pm,Na', 3113322112',
27 `13, Al, `Mg', 1113222112',
28 `14, Si, `Al', 1322112',
29 `15, P, `Ho,Si', 311311222112',
30 `16, S, `P', 1113122112',
31 `17, Cl, `S', 132112',
32 `18, Ar, `Cl', 3112',
33 `19, K, `Ar', 1112',
34 `20, Ca, `K', 12',
35 `21, Sc, `Ho,Pa,H,Ca,Co', 3113112221133112',
36 `22, Ti, `Sc', 11131221131112',
37 `23, V, `Ti', 13211312',
38 `24, Cr, `V', 31132',
39 `25, Mn, `Cr,Si', 111311222112',
40 `26, Fe, `Mn', 13122112',
41 `27, Co, `Fe', 32112',
42 `28, Ni, `Zn,Co', 11133112',
43 `29, Cu, `Ni', 131112',
44 `30, Zn, `Cu', 312',
45 `31, Ga, `Eu,Ca,Ac,H,Ca,Zn', 13221133122211332',
46 `32, Ge, `Ho,Ga', 31131122211311122113222',
47 `33, As, `Ge,Na', 11131221131211322113322112',
48 `34, Se, `As', 13211321222113222112',
49 `35, Br, `Se', 3113112211322112',
50 `36, Kr, `Br', 11131221222112',
51 `37, Rb, `Kr', 1321122112',
52 `38, Sr, `Rb', 3112112',
53 `39, Y, `Sr,U', 1112133',
54 `40, Zr, `Y,H,Ca,Tc', 12322211331222113112211',
55 `41, Nb, `Er,Zr', 1113122113322113111221131221',
56 `42, Mo, `Nb', 13211322211312113211',
57 `43, Tc, `Mo', 311322113212221',
58 `44, Ru, `Eu,Ca,Tc', 132211331222113112211',
59 `45, Rh, `Ho,Ru', 311311222113111221131221',
60 `46, Pd, `Rh', 111312211312113211',
61 `47, Ag, `Pd', 132113212221',
62 `48, Cd, `Ag', 3113112211',
63 `49, In, `Cd', 11131221',
64 `50, Sn, `In', 13211',
65 `51, Sb, `Pm,Sn', 3112221',
66 `52, Te, `Eu,Ca,Sb', 1322113312211',
67 `53, I, `Ho,Te', 311311222113111221',
68 `54, Xe, `I', 11131221131211',
69 `55, Cs, `Xe', 13211321',
70 `56, Ba, `Cs', 311311',
71 `57, La, `Ba', 11131',
72 `58, Ce, `La,H,Ca,Co', 1321133112',
73 `59, Pr, `Ce', 31131112',
74 `60, Nd, `Pr', 111312',
75 `61, Pm, `Nd', 132',
76 `62, Sm, `Pm,Ca,Zn', 311332',
77 `63, Eu, `Sm', 1113222',
78 `64, Gd, `Eu,Ca,Co', 13221133112',
79 `65, Tb, `Ho,Gd', 3113112221131112',
80 `66, Dy, `Tb', 111312211312',
81 `67, Ho, `Dy', 1321132',
82 `68, Er, `Ho,Pm', 311311222',
83 `69, Tm, `Er,Ca,Co', 11131221133112',
84 `70, Yb, `Tm', 1321131112',
85 `71, Lu, `Yb', 311312',
86 `72, Hf, `Lu', 11132',
87 `73, Ta, `Hf,Pa,H,Ca,W', 13112221133211322112211213322113',
88 `74, W, `Ta', 312211322212221121123222113',
89 `75, Re, `Ge,Ca,W', 111312211312113221133211322112211213322113',
90 `76, Os, `Re', 1321132122211322212221121123222113',
91 `77, Ir, `Os', 3113112211322112211213322113',
92 `78, Pt, `Ir', 111312212221121123222113',
93 `79, Au, `Pt', 132112211213322113',
94 `80, Hg, `Au', 31121123222113',
95 `81, Tl, `Hg', 111213322113',
96 `82, Pb, `Tl', 123222113',
97 `83, Bi, `Pm,Pb', 3113322113',
98 `84, Po, `Bi', 1113222113',
99 `85, At, `Po', 1322113',
100 `86, Rn, `Ho,At', 311311222113',
101 `87, Fr, `Rn', 1113122113',
102 `88, Ra, `Fr', 132113',
103 `89, Ac, `Ra', 3113',
104 `90, Th, `Ac', 1113',
105 `91, Pa, `Th', 13',
106 `92, U, `Pa', 3'')
107 define(`prep', `_$0($1)')
108 define(`_prep', `define(`e$1', `$4')define(`l$1', len(`$4'))define(`$2',
109 $1)ifelse('seed`, `$4', `define(`init', $1)')')
110 foreach(`prep', table)
111 ifdef(`init', `',
112 `errprintn(`unsure how to break 'seed` into elements')m4exit(1)')
114 ifelse(algo, `full', `
115 output(1, `Using full matrix multiply, O(log n)')
116 define(`_prep', `_foreach(`setup($1,', `)', `', $3)')
117 define(`setup', `define(`m1_$1_$2', incr(0defn(`m1_$1_$2')))')
118 foreach(`prep', table)
119 define(`_prep', `ifdef(`m1_$1_$2', `', `define(`m1_$1_$2', 0)')')
120 define(`prep', `forloop(1, 92, `_$0($1,', `)')')
121 forloop_arg(1, 92, `prep')
122 define(`_dot', `+m$1_$3_$5*m$2_$5_$4')
123 define(`dot', `define(`m$3_$4_$5', eval(forloop(1, 92, `_$0($1, $2, $4, $5, ',
124 `)')))')
125 define(`_mult', `forloop(1, 92, `dot($1, $2, $3, $4, ', `)')')
126 define(`mult', `output(1, $3)forloop(1, 92, `_$0($1, $2, $3, ', `)')')
127 mult(1, 1, 2)
128 mult(2, 2, 4)
129 mult(1, 4, 5)
130 mult(5, 5, 10)
131 mult(10, 10, 20)
132 mult(20, 20, 40)
133 define(`prod', `+m$1_$2_$3*l$3')
134 define(`part1', eval(forloop(1, 92, `prod(40, 'init`, ', `)')))
135 mult(10, 40, 50)
136 define(`part2', eval(forloop(1, 92, `prod(50, 'init`, ', `)')))
138 ', algo, `sparse', `
139 output(1, `Using sparse matrix lookup, O(n)')
140 define(`_prep', `define(`L$1', quote($3))')
141 foreach(`prep', table)
142 pushdef(`q0', init)define(`c0_'init, 1)
143 define(`iter', `_$0(decr($1), $1)')
144 define(`_iter', `ifdef(`q$1', `bump(q$1, $1, $2)popdef(`q$1')$0($@)')')
145 define(`bump', `_foreach(`_$0(c$2_$1, $3, ', `)', `', L$1)popdef(`c$2_$1')')
146 define(`_bump', `ifdef(`c$2_$3', `define(`c$2_$3', eval(c$2_$3 + $1))',
147 `pushdef(`q$2', $3)define(`c$2_$3', $1)')')
148 define(`_tally', `+c$1_$2*l$2')
149 define(`tally', `eval(0_stack_foreach(`q$1', `_$0($1, ', `)', `t'))')
150 forloop_arg(1, 40, `iter')
151 define(`part1', tally(40))
152 forloop_arg(41, 50, `iter')
153 define(`part2', tally(50))
155 ', `errprintn(`unrecognized algorithm 'algo)m4exit(1)')
157 divert`'part1
158 part2