Solve 2024 day 18 part 2

sim642 · sim642 · commit 5a0f9574fc0e · 2024-12-18T08:08:54.000+02:00
diff --git a/src/main/scala/eu/sim642/adventofcode2024/Day18.scala b/src/main/scala/eu/sim642/adventofcode2024/Day18.scala
@@ -26,6 +26,35 @@ object Day18 {
     BFS.search(graphSearch).target.get._2
   }
 
+  // TODO: deduplicate
+  def exitSteps2(bytes: Seq[Pos], max: Pos = Pos(70, 70), after: Int = 1024): Boolean = {
+    val fallenBytes = bytes.take(after).toSet
+
+    val graphSearch = new GraphSearch[Pos] with UnitNeighbors[Pos] with TargetNode[Pos] {
+      override val startNode: Pos = Pos.zero
+
+      override def unitNeighbors(pos: Pos): IterableOnce[Pos] = {
+        for {
+          offset <- Pos.axisOffsets
+          newPos = pos + offset
+          if Pos.zero <= newPos && newPos <= max
+          if !fallenBytes(newPos)
+        } yield newPos
+      }
+
+      override val targetNode: Pos = max
+    }
+
+    BFS.search(graphSearch).target.isDefined
+  }
+
+  def findBlockingByte(bytes: Seq[Pos], max: Pos = Pos(70, 70)): String = {
+    // TODO: optimize (~5.7s)
+    val after = (0 to bytes.size).find(after => !exitSteps2(bytes, max, after)).get
+    val afterPos = bytes(after - 1)
+    s"${afterPos.x},${afterPos.y}"
+  }
+
   def parseByte(s: String): Pos = s match {
     case s"$x,$y" => Pos(x.toInt, y.toInt)
   }
@@ -36,5 +65,6 @@ object Day18 {
 
   def main(args: Array[String]): Unit = {
     println(exitSteps(parseBytes(input)))
+    println(findBlockingByte(parseBytes(input)))
   }
 }
diff --git a/src/test/scala/eu/sim642/adventofcode2024/Day18Test.scala b/src/test/scala/eu/sim642/adventofcode2024/Day18Test.scala
@@ -40,4 +40,12 @@ class Day18Test extends AnyFunSuite {
   test("Part 1 input answer") {
     assert(exitSteps(parseBytes(input)) == 304)
   }
+
+  test("Part 2 examples") {
+    assert(findBlockingByte(parseBytes(exampleInput), Pos(6, 6)) == "6,1")
+  }
+
+  ignore("Part 2 input answer") { // TODO: optimize (~5.7s)
+    assert(findBlockingByte(parseBytes(input)) == "50,28")
+  }
 }

Original file line number	Diff line number	Diff line change
`@@ -40,4 +40,12 @@ class Day18Test extends AnyFunSuite {`
`40`	`40`	`test("Part 1 input answer") {`
`41`	`41`	`assert(exitSteps(parseBytes(input)) == 304)`
`42`	`42`	`}`
	`43`	`+`
	`44`	`+ test("Part 2 examples") {`
	`45`	`+ assert(findBlockingByte(parseBytes(exampleInput), Pos(6, 6)) == "6,1")`
	`46`	`+ }`
	`47`	`+`
	`48`	`+ ignore("Part 2 input answer") { // TODO: optimize (~5.7s)`
	`49`	`+ assert(findBlockingByte(parseBytes(input)) == "50,28")`
	`50`	`+ }`
`43`	`51`	`}`