10000 Solve 2018 day 9 part 2 · sim642/adventofcode@d190e51 · GitHub
[go: up one dir, main page]
Skip to content

Commit d190e51

Browse files
sim642sim642
committed
Solve 2018 day 9 part 2
1 parent 4ba22e4 commit d190e51

File tree

2 files changed

+48
-14
lines changed

2 files changed

+48
-14
lines changed

‎src/main/scala/eu/sim642/adventofcode2018/Day9.scala

Lines changed: 44 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -2,33 +2,62 @@ package eu.sim642.adventofcode2018
22

33
object Day9 {
44

5-
def highscore(playerCount: Int, lastMarble: Int): Int = {
6-
def helper(marbles: Vector[Int], currentIndex: Int, marble: Int, player: Int, scores: Map[Int, Int]): Map[Int, Int] = {
5+
/**
6+
* Zipper-like immutable circular buffer.
7+
*/
8+
case class MarbleCircle(init: List[Int], current: Int, tail: List[Int]) {
9+
def next: MarbleCircle = tail match {
10+
case hd :: tl => MarbleCircle(current :: init, hd, tl)
11+
case Nil =>
12+
init.reverse match {
13+
case hd :: it => MarbleCircle(List(current), hd, it)
14+
case Nil => this
15+
}
16+
}
17+
18+
def prev: MarbleCircle = init match {
19+
case hd :: it => MarbleCircle(it, hd, current :: tail)
20+
case Nil =>
21+
tail.reverse match {
22+
case hd :: tl => MarbleCircle(tl, hd, List(current))
23+
case Nil => this
24+
}
25+
}
26+
27+
def inserted(elem: Int): MarbleCircle = MarbleCircle(init, elem, current :: tail)
28+
29+
def removed: MarbleCircle = tail match {
30+
case hd :: tl => MarbleCircle(init, hd, tl)
31+
case Nil =>
32+
val hd :: it = init
33+
MarbleCircle(it, hd, tail)
34+
}
35+
}
36+
37+
def highscore(playerCount: Int, lastMarble: Int): Long = {
38+
def helper(marbles: MarbleCircle, marble: Int, player: Int, scores: Map[Int, Long]): Map[Int, Long] = {
739
val nextPlayer = ((player - 1) + 1) % playerCount + 1
840

941
if (marble > lastMarble)
1042
scores
1143
else if (marble % 23 == 0) {
12-
val removeIndex = (currentIndex - 7 + marbles.length) % marbles.length
13-
val (init, removed +: tail) = marbles.splitAt(removeIndex)
14-
val newMarbles = init ++ tail
15-
val newScores = scores.updated(player, scores(player) + marble + removed)
16-
helper(newMarbles, removeIndex, marble + 1, nextPlayer, newScores)
44+
val beforeRemoved = marbles.prev.prev.prev.prev.prev.prev.prev
45+
val newMarbles = beforeRemoved.removed
46+
val newScores = scores.updated(player, scores(player) + marble + beforeRemoved.current)
47+
helper(newMarbles, marble + 1, nextPlayer, newScores)
1748
}
1849
else {
19-
val insertIndex = (currentIndex + 2) % marbles.length
20-
val (init, tail) = marbles.splitAt(insertIndex)
21-
val newMarbles: Vector[Int] = (init :+ marble) ++ tail
22-
helper(newMarbles, insertIndex, marble + 1, nextPlayer, scores)
50+
val newMarbles = marbles.next.next.inserted(marble)
51+
helper(newMarbles, marble + 1, nextPlayer, scores)
2352
}
2453
}
2554

26-
helper(Vector(0), 0, 1, 1, Map.empty.withDefaultValue(0)).values.max
55+
helper(MarbleCircle(Nil, 0, Nil), 1, 1, Map.empty.withDefaultValue(0)).values.max
2756
}
2857

29-
def highscore(input: String): Int = {
58+
def highscore(input: String, lastMarbleMult: Int = 1): Long = {
3059
val (playerCount, lastMarble) = parseInput(input)
31-
highscore(playerCount, lastMarble)
60+
highscore(playerCount, lastMarble * lastMarbleMult)
3261
}
3362

3463
private val inputRegex = """(\d+) players; last marble is worth (\d+) points""".r
@@ -41,5 +70,6 @@ object Day9 {
4170

4271
def main(args: Array[String]): Unit = {
4372
println(highscore(input))
73+
println(highscore(input, lastMarbleMult = 100))
4474
}
4575
}

‎src/test/scala/eu/sim642/adventofcode2018/Day9Test.scala

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,4 +18,8 @@ class Day9Test extends FunSuite {
1818
test("Part 1 input answer") {
1919
assert(highscore(input) == 398371)
2020
}
21+
22+
test("Part 2 input answer") {
23+
assert(highscore(input, 100) == 3212830280L)
24+
}
2125
}

0 commit comments

Comments
 (0)
0