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.

  • Rust

    Part 2 is crazy slow, but it works, so thats cool :D

    Edit: Gonna fix this, because pt2 is stupid.

    Much better, 2.4s. Still slow, but not 6 minutes slow.

     rust
        
    #[cfg(test)]
    mod tests {
        use std::collections::HashMap;
        use std::iter::zip;
    
        fn step(start: usize) -> usize {
            let mut next = start;
            next = ((next * 64) ^ next) % 16777216;
            next = ((next / 32) ^ next) % 16777216;
            next = ((next * 2048) ^ next) % 16777216;
            next
        }
    
        fn simulate(initial: usize) -> usize {
            let mut next = initial;
            for _ in 0..2000 {
                next = step(next);
            }
            next
        }
        #[test]
        fn test_step() {
            assert_eq!(15887950, step(123));
        }
        #[test]
        fn test_simulate() {
            assert_eq!(8685429, simulate(1));
        }
    
        #[test]
        fn day22_part1_test() {
            let input = std::fs::read_to_string("src/input/day_22.txt").unwrap();
            let initial_values = input
                .split("\n")
                .map(|s| s.parse::<usize>().unwrap())
                .collect::<Vec<usize>>();
    
            let mut total = 0;
    
            for value in initial_values {
                total += simulate(value);
            }
    
            println!("{}", total);
        }
    
        #[test]
        fn day22_part2_test() {
            let input = std::fs::read_to_string("src/input/day_22.txt").unwrap();
            let initial_values = input
                .split("\n")
                .map(|s| s.parse::<usize>().unwrap())
                .collect::<Vec<usize>>();
    
            let mut all_deltas = vec![];
            let mut all_values = vec![];
    
            for value in initial_values {
                let mut deltas = String::with_capacity(2000);
                let mut values = vec![];
                let mut prev = value;
                for _ in 0..2000 {
                    let next = step(prev);
                    values.push(next % 10);
                    deltas.push((10u8 + b'A' + ((prev % 10) as u8) - ((next % 10) as u8)) as char);
                    prev = next;
                }
    
                all_deltas.push(deltas);
                all_values.push(values);
            }
    
            let mut totals = HashMap::with_capacity(100000);
    
            for (delta, value) in zip(&all_deltas, &all_values) {
                let mut cache = HashMap::with_capacity(2000);
                for j in 0..delta.len() - 4 {
                    let seq = &delta[j..j + 4];
                    let bananas = value[j + 3];
                    cache.entry(seq).or_insert(bananas);
                }
                for (key, value) in cache {
                    *totals.entry(key).or_insert(0) += value;
                }
            }
    
            let max_bananas = totals.values().max().unwrap();
    
            println!("{}", max_bananas);
        }
    }
    
    
      
  • 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;
    }
    
      
  • Haskell

  • Kotlin

    I experimented a lot to improve the runtime and now I am happy with my solution. The JVM doesn't optimize code that quickly :)

    I have implemented a few optimizations in regards to transformations so that they use arrays directly (The file with the implementations is here)

  • 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)
    }
    
      
  • C

    Really proud of this one! Started with with an O(n^atoms in the universe) scan which took 44s even after adding a dedup check.

    But iterating on a trick to encode the deltas for the dedup check, using it to build a mapping table here, a lookup there etc brought it down to a very fast, fairly low memory, linear complexity solution!

    day22 0m00.04s real

    https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day22.c

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

    Hey there lemmy, I recently transitioned from using notepad to Visual Studio Code along with running a local LLM for autocomplete(faster than copilot, big plus but hot af room)

    I was able to make this python script with a bunch of fancy comments and typing silliness. I ended up spamming so many comments. yay documentation! lol

    Solve time: ~3 seconds (can swing up to 5 seconds)

    • Bit odd having main() returning an actual value, probably would have named it something else, otherwise, nicely documented solution.

      I bet VSC is a lot nicer to work in than notepad :D

      • you have a point to call name it something else, but lazy to do that. should I simply call it solve() maybe, that would work fine.
        I do want to note that having it return a value is not unheard of, it is just part of being lazy with the naming of the functions.
        I definitely would not have the code outside of main() be included in the main function as it is just something to grab the input pass it to the solver function( main in this case, but as you noted should be called something else ) and print out the results. if you imported it as a module, then you can call main() with any input and get back the results to do whatever you want with. Just something I think makes the code better to look at and use.

        While doing this is highly unnecessary for these challenge, I wish to keep a little bit of proper syntax than just writing the script with everything at the top level. It feels dirty.

        Coding in notepad was a bit brutal, but I stuck with notepad for years and never really cared because I copy pasta quite a bit from documentation or what not.(now a days, gpt helps me fix my shit code, now that hallucinations are reduced decently) even with VSCode, I don't pay attention to many of its features. I still kinda treat it as a text editor, but extra nagging on top.(nagging is a positive I guess, but I am an ape who gives little fucks) I do like VSCode having a workspace explorer on the side. I dislike needing to alt-tab to various open file explorer windows. Having tabs for open files is really nice, too.

        VSCode is nice, and running my Qwen-coder-1.5B locally is neat for helping somethings out. Not like I rely on it for helping with coding, but rather use it for comments or sometimes I stop to think or sometimes the autocomplete is updated in realtime while I am typing. really neat stuff, I think running locally is better than copilot because of it just being more real-time than the latency with interacting with MS servers. though I do think about all the random power it is using and extra waste heat from me constantly typing and it having to constantly keep up with the new context.

        The quality took a little hit with the smaller model than just copilot, but so far it is not bad at all for things I expect it to help with. It definitely is capable of helping out. I do get annoyed when the autocomplete tries too hard to help by generating a lot more stuff that I don't want.(even if the first part of what it generated is what I wanted but the rest is not) thankfully, that is not too often.
        I give the local llm is helping with 70% of the comments and 15% of the code on average but it is not too consistent for the code.
        For python, there is not enough syntax overhead to worry about and the autocomplete isn't needed as much.

21 comments