8000 Solve 2020 day 22 part 2 · sim642/adventofcode@b6a97ed · GitHub
[go: up one dir, main page]
Skip to content

Commit b6a97ed

Browse files
sim642sim642
committed
Solve 2020 day 22 part 2
1 parent 31b9056 commit b6a97ed

File tree

2 files changed

+96
-22
lines changed

2 files changed

+96
-22
lines changed

‎src/main/scala/eu/sim642/adventofcode2020/Day22.scala

Lines changed: 86 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -2,35 +2,100 @@ package eu.sim642.adventofcode2020
22

33
import scala.collection.immutable.Queue
44
import eu.sim642.adventofcodelib.LazyListImplicits._
5+
import eu.sim642.adventofcodelib.cycle.NaiveCycleFinder
56

67
object Day22 {
78

89
type Deck = Queue[Int]
910
type Decks = (Deck, Deck)
1011

11-
def playRound(decks: Decks): Option[Decks] = {
12-
val (deck1, deck2) = decks
13-
(deck1.dequeueOption, deck2.dequeueOption) match {
14-
case (Some((card1, newDeck1)), Some((card2, newDeck2))) =>
15-
if (card1 > card2)
16-
Some((newDeck1.enqueue(card1).enqueue(card2), newDeck2))
17-
< 10000 span class="pl-k">else
18-
Some((newDeck1, newDeck2.enqueue(card2).enqueue(card1)))
19-
case (_, _) =>
20-
None
12+
sealed trait Part {
13+
def playWinner(decks: Decks): Either[Decks, Decks]
14+
15+
def winningScore(decks: Decks): Int = {
16+
val winningDeck = playWinner(decks) match {
17+
case Left((deck1, _)) => deck1
18+
case Right((_, deck2)) => deck2
19+
}
20+
winningDeck
21+
.reverseIterator
22+
.zipWithIndex
23+
.map({ case (card, i) => card * (i + 1) })
24+
.sum
25+
}
26+
}
27+
28+
object Part1 extends Part {
29+
30+
override def playWinner(decks: Decks): Either[Decks, Decks] = {
31+
val roundDecks = LazyList.unfold0(decks)(playRound)
32+
val lastDecks@(lastDeck1, _) = roundDecks.last
33+
if (lastDeck1.nonEmpty)
34+
Left(lastDecks)
35+
else
36+
Right(lastDecks)
37+
}
38+
39+
def playRound(decks: Decks): Option[Decks] = {
40+
val (deck1, deck2) = decks
41+
(deck1.dequeueOption, deck2.dequeueOption) match {
42+
case (Some((card1, newDeck1)), Some((card2, newDeck2))) =>
43+
if (card1 > card2)
44+
Some((newDeck1.enqueue(card1).enqueue(card2), newDeck2))
45+
else
46+
Some((newDeck1, newDeck2.enqueue(card2).enqueue(card1)))
47+
case (_, _) =>
48+
None
49+
}
2150
}
2251
}
2352

24-
def play(decks: Decks): < 10000 span class="pl-en x">LazyList[Decks] = LazyList.unfold0(decks)(playRound)
53+
object Part2 extends Part {
2554

26-
def winningScore(decks: Decks): Int = {
27-
val (deck1, deck2) = play(decks).last
28-
val winningDeck = if (deck1.isEmpty) deck2 else deck1
29-
winningDeck
30-
.reverseIterator
31-
.zipWithIndex
32-
.map({ case (card, i) => card * (i + 1) })
33-
.sum
55+
override def playWinner(decks: Decks): Either[Decks, Decks] = {
56+
//println(s"GAME: $decks")
57+
val roundDecks = decks #:: LazyList.unfold0(decks)(playRound)
58+
NaiveCycleFinder.find(roundDecks) match {
59+
case None =>
60+
val lastDecks@(lastDeck1, _) = roundDecks.last
61+
//println("GAME OVER (normal)")
62+
if (lastDeck1.nonEmpty)
63+
Left(lastDecks)
64+
else
65+
Right(lastDecks)
66+
case Some(cycle) =>
67+
//println("GAME OVER (cycle)")
68+
Left(cycle.cycleHead)
69+
}
70+
}
71+
72+
def playRound(decks: Decks): Option[Decks] = {
73+
//println(s"ROUND: $decks")
74+
val (deck1, deck2) = decks
75+
(deck1.dequeueOption, deck2.dequeueOption) match {
76+
case (Some((card1, newDeck1)), Some((card2, newDeck2))) =>
77+
//println(s" $card1 vs $card2")
78+
// TODO: Queue has inefficient length?
79+
if (!(newDeck1.length >= card1 && newDeck2.length >= card2)) {
80+
if (card1 > card2)
81+
Some((newDeck1.enqueue(card1).enqueue(card2), newDeck2))
82+
else
83+
Some((newDeck1, newDeck2.enqueue(card2).enqueue(card1)))
84+
}
85+
else {
86+
val recDeck1 = newDeck1.take(card1)
87+
val recDeck2 = newDeck2.take(card2)
88+
playWinner((recDeck1, recDeck2)) match {
89+
case Left(_) =>
90+
Some((newDeck1.enqueue(card1).enqueue(card2), newDeck2))
91+
case Right(_) =>
92+
Some((newDeck1, newDeck2.enqueue(card2).enqueue(card1)))
93+
}
94+
}
95+
case (_, _) =>
96+
None
97+
}
98+
}
3499
}
35100

36101

@@ -44,6 +109,7 @@ object Day22 {
44109
lazy val input: String = io.Source.fromInputStream(getClass.getResourceAsStream("day22.txt")).mkString.trim
45110

46111
def main(args: Array[String]): Unit = {
47-
println(winningScore(parseDecks(input)))
112+
println(Part1.winningScore(parseDecks(input)))
113+
println(Part2.winningScore(parseDecks(input)))
48114
}
49115
}

‎src/test/scala/eu/sim642/adventofcode2020/Day22Test.scala

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,10 +21,18 @@ class Day22Test extends AnyFunSuite {
2121
|10""".stripMargin
2222

2323
test("Part 1 examples") {
24-
assert(winningScore(parseDecks(exampleInput)) == 306)
24+
assert(Part1.winningScore(parseDecks(exampleInput)) == 306)
2525
}
2626

2727
test("Part 1 input answer") {
28-
assert(winningScore(parseDecks(input)) == 35202)
28+
assert(Part1.winningScore(parseDecks(input)) == 35202)
29+
}
30+
31+
test("Part 2 examples") {
32+
assert(Part2.winningScore(parseDecks(exampleInput)) == 291)
33+
}
34+
35+
test("Part 2 input answer") {
36+
assert(Part2.winningScore(parseDecks(input)) == 32317)
2937
}
3038
}

0 commit comments

Comments
 (0)
0