Day 22: Monkey Market
Scala Center Advent of Code 2024, Day 22
Solution Summary
- Parse input into a
List[Int]
- Make a function that advances the hidden number
Part 1 and part 2 are pretty disjoint after this.
For part 1, then:
- For each value in the input, apply this function 2000 times, and convert to
Long
at the end - Sum all these values
For part 2, then:
- For each value, get the first 2000 numbers in the sequence, and modulo them by 10.
- Get a list of all possible valid combinations of diffs (so
-9 to 9
* 4) - For all of the sequences of the first 2000 numbers, get a sequence of all diffs in the list and what number they result in
- Go through each valid combination and sum the resulting number from each sequence for that combination
- Pick the max of these
Part 1
First, let's get parsing out of the way:
def parse(str: String): List[Int] =
str.linesIterator.map(_.toInt).toList
Next, the bulk of part 1: The seed function.
The wording in the puzzle description isn't very helpful, so let's simplify it a bit.
It's worth noting that all the numbers used in advancing are powers of two, so bitwise operations can replace the multiplying, dividing, and moduloing.
Now for the actual process:
- Save the secret number to a temporary register (
x
) - Set
x
tox
xorx
times 64 (orx
bitshift left by 6) - Set
x
tox
modulo 16777216 (orx
bitwise and 16777216 - 1) - Set
x
tox
xorx
divided by 32, rounded down (orx
bitshift right by 5) - Set
x
tox
modulo 16777216 (orx
bitwise and 16777216 - 1) - Set
x
tox
xorx
times 2048 (orx
bitshift left by 11) - Set
x
tox
modulo 16777216 (orx
bitwise and 16777216 - 1) - Return the new secret number as
x
's value.
Here's the real code:
val pow2to24minus1 = 16777216 - 1
def advance(i: Int): Int =
var x = i
x ^= (x << 6)
x &= pow2to24minus1
x ^= (x >> 5)
x &= pow2to24minus1
x ^= (x << 11)
x &= pow2to24minus1
x
Let's also make a helper function for applying a function n
times:
extension[A](f: A => A)
def repeated(n: Int): A => A = (x: A) =>
Iterator.iterate(x)(f).drop(n).next()
Now we can solve part 1:
def part1(input: List[Int]): Long =
input.map: l =>
advance.repeated(2000)(l).toLong
.sum
Part 2
Part 2 is kind of a lot, but it's all in the part2
function, so let's step through the part 2 function bit by bit.
def part2(input: List[Int]): Long =
First, let's get the list of sequences of the first 2000 prices.
val sequences = input.map: l =>
Iterator.iterate(l)(advance).take(2000).map(_ % 10).toList
Then, let's get all of the valid combinations of difference sequences:
val validDiffSequences =
for {
x <- -9 to 9
y <- -9 to 9
z <- -9 to 9
w <- -9 to 9
} yield Vector(x, y, z, w)
Now here is the somewhat hard part to optimize correctly, but I found that calculating the sum of all the sequences here is the fastest. Let's make a map of all of the sums for all the valid combinations.
val diffMap =
For each sequence, we have to make a map of the first time we see each difference sequence and what value it results in. A simple
sliding
with a foldLeft
works for this.
Note the updatedWith never overrides a value if it's already present, as we only want the first value we see with that difference sequence.
sequences.map: seq =>
seq.sliding(5).foldLeft(Map[Vector[Int], Int]()):
case (acc, Seq(x, y, z, w, v)) =>
acc.updatedWith(Vector(y - x, z - y, w - z, v - w)):
case Some(value) => Some(value)
case None => Some(v)
Then we have to sum all of these together. Two more foldLeft
s work here:
.foldLeft(Map[Vector[Int], Long]()): (acc, oldMap) =>
oldMap.foldLeft(acc):
case (c, (k, v)) =>
c.updatedWith(k):
case Some(value) => Some(value + v.toLong)
case _ => Some(v.toLong)
Now we actually have our map of diffs, we just find the maximum.
validDiffSequences.flatMap: i =>
diffMap.get(i).map(v => (i, v))
.maxBy(_._2)._2
And that's part2
.
Final code:
def parse(str: String): List[Int] =
str.linesIterator.map(_.toInt).toList
// 16777216 == 2 ^ 24
val pow2to24minus1 = 16777216 - 1
def advance(i: Int): Int =
var x = i
x ^= (x << 6)
x &= pow2to24minus1
x ^= (x >> 5)
x &= pow2to24minus1
x ^= (x << 11)
x &= pow2to24minus1
x
def part1(input: List[Int]): Long =
input.map: l =>
advance.repeated(2000)(l).toLong
.sum
def part2(input: List[Int]): Long =
val sequences = input.map: l =>
Iterator.iterate(l)(advance).take(2000).map(_ % 10).toList
val validDiffSequences =
for {
x <- -9 to 9
y <- -9 to 9
z <- -9 to 9
w <- -9 to 9
} yield Vector(x, y, z, w)
val diffMap =
sequences.map: seq =>
seq.sliding(5).foldLeft(Map[Vector[Int], Int]()):
case (acc, Seq(x, y, z, w, v)) =>
acc.updatedWith(Vector(y - x, z - y, w - z, v - w)):
case Some(value) => Some(value)
case None => Some(v)
.foldLeft(Map[Vector[Int], Long]()): (acc, oldMap) =>
oldMap.foldLeft(acc):
case (c, (k, v)) =>
c.updatedWith(k):
case Some(value) => Some(value + v.toLong)
case _ => Some(v.toLong)
validDiffSequences.flatMap: i =>
diffMap.get(i).map(v => (i, v))
.maxBy(_._2)._2
On my machine this only takes 3 seconds.