Optimize 2020 day 22 part 2 using "supercard" optimization

sim642 · sim642 · commit 204ae79468f0 · 2020-12-22T20:29:53.000+02:00
No difference on my input, 20× difference on mstksg input.
diff --git a/src/main/scala/eu/sim642/adventofcode2020/Day22.scala b/src/main/scala/eu/sim642/adventofcode2020/Day22.scala
@@ -69,8 +69,19 @@ object Day22 {
       case (card1 +: newDeck1, card2 +: newDeck2) =>
         val winner: Either[Any, Any] = {
           if (newDeck1.lengthIs >= card1 && newDeck2.lengthIs >= card2) {
-            val recDecks = (newDeck1.take(card1), newDeck2.take(card2))
-            playWinner(recDecks)
+            val recDec1 = newDeck1.take(card1)
+            val recDec2 = newDeck2.take(card2)
+            // "Supercard" optimization:
+            // https://github.com/glguy/advent2020/blob/1776cb3388581a1fbab79f1802650d43e24ffa66/execs/Day22.hs#L62-L65
+            // No difference on my input, 20× difference on mstksg input
+            val recDec1Max = recDec1.max
+            val recDec2Max = recDec2.max
+            if (recDec1Max > recDec2Max && recDec1Max >= (card1 + card2))
+              Left(())
+            else {
+              val recDecks = (recDec1, recDec2)
+              playWinner(recDecks)
+            }
           } else {
             if (card1 > card2)
               Left(())
diff --git a/src/test/scala/eu/sim642/adventofcode2020/Day22Test.scala b/src/test/scala/eu/sim642/adventofcode2020/Day22Test.scala
@@ -20,6 +20,8 @@ class Day22Test extends AnyFunSuite {
       |7
       |10""".stripMargin
 
+  lazy val mstksgInput: String = io.Source.fromInputStream(getClass.getResourceAsStream("day22mstksg.txt")).mkString.trim
+
   test("Part 1 examples") {
     assert(Part1.winningScore(parseDecks(exampleInput)) == 306)
   }
@@ -35,4 +37,8 @@ class Day22Test extends AnyFunSuite {
   test("Part 2 input answer") {
     assert(Part2.winningScore(parseDecks(input)) == 32317)
   }
+
+  test("Part 2 mstksg") {
+    assert(Part2.winningScore(parseDecks(mstksgInput)) == 32760) // unconfirmed answer
+  }
 }

Original file line number	Diff line number	Diff line change
`@@ -20,6 +20,8 @@ class Day22Test extends AnyFunSuite {`
`20`	`20`	`\|7`
`21`	`21`	`\|10""".stripMargin`
`22`	`22`
	`23`	`+ lazy val mstksgInput: String = io.Source.fromInputStream(getClass.getResourceAsStream("day22mstksg.txt")).mkString.trim`
	`24`	`+`
`23`	`25`	`test("Part 1 examples") {`
`24`	`26`	`assert(Part1.winningScore(parseDecks(exampleInput)) == 306)`
`25`	`27`	`}`
`@@ -35,4 +37,8 @@ class Day22Test extends AnyFunSuite {`
`35`	`37`	`test("Part 2 input answer") {`
`36`	`38`	`assert(Part2.winningScore(parseDecks(input)) == 32317)`
`37`	`39`	`}`
	`40`	`+`
	`41`	`+ test("Part 2 mstksg") {`
	`42`	`+ assert(Part2.winningScore(parseDecks(mstksgInput)) == 32760) // unconfirmed answer`
	`43`	`+ }`
`38`	`44`	`}`