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

  • @[email protected]
    2•6 months ago

    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<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];
  }
}
    • @[email protected]
      3•6 months ago

      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];
    }
      • @[email protected]
        1•6 months ago

        I think that caching the lengths is really the only thing that matters.

        Yep, it is just a dynamic programming problem really.