day18.nim (3322B)
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, map, mapIt, newSeqWith, toSeq 16 from std/strutils import split, parseInt, repeat 17 from std/tables import `[]`, `[]=`, contains, getOrDefault, initTable, 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 proc `[]=`(m: var seq[string], p: Point, c: char): void = m[p.y][p.x] = c 28 29 func seq_to_point(s: seq[int]): Point = 30 assert len(s) == 2 31 result = (x: s[0], y: s[1]) 32 33 let 34 data = stdin.lines().toSeq().mapIt(seq_to_point(it.split(",").map(parseInt))) 35 xmax = max(data.mapIt(it[0])) 36 ymax = max(data.mapIt(it[1])) 37 38 # Puzzle 1 39 40 func next(unvisited: seq[Point], scores: Table[Point, int]): (int, int) = 41 result = (0, scores[unvisited[0]]) 42 for i in 1 ..< len(unvisited): 43 let s = scores[unvisited[i]] 44 if i == 0 or s < result[1]: 45 result = (i, s) 46 47 proc update(unvisited: var seq[Point], scores: var Table[Point, int], d: seq[string], p: Point, s: int): void = 48 if p.x < 0 or p.y < 0 or p.y >= len(d) or p.x >= len(d[p.y]) or d[p] == '#': 49 return 50 if not scores.contains(p) or scores[p] > s: 51 unvisited.addUnique(p) 52 scores[p] = s 53 54 func to_map(blocks: seq[Point], xmax, ymax: int): seq[string] = 55 result = newSeqWith(ymax + 1, repeat('.', xmax + 1)) 56 for b in blocks: 57 result[b] = '#' 58 59 func answer1(blocks: seq[Point], xmax, ymax: int): int = 60 let m = to_map(blocks, xmax, ymax) 61 var 62 scores = initTable[Point, int]() 63 unvisited = @[(x: 0, y: 0)] 64 scores[unvisited[0]] = 0 65 while len(unvisited) > 0: 66 let 67 (i, s) = next(unvisited, scores) 68 p = unvisited[i] 69 if p.x == xmax and p.y == ymax: 70 return s 71 unvisited = concat(unvisited[0 ..< i], unvisited[i + 1 .. ^1]) 72 update(unvisited, scores, m, (x: p.x + 1, y: p.y), s + 1) 73 update(unvisited, scores, m, (x: p.x - 1, y: p.y), s + 1) 74 update(unvisited, scores, m, (x: p.x, y: p.y + 1), s + 1) 75 update(unvisited, scores, m, (x: p.x, y: p.y - 1), s + 1) 76 return -1 77 78 echo "Puzzle 1: ", answer1(data, xmax, ymax) 79 80 # Puzzle 2 81 82 var 83 bottom = 0 84 top = len(data) - 1 85 86 if answer1(data[0 .. bottom], xmax, ymax) >= 0 and answer1(data[0 .. top], xmax, ymax) < 0: 87 # echo "starting with ", bottom, " .. ", top 88 while top - bottom >= 2: 89 let 90 mid = bottom + (top - bottom) div 2 91 s = answer1(data[0 .. mid], xmax, ymax) 92 # echo mid, ": ", s 93 if s >= 0: 94 bottom = mid 95 else: 96 top = mid 97 echo "Puzzle 2: ", data[top].x, ",", data[top].y, " (", top, ")"