day06.nim (4878B)
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 repeat, toSeq 16 17 # Read input file 18 19 let data = stdin.lines().toSeq() 20 let nlines = len(data) 21 let ncols = len(data[0]) 22 23 # Puzzle 1 24 25 func find_start_pos(m: seq[string]): (int, int) = 26 for y in 0 ..< len(m): 27 for x in 0 ..< len(m[y]): 28 if m[y][x] == '^': 29 return (x, y) 30 31 let start_pos = find_start_pos(data) 32 33 type direction = enum north, east, south, west 34 35 func dx(d: direction): int = 36 case d 37 of north: result = 0 38 of east: result = 1 39 of south: result = 0 40 of west: result = -1 41 42 func dy(d: direction): int = 43 case d 44 of north: result = -1 45 of east: result = 0 46 of south: result = 1 47 of west: result = 0 48 49 func dnext(d: direction): direction = 50 case d 51 of north: result = east 52 of east: result = south 53 of south: result = west 54 of west: result = north 55 56 func dprev(d: direction): direction = 57 case d 58 of north: result = west 59 of east: result = north 60 of south: result = east 61 of west: result = south 62 63 proc puzzle1(start_x, start_y: int): int = 64 var 65 visited = repeat(repeat(false, ncols), nlines) 66 x = start_x 67 y = start_y 68 dir = north 69 result = 0 70 while x >= 0 and y >= 0 and y < nlines and x < ncols: 71 if data[y][x] == '#': 72 # backtrack and turn 73 x -= dx(dir) 74 y -= dy(dir) 75 dir = dnext(dir) 76 elif not visited[y][x]: 77 visited[y][x] = true 78 result += 1 79 x += dx(dir) 80 y += dy(dir) 81 82 let result1 = puzzle1(start_pos[0], start_pos[1]) 83 echo "Puzzle 1: ", result1 84 85 # Puzzle 2 86 87 proc backtrack(visited: var array[direction, seq[seq[bool]]], 88 start_x, start_y: int, start_dir: direction): void = 89 var 90 x = start_x 91 y = start_y 92 dir = start_dir 93 94 while x >= 0 and y >= 0 and y < nlines and x < ncols: 95 if data[y][x] == '#': 96 x += dx(dir) 97 y += dy(dir) 98 dir = dprev(dir) 99 100 if visited[dir][y][x]: 101 break 102 103 visited[dir][y][x] = true 104 x -= dx(dir) 105 y -= dy(dir) 106 107 108 proc bad_puzzle2(start_x, start_y: int): int {.used.} = 109 var 110 visited: array[direction, seq[seq[bool]]] 111 bvisited: array[direction, seq[seq[bool]]] 112 x = start_x 113 y = start_y 114 dir = north 115 for d in direction: 116 visited[d] = repeat(repeat(false, ncols), nlines) 117 bvisited[d] = repeat(repeat(false, ncols), nlines) 118 119 backtrack(bvisited, x, y + 1, dir) 120 121 result = 0 122 while x >= 0 and y >= 0 and y < nlines and x < ncols: 123 if data[y][x] == '#': 124 # backtrack and turn 125 x -= dx(dir) 126 y -= dy(dir) 127 dir = dnext(dir) 128 backtrack(bvisited, x, y, dir) 129 130 if not visited[dir][y][x]: 131 visited[dir][y][x] = true 132 bvisited[dir][y][x] = true 133 let nx = x - dx(dir) + dx(dnext(dir)) 134 let ny = y - dy(dir) + dy(dnext(dir)) 135 if nx >= 0 and ny >= 0 and ny < nlines and nx < ncols and bvisited[dnext(dir)][ny][nx]: 136 result += 1 137 138 x += dx(dir) 139 y += dy(dir) 140 141 proc is_looping(start_x, start_y, extra_x, extra_y: int): bool = 142 var 143 visited: array[direction, seq[seq[bool]]] 144 x = start_x 145 y = start_y 146 dir = north 147 for d in direction: 148 visited[d] = repeat(repeat(false, ncols), nlines) 149 150 result = false 151 while x >= 0 and y >= 0 and y < nlines and x < ncols: 152 if data[y][x] == '#' or (x == extra_x and y == extra_y): 153 # backtrack and turn 154 x -= dx(dir) 155 y -= dy(dir) 156 dir = dnext(dir) 157 158 if visited[dir][y][x]: 159 return true 160 161 visited[dir][y][x] = true 162 x += dx(dir) 163 y += dy(dir) 164 165 proc brute_puzzle2(start_x, start_y: int): int = 166 var 167 visited = repeat(repeat(false, ncols), nlines) 168 x = start_x 169 y = start_y 170 dir = north 171 steps = 0 172 173 result = 0 174 visited[start_y][start_x] = true 175 while x >= 0 and y >= 0 and y < nlines and x < ncols: 176 if data[y][x] == '#': 177 # backtrack and turn 178 x -= dx(dir) 179 y -= dy(dir) 180 steps -= 1 181 dir = dnext(dir) 182 elif not visited[y][x]: 183 visited[y][x] = true 184 if is_looping(start_x, start_y, x, y): 185 result += 1 186 187 steps += 1 188 x += dx(dir) 189 y += dy(dir) 190 stdout.write steps, " / ", result1, "\r" 191 192 echo "Puzzle 2: ", brute_puzzle2(start_pos[0], start_pos[1])