day16.nim (3484B)
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 addUnique, concat, mapIt, toSeq, zip 16 from std/tables import `[]`, `[]=`, contains, getOrDefault, initTable, Table 17 18 # Read input file 19 20 let data = stdin.lines().toSeq() 21 22 # Puzzles 23 24 type 25 Direction = enum 26 north, east, south, west 27 Point = tuple 28 x, y: int 29 Node = tuple 30 p: Point 31 dir: Direction 32 PathData = tuple 33 score: int 34 prev: seq[Node] 35 36 func delta(d: Direction): Point = 37 case d 38 of north: (x: 0, y: -1) 39 of south: (x: 0, y: 1) 40 of east: (x: 1, y: 0) 41 of west: (x: -1, y: 0) 42 43 func `+`(a, b: Point): Point = (x: a.x + b.x, y: a.y + b.y) 44 func `[]`(m: seq[string], p: Point): char = m[p.y][p.x] 45 46 func start(d: seq[string], c: char): Node = 47 var found = false 48 for y in 0 ..< len(d): 49 for x in 0 ..< len(d[y]): 50 if d[y][x] == c: 51 assert not found 52 found = true 53 result = (p: (x: x, y: y), dir: east) 54 assert found 55 56 func next(unvisited: seq[Node], path: Table[Node, PathData]): (int, int) = 57 result = (0, path[unvisited[0]].score) 58 for i in 1 ..< len(unvisited): 59 let s = path[unvisited[i]].score 60 if i == 0 or s < result[1]: 61 result = (i, s) 62 63 proc update(unvisited: var seq[Node], path: var Table[Node, PathData], d: seq[string], prev, n: Node, s: int): void = 64 if d[n.p] == '#': 65 return 66 if not path.contains(n) or path[n].score > s: 67 unvisited.addUnique(n) 68 path[n] = (score: s, prev: @[prev]) 69 elif path[n].score == s: 70 path[n].prev.add(prev) 71 72 func search(d: seq[string]): (Table[Node, PathData], int) = 73 var 74 unvisited = @[start(d, 'S')] 75 path = initTable[Node, PathData]() 76 finish = start(d, 'E').p 77 found = false 78 path[unvisited[0]] = (score: 0, prev: @[]) 79 while len(unvisited) > 0: 80 let 81 (i, s) = next(unvisited, path) 82 n = unvisited[i] 83 if found: 84 if s > result[1]: 85 return 86 elif n.p == finish: 87 result = (path, s) 88 found = true 89 unvisited = concat(unvisited[0 ..< i], unvisited[i + 1 ..< len(unvisited)]) 90 update(unvisited, path, d, n, (p: n.p + delta(n.dir), dir: n.dir), s + 1) 91 for dir in Direction: 92 update(unvisited, path, d, n, (p: n.p, dir: dir), s + 1000) 93 assert false 94 95 let (path_data, answer1) = search(data) 96 echo "Puzzle 1: ", answer1 97 98 func answer2(path: Table[Node, PathData], p: Point): int = 99 var 100 visited = initTable[Point, bool]() 101 queue: seq[Node] 102 for d in Direction: 103 let n = (p: p, dir: d) 104 if path.contains(n): 105 queue.add(n) 106 assert len(queue) > 0 107 result = 0 108 while len(queue) > 0: 109 if not visited.contains(queue[0].p): 110 visited[queue[0].p] = true 111 result += 1 112 queue = concat(queue[1 .. ^1], path[queue[0]].prev) 113 114 echo "Puzzle 2: ", answer2(path_data, start(data, 'E').p)