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))
