day12.nim (3379B)
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 foldl, mapIt, toSeq 16 from std/tables import `[]=`, getOrDefault, initTable, pairs, Table, values 17 18 # Read input file 19 20 let data = stdin.lines().toSeq() 21 22 # Puzzle 1 23 24 func reg(d: seq[string]): seq[seq[int]] = 25 let dirs = @[(-1, 0), (1, 0), (0, -1), (0, 1)] 26 result = d.mapIt(it.mapIt(0 * ord(it))) 27 var n_reg = 0 28 for start_y in 0 ..< len(d): 29 for start_x in 0 ..< len(d[start_y]): 30 if result[start_y][start_x] > 0: 31 continue 32 n_reg += 1 33 result[start_y][start_x] = n_reg 34 var queue = dirs.mapIt((start_x + it[0], start_y + it[1])) 35 while len(queue) > 0: 36 let 37 x = queue[0][0] 38 y = queue[0][1] 39 queue = queue[1 .. ^1] 40 if y < 0 or y >= len(d) or x < 0 or x >= len(d[y]) or result[y][x] > 0 or d[y][x] != d[start_y][start_x]: 41 continue 42 result[y][x] = n_reg 43 for d in dirs: 44 queue.add((x + d[0], y + d[1])) 45 46 proc cost1(d: seq[seq[int]], n: int): int = 47 let dirs = @[(-1, 0), (1, 0), (0, -1), (0, 1)] 48 var area = 0 49 var peri = 0 50 for y in 0 ..< len(d): 51 for x in 0 ..< len(d[y]): 52 if d[y][x] != n: 53 continue 54 area += 1 55 for dir in dirs: 56 let 57 dx = x + dir[0] 58 dy = y + dir[1] 59 if dy < 0 or dy >= len(d) or dx < 0 or dx >= len(d[dy]) or d[dy][dx] != n: 60 peri += 1 61 result = area * peri 62 # echo n, ": ", area, " * ", peri 63 64 let 65 regions = reg(data) 66 n_regs = regions.mapIt(max(it)).max() 67 68 echo "Puzzle 1: ", (1 .. n_regs).mapIt(cost1(regions, it)).foldl(a + b) 69 70 # Puzzle 2 71 72 proc inc(t: var Table[(int, int), int], x, y: int): void = 73 t[(x, y)] = t.getOrDefault((x, y), 0) + 1 74 75 proc cost2(d: seq[seq[int]], n: int): int = 76 let dirs = @[(-1, 0), (1, 0), (0, -1), (0, 1)] 77 var area = 0 78 var h_corners = initTable[(int, int), int]() 79 var v_corners = initTable[(int, int), int]() 80 for y in 0 ..< len(d): 81 for x in 0 ..< len(d[y]): 82 if d[y][x] != n: 83 continue 84 area += 1 85 for dir in dirs: 86 let 87 dx = x + dir[0] 88 dy = y + dir[1] 89 if dy < 0 or dy >= len(d) or dx < 0 or dx >= len(d[dy]) or d[dy][dx] != n: 90 if dir[0] == 0: 91 v_corners.inc(x, max(y, dy)) 92 v_corners.inc(x + 1, max(y, dy)) 93 if dir[1] == 0: 94 h_corners.inc(max(x, dx), y) 95 h_corners.inc(max(x, dx), y + 1) 96 var corners = 0 97 for k, v in h_corners: 98 if v_corners.getOrDefault(k, 0) == v: 99 corners += v 100 result = area * corners 101 # echo n, ": ", area, " * ", corners 102 103 echo "Puzzle 2: ", (1 .. n_regs).mapIt(cost2(regions, it)).foldl(a + b)