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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 2 points
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];
}
}
3 points
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];
}
1 point
