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
- the_beber ( @the_beber@lemm.ee ) 1•1 day ago
Kotlin
Gone mathematical.
Also overflowing indices screwed with me a bit.
Here's the code:
import kotlin.math.floor import kotlin.math.log import kotlin.math.pow import kotlin.time.DurationUnit fun main() { fun part1(input: List): Long = Day11Solver(input).solve(25) fun part2(input: List): Long = Day11Solver(input).solve(75) val testInput = readInput("Day11_test") check(part1(testInput) == 55312L) //check(part2(testInput) == 0L) No test output available. val input = readInput("Day11") part1(input).println() part2(input).println() timeTrials("Part 1", unit = DurationUnit.MICROSECONDS) { part1(input) } timeTrials("Part 2", repetitions = 1000) { part2(input) } } class Day11Solver(input: List) { private val parsedInput = input[0].split(' ').map { it.toLong() } /* * i ∈ ℕ₀ ∪ {-1}, φᵢ: ℕ₀ → ℕ shall be the function mapping the amount of stones generated to the amount of steps * taken with a stone of starting number i. * * Furthermore, ѱ: ℕ₀ → ℕ₀ ⨯ (ℕ₀ ∪ {-1}) shall be the function mapping an index to two new indices after a step. * * ⎧ (1, -1) if i = 0 * ѱ(i) := ⎨ (a, b) if ⌊lg(i)⌋ + 1 ∈ 2 ℕ with a := i/(10^((⌊lg(i)⌋ + 1) / 2)), b := i - 10^((⌊lg(i)⌋ + 1) / 2) * a * ⎩ (2024 i, -1) otherwise * * ⎧ 0 if i = -1 * φᵢ(n) := ⎨ 1 if n = 0 * ⎩ φₖ(n - 1) + φₗ(n - 1) otherwise with (k, l) := ѱ(i) * * With that φᵢ(n) is a sum with n up to 2ⁿ summands, that are either 0 or 1. */ private val cacheIndices = mutableMapOf>() // Cache the next indices for going from φᵢ(n) to φₖ(n - 1) + φₗ(n - 1). private val cacheValues = mutableMapOf, Long>() // Also cache already calculated φᵢ(n) fun calculatePsi(i: Long): Pair = cacheIndices.getOrPut(i) { if(i == -1L) throw IllegalArgumentException("Advancement made: How did we get here?") else if (i == 0L) 1L to -1L else { val amountOfDigits = (floor(log(i.toDouble(), 10.0)) + 1) if (amountOfDigits.toLong() % 2 == 0L) { // Split digits at the midpoint. val a = floor(i / 10.0.pow(amountOfDigits / 2)) val b = i - a * 10.0.pow(amountOfDigits / 2) a.toLong() to b.toLong() } else { 2024 * i to -1L } } } fun calculatePhi(i: Long, n: Int): Long = cacheValues.getOrPut(i to n) { if (i == -1L) 0L else if (n == 0) 1L else { val (k, l) = calculatePsi(i) calculatePhi(k, n - 1) + calculatePhi(l, n - 1) } } fun solve(steps: Int): Long = parsedInput.sumOf { val debug = calculatePhi(it, steps) debug } }
Try it out here.
And this is the full repo.
- sjmulder ( @sjmulder@lemmy.sdf.org ) 4•3 days ago
Zee
Zee is my Dutch dialect of C. Since Dutch has compound words, so does Zee: “const char **” becomes vasteletterverwijzingsverwijzing, not vaste letter verwijzing verwijzing, which would be incorrect. A pointer to a long long unsigned int is, obviously, a zeergrootnatuurlijkgetalverwijzing.
Code
#ingesloten "zee.kop" #ingesloten "algemeen.kop" besloten getal splits( zeer groot natuurlijk getal x, zeergrootnatuurlijkgetalverwijzing a, zeergrootnatuurlijkgetalverwijzing b) { zeer groot natuurlijk getal m; getal n, g; mits (!x) lever 0; voor (n=0, m=1; m<=x; n++, m*=10) ; mits (n%2) lever 0; voor (g=0, m=1; g 1) VERWERP(heropen(parameters[1], "r", standaardinvoer)); zolang (invorm(" %llu", &waarde) == 1) { d1 += afdalen(waarde, 25); d2 += afdalen(waarde, 75); } uitvorm("11: %llu %llu\n", d1, d2); lever 0; }
And of course we don’t have a Makefile but a Maakbestand:
alles: €{DAGEN} schoon: €{WIS} -f €{DAGEN} *.o ... .TWIJFELACHTIG: alles schoon oplossingen .UITGANGEN: .zee .o .zee.o: €{ZEE} €{VOORWERKVLAG} €{ZEEVLAG} -o €@ -c €<
Yet more proof that the dutch are mad :D
Is it your own esolang, or is it commonly used by dutch speakers?
- sjmulder ( @sjmulder@lemmy.sdf.org ) 3•3 days ago
No it’s just me messing about with macros (but it does work!)
I do want to explore the type naming rules, see if I can write a parser for it. The C rules are funky by themselves but this is another level. “vaste letterverwijzing” is “char * const” but “vasteletterverwijzing” (without the space) is “const char *”. Then there’s grammatical gender: “vast getal” (const int) but “vaste letter” (const char)
- Gobbel2000 ( @Gobbel2000@programming.dev ) 3•4 days ago
Rust
Part 2 is solved with recursion and a cache, which is indexed by stone numbers and remaining rounds and maps to the previously calculated expansion size. In my case, the cache only grew to 139320 entries, which is quite reasonable given the size of the result.
Solution
use std::collections::HashMap; fn parse(input: String) -> Vec { input .split_whitespace() .map(|w| w.parse().unwrap()) .collect() } fn part1(input: String) { let mut stones = parse(input); for _ in 0..25 { let mut new_stones = Vec::with_capacity(stones.len()); for s in &stones { match s { 0 => new_stones.push(1), n => { let digits = s.ilog10() + 1; if digits % 2 == 0 { let cutoff = 10u64.pow(digits / 2); new_stones.push(n / cutoff); new_stones.push(n % cutoff); } else { new_stones.push(n * 2024) } } } } stones = new_stones; } println!("{}", stones.len()); } fn expansion(s: u64, rounds: u32, cache: &mut HashMap<(u64, u32), u64>) -> u64 { // Recursion anchor if rounds == 0 { return 1; } // Calculation is already cached if let Some(res) = cache.get(&(s, rounds)) { return *res; } // Recurse let res = match s { 0 => expansion(1, rounds - 1, cache), n => { let digits = s.ilog10() + 1; if digits % 2 == 0 { let cutoff = 10u64.pow(digits / 2); expansion(n / cutoff, rounds - 1, cache) + expansion(n % cutoff, rounds - 1, cache) } else { expansion(n * 2024, rounds - 1, cache) } } }; // Save in cache cache.insert((s, rounds), res); res } fn part2(input: String) { let stones = parse(input); let mut cache = HashMap::new(); let sum: u64 = stones.iter().map(|s| expansion(*s, 75, &mut cache)).sum(); println!("{sum}"); } util::aoc_main!();
Also on github
- Ananace ( @ace@lemmy.ananace.dev ) 3•4 days 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 stones = new List(); public void Input(IEnumerable 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 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 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; }
- ystael ( @ystael@beehaw.org ) 2•3 days ago
J
If one line of code needs five lines of comment, I’m not sure how much of an improvement the “expressive power” is! But I learned how to use J’s group-by operator (
/.
or/..
) and a trick with evoke gerund (`:0"1) to transform columns of a matrix separately. It might have been simpler to transpose and apply to rows.data_file_name =: '11.data' data =: ". > cutopen fread data_file_name NB. split splits an even digit positive integer into left digits and right digits split =: ; @: ((10 & #.) &.>) @: (({.~ ; }.~) (-: @: #)) @: (10 & #.^:_1) NB. step consumes a single number and yields the boxed count-matrix of acting on that number step =: monad define if. y = 0 do. < 1 1 elseif. 2 | <. 10 ^. y do. < (split y) ,. 1 1 else. < (y * 2024), 1 end. ) NB. reduce_count_matrix consumes an unboxed count-matrix of shape n 2, left column being NB. the item and right being the count of that item, and reduces it so that each item NB. appears once and the counts are summed; it does not sort the items. Result is unboxed. NB. Read the vocabulary page for /.. to understand the grouped matrix ;/.. builds; the NB. gerund evoke `:0"1 then sums under boxing in the right coordinate of each row. reduce_count_matrix =: > @: (({. ` ((+/&.>) @: {:)) `:0"1) @: ({. ;/.. {:) @: |: initial_count_matrix =: reduce_count_matrix data ,. (# data) $ 1 NB. iterate consumes a count matrix and yields the result of stepping once across that NB. count matrix. There's a lot going on here. On rows (item, count) of the incoming count NB. matrix, (step @: {.) yields the (boxed count matrix) result of step item; NB. (< @: (1&,) @: {:) yields <(1, count); then *"1&.> multiplies those at rank 1 under NB. boxing. Finally raze and reduce. iterate =: reduce_count_matrix @: ; @: (((step @: {.) (*"1&.>) (< @: (1&,) @: {:))"1) count_pebbles =: +/ @: ({:"1) result1 =: count_pebbles iterate^:25 initial_count_matrix result2 =: count_pebbles iterate^:75 initial_count_matrix
- lwhjp ( @lwhjp@lemmy.sdf.org ) 2•4 days ago
Haskell
Yay, mutation! Went down the route of caching the expanded lists of stones at first. Oops.
import Data.IORef import Data.Map.Strict (Map) import Data.Map.Strict qualified as Map blink :: Int -> [Int] blink 0 = [1] blink n | s <- show n, l <- length s, even l = let (a, b) = splitAt (l `div` 2) s in map read [a, b] | otherwise = [n * 2024] countExpanded :: IORef (Map (Int, Int) Int) -> Int -> [Int] -> IO Int countExpanded _ 0 = return . length countExpanded cacheRef steps = fmap sum . mapM go where go n = let key = (n, steps) computed = do result <- countExpanded cacheRef (steps - 1) $ blink n modifyIORef' cacheRef (Map.insert key result) return result in readIORef cacheRef >>= maybe computed return . (Map.!? key) main = do input <- map read . words <$> readFile "input11" cache <- newIORef Map.empty mapM_ (\steps -> countExpanded cache steps input >>= print) [25, 75]
- janAkali ( @janAkali@lemmy.one ) English2•4 days ago
Nim
Runtime: 30-40 ms
I’m not very experienced with recursion and memoization, so this took me quite a while.Edit: slightly better version
template splitNum(numStr: string): seq[int] = @[parseInt(numStr[0..
- hades ( @hades@lemm.ee ) 2•4 days ago
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 subtree_pointers = []; public void Presolve(string input) { data = input.Trim().Split(" ").Select(long.Parse).ToArray(); List roots = data.Select(value => new TreeNode(null, null, value)).ToList(); List 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 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 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]; } }
- SteveDinn ( @SteveDinn@lemmy.ca ) 3•4 days ago
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]; }
- hades ( @hades@lemm.ee ) 1•3 days ago
I think that caching the lengths is really the only thing that matters.
Yep, it is just a dynamic programming problem really.
- sjmulder ( @sjmulder@lemmy.sdf.org ) 1•4 days ago
C
Started out a bit sad that this problem really seemed to call for hash tables - either for storing counts for an iterative approach, or to memoize a recursive one.
Worried that the iterative approach would have me doing problematic O(n^2) array scans I went with recursion and a plan to memoize only the first N integers in a flat array, expecting low integers to be much more frequent (and dense) than higher ones.
After making an embarrassing amount of mistakes it worked out beautifully with N=1m (testing revealed that to be about optimal). Also applied some tail recursion shortcuts where possible.
day11 0:00.01 6660 Kb 0+1925 faults
Code
#include "common.h" /* returns 1 and splits x if even-digited, 0 otherwise */ static int split(uint64_t x, uint64_t *a, uint64_t *b) { uint64_t p; int n, i; if (!x) return 0; for (n=0, p=1; p<=x; n++, p*=10) ; if (n%2) return 0; for (i=0, p=1; i 1) DISCARD(freopen(argv[1], "r", stdin)); while (scanf(" %"SCNu64, &val) == 1) { p1 += recur(val, 25); p2 += recur(val, 75); } printf("10: %"PRId64" %"PRId64"\n", p1, p2); return 0; }