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.