Skip Navigation

πŸ’ - 2024 DAY 22 SOLUTIONS - πŸ’

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

21 comments
  • Uiua

    It's been a while since I posted one of these, but I thought this would be straightforward in Uiua. Turns out that bitwise operations are a bit (haha) of a pain, so the Rng operation is very slow at 4sec for live data.

    I took this as an opportunity to play with the ⧈(stencil) operator which probably slowed things down too.

     
        
    Data ← 1_2_3_2024
    Xor  ← Β°β‹―β—Ώ2⬚0+βˆ©β‹― # Bitwise xor of two numbers.
    Rng  ← βŠ™β—Œβ—Ώ,XorΓ—2048.β—Ώ,Xor⌊÷32.β—Ώ,XorΓ—64.βŠ™16777216
    Runs ← ⍉(β‡Œ[β₯(Rng.)])2000 Data # Should be constant?
    Firsts ← (
      βŠŸβŠ‚0β§ˆβ‚‚/-.β—Ώ10 β†˜Β―1         # Build run, gen pair diffs
      ⊒⧈(βŠŸβŠ™βŠ£/(+Γ—40+20)°⊟) 2_4 # Convert 4-diff into key, collect.
      βŠ•βŠ’βŠ›βŠ™β‰βŠ™β—ŒΒ°βŠŸ.⍉             # Only keep first of each key. # ⍜(mapΒ°βŠŸβ‰β‡Œ|∘) failed. 
    )
    &p /+β‰‘βŠ£.Runs
    &p /β†₯βŠ•(/+)+1βŠ›Β°βŠŸβ‰/β—‡βŠ‚wait≑spawn(β–‘Firsts) # Group by key, sum prices, return highest.
    
      
  • 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.

    Also on github

    • How have I never noticed that scan() exists? Very handy.

      I liked the zipping of the offset prices, neater than my helper method.

  • 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.

     haskell
        
    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.

  • Rust

    Not too hard today, apart from yesterday's visit to a cocktail bar leaving me a little hazy in the mind.

  • 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;
    }
    
      
  • 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.

     Go
        
    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)
    }
    
      
  • 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
    
      
21 comments