diff options
| -rw-r--r-- | d11.nim | 58 |
1 files changed, 28 insertions, 30 deletions
@@ -1,4 +1,4 @@ -import std/os, std/sugar, std/strutils, std/sequtils +import std/os, std/sugar, std/sequtils, std/deques type OctoState = Natural @@ -20,45 +20,43 @@ proc print_map(map: Map) = stdout.write(('0'.ord + map.map[x + map.width * y]).char) stdout.write('\n') +iterator neighbours(map: Map, i: int): int = + let + x = i mod map.width + y = i div map.width + for dy in countup(-1, 1): + for dx in countup(-1, 1): + if dy == 0 and dx == 0: continue + let + x = x + dx + y = y + dy + if x < 0 or x >= map.width: continue + if y < 0 or y >= map.height: continue + yield x + map.width * y + proc solve(map: Map): tuple[part1, part2: int] = var current = map.map flashed = new_seq[bool](current.len) - flash = new_seq[bool](current.len) + pending = init_deque[int](current.len) flashes = 0 for step in 1..1000: - #print_map((current, map.width, map.height)) - #echo "" flashed.apply(proc(_: bool): bool = false) - current.apply(proc(s: OctoState): OctoState = s + 1) - while true: - var any = false - flash.apply(proc(_: bool): bool = false) - for i, s in current: - if flashed[i] or s <= 9: continue - flashed[i] = true - flash[i] = true - any = true - if not any: break - for i, s in flash: - if not s: continue - let - x = i mod map.width - y = i div map.width - for dy in countup(-1, 1): - for dx in countup(-1, 1): - if dx == 0 and dy == 0: continue - let - x = x + dx - y = y + dy - if x < 0 or x >= map.width: continue - if y < 0 or y >= map.height: continue - inc current[x + map.width * y] + for i, s in current.mpairs: + inc s + if s > 9: pending.add_first(i) var sum = 0 - for i, s in flashed: - if not s: continue + while pending.len() > 0: + let i = pending.pop_last() + if flashed[i]: continue + flashed[i] = true current[i] = 0 inc sum + for i in neighbours(map, i): + if flashed[i]: continue + inc current[i] + if current[i] > 9: + pending.add_first(i) flashes += sum if step == 100: result.part1 = flashes |