Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

πŸͺ - 2024 DAY 11 SOLUTIONS -πŸͺ

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

30 comments

  • Uiua

    I thought this was going to be trivial to implement in Uiua, but I managed to blow the stack, meaning I had to set an environment variable in order to get it to run. That doesn't work in Uiua Pad, so for any counts larger than 15 you need to run it locally. Built-in memoisation though so that's nice. 

     undefined
        
# NB Needs env var UIUA_RECURSION_LIMIT=300
Next  ← ⍣([1] Β°0|[Γ—2024] Β°1β—Ώ2⧻°⋕.|βœΒ°β‹•(β†―2_∞))
Count ← |2 memo(⨬(1|/+≑CountΒ€-1βŠ™Next)β‰ 0.) # rounds, stone
≑(&p/+≑CountΒ€: βŠœβ‹•βŠΈβ‰ @\s "125 17")[25 75]

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

    Also on github

  • Haskell

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

     undefined
        
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]

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

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

     undefined
        
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 &amp; #.) &amp;.>) @: (({.~ ; }.~) (-: @: #)) @: (10 &amp; #.^:_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. &lt; 1 1
   elseif. 2 | &lt;. 10 ^. y do. &lt; (split y) ,. 1 1
   else. &lt; (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 =: > @: (({. ` ((+/&amp;.>) @: {:)) `: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. (&lt; @: (1&amp;,) @: {:) yields &lt;(1, count); then *"1&amp;.> multiplies those at rank 1 under
NB. boxing. Finally raze and reduce.
iterate =: reduce_count_matrix @: ; @: (((step @: {.) (*"1&amp;.>) (&lt; @: (1&amp;,) @: {:))"1)
count_pebbles =: +/ @: ({:"1)
result1 =: count_pebbles iterate^:25 initial_count_matrix
result2 =: count_pebbles iterate^:75 initial_count_matrix

  • Python

    I initially cached the calculate_next function but honestly number of unique numbers don't grow that much (couple thousands) so I did not feel a difference when I removed the cache. Using a dict just blazes through the problem. 

     undefined
        
from pathlib import Path
from collections import defaultdict
cwd = Path(__file__).parent

def parse_input(file_path):
  with file_path.open("r") as fp:
    numbers = list(map(int, fp.read().splitlines()[0].split(' ')))

  return numbers

def calculate_next(val):

  if val == 0:
    return [1]
  if (l:=len(str(val)))%2==0:
    return [int(str(val)[:int(l/2)]), int(str(val)[int(l/2):])]
  else:
    return [2024*val]

def solve_problem(file_name, nblinks):

  numbers = parse_input(Path(cwd, file_name))
  nvals = 0

  for indt, node in enumerate(numbers):

    last_nodes = {node:1}
    counter = 0

    while counter<nblinks:
      new_nodes = defaultdict(int)

      for val,count in last_nodes.items():
        val_next_nodes = calculate_next(val)

        for node in val_next_nodes:
          new_nodes[node] += count

      last_nodes = new_nodes
      counter += 1
    nvals += sum(last_nodes.values())

  return nvals

  • C# 

     undefined
        
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<long, TreeNode> subtree_pointers = [];

  public void Presolve(string input) {
    data = input.Trim().Split(" ").Select(long.Parse).ToArray();
    List<TreeNode> roots = data.Select(value => new TreeNode(null, null, value)).ToList();
    List<TreeNode> 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<TreeNode> 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<long> 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#

       undefined
          
    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];
    }

  • Dart

    I really wish Dart had memoising built in. Maybe the new macro feature will allow this to happen, but in the meantime, here's my hand-rolled solution. 

     undefined
        
import 'package:collection/collection.dart';

var counter_ = <(int, int), int>{};
int counter(s, [r = 75]) => counter_.putIfAbsent((s, r), () => _counter(s, r));
int _counter(int stone, rounds) =>
    (rounds == 0) ? 1 : next(stone).map((e) => counter(e, rounds - 1)).sum;

List<int> next(int s) {
  var ss = s.toString(), sl = ss.length;
  if (s == 0) return [1];
  if (sl.isOdd) return [s * 2024];
  return [ss.substring(0, sl ~/ 2), ss.substring(sl ~/ 2)]
      .map(int.parse)
      .toList();
}

solve(List<String> lines) => lines.first.split(' ').map(int.parse).map(counter).sum;

  • 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 

     nim
        
template splitNum(numStr: string): seq[int] =
  @[parseInt(numStr[0..<numStr.len div 2]), parseInt(numStr[numStr.len div 2..^1])]

template applyRule(stone: int): seq[int] =
  if stone == 0: @[1]
  else:
    let numStr = $stone
    if numStr.len mod 2 == 0: splitNum(numStr)
    else: @[stone * 2024]

proc memRule(st: int): seq[int] =
  var memo {.global.}: Table[int, seq[int]]
  if st in memo: return memo[st]
  result = st.applyRule
  memo[st] = result

proc countAfter(stone: int, targetBlinks: int): int =
  var memo {.global.}: Table[(int, int), int]
  if (stone,targetBlinks) in memo: return memo[(stone,targetBlinks)]

  if targetBlinks == 0: return 1
  for st in memRule(stone):
    result += st.countAfter(targetBlinks - 1)
  memo[(stone,targetBlinks)] = result

proc solve(input: string): AOCSolution[int, int] =
  for stone in input.split.map(parseInt):
    result.part1 += stone.countAfter(25)
    result.part2 += stone.countAfter(75)

    Codeberg repo

30 comments