Nu sÄ blev det Àntligen löst. Min stackars hjÀrna fick gÄ pÄ högvarv idag
Började med att jag tÀnkte "Det hÀr Àr ju lÀtt! Bara skapa en lista med alla nummer.. sen summerar jag dom i slutet!"
.. Ja, det funkade ju med 25 iterationer (typ typ 200ms?) men minnet kÀkades upp ganska snabbt.
Gjorde om till rekursiva funktioner istÀllet och fick ner minnesanvÀndningen till nÄgra enstaka MB - stenarnas vÀrden sparades aldrig, ökade endast en counter nÀr jag var pÄ sista indexet i min iteration. Funkade Ànnu bÀttre vid 25 iterationer (20ms ish).
Del 2.. jahopp, för att Del 2 ska bli klar (75 iterationer) hade jag tydligen behövt vÀnta ett Är eller tvÄ Bruteforce (trots effektiv minnesanvÀndning) hade alltsÄ inte funkat.
Fick skriva om lösningen till att anvÀnda ett cache istÀllet.
Om jag rÀknat ut ett vÀrde redan sÄ ÄteranvÀnder jag resultatet istÀllet för att berÀkna det pÄ nytt.
Samma gÀller antalet stenar med ett visst vÀrde - öka antalet med nÀsta vÀrde med nuvarande vÀrdes antal. SÄ har jag 4 stenar med vÀrdet 2024 sÄ lÀgger jag nu in att vÀrdena 20 och 24 ökat med 4st. Tack @kode för ledtrÄden
Del 1 tar ca 0.8ms
Del 2 tar ca 25ms
public static class Solver
{
private static long GetNumberOfDigits(long n) => n > 0 ? (long)Math.Log10(n) + 1 : 1;
private static RuleResult ExecuteRules(long number)
{
if (number == 0)
return new RuleResult(1, -1);
var numberOfDigits = GetNumberOfDigits(number);
if (numberOfDigits % 2 != 0) return new RuleResult(number * 2024, -1);
var divisor = (long)Math.Pow(10, numberOfDigits * 0.5);
return new RuleResult(number / divisor, number % divisor);
}
private static Dictionary<long, long> GetNewValues(Dictionary<long, long> prevValues,
Dictionary<long, RuleResult> cachedRuleValues)
{
var newValues = new Dictionary<long, long>();
foreach (var kvp in prevValues)
{
if (!cachedRuleValues.TryGetValue(kvp.Key, out var val))
{
val = ExecuteRules(kvp.Key);
cachedRuleValues[kvp.Key] = val;
}
if (newValues.TryGetValue(val.A, out _))
newValues[val.A] += kvp.Value;
else
newValues[val.A] = kvp.Value;
if (val.B == -1) continue;
if (newValues.TryGetValue(val.B, out _))
newValues[val.B] += kvp.Value;
else
newValues[val.B] = kvp.Value;
}
return newValues;
}
private static long GenerateStones(List<int> numbers, int iterations)
{
var dict = numbers.GroupBy(n => (long)n)
.ToDictionary(group => group.Key, group => (long)group.Count());
var cache = new Dictionary<long, RuleResult>();
for (var i = 0; i < iterations; i++)
{
var output = GetNewValues(dict, cache);
dict = output;
}
return dict.Values.Sum();
}
public static long Run_PartOne(string input)
{
var numbers = input.Split(" ").Select(int.Parse).ToList();
return GenerateStones(numbers, 25);
}
public static long Run_PartTwo(string input)
{
var numbers = input.Split(" ").Select(int.Parse).ToList();
return GenerateStones(numbers, 75);
}
private readonly struct RuleResult(long a, long b)
{
public long A { get; } = a;
public long B { get; } = b;
}
}
