aoc2024

commit ddaa88f98f745cf6df86ceca1ccc03511b5856f5
parent f6823d927c5a160a5db961ab01269cfa3b482a60
Author: Martin Ashby <martin@ashbysoft.com>
Date:   Fri, 13 Dec 2024 23:27:38 +0000

Day6 pt2, but it's wrong and extremely slow

Diffstat:
M
src/main/scala/Day6.scala
 | 
92
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------
M
src/main/scala/Main.scala
 | 
4
++--

2 files changed, 76 insertions(+), 20 deletions(-)
diff --git a/src/main/scala/Day6.scala b/src/main/scala/Day6.scala
@@ -5,33 +5,89 @@ def day6_pt1(input: Iterator[String]): Int =
     val grid = updated(lst, pos, '.')
     do_follow(grid, pos, '^')
 
+@tailrec()
+def do_follow(grid: List[String], pos: (Int,Int), dir: Char): Int =
+    val grid2 = updated(grid, pos, 'X')
+    val pos2 = next_pos(pos, dir)
+    val (x2, y2) = pos2
+    if (oob(grid2, pos2)) {
+        return grid2.map(line => line.count(ch => ch == 'X')).sum
+    }
+    if (grid_at(grid2, pos2) == '#') {
+        val dir2 = next_dir(dir)
+        do_follow(grid2, pos, dir2)
+    } else {
+        do_follow(grid2, pos2, dir)
+    }
 
-def updated(grid: List[String], pos: (Int,Int), replacement: Char): List[String] =
-    val (x, y) = pos
-    return grid.updated(y, grid(y).updated(x, replacement))    
+def day6_pt2(input: Iterator[String]): Int =
+    val lst = input.toList
+    val pos = lst.zipWithIndex.find((s, y) => s.contains("^")).map((s, y) => (s.indexOf('^'), y)).get
+    val grid = updated(lst, pos, '.')
+    do_follow2(grid, pos, '^', List(), Set())
+
+@tailrec()
+def do_follow2(grid: List[String], pos: (Int,Int), dir: Char, hist: List[((Int,Int), Char)], cand: Set[(Int,Int)]): Int =
+    val hist2 = hist.appended((pos, dir))
+    val pos2 = next_pos(pos, dir)
+    if (oob(grid, pos2)) {
+        println(cand)
+        return cand.size
+    } 
+    if (grid_at(grid, pos2) == '#') {
+        do_follow2(grid, pos, next_dir(dir), hist2, cand)
+    } else {
+        // Test if there _was_ a block at pos2; would it result in a cycle?
+        val dir_spec = next_dir(dir)
+        val pos_spec = next_pos(pos2, dir_spec)
+        val cand2 = if (!oob(grid, pos_spec) && grid_at(grid, pos_spec) != '#' && do_follow3(grid, pos_spec, dir_spec, hist2)) {
+            cand + pos2
+        } else {
+            cand
+        }
+        do_follow2(grid, pos2, dir, hist2, cand2)
+    }
+
+@tailrec()
+def do_follow3(grid: List[String], pos: (Int,Int), dir: Char, hist: List[((Int,Int), Char)]): Boolean =
+    val pos2 = next_pos(pos, dir)
+    if (oob(grid, pos2)) {
+        false
+    } else if (hist.contains(pos2, dir)) {
+        true
+    } else {
+        val hist2 = hist.appended((pos2, dir))
+        if (grid_at(grid, pos2) == '#') {
+            do_follow3(grid, pos, next_dir(dir), hist2)
+        } else {
+            do_follow3(grid, pos2, dir, hist2)
+        }
+    }
 
 // def print(grid: List[String]): Unit =
 //     grid.foreach(line => println(line))
 
-@tailrec()
-def do_follow(grid: List[String], pos: (Int,Int), dir: Char): Int =
-    val grid2 = updated(grid, pos, 'X')
-    val pos2 = dir match
+def grid_at(grid: List[String], pos: (Int, Int)): Char =
+    grid(pos(1)).charAt(pos(0))
+
+def updated(grid: List[String], pos: (Int,Int), replacement: Char): List[String] =
+    val (x, y) = pos
+    return grid.updated(y, grid(y).updated(x, replacement))    
+
+def next_pos(pos: (Int,Int), dir: Char): (Int,Int) =
+    dir match
         case '^' => (pos(0), pos(1)-1)
         case '>' => (pos(0)+1, pos(1))
         case 'v' => (pos(0), pos(1)+1)
         case '<' => (pos(0)-1, pos(1))
-    val (x2, y2) = pos2
-    if (x2 < 0 || y2 < 0 || x2 >= grid(0).size || y2 >= grid.size) {
-        return grid2.map(line => line.count(ch => ch == 'X')).sum
-    }
-    if (grid2(pos2(1)).charAt(pos2(0)) == '#') {
-        val dir2 = dir match
+
+def next_dir(dir: Char): Char =
+    dir match
             case '^' => '>'
             case '>' => 'v'
             case 'v' => '<'
             case '<' => '^'
-        do_follow(grid2, pos, dir2)
-    } else {
-        do_follow(grid2, pos2, dir)
-    }
-\ No newline at end of file
+
+def oob(grid: List[String], pos: (Int,Int)): Boolean =
+    val (x, y) = pos
+    x < 0 || y < 0 || x >= grid(0).size || y >= grid.size
+\ No newline at end of file
diff --git a/src/main/scala/Main.scala b/src/main/scala/Main.scala
@@ -1,2 +1,2 @@
 @main def run(): Unit = 
-  println(day6_pt1(scala.io.Source.fromFile("day6.txt").getLines()))
-\ No newline at end of file
+  println(day6_pt2(scala.io.Source.fromFile("day6.txt").getLines()))
+\ No newline at end of file