Advent of Code 2024: Day 22

On Day 22 we are introduced to a simple pseudo-random number generator (PRNG) that uses this recurrance to generate pseudo-random numbers:

S1 = ((Xn << 6) ⊕ Xn) mod 224
S2 = ((S1 >> 5) ⊕ S1) mod 224
Xn+1 = ((S2 << 11) ⊕ S2) mod 224

We just define this as a simple function, but we are carful to put a check-type on the input to make sure it is a number in the correct range. This gives the compiler enough information to optimize the body of the generator to a sequence of inline fixed-point operations, avoid the overhead of a function call out to the generic arithmetic.

(defun next-pseudorandom (pseudorandom)
  (check-type pseudorandom (integer 0 (16777216)))
  (macrolet ((mix (a b) ‘(logxor ,a ,b))
             (prune (x) ‘(mod ,x 16777216)))
    (let* ((s1 (prune (mix (* pseudorandom 64) pseudorandom)))
           (s2 (prune (mix (floor s1 32) s1)))
           (s3 (prune (mix (* s2 2048) s2))))
      s3)))

We can generate a series of random numbers from a given seed:

(defun scan-pseudorandom (seed)
  (declare (optimizable-series-function))
  (scan-fn '(integer 0 (16777216))
           (lambda () seed)
           #'next-pseudorandom))

The nth pseudorandom number is the nth element in the series, i.e. the result of applying the next-pseudorandom function n times to the seed:

(defun nth-pseudorandom (seed n)
  (collect-nth n (scan-pseudorandom seed)))

Part 1 of the problem is to sum the 2000th pseudorandom numbers generated from seeds given in a file.

(defun part-1 ()
  (collect-sum (#Mnth-pseudorandom (scan-file (input-pathname)) (series 2000))))

For part 2, we're going to be simulating a market. The prices are single digit pseudorandom numbers:

(defun scan-prices (seed)
  (declare (optimizable-series-function))
  (#Mmod (scan-pseudorandom seed) (series 10)))

The bidders in our market are monkeys, and we read them from our input file:

(defun scan-monkeys (input-pathname)
  (declare (optimizable-series-function 2))
  (cotruncate (scan-range :from 0)
              (scan-file input-pathname)))

The seed that we read from the input pathname will be used to create a price series for each monkey.

Each monkey looks for trends in the market by looking at the last four price changes. If the last four prices changes match the trend the monkey looks for, the monkey will make a trade and get a profit of the current price.

For part 2, we assume all the monkeys look for the same trend. Some trend will maximize the total profit of all the monkeys. We want to know what that maximum profit is.

We'll proceed in two steps. First, we make a table that maps trends to profits for each monkey. We'll start with an empty table, then we'll iterate over the monkeys, adding the trend info for that monkey. Once we have the table, we'll iterate over all the possible trends and find the one that maximizes the total profit.

price-deltas is a series of the differences between the prices in the price series. We'll use this to determine the trend.

(defun price-deltas (price-series)
  (declare (optimizable-series-function)
           (off-line-port price-series))
  (mapping (((before after) (chunk 2 1 price-series)))
     (- after before)))

price-trends is a series of trends. The trend is simply a list of the last four price deltas.

(defun price-trends (price-series)
  (declare (optimizable-series-function)
           (off-line-port price-series))
  (mapping (((d1 d2 d3 d4) (chunk 4 1 (price-deltas price-series))))
           (list d1 d2 d3 d4)))

add-trend-info! adds the trend info for a monkey to the table. We'll look at a count of 2000 prices (minus the first four because there aren't enough to establish a trend). The key to an entry in the table will be taken from the price-trends. The value for an entry is the price after that trend. The table maps a trend to an alist that maps monkeys to profits, so once we know the trend, we look to see if an entry for the monkey already exists in the value. If it does, we're done. But if it doesn't, we add an entry for the monkey with the profit.

(defun add-trend-info! (table monkeyid seed)
  (iterate ((count (scan-range :from 4 :below 2001))
            (trend (price-trends (scan-prices seed)))
            (value (subseries (scan-prices seed) 4)))
    (declare (ignore count))
    (unless (assoc monkeyid (gethash trend table '()))
      (push (cons monkeyid value) (gethash trend table '())))))

Once we have added the trend info for all the monkeys, we find the entry in the table that maximizes the total profit.

(defun trend-table-maximum (table)
  (let ((best-score 0)
        (best-key nil))
    (maphash (lambda (key value)
               (let ((score (reduce #'+ (map 'list #'cdr value))))
                 (when (> score best-score)
                   (setq best-key key)
                   (setq best-score score))))
             table)
    (values best-key best-score)))

Finally, we can put it all together in the part-2 function:

(defun part-2 ()
  (multiple-value-bind (best-key best-value)
      (let ((table (make-hash-table :test #'equal)))
        (iterate (((monkeyid seed) (scan-monkeys (input-pathname))))
          (add-trend-info! table monkeyid seed))
        (trend-table-maximum table))
    (declare (ignore best-key))
    best-value))