--- Day 11: Counting rocks ---

December 11

Listening to: Pulse: FINAL FANTASY XIV Remix Album


This one is a strange one. I have a feeling there's going to be a huge trick to this once Part 2 comes along, but for now, it doesn't seem that bad. My guess is that it's going to be something like the classic lanternfish problem, and Part 2 is just a rediculous number of iterations, but let's see.

private List<long> IterateStones(List<long> stones)
{
    var blink = new List<long>();

    foreach (var stone in stones)
    {
        if (stone == 0)
        {
            blink.Add(1);
        }
        else if (stone.ToString().Length % 2 == 0)
        {
            var stoneString = stone.ToString();
            blink.Add(long.Parse(stoneString.Substring(0, stoneString.Length / 2)));
            blink.Add(long.Parse(stoneString.Substring(stoneString.Length / 2)));
        }
        else
        {
            blink.Add(stone * 2024);
        }
    }

    return blink;
}

I can already see a problem... or rather... a potental solution: All stones with the same start value with end with the same number of stones at the end! I just need to start caching things a bit.

Dictionary<(long, uint), long> stoneCache;

private long ExplodeStones(long value, uint iterations)
{
    if (stoneCache.ContainsKey((value, iterations)))
    {
        return stoneCache[(value, iterations)];
    }

    if (iterations == 0) return 1;

    if (value == 0)
    {
        return ExplodeStones(1, iterations - 1);
    }

    var stringValue = value.ToString();
    if (stringValue.Length % 2 == 0)
    {
        var left = long.Parse(stringValue.Substring(0, stringValue.Length / 2));
        var right = long.Parse(stringValue.Substring(stringValue.Length / 2));
        return ExplodeStones(left, iterations - 1) + ExplodeStones(right, iterations - 1);
    }

    return ExplodeStones(value * 2024, iterations - 1);
}

Much better!


I am so glad I did caching. Part 2 is just to do 75 iterations, instead of just 25. I imagine doing this like the first solution I coded would have taken a looooooooong time, and a lot of memory. Instead, here's the results (answers partially censored):

+----------------------------+
|   Results                  |
+---+-----------------+------+
| 1 |          23xxxx |  4ms |
| 2 | 28xxxxxxxxxxxxx | 29ms |
+----------------------------+

29ms! Damn! Caching is good.


Time taken: 25 minutes

My solutions for today's puzzles