From 8f91ed0074f09a0487d2d807a515bd68fe42dcf0 Mon Sep 17 00:00:00 2001
From: Tomasz Kramkowski <tk@the-tk.com>
Date: Sat, 11 Dec 2021 23:46:14 +0000
Subject: day 11: nim - now much faster

---
 d11.nim | 58 ++++++++++++++++++++++++++++------------------------------
 1 file changed, 28 insertions(+), 30 deletions(-)

diff --git a/d11.nim b/d11.nim
index 73ddfe3..811ef9f 100644
--- a/d11.nim
+++ b/d11.nim
@@ -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
-- 
cgit v1.2.3-54-g00ecf