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

  • Ananace@lemmy.ananace.dev
    3·
    7 hours ago

    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<long> stones = new List<long>();
public void Input(IEnumerable<string> 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<long> 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<long> 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;
}