Advent of Code 2024-Day 22: Monkey Market
from advent import parse, iterate, Counter
input = parse(22, int)
def evolve(n):
n = (n * 64 ^ n) % 16777216
n = (n // 32 ^ n) % 16777216
return (n * 2048 ^ n) % 16777216
def get_changes(n):
prev_digit = n % 10
changes = []
for _ in range(2000):
n = evolve(n)
digit = n % 10
changes.append((digit, digit - prev_digit))
prev_digit = digit
return changes
def count_sequences(n):
changes = get_changes(n)
d = {}
for i in range(3, len(changes)):
t = (changes[i-3][1], changes[i-2][1], changes[i-1][1], changes[i][1])
if not t in d:
d[t] = changes[i][0]
return d
def part1():
return sum(iterate(evolve, n, 2000) for n in input)
def part2():
bananas = Counter()
for n in input:
for t, v in count_sequences(n).items():
bananas[t] += v
return bananas.most_common(1)[0][1]
# ---------------------------------------------------------------------------------------------
assert part1() == 19927218456 # 1.6 s
assert part2() == 2189 # 5.4 s
Parsing
We're given a list of secret numbers:
Part 1
For part 1, we're given an algorithm for computing the next secret number from a secret number:
def evolve(n):
n = (n * 64 ^ n) % 16777216
n = (n // 32 ^ n) % 16777216
return (n * 2048 ^ n) % 16777216
Our task is simply to iterate this function 2,000 times for each secret number in our input, and sum all the results:
Part 2
Part 2 is much more involved. We'll need some helper functions. First, we'll create a function
to get a list of 2-tuples, where each one is of the form (price, delta) where price is simply the
last digit of secret number n and delta is the price change between secret number n and secret number n-1:
def get_changes(n):
prev_digit = n % 10
changes = []
for _ in range(2000):
n = evolve(n)
digit = n % 10
changes.append((digit, digit - prev_digit))
prev_digit = digit
return changes
Our next helper will compute the price for each unique 4-tuple of price changes. We'll only store the price
for a 4-tuple when encountering it for the first time. It returns a dict of { (a,b,c,d) : price }:
def count_sequences(n):
changes = get_changes(n)
d = {}
for i in range(3, len(changes)):
t = (changes[i-3][1], changes[i-2][1], changes[i-1][1], changes[i][1])
if not t in d:
d[t] = changes[i][0]
return d
With that in place, part2() simply computes a dictionary of { 4-tuple : price } for each number
in our input, and updates a running counter of bananas for each 4-tuple:
def part2():
bananas = Counter()
for n in input:
for t, v in count_sequences(n).items():
bananas[t] += v
return bananas.most_common(1)[0][1]
Conclusion
I really enjoyed today's puzzle - it was nice to have a little break from the tougher ones! My solution isn't very speedy with 1.6 seconds for part 1 and 5.4 seconds for part 2. I think this is likely due to Python's speed since we're doing a lot of looping and calculating. I'm not motivated to speed up the Python version, but I may create a Go solution later to compare.
Postscript
I used ChatGPT to quickly translate my Python solution to Go. It's about 7.4x faster than Python for part 2. I timed both from the command line, so it includes startup time for the Python interpreter and time to parse the input file:
- Python => 6,100 ms
- Go => 818 ms
package main
import (
"bufio"
"log"
"os"
"strconv"
)
func parse(filename string) []int {
file, err := os.Open(filename)
if err != nil {
panic(err)
}
defer file.Close()
var numbers []int
scanner := bufio.NewScanner(file)
for scanner.Scan() {
line := scanner.Text()
num, err := strconv.Atoi(line)
if err != nil {
panic(err)
}
numbers = append(numbers, num)
}
if err := scanner.Err(); err != nil {
panic(err)
}
return numbers
}
func evolve(n int) int {
n = (n*64 ^ n) % 16777216
n = (n/32 ^ n) % 16777216
return (n*2048 ^ n) % 16777216
}
func getChanges(n int) [][2]int {
prevDigit := n % 10
changes := make([][2]int, 0, 2000)
for i := 0; i < 2000; i++ {
n = evolve(n)
digit := n % 10
changes = append(changes, [2]int{digit, digit - prevDigit})
prevDigit = digit
}
return changes
}
func countSequences(n int) map[[4]int]int {
changes := getChanges(n)
d := make(map[[4]int]int)
for i := 3; i < len(changes); i++ {
t := [4]int{ changes[i-3][1], changes[i-2][1], changes[i-1][1], changes[i][1] }
if _, exists := d[t]; !exists {
d[t] = changes[i][0]
}
}
return d
}
func part1(input []int) int {
totalSum := 0
for _, n := range input {
for i := 0; i < 2000; i++ {
n = evolve(n)
}
totalSum += n
}
return totalSum
}
func part2(input []int) int {
bananas := make(map[[4]int]int)
for _, n := range input {
for t, v := range countSequences(n) {
bananas[t] += v
}
}
maxValue := 0
for _, v := range bananas {
if v > maxValue {
maxValue = v
}
}
return maxValue
}
func main() {
if part2(parse("day22.txt")) != 2189 {
log.Fatalf("Part 2 failed")
}
}
Postscript 2
I also had ChatGPT parallelize the code, this dropped the time from 818 ms to 457 ms:
package main
import (
"bufio"
"log"
"os"
"strconv"
"sync"
)
func parse(filename string) []int {
file, err := os.Open(filename)
if err != nil {
panic(err)
}
defer file.Close()
var numbers []int
scanner := bufio.NewScanner(file)
for scanner.Scan() {
line := scanner.Text()
num, err := strconv.Atoi(line)
if err != nil {
panic(err)
}
numbers = append(numbers, num)
}
if err := scanner.Err(); err != nil {
panic(err)
}
return numbers
}
func evolve(n int) int {
n = (n*64 ^ n) % 16777216
n = (n/32 ^ n) % 16777216
return (n*2048 ^ n) % 16777216
}
func getChanges(n int) [][2]int {
prevDigit := n % 10
changes := make([][2]int, 0, 2000)
for i := 0; i < 2000; i++ {
n = evolve(n)
digit := n % 10
changes = append(changes, [2]int{digit, digit - prevDigit})
prevDigit = digit
}
return changes
}
func countSequences(n int) map[[4]int]int {
changes := getChanges(n)
d := make(map[[4]int]int)
for i := 3; i < len(changes); i++ {
t := [4]int{ changes[i-3][1], changes[i-2][1], changes[i-1][1], changes[i][1] }
if _, exists := d[t]; !exists {
d[t] = changes[i][0]
}
}
return d
}
func part1(input []int) int {
totalSum := 0
for _, n := range input {
for i := 0; i < 2000; i++ {
n = evolve(n)
}
totalSum += n
}
return totalSum
}
func part2(input []int) int {
var bananas sync.Map
var wg sync.WaitGroup
for _, n := range input {
wg.Add(1)
go func(n int) {
defer wg.Done()
for t, v := range countSequences(n) {
actual, _ := bananas.LoadOrStore(t, 0)
bananas.Store(t, actual.(int)+v)
}
}(n)
}
wg.Wait()
maxValue := 0
bananas.Range(func(_, value any) bool {
if value.(int) > maxValue {
maxValue = value.(int)
}
return true
})
return maxValue
}
func main() {
if part2(parse("day22.txt")) != 2189 {
log.Fatalf("Part 2 failed")
}
}