Day 11: Plutonian Pebbles

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

  • Kotlin

    Gone mathematical.

    Also overflowing indices screwed with me a bit.

    Here's the code:
    import kotlin.math.floor
    import kotlin.math.log
    import kotlin.math.pow
    import kotlin.time.DurationUnit
    
    fun main() {
        fun part1(input: List): Long = Day11Solver(input).solve(25)
    
        fun part2(input: List): Long = Day11Solver(input).solve(75)
    
        val testInput = readInput("Day11_test")
        check(part1(testInput) == 55312L)
        //check(part2(testInput) == 0L)  No test output available.
    
        val input = readInput("Day11")
        part1(input).println()
        part2(input).println()
    
        timeTrials("Part 1", unit = DurationUnit.MICROSECONDS) { part1(input) }
        timeTrials("Part 2", repetitions = 1000) { part2(input) }
    }
    
    class Day11Solver(input: List) {
        private val parsedInput = input[0].split(' ').map { it.toLong() }
    
        /*
         * i ∈ ℕ₀ ∪ {-1}, φᵢ: ℕ₀ → ℕ shall be the function mapping the amount of stones generated to the amount of steps
         * taken with a stone of starting number i.
         *
         * Furthermore, ѱ: ℕ₀ → ℕ₀ ⨯ (ℕ₀ ∪ {-1}) shall be the function mapping an index to two new indices after a step.
         *
         *         ⎧ (1, -1)       if i = 0
         * ѱ(i) := ⎨ (a, b)        if ⌊lg(i)⌋ + 1 ∈ 2 ℕ    with a := i/(10^((⌊lg(i)⌋ + 1) / 2)), b := i - 10^((⌊lg(i)⌋ + 1) / 2) * a
         *         ⎩ (2024 i, -1)  otherwise
         *
         *          ⎧ 0                      if i = -1
         * φᵢ(n) := ⎨ 1                      if n = 0
         *          ⎩ φₖ(n - 1) + φₗ(n - 1)  otherwise    with (k, l) := ѱ(i)
         *
         * With that φᵢ(n) is a sum with n up to 2ⁿ summands, that are either 0 or 1.
         */
        private val cacheIndices = mutableMapOf>()  // Cache the next indices for going from φᵢ(n) to φₖ(n - 1) + φₗ(n - 1).
        private val cacheValues = mutableMapOf, Long>()  // Also cache already calculated φᵢ(n)
    
        fun calculatePsi(i: Long): Pair = cacheIndices.getOrPut(i) {
            if(i == -1L) throw IllegalArgumentException("Advancement made: How did we get here?")
            else if (i == 0L) 1L to -1L
            else {
                val amountOfDigits = (floor(log(i.toDouble(), 10.0)) + 1)
    
                if (amountOfDigits.toLong() % 2 == 0L) {
                    // Split digits at the midpoint.
                    val a = floor(i / 10.0.pow(amountOfDigits / 2))
                    val b = i - a * 10.0.pow(amountOfDigits / 2)
                    a.toLong() to b.toLong()
                } else {
                    2024 * i to -1L
                }
            }
        }
    
        fun calculatePhi(i: Long, n: Int): Long = cacheValues.getOrPut(i to n) {
            if (i == -1L) 0L
            else if (n == 0) 1L
            else {
                val (k, l) = calculatePsi(i)
                calculatePhi(k, n - 1) + calculatePhi(l, n - 1)
            }
        }
    
        fun solve(steps: Int): Long = parsedInput.sumOf {
            val debug = calculatePhi(it, steps)
            debug
        }
    }
    
    

    Try it out here.

    And this is the full repo.

  • Zee

    Zee is my Dutch dialect of C. Since Dutch has compound words, so does Zee: “const char **” becomes vasteletterverwijzingsverwijzing, not vaste letter verwijzing verwijzing, which would be incorrect. A pointer to a long long unsigned int is, obviously, a zeergrootnatuurlijkgetalverwijzing.

    Code
    #ingesloten "zee.kop"
    #ingesloten "algemeen.kop"
    
    besloten getal
    splits(
        zeer groot natuurlijk getal x,
        zeergrootnatuurlijkgetalverwijzing a,
        zeergrootnatuurlijkgetalverwijzing b)
    {
    	zeer groot natuurlijk getal m;
    	getal n, g;
    
    	mits (!x) lever 0;
    	voor (n=0, m=1; m<=x;  n++, m*=10) ; mits (n%2) lever 0;
    	voor (g=0, m=1; g 1)
    		VERWERP(heropen(parameters[1], "r", standaardinvoer));
    
    	zolang (invorm(" %llu", &waarde) == 1) {
    		d1 += afdalen(waarde, 25);
    		d2 += afdalen(waarde, 75);
    	}
    
    	uitvorm("11: %llu %llu\n", d1, d2);
    	lever 0;
    }
    

    And of course we don’t have a Makefile but a Maakbestand:

    alles: €{DAGEN}
    
    schoon:
    	€{WIS} -f €{DAGEN} *.o
    
    ...
    
    .TWIJFELACHTIG:	alles schoon oplossingen
    .UITGANGEN:	.zee .o
    
    .zee.o:
    	€{ZEE} €{VOORWERKVLAG} €{ZEEVLAG} -o €@ -c €<
    
      • No it’s just me messing about with macros (but it does work!)

        I do want to explore the type naming rules, see if I can write a parser for it. The C rules are funky by themselves but this is another level. “vaste letterverwijzing” is “char * const” but “vasteletterverwijzing” (without the space) is “const char *”. Then there’s grammatical gender: “vast getal” (const int) but “vaste letter” (const char)

  • Rust

    Part 2 is solved with recursion and a cache, which is indexed by stone numbers and remaining rounds and maps to the previously calculated expansion size. In my case, the cache only grew to 139320 entries, which is quite reasonable given the size of the result.

    Solution
    use std::collections::HashMap;
    
    fn parse(input: String) -> Vec {
        input
            .split_whitespace()
            .map(|w| w.parse().unwrap())
            .collect()
    }
    
    fn part1(input: String) {
        let mut stones = parse(input);
        for _ in 0..25 {
            let mut new_stones = Vec::with_capacity(stones.len());
            for s in &stones {
                match s {
                    0 => new_stones.push(1),
                    n => {
                        let digits = s.ilog10() + 1;
                        if digits % 2 == 0 {
                            let cutoff = 10u64.pow(digits / 2);
                            new_stones.push(n / cutoff);
                            new_stones.push(n % cutoff);
                        } else {
                            new_stones.push(n * 2024)
                        }
                    }
                }
            }
            stones = new_stones;
        }
        println!("{}", stones.len());
    }
    
    fn expansion(s: u64, rounds: u32, cache: &mut HashMap<(u64, u32), u64>) -> u64 {
        // Recursion anchor
        if rounds == 0 {
            return 1;
        }
        // Calculation is already cached
        if let Some(res) = cache.get(&(s, rounds)) {
            return *res;
        }
    
        // Recurse
        let res = match s {
            0 => expansion(1, rounds - 1, cache),
            n => {
                let digits = s.ilog10() + 1;
                if digits % 2 == 0 {
                    let cutoff = 10u64.pow(digits / 2);
                    expansion(n / cutoff, rounds - 1, cache) +
                    expansion(n % cutoff, rounds - 1, cache)
                } else {
                    expansion(n * 2024, rounds - 1, cache)
                }
            }
        };
        // Save in cache
        cache.insert((s, rounds), res);
        res
    }
    
    fn part2(input: String) {
        let stones = parse(input);
        let mut cache = HashMap::new();
        let sum: u64 = stones.iter().map(|s| expansion(*s, 75, &mut cache)).sum();
        println!("{sum}");
    }
    
    util::aoc_main!();
    

    Also on github

  • And now we get into the days where caching really is king. My first attempt didn’t go so well, I tried to handle the full list result as one cache step, instead of individually caching the result of calculating each stone per step.

    I think my original attempt is still calculating at home, but I finished up this much better version on the trip to work.
    All hail public transport.

    C#
    List stones = new List();
    public void Input(IEnumerable lines)
    {
      stones = string.Concat(lines).Split(' ').Select(v => long.Parse(v)).ToList();
    }
    
    public void Part1()
    {
      var expanded = TryExpand(stones, 25);
    
      Console.WriteLine($"Stones: {expanded}");
    }
    public void Part2()
    {
      var expanded = TryExpand(stones, 75);
    
      Console.WriteLine($"Stones: {expanded}");
    }
    
    public long TryExpand(IEnumerable stones, int steps)
    {
      if (steps == 0)
        return stones.Count();
      return stones.Select(s => TryExpand(s, steps)).Sum();
    }
    Dictionary<(long, int), long> cache = new Dictionary<(long, int), long>();
    public long TryExpand(long stone, int steps)
    {
      var key = (stone, steps);
      if (cache.ContainsKey(key))
        return cache[key];
    
      var result = TryExpand(Blink(stone), steps - 1);
      cache[key] = result;
      return result;
    }
    
    public IEnumerable Blink(long stone)
    {
      if (stone == 0)
      {
        yield return 1;
        yield break;
      }
      var str = stone.ToString();
      if (str.Length % 2 == 0)
      {
        yield return long.Parse(str[..(str.Length / 2)]);
        yield return long.Parse(str[(str.Length / 2)..]);
        yield break;
      }
      yield return stone * 2024;
    }
    
  • J

    If one line of code needs five lines of comment, I’m not sure how much of an improvement the “expressive power” is! But I learned how to use J’s group-by operator (/. or /..) and a trick with evoke gerund (`:0"1) to transform columns of a matrix separately. It might have been simpler to transpose and apply to rows.

    data_file_name =: '11.data'
    data =: ". > cutopen fread data_file_name
    NB. split splits an even digit positive integer into left digits and right digits
    split =: ; @: ((10 & #.) &.>) @: (({.~ ; }.~) (-: @: #)) @: (10 & #.^:_1)
    NB. step consumes a single number and yields the boxed count-matrix of acting on that number
    step =: monad define
       if. y = 0 do. < 1 1
       elseif. 2 | <. 10 ^. y do. < (split y) ,. 1 1
       else. < (y * 2024), 1 end.
    )
    NB. reduce_count_matrix consumes an unboxed count-matrix of shape n 2, left column being
    NB. the item and right being the count of that item, and reduces it so that each item
    NB. appears once and the counts are summed; it does not sort the items. Result is unboxed.
    NB. Read the vocabulary page for /.. to understand the grouped matrix ;/.. builds; the
    NB. gerund evoke `:0"1 then sums under boxing in the right coordinate of each row.
    reduce_count_matrix =: > @: (({. ` ((+/&.>) @: {:)) `:0"1) @: ({. ;/.. {:) @: |:
    initial_count_matrix =: reduce_count_matrix data ,. (# data) $ 1
    NB. iterate consumes a count matrix and yields the result of stepping once across that
    NB. count matrix. There's a lot going on here. On rows (item, count) of the incoming count
    NB. matrix, (step @: {.) yields the (boxed count matrix) result of step item;
    NB. (< @: (1&,) @: {:) yields <(1, count); then *"1&.> multiplies those at rank 1 under
    NB. boxing. Finally raze and reduce.
    iterate =: reduce_count_matrix @: ; @: (((step @: {.) (*"1&.>) (< @: (1&,) @: {:))"1)
    count_pebbles =: +/ @: ({:"1)
    result1 =: count_pebbles iterate^:25 initial_count_matrix
    result2 =: count_pebbles iterate^:75 initial_count_matrix
    
  • Haskell

    Yay, mutation! Went down the route of caching the expanded lists of stones at first. Oops.

    import Data.IORef
    import Data.Map.Strict (Map)
    import Data.Map.Strict qualified as Map
    
    blink :: Int -> [Int]
    blink 0 = [1]
    blink n
      | s <- show n,
        l <- length s,
        even l =
          let (a, b) = splitAt (l `div` 2) s in map read [a, b]
      | otherwise = [n * 2024]
    
    countExpanded :: IORef (Map (Int, Int) Int) -> Int -> [Int] -> IO Int
    countExpanded _ 0 = return . length
    countExpanded cacheRef steps = fmap sum . mapM go
      where
        go n =
          let key = (n, steps)
              computed = do
                result <- countExpanded cacheRef (steps - 1) $ blink n
                modifyIORef' cacheRef (Map.insert key result)
                return result
           in readIORef cacheRef >>= maybe computed return . (Map.!? key)
    
    main = do
      input <- map read . words <$> readFile "input11"
      cache <- newIORef Map.empty
      mapM_ (\steps -> countExpanded cache steps input >>= print) [25, 75]
    
  •  janAkali   ( @janAkali@lemmy.one ) 
    link
    fedilink
    English
    2
    edit-2
    4 days ago

    Nim

    Runtime: 30-40 ms
    I’m not very experienced with recursion and memoization, so this took me quite a while.

    Edit: slightly better version

    template splitNum(numStr: string): seq[int] =
      @[parseInt(numStr[0..
  • C#

    public class Day11 : Solver
    {
      private long[] data;
    
      private class TreeNode(TreeNode? left, TreeNode? right, long value) {
        public TreeNode? Left = left;
        public TreeNode? Right = right;
        public long Value = value;
      }
    
      private Dictionary<(long, int), long> generation_length_cache = [];
      private Dictionary subtree_pointers = [];
    
      public void Presolve(string input) {
        data = input.Trim().Split(" ").Select(long.Parse).ToArray();
        List roots = data.Select(value => new TreeNode(null, null, value)).ToList();
        List last_level = roots;
        subtree_pointers = roots.GroupBy(root => root.Value)
          .ToDictionary(grouping => grouping.Key, grouping => grouping.First());
        for (int i = 0; i < 75; i++) {
          List next_level = [];
          foreach (var node in last_level) {
            long[] children = Transform(node.Value).ToArray();
            node.Left = new TreeNode(null, null, children[0]);
            if (subtree_pointers.TryAdd(node.Left.Value, node.Left)) {
              next_level.Add(node.Left);
            }
            if (children.Length <= 1) continue;
            node.Right = new TreeNode(null, null, children[1]);
            if (subtree_pointers.TryAdd(node.Right.Value, node.Right)) {
              next_level.Add(node.Right);
            }
          }
          last_level = next_level;
        }
      }
    
      public string SolveFirst() => data.Select(value => GetGenerationLength(value, 25)).Sum().ToString();
      public string SolveSecond() => data.Select(value => GetGenerationLength(value, 75)).Sum().ToString();
    
      private long GetGenerationLength(long value, int generation) {
        if (generation == 0) { return 1; }
        if (generation_length_cache.TryGetValue((value, generation), out var result)) return result;
        TreeNode cur = subtree_pointers[value];
        long sum = GetGenerationLength(cur.Left.Value, generation - 1);
        if (cur.Right is not null) {
          sum += GetGenerationLength(cur.Right.Value, generation - 1);
        }
        generation_length_cache[(value, generation)] = sum;
        return sum;
      }
    
      private IEnumerable Transform(long arg) {
        if (arg == 0) return [1];
        if (arg.ToString() is { Length: var l } str && (l % 2) == 0) {
          return [int.Parse(str[..(l / 2)]), int.Parse(str[(l / 2)..])];
        }
        return [arg * 2024];
      }
    }
    
    • I had a very similar take on this problem, but I was not caching the results of a blink for a single stone, like youre doing with subtree_pointers. I tried adding that to my solution, but it didn’t make an appreciable difference. I think that caching the lengths is really the only thing that matters.

      C#

          static object Solve(Input i, int numBlinks)
          {
              // This is a cache of the tuples of (stoneValue, blinks) to
              // the calculated count of their child stones.
              var lengthCache = new Dictionary<(long, int), long>();
              return i.InitialStones
                  .Sum(stone => CalculateUltimateLength(stone, numBlinks, lengthCache));
          }
      
          static long CalculateUltimateLength(
              long stone,
              int numBlinks,
              IDictionary<(long, int), long> lengthCache)
          {
              if (numBlinks == 0) return 1;
              
              if (lengthCache.TryGetValue((stone, numBlinks), out var length)) return length;
      
              length = Blink(stone)
                  .Sum(next => CalculateUltimateLength(next, numBlinks - 1, lengthCache));
              lengthCache[(stone, numBlinks)] = length;
              return length;
          }
      
          static long[] Blink(long stone)
          {
              if (stone == 0) return [1];
      
              var stoneText = stone.ToString();
              if (stoneText.Length % 2 == 0)
              {
                  var halfLength = stoneText.Length / 2;
                  return
                  [
                      long.Parse(stoneText.Substring(0, halfLength)),
                      long.Parse(stoneText.Substring(halfLength)),
                  ];
              }
      
              return [stone * 2024];
          }
      
  • C

    Started out a bit sad that this problem really seemed to call for hash tables - either for storing counts for an iterative approach, or to memoize a recursive one.

    Worried that the iterative approach would have me doing problematic O(n^2) array scans I went with recursion and a plan to memoize only the first N integers in a flat array, expecting low integers to be much more frequent (and dense) than higher ones.

    After making an embarrassing amount of mistakes it worked out beautifully with N=1m (testing revealed that to be about optimal). Also applied some tail recursion shortcuts where possible.

    day11  0:00.01  6660 Kb  0+1925 faults
    
    Code
    #include "common.h"
    
    /* returns 1 and splits x if even-digited, 0 otherwise */
    static int
    split(uint64_t x, uint64_t *a, uint64_t *b)
    {
    	uint64_t p;
    	int n, i;
    
    	if (!x) return 0;
    	for (n=0, p=1; p<=x;  n++, p*=10) ; if (n%2) return 0;
    	for (i=0, p=1; i 1)
    		DISCARD(freopen(argv[1], "r", stdin));
    
    	while (scanf(" %"SCNu64, &val) == 1) {
    		p1 += recur(val, 25);
    		p2 += recur(val, 75);
    	}
    
    	printf("10: %"PRId64" %"PRId64"\n", p1, p2);
    	return 0;
    }
    

    https://github.com/sjmulder/aoc/blob/master/2024/c/day11.c