day21.nim (7897B)
1 # Copyright (c) 2024, Natacha Porté 2 # 3 # Permission to use, copy, modify, and distribute this software for any 4 # purpose with or without fee is hereby granted, provided that the above 5 # copyright notice and this permission notice appear in all copies. 6 # 7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 from std/sequtils import concat, filterIt, foldl, map, mapIt, toSeq, zip 16 from std/strutils import parseInt, repeat 17 from std/tables import `[]`, `[]=`, hasKey, Table, toTable, pairs, keys 18 19 # Read input file 20 21 type 22 Point = tuple 23 x, y: int 24 25 let 26 data = stdin.lines().toSeq() 27 num_pad = { 28 '7': (x: 0, y: 0), 29 '8': (x: 1, y: 0), 30 '9': (x: 2, y: 0), 31 '4': (x: 0, y: 1), 32 '5': (x: 1, y: 1), 33 '6': (x: 2, y: 1), 34 '1': (x: 0, y: 2), 35 '2': (x: 1, y: 2), 36 '3': (x: 2, y: 2), 37 '*': (x: 0, y: 3), 38 '0': (x: 1, y: 3), 39 'A': (x: 2, y: 3) 40 }.toTable 41 dir_pad = { 42 '*': (x: 0, y: 0), 43 '^': (x: 1, y: 0), 44 'A': (x: 2, y: 0), 45 '<': (x: 0, y: 1), 46 'v': (x: 1, y: 1), 47 '>': (x: 2, y: 1) 48 }.toTable 49 50 # Puzzle 1 51 52 func minimize(s: seq[string]): seq[string] = 53 let l = min(s.mapIt(len(it))) 54 result = s.filterIt(len(it) == l) 55 56 func cat4(a, b, c, d: string): string = a & b & c & d 57 58 proc cmd(s: string, pad: Table[char, Point]): seq[string] = 59 var p = pad['A'] 60 result = @[""] 61 for d in s.mapIt(pad[it]): 62 var h, v: string 63 if d.y > p.y: 64 v = repeat('v', d.y - p.y) 65 if d.y < p.y: 66 v = repeat('^', p.y - d.y) 67 if d.x > p.x: 68 h = repeat('>', d.x - p.x) 69 if d.x < p.x: 70 h = repeat('<', p.x - d.x) 71 72 if h == "" or v == "" or pad['*'] == (x: p.x, y: d.y): 73 result = result.mapIt(cat4(it, h, v, "A")) 74 elif pad['*'] == (x: d.x, y: p.y): 75 result = result.mapIt(cat4(it, v, h, "A")) 76 else: 77 result = concat(result.mapIt(cat4(it, h, v, "A")), result.mapIt(cat4(it, v, h, "A"))) 78 79 p = d 80 81 result = minimize(result) 82 83 proc cmd_seq(s: seq[string], pad: Table[char, Point]): seq[string] = 84 for c in s: 85 result = minimize(concat(result, cmd(c, pad))) 86 87 proc puzzle1(s: string): int = 88 let 89 s1 = cmd(s, num_pad) 90 s2 = cmd_seq(s1, dir_pad) 91 s3 = cmd_seq(s2, dir_pad) 92 n = parseInt(s[0 .. ^2]) 93 result = len(s3[0]) * n 94 95 echo "Puzzle 1: ", data.map(puzzle1).foldl(a + b) 96 97 # Puzzle 2 98 # 154115708116294 is too low 99 100 var memo: Table[(char, char, int), int] 101 102 proc base_steps(start, dest: char, depth: int, pad: Table[char, Point]): int 103 104 proc steps(start, dest: char, depth: int): int = 105 if start == dest: 106 return 1 107 elif memo.hasKey((start, dest, depth)): 108 return memo[(start, dest, depth)] 109 result = base_steps(start, dest, depth, dir_pad) 110 # echo repeat(" ", depth), "storing(", start, ", ", dest, ", ", depth, "): ", result 111 memo[(start, dest, depth)] = result 112 113 proc base_steps(start, dest: char, depth: int, pad: Table[char, Point]): int = 114 let 115 ps = pad[start] 116 pd = pad[dest] 117 cx = if ps.x < pd.x: '>' elif ps.x > pd.x: '<' else: '.' 118 cy = if ps.y < pd.y: 'v' elif ps.y > pd.y: '^' else: '.' 119 dx = abs (ps.x - pd.x) 120 dy = abs (ps.y - pd.y) 121 if depth == 0: 122 return dx + dy + 1 123 124 if dx == 0: 125 assert dy > 0 126 result = steps('A', cy, depth - 1) + (dy-1) + steps(cy, 'A', depth - 1) 127 elif dy == 0: 128 assert dx > 0 129 result = steps('A', cx, depth - 1) + (dx-1) + steps(cx, 'A', depth - 1) 130 elif pad['*'] == (x: pd.x, y: ps.y): 131 result = steps('A', cy, depth - 1) + (dy-1) + steps(cy, cx, depth - 1) + (dx-1) + steps(cx, 'A', depth - 1) 132 elif pad['*'] == (x: ps.x, y: pd.y): 133 result = steps('A', cx, depth - 1) + (dx-1) + steps(cx, cy, depth - 1) + (dy-1) + steps(cy, 'A', depth - 1) 134 else: 135 let 136 rvh = steps('A', cy, depth - 1) + (dy-1) + steps(cy, cx, depth - 1) + (dx-1) + steps(cx, 'A', depth - 1) 137 rhv = steps('A', cx, depth - 1) + (dx-1) + steps(cx, cy, depth - 1) + (dy-1) + steps(cy, 'A', depth - 1) 138 result = min(rvh, rhv) 139 140 proc full_steps(s: string, depth: int): int = 141 for (s,d) in zip("A" & s[0 .. ^2], s): 142 result += base_steps(s, d, depth, num_pad) 143 144 proc puzzle2(s: string, depth: int): int = 145 full_steps(s, depth) * parseInt(s[0 .. ^2]) 146 147 for cmd in data: 148 # echo cmd, ": ", full_steps(cmd, 2) 149 assert puzzle2(cmd, 2) == puzzle1(cmd) 150 151 echo "Puzzle 2: ", data.mapIt(puzzle2(it, 25)).foldl(a + b) 152 153 var debug_memo: Table[(char, char, int), string] 154 155 proc debug_base_steps(start, dest: char, depth: int, pad: Table[char, Point]): string 156 157 proc debug_steps(start, dest: char, depth: int): string = 158 if start == dest: 159 return "A" 160 elif debug_memo.hasKey((start, dest, depth)): 161 return debug_memo[(start, dest, depth)] 162 result = debug_base_steps(start, dest, depth, dir_pad) 163 echo repeat(" ", 4 - depth), "storing(", start, ", ", dest, ", ", depth, "): ", result 164 debug_memo[(start, dest, depth)] = result 165 166 proc debug_base_steps(start, dest: char, depth: int, pad: Table[char, Point]): string = 167 let 168 ps = pad[start] 169 pd = pad[dest] 170 cx = if ps.x < pd.x: '>' elif ps.x > pd.x: '<' else: '.' 171 cy = if ps.y < pd.y: 'v' elif ps.y > pd.y: '^' else: '.' 172 dx = abs (ps.x - pd.x) 173 dy = abs (ps.y - pd.y) 174 if depth == 0: 175 if pad['*'] == (x: pd.x, y: ps.y): 176 return repeat(cy, dy) & repeat(cx, dx) & "A" 177 else: 178 return repeat(cx, dx) & repeat(cy, dy) & "A" 179 180 if dx == 0: 181 assert dy > 0 182 echo repeat(" ", 4 - depth), "expanding(", start, ", ", dest, ", ", depth, "): \"", repeat(cy, dy), "A\"" 183 result = debug_steps('A', cy, depth - 1) & repeat('A', dy-1) & debug_steps(cy, 'A', depth - 1) 184 elif dy == 0: 185 assert dx > 0 186 echo repeat(" ", 4 - depth), "expanding(", start, ", ", dest, ", ", depth, "): \"", repeat(cx, dx), "A\"" 187 result = debug_steps('A', cx, depth - 1) & repeat('A', dx-1) & debug_steps(cx, 'A', depth - 1) 188 elif pad['*'] == (x: pd.x, y: ps.y): 189 echo repeat(" ", 4 - depth), "expanding(", start, ", ", dest, ", ", depth, "): \"", repeat(cy, dy), repeat(cx, dx), "A\"" 190 result = debug_steps('A', cy, depth - 1) & repeat('A', dy-1) & debug_steps(cy, cx, depth - 1) & repeat('A', dx-1) & debug_steps(cx, 'A', depth - 1) 191 elif pad['*'] == (x: ps.x, y: pd.y): 192 echo repeat(" ", 4 - depth), "expanding(", start, ", ", dest, ", ", depth, "): \"", repeat(cx, dx), repeat(cy, dy), "A\"" 193 result = debug_steps('A', cx, depth - 1) & repeat('A', dx-1) & debug_steps(cx, cy, depth - 1) & repeat('A', dy-1) & debug_steps(cy, 'A', depth - 1) 194 else: 195 echo repeat(" ", 4 - depth), "expanding(", start, ", ", dest, ", ", depth, "): \"", repeat(cx, dx), repeat(cy, dy), "A\" and \"", repeat(cy, dy), repeat(cx, dx), "A\"" 196 let 197 rvh = debug_steps('A', cy, depth - 1) & repeat('A', dy-1) & debug_steps(cy, cx, depth - 1) & repeat('A', dx-1) & debug_steps(cx, 'A', depth - 1) 198 rhv = debug_steps('A', cx, depth - 1) & repeat('A', dx-1) & debug_steps(cx, cy, depth - 1) & repeat('A', dy-1) & debug_steps(cy, 'A', depth - 1) 199 if len(rvh) < len(rvh): 200 echo repeat(" ", 4 - depth), "↳ choosing \"", repeat(cy, dy), repeat(cx, dx), "A\" (", len(rvh), " over ", len(rhv), ")" 201 result = rvh 202 else: 203 echo repeat(" ", 4 - depth), "↳ choosing \"", repeat(cx, dx), repeat(cy, dy), "A\" (", len(rhv), " over ", len(rvh), ")" 204 result = rhv 205 206 proc debug_full_steps(s: string, depth: int): string = 207 for (s,d) in zip("A" & s[0 .. ^2], s): 208 result &= debug_base_steps(s, d, depth, num_pad) 209 210 # for cmd in data: 211 # echo cmd, ": ", debug_full_steps(cmd, 2)