Advent of Code 2024 - Day 22: Monkey Market

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
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:

1
 
input = parse(22, int)

Part 1

For part 1, we’re given an algorithm for computing the next secret number from a secret number:

1
2
3
4
 
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:

1
2
 
def part1():
    return sum(iterate(evolve, n, 2000) for n in input)

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
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 }:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
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:

1
2
3
4
5
6
7
8
 
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
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
 
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:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
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")
  }
}