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

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    2
    ·
    17 days 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];
      }
    }
    
    • SteveDinn@lemmy.ca
      link
      fedilink
      arrow-up
      3
      ·
      16 days 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];
          }
      
      • hades@lemm.ee
        link
        fedilink
        arrow-up
        1
        ·
        16 days ago

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

        Yep, it is just a dynamic programming problem really.