Day 22: Monkey Market
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Haskell
I have no Idea how to optimize this and am looking forward to the other solutions that probably run in sub-single-second times. I like my solution because it was simple to write which I hadnβt managed in the previous days, runs in 17 seconds with no less than 100MB of RAM.
import Control.Arrow
import Data.Bits (xor)
import Data.Ord (comparing)
import qualified Data.List as List
import qualified Data.Map as Map
parse :: String -> [Int]
parse = map read . filter (/= "") . lines
mix = xor
prune = flip mod 16777216
priceof = flip mod 10
nextSecret step0 = do
let step1 = prune . mix step0 $ step0 * 64
let step2 = prune . mix step1 $ step1 `div` 32
let step3 = prune . mix step2 $ step2 * 2048
step3
part1 = sum . map (head . drop 2000 . iterate nextSecret)
part2 = map (iterate nextSecret
>>> take 2001
>>> map priceof
>>> (id &&& tail)
>>> uncurry (zipWith (curry (uncurry (flip (-)) &&& snd)))
>>> map (take 4) . List.tails
>>> filter ((==4) . length)
>>> map (List.map fst &&& snd . List.last)
>>> List.foldl (\ m (s, p) -> Map.insertWith (flip const) s p m) Map.empty
)
>>> Map.unionsWith (+)
>>> Map.assocs
>>> List.maximumBy (comparing snd)
main = getContents
>>= print
. (part1 &&& part2)
. parse
Haha, same! Mine runs in a bit under 4s compiled, but uses a similar 100M-ish peak. Looks like we used the same method.
Maybe iterate all the secrets in parallel, and keep a running note of the best sequences so far? Iβm not sure how youβd decide when to throw away old candidates, though. Sequences might match one buyer early and another really late.
Haskell
A nice easy one today; shame I couldnβt start on time. I had a go at refactoring to reduce the peak memory usage, but it just ended up a mess. Hereβs a tidy version.
import Data.Bits
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
next :: Int -> Int
next = flip (foldl' (\x n -> (x `xor` shift x n) .&. 0xFFFFFF)) [6, -5, 11]
bananaCounts :: Int -> Map [Int] Int
bananaCounts seed =
let secrets = iterate next seed
prices = map (`mod` 10) secrets
changes = zipWith (-) (drop 1 prices) prices
sequences = map (take 4) $ tails changes
in Map.fromListWith (const id) $
take 2000 (zip sequences (drop 4 prices))
main = do
input <- map read . lines <$> readFile "input22"
print . sum $ map ((!! 2000) . iterate next) input
print . maximum $ Map.unionsWith (+) $ map bananaCounts input
Rust
Nice breather today (still traumatized from the robots). At some point I thought you had to do some magic for predicting special properties of the pseudorandom function, but no, just collect all values, have a big table for all sequences and in the end take the maximum value in that table. Part 1 takes 6.7ms, part 2 19.2ms.
Solution
fn step(n: u32) -> u32 {
let a = (n ^ (n << 6)) % (1 << 24);
let b = a ^ (a >> 5);
(b ^ (b << 11)) % (1 << 24)
}
fn part1(input: String) {
let sum = input
.lines()
.map(|l| {
let n = l.parse().unwrap();
(0..2000).fold(n, |acc, _| step(acc)) as u64
})
// More than 2ΒΉβ° 24-bit numbers requires 35 bits
.sum::<u64>();
println!("{sum}");
}
const N_SEQUENCES: usize = 19usize.pow(4);
fn sequence_key(sequence: &[i8]) -> usize {
sequence
.iter()
.enumerate()
.map(|(i, x)| (x + 9) as usize * 19usize.pow(i as u32))
.sum()
}
fn part2(input: String) {
// Table for collecting the amount of bananas for every possible sequence
let mut table = vec![0; N_SEQUENCES];
// Mark the sequences we encountered in a round to ensure that only the first occurence is used
let mut seen = vec![false; N_SEQUENCES];
for l in input.lines() {
let n = l.parse().unwrap();
let (diffs, prices): (Vec<i8>, Vec<u8>) = (0..2000)
.scan(n, |acc, _| {
let next = step(*acc);
let diff = (next % 10) as i8 - (*acc % 10) as i8;
*acc = next;
Some((diff, (next % 10) as u8))
})
.unzip();
for (window, price) in diffs.windows(4).zip(prices.iter().skip(3)) {
let key = sequence_key(window);
if !seen[key] {
seen[key] = true;
table[key] += *price as u32;
}
}
// Reset seen sequences for next round
seen.fill(false);
}
let bananas = table.iter().max().unwrap();
println!("{bananas}");
}
util::aoc_main!();
Also on github
Go
Re-familiarizing myself with Go. The solution to Part 2 is fairly simply, the whole packing of the sequence into a single integer to save on memory was an optimization I did afterwards based on looking at other solutions. I thought it was cool.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type SequenceMap struct {
Data map[int32]int
}
func PackSeq(numbers [4]int8) int32 {
var packed int32
for i, num := range numbers {
packed |= int32(num+9) << (i * 5)
}
return packed
}
func UnpackSeq(packed int32) [4]int8 {
var numbers [4]int8
for i := range numbers {
numbers[i] = int8((packed>>(i*5))&0x1F) - 9
}
return numbers
}
func NewSequenceMap() SequenceMap {
return SequenceMap{make(map[int32]int)}
}
func (m *SequenceMap) Increment(seq [4]int8, val int) {
pSeq := PackSeq(seq)
acc, ok := m.Data[pSeq]
if ok {
m.Data[pSeq] = acc + val
} else {
m.Data[pSeq] = val
}
}
func (m *SequenceMap) Has(seq [4]int8) bool {
pSeq := PackSeq(seq)
_, ok := m.Data[pSeq]
return ok
}
type Generator struct {
Secret int64
LastPrice int8
ChangeSequence []int8
}
func NewGenerator(Secret int64) Generator {
var ChangeSequence []int8
return Generator{Secret, int8(Secret % 10), ChangeSequence}
}
func (g *Generator) Mix(value int64) *Generator {
g.Secret = g.Secret ^ value
return g
}
func (g *Generator) Prune() *Generator {
g.Secret = g.Secret % 16777216
return g
}
func (g *Generator) Next() {
g.Mix(g.Secret * 64).Prune().Mix(g.Secret / 32).Prune().Mix(g.Secret * 2048).Prune()
Price := int8(g.Secret % 10)
g.ChangeSequence = append(g.ChangeSequence, Price-g.LastPrice)
g.LastPrice = Price
if len(g.ChangeSequence) > 4 {
g.ChangeSequence = g.ChangeSequence[1:]
}
}
func ParseInput() []int64 {
if fileInfo, _ := os.Stdin.Stat(); (fileInfo.Mode() & os.ModeCharDevice) != 0 {
fmt.Println("This program expects input from stdin.")
os.Exit(1)
}
scanner := bufio.NewScanner(os.Stdin)
var numbers []int64
for scanner.Scan() {
line := scanner.Text()
num, err := strconv.ParseInt(line, 10, 64)
if err != nil {
fmt.Printf("ERROR PARSING VALUE: %s\n", line)
os.Exit(1)
}
numbers = append(numbers, num)
}
return numbers
}
func main() {
numbers := ParseInput()
m := NewSequenceMap()
sum := int64(0)
for i := 0; i < len(numbers); i += 1 {
g := NewGenerator(numbers[i])
tM := NewSequenceMap()
for j := 0; j < 2000; j += 1 {
g.Next()
if len(g.ChangeSequence) == 4 {
if !tM.Has([4]int8(g.ChangeSequence)) {
tM.Increment([4]int8(g.ChangeSequence), 1)
if g.LastPrice > 0 {
m.Increment([4]int8(g.ChangeSequence), int(g.LastPrice))
}
}
}
}
sum += g.Secret
}
fmt.Printf("Part One: %d\n", sum)
var bestSeq [4]int8
bestPrice := 0
for pSeq, price := range m.Data {
if price > bestPrice {
bestPrice = price
bestSeq = UnpackSeq(pSeq)
}
}
fmt.Printf("Part Two: %d\n", bestPrice)
fmt.Printf("Best Sequence: %d\n", bestSeq)
}
Dart
Well, that was certainly a bit easier than yesterdayβ¦
I know running a window over each full list of 2000 prices rather than looking for cycles etc means Iβm doing a lot of unnecessary work, but it only takes a couple of seconds, so thatβll do.
import 'package:collection/collection.dart';
import 'package:more/more.dart';
rng(int i) {
i = ((i << 6) ^ i) % 16777216;
i = ((i >> 5) ^ i) % 16777216;
i = ((i << 11) ^ i) % 16777216;
return i;
}
Iterable<int> getPrices(int val, int rounds) {
var ret = [val];
for (var _ in 1.to(rounds)) {
ret.add(val = rng(val));
}
return ret.map((e) => e % 10);
}
int run(int val, int rounds) => 0.to(rounds).fold(val, (s, t) => s = rng(s));
part1(lines) => [for (var i in lines.map(int.parse)) run(i, 2000)].sum;
part2(List<String> lines) {
var market = <int, int>{}.withDefault(0);
for (var seed in lines.map(int.parse)) {
var seen = <int>{};
for (var w in getPrices(seed, 2000).window(5)) {
var key = // Can't use lists as keys, so make cheap hash.
w.window(2).map((e) => e[1] - e[0]).reduce((s, t) => (s << 4) + t);
if (seen.contains(key)) continue;
seen.add(key);
market[key] += w.last;
}
}
return market.values.max;
}