Add optimized via pair solution to 2025 day 11

sim642 · sim642 · commit da0c8cc8a286 · 2025-12-11T20:45:26.000+02:00
diff --git a/src/main/scala/eu/sim642/adventofcode2025/Day11.scala b/src/main/scala/eu/sim642/adventofcode2025/Day11.scala
@@ -59,6 +59,45 @@ object Day11 {
     override object Part2 extends ViaMapPartSolution with Part2Devices
   }
 
+  /**
+   * Optimized version of [[ViaMapSolution]], which only keeps the largest key pair from the mapping.
+   * Others are useless for passing all the vias.
+   */
+  object ViaPairSolution extends Solution {
+    trait ViaPairPartSolution extends PartSolution {
+      override def countPaths(devices: Devices): Long = {
+        val memo = mutable.Map.empty[Device, (Set[Device], Long)]
+
+        def helper(device: Device): (Set[Device], Long) = {
+          memo.getOrElseUpdate(device, {
+            val deviceVia = via.intersect(Set(device))
+            if (device == to)
+              deviceVia -> 1
+            else {
+              val (a, b) = devices(device).map(helper).foldLeft(Set.empty[Device] -> 0L)({ case (a@(accVia, acc), n@(newVia, newCount)) =>
+                if (accVia == newVia)
+                  accVia -> (acc + newCount)
+                else if (accVia subsetOf newVia)
+                  n
+                else if (newVia subsetOf accVia)
+                  a
+                else
+                  throw new IllegalStateException("")
+              })
+              a.union(deviceVia) -> b
+            }
+          })
+        }
+
+        helper(from)._2
+      }
+    }
+
+    override object Part1 extends ViaPairPartSolution with Part1Devices
+
+    override object Part2 extends ViaPairPartSolution with Part2Devices
+  }
+
   /**
    * Solution, which tries all permutations of vias and counts each one by multiplying adjacent steps.
    */
diff --git a/src/test/scala/eu/sim642/adventofcode2025/Day11Test.scala b/src/test/scala/eu/sim642/adventofcode2025/Day11Test.scala
@@ -7,6 +7,7 @@ import org.scalatest.funsuite.AnyFunSuite
 
 class Day11Test extends Suites(
   new ViaMapSolutionTest,
+  new ViaPairSolutionTest,
   new PermutationSolutionTest,
 )
 
@@ -59,5 +60,7 @@ object Day11Test {
 
   class ViaMapSolutionTest extends SolutionTest(ViaMapSolution)
 
+  class ViaPairSolutionTest extends SolutionTest(ViaPairSolution)
+
   class PermutationSolutionTest extends SolutionTest(PermutationSolution)
 }

Original file line number	Diff line number	Diff line change
`@@ -7,6 +7,7 @@ import org.scalatest.funsuite.AnyFunSuite`
`7`	`7`
`8`	`8`	`class Day11Test extends Suites(`
`9`	`9`	`new ViaMapSolutionTest,`
	`10`	`+ new ViaPairSolutionTest,`
`10`	`11`	`new PermutationSolutionTest,`
`11`	`12`	`)`
`12`	`13`
`@@ -59,5 +60,7 @@ object Day11Test {`
`59`	`60`
`60`	`61`	`class ViaMapSolutionTest extends SolutionTest(ViaMapSolution)`
`61`	`62`
	`63`	`+ class ViaPairSolutionTest extends SolutionTest(ViaPairSolution)`
	`64`	`+`
`62`	`65`	`class PermutationSolutionTest extends SolutionTest(PermutationSolution)`
`63`	`66`	`}`