day20.nim (3412B)
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/algorithm import sorted 16 from std/sequtils import toSeq 17 from std/tables import `[]`, `[]=`, getOrDefault, initTable, keys, pairs, Table 18 19 # Read input file 20 21 type 22 Point = tuple 23 x, y: int 24 25 func `+`(a, b: Point): Point = (x: a.x + b.x, y: a.y + b.y) 26 func `[]`(m: seq[string], p: Point): char = m[p.y][p.x] 27 28 func neighbors(m: seq[string], p: Point): seq[Point] = 29 let s = @[(x: p.x + 1, y: p.y), (x: p.x - 1, y: p.y), (x: p.x, y: p.y - 1), (x: p.x, y: p.y + 1)] 30 for n in s: 31 if n.x >= 0 and n.y >= 0 and n.y < len(m) and n.x < len(m[n.y]) and m[n] != '#': 32 result.add(n) 33 34 func race_path(m: seq[string]): seq[Point] = 35 for y in 0 ..< len(m): 36 for x in 0 ..< len(m[y]): 37 if m[y][x] == 'S': 38 assert len(result) == 0 39 result.add((x: x, y: y)) 40 assert len(neighbors(m, result[0])) == 1 41 result.add(neighbors(m, result[0])[0]) 42 43 while m[result[^1]] != 'E': 44 let n = neighbors(m, result[^1]) 45 assert len(n) == 2 46 if n[0] == result[^2]: 47 result.add(n[1]) 48 else: 49 assert n[1] == result[^2] 50 result.add(n[0]) 51 52 let 53 data = stdin.lines().toSeq() 54 path = race_path(data) 55 56 # Puzzle 1 57 58 func count_shortcuts1(s: seq[Point]): Table[int, int] = 59 for start in 0 .. len(s) - 4: 60 for dest in start + 3 .. len(s) - 1: 61 if (s[start].x == s[dest].x and abs(s[start].y - s[dest].y) == 2) or (s[start].y == s[dest].y and abs(s[start].x - s[dest].x) == 2): 62 let k = dest - start - 2 63 result[k] = result.getOrDefault(k, 0) + 1 64 65 proc puzzle1(s: seq[Point]): void = 66 let shortcuts = count_shortcuts1(path) 67 var sum = 0 68 69 for k, v in shortcuts.pairs: 70 if k >= 100: 71 sum += v 72 73 if sum == 0: 74 echo "Puzzle 1:" 75 for k in shortcuts.keys.toSeq.sorted: 76 if shortcuts[k] >= 2: 77 echo " - There are ", shortcuts[k], " cheats saving ", k, " ps" 78 else: 79 echo " - There is one cheat saving ", k, " ps" 80 else: 81 echo "Puzzle 1: ", sum 82 83 puzzle1(path) 84 85 # Puzzle 2 86 87 func count_shortcuts2(s: seq[Point]): Table[int, int] = 88 for start in 0 .. len(s) - 4: 89 for dest in start + 3 .. len(s) - 1: 90 let 91 d = abs(s[start].x - s[dest].x) + abs(s[start].y - s[dest].y) 92 k = dest - start - d 93 if d <= 20 and k > 0: 94 result[k] = result.getOrDefault(k, 0) + 1 95 96 proc puzzle2(s: seq[Point]): void = 97 let shortcuts = count_shortcuts2(path) 98 var sum = 0 99 100 for k, v in shortcuts.pairs: 101 if k >= 100: 102 sum += v 103 104 if sum == 0: 105 echo "Puzzle 2:" 106 for k in shortcuts.keys.toSeq.sorted: 107 if k >= 50: 108 echo " - There are ", shortcuts[k], " cheats saving ", k, " ps" 109 else: 110 echo "Puzzle 2: ", sum 111 112 puzzle2(path)