day14.nim (3257B)
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/math import euclMod, lcm 16 from std/sequtils import allIt, foldl, map, mapIt, newSeqWith, toSeq 17 from std/strutils import join, parseInt, split 18 19 # Read input file 20 21 type 22 Point = tuple 23 x, y: int 24 Robot = tuple 25 p, v: Point 26 27 func process_line(s: string): Robot = 28 let h = s.split(" ") 29 assert len(h) == 2 30 assert h[0][0 .. 1] == "p=" 31 assert h[1][0 .. 1] == "v=" 32 let 33 p1 = h[0][2 .. ^1].split(",") 34 p2 = h[1][2 .. ^1].split(",") 35 assert len(p1) == 2 36 assert len(p2) == 2 37 result = (p: (x: parseInt(p1[0]), y: parseInt(p1[1])), v: (x: parseInt(p2[0]), y: parseInt(p2[1]))) 38 39 let 40 data = stdin.lines().toSeq().map(process_line) 41 xlen = max(data.mapIt(it.p.x)) + 1 42 ylen = max(data.mapIt(it.p.y)) + 1 43 44 # Puzzle 1 45 46 func forward(r: Robot, t, xmod, ymod: int): Robot = 47 (p: (x: euclMod(r.p.x + t * r.v.x, xmod), y: euclMod(r.p.y + t * r.v.y, ymod)), v: r.v) 48 49 func safety_factor(s: seq[Robot], xmod, ymod: int): int = 50 assert xmod mod 2 == 1 51 assert ymod mod 2 == 1 52 let 53 hx = (xmod - 1) div 2 54 hy = (ymod - 1) div 2 55 var q = @[0, 0, 0, 0] 56 for r in s: 57 if r.p.y < hy: 58 if r.p.x < hx: 59 q[0] += 1 60 elif r.p.x > hx: 61 q[1] += 1 62 elif r.p.y > hy: 63 if r.p.x < hx: 64 q[2] += 1 65 elif r.p.x > hx: 66 q[3] += 1 67 result = q.foldl(a * b) 68 69 echo "Puzzle 1: ", data.mapIt(forward(it, 100, xlen, ylen)).safety_factor(xlen, ylen) 70 71 # Puzzle 2 72 73 func display_char(i: int): char = 74 case i 75 of 0: 76 result = '.' 77 of 1 .. 9: 78 result = ($i)[0] 79 else: 80 result = '*' 81 82 proc display(s: seq[Robot], xmod, ymod: int): void = 83 var map = newSeqWith(ymod, newSeqWith(xmod, 0)) 84 for r in s: 85 map[r.p.y][r.p.x] += 1 86 for line in map: 87 echo line.map(display_char).join() 88 89 proc is_tree(s: seq[Robot], xmod, ymod: int): bool = 90 assert xmod mod 2 == 1 91 assert ymod mod 2 == 1 92 # use a horizontal segment as a proxy for tree-likeness 93 let line_size = 11 94 var map = newSeqWith(ymod, newSeqWith(xmod, 0)) 95 for r in s: 96 map[r.p.y][r.p.x] += 1 97 for y in 0 ..< ymod: 98 for x in 0 .. xmod - line_size - 1: 99 if map[y][x ..< x + line_size].allIt(it > 0): 100 for line in map: 101 echo line.map(display_char).join() 102 return true 103 104 proc find_tree(s0: seq[Robot], xmod, ymod: int): int = 105 var s = s0 106 result = 0 107 while not is_tree(s, xmod, ymod): 108 s = s.mapIt(forward(it, 1, xmod, ymod)) 109 result += 1 110 if result > lcm(xmod, ymod): 111 return -1 112 113 echo "Puzzle 2: ", find_tree(data, xlen, ylen)