Day 7: Bridge Repair
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
I’m way behind, but I’m trying to learn F#.
I’m using the library Combinatorics in dotnet, which I’ve used in the past, generate in this case every duplicating possibility of the operations. I the only optimization that I did was to use a function to concatenate numbers without converting to strings, but that didn’t actually help much.
I have parser helpers that use ReadOnlySpans over strings to prevent unnecessary allocations. However, here I’m adding to a C# mutable list and then converting to an FSharp (linked) list, which this language is more familiar with. Not optimal, but runtime was pretty good.
I’m not terribly good with F#, but I think I did ok for this challenge.
F#
// in another file: let concatenateLong (a:Int64) (b:Int64) : Int64 = let rec countDigits (n:int64) = if n = 0 then 0 else 1 + countDigits (n / (int64 10)) let bDigits = if b = 0 then 1 else countDigits b let multiplier = pown 10 bDigits |> int64 a * multiplier + b // challenge file type Operation = {Total:Int64; Inputs:Int64 list } let parse (s:ReadOnlySpan<char>) : Operation = let sep = s.IndexOf(':') let total = Int64.Parse(s.Slice(0, sep)) let inputs = System.Collections.Generic.List<Int64>() let right:ReadOnlySpan<char> = s.Slice(sep + 1).Trim() // because the Split function on a span returns a SpanSplitEnumerator, which is a ref-struct and can only live on the stack, // I can't use the F# list syntax here for range in right.Split(" ") do inputs.Add(Int64.Parse(sliceRange right range)) {Total = total; Inputs = List.ofSeq(inputs) } let part1Ops = [(+); (*)] let execute ops input = input |> PSeq.choose (fun op -> let total = op.Total let inputs = op.Inputs let variations = Variations(ops, inputs.Length - 1, GenerateOption.WithRepetition) variations |> Seq.tryFind (fun v -> let calcTotal = (inputs[0], inputs[1..], List.ofSeq(v)) |||> List.fold2 (fun acc n f -> f acc n) calcTotal = total ) |> Option.map(fun _ -> total) ) |> PSeq.fold (fun acc n -> acc + n) 0L let part1 input = (read input parse) |> execute part1Ops let part2Ops = [(+); (*); concatenateLong] let part2 input = (read input parse) |> execute part2Ops
The Gen0 garbage collection looks absurd, but Gen0 is generally considered “free”.
Method Mean Error StdDev Gen0 Gen1 Allocated Part1 19.20 ms 0.372 ms 0.545 ms 17843.7500 156.2500 106.55 MB Part2 17.94 ms 0.355 ms 0.878 ms 17843.7500 156.2500 106.55 MB V2 - concatenate numbers did little for the runtime, but did help with Gen1 garbage, but not the overall allocation.
Method Mean Error StdDev Gen0 Gen1 Allocated Part1 17.34 ms 0.342 ms 0.336 ms 17843.7500 125.0000 106.55 MB Part2 17.24 ms 0.323 ms 0.270 ms 17843.7500 93.7500 106.55 MB Uiua
This turned out to be reasonably easy in Uiua, though this solution relies on macros which maybe slow it down.
(edit: removing one macro sped it up quite a bit)
(edit2: Letting Uiua build up an n-dimensional array turned out to be the solution, though sadly my mind only works in 3 dimensions. Now runs against the live data in around 0.3 seconds.)
Data ← ⊜(□⊜⋕⊸(¬∈": "))⊸≠@\n "190: 10 19\n3267: 81 40 27\n83: 17 5\n156: 15 6\n7290: 6 8 6 15\n161011: 16 10 13\n192: 17 8 14\n21037: 9 7 18 13\n292: 11 6 16 20" Calib! ← ≡◇⊢▽⊸≡◇(∈♭/[^0]:°⊂) # Calibration targets which can be constructed from their values. &p/+Calib!⊃(+|×)Data &p/+Calib!⊃(+|×|+×ⁿ:10+1⌊ₙ₁₀,)Data
Thanks to your solution I learned more about how to use
reduce
:DMy solution did work for the example input but not for the actual one. When I went here and saw this tiny code block and you saying
This turned out to be reasonably easy
I was quite taken aback. And it’s so much better performance-wise too :D (well, until part 2 comes along in my case. Whatever this black magic is you used there is too high for my fried brain atm)
Haha, sorry about that, it does seem quite smug :-) I went into it expecting it to be a nightmare of boxes and dimensions, but finding it something I could deal with was a massive relief. Of course once I had a working solution I reversed it back into a multi-dimensional nightmare. That’s where the performance gains came from: about 10x speedup from letting Uiua build up as many dimensions as it needed before doing a final deshaping.
I enjoyed reading a different approach to this, and thanks for reminding me that
⋕$"__"
exists, that’s a great idiom to have up your sleeve.Let me know if there’s any bits of my solution that you’d like me to talk you through.
No worries, it does seem a lot less difficult in hindsight now, my mind just blanked at what I expected to be a lot more code :))
That performance improvement is amazing, I’ll definitely take a look at how that works in detail later. Just gotta recover from the mental stretch gymnastics trying to remember the state of the stack at different code positions
I feel like I need a Rosetta stone to read this code
thanks that indeed is a Rosetta stone
Haskell
A surprisingly gentle one for the weekend! Avoiding string operations for
concatenate
got the runtime down below one second on my machine.import Control.Arrow import Control.Monad import Data.List import Data.Maybe readInput :: String -> [(Int, [Int])] readInput = lines >>> map (break (== ':') >>> (read *** map read . words . tail)) equatable :: [Int -> Int -> Int] -> (Int, [Int]) -> Bool equatable ops (x, y : ys) = elem x $ foldM apply y ys where apply a y = (\op -> a `op` y) <$> ops concatenate :: Int -> Int -> Int concatenate x y = x * mag y + y where mag z = fromJust $ find (> z) $ iterate (* 10) 10 main = do input <- readInput <$> readFile "input07" mapM_ (print . sum . map fst . (`filter` input) . equatable) [ [(+), (*)], [(+), (*), concatenate] ]
Love the fold on the list monad to apply the operations.
Since all operations increase the accumulator, I tried putting a
guard (a <= x)
inapply
, but it doesn’t actually help all that much (0.65s -> 0.43s).0.65 -> 0.43 sounds pretty strong, isn’t that a one-fourth speedup?
Edit: I was able to achieve a 30% speed improvement using this on my solution
It’s not insignificant, sure, but I’d prefer 10x faster :D
Plus I’m not sure it’s worth the loss of generality and readability. It is tempting to spend hours chasing this kind of optimization though!
I wanted to this the way yo did, by repeatedly applying functions, but I didn’t dare to because I like to mess up and spend some minutes debugging signatures, may I ask what your IDE setup is for the LSP-Hints with Haskell?
Setting up on my PC was a little bit of a pain because it needed matchingghc
andghcide
versions, so I hadn’t bothered doing it on my Laptop yet.I use neovim with
haskell-tools.nvim
plugin. Forghc
,haskell-language-server
and others I usenix
which, among other benefits makes my development environment reproducible and all haskellPackages are built on the same version so there are no missmatches.But, as much as I love
nix
, there are probably easier ways to setup your environment.I just checked and I have haskell-tools.nvim on my PC but it somehow crashes the default config of the autocompletion for me, which I am too inexperienced to debug. I’ll try it nonetheless, since I don’t have autocompletion on the laptop anyways, thank you for the suggestion!
Ah, well, I have a bit of a weird setup. GHC is 9.8.4, built from git. I’m using HLS version 2.9.0.1 (again built from git) under Emacs with the LSP and flycheck packages. There are probably much easier ways of getting it to work :)
I envy emacs for all of its modes, but I don’t think I’m relearning the little I know about vi. Thank you for the answer on the versions and building!
Haskell
import Control.Arrow import Data.Char import Text.ParserCombinators.ReadP numP = read <$> munch1 isDigit parse = endBy ((,) <$> (numP <* string ": ") <*> sepBy numP (char ' ')) (char '\n') valid n [m] = m == n valid n (x : xs) = n > 0 && valid (n - x) xs || (n `mod` x) == 0 && valid (n `div` x) xs part1 = sum . fmap fst . filter (uncurry valid . second reverse) concatNum r = (+r) . (* 10 ^ digits r) where digits = succ . floor . logBase 10 . fromIntegral allPossible [n] = [n] allPossible (x:xs) = ((x+) <$> rest) ++ ((x*) <$> rest) ++ (concatNum x <$> rest) where rest = allPossible xs part2 = sum . fmap fst . filter (uncurry elem . second (allPossible . reverse)) main = getContents >>= print . (part1 &&& part2) . fst . last . readP_to_S parse
Oooh, some nice number theory going on there!
Python
It is a tree search
def parse_input(path): with path.open("r") as fp: lines = fp.read().splitlines() roots = [int(line.split(':')[0]) for line in lines] node_lists = [[int(x) for x in line.split(':')[1][1:].split(' ')] for line in lines] return roots, node_lists def construct_tree(root, nodes, include_concat): levels = [[] for _ in range(len(nodes)+1)] levels[0] = [(str(root), "")] # level nodes are tuples of the form (val, operation) where both are str # val can be numerical or empty string # operation can be *, +, || or empty string for indl, level in enumerate(levels[1:], start=1): node = nodes[indl-1] for elem in levels[indl-1]: if elem[0]=='': continue if elem[0][-len(str(node)):] == str(node) and include_concat: levels[indl].append((elem[0][:-len(str(node))], "||")) if (a:=int(elem[0]))%(b:=int(node))==0: levels[indl].append((str(int(a/b)), '*')) if (a:=int(elem[0])) - (b:=int(node))>0: levels[indl].append((str(a - b), "+")) return levels[-1] def solve_problem(file_name, include_concat): roots, node_lists = parse_input(Path(cwd, file_name)) valid_roots = [] for root, nodes in zip(roots, node_lists): top = construct_tree(root, nodes[::-1], include_concat) if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or (x[0]=='' and x[1]=='||') for x in top): valid_roots.append(root) return sum(valid_roots)
I asked ChatGPT to explain your code and mentioned you said it was a binary search. idk why, but it output a matter of fact response that claims you were wrong. lmao, I still don’t understand how your code works
This code doesn’t perform a classic binary search. Instead, it uses each input node to generate new possible states or “branches,” forming a tree of transformations. At each level, it tries up to three operations on the current value (remove digits, divide, subtract). These expansions create multiple paths, and the code checks which paths end in a successful condition. While the author may have described it as a “binary search,” it’s more accurately a state-space search over a tree of possible outcomes, not a binary search over a sorted data structure.
I understand it now! I took your solution and made it faster. it is now like 36 milliseconds faster for me. which is interesting because if you look at the code. I dont process the entire list of integers. I sometimes stop prematurely before the next level, clear it, and add the root. I don’t know why but it just works for my input and the test input.
code
def main(input_data): input_data = input_data.replace('\r', '') parsed_data = {int(line[0]): [int(i) for i in line[1].split()[::-1]] for line in [l.split(': ') for l in input_data.splitlines()]} part1 = 0 part2 = 0 for item in parsed_data.items(): root, num_array = item part_1_branches = [set() for _ in range(len(num_array)+1)] part_2_branches = [set() for _ in range(len(num_array)+1)] part_1_branches[0].add(root) part_2_branches[0].add(root) for level,i in enumerate(num_array): if len(part_1_branches[level]) == 0 and len(part_2_branches[level]) == 0: break for branch in part_1_branches[level]: if branch == i: part_1_branches[level+1] = set() # clear next level to prevent adding root again part1 += root break if branch % i == 0: part_1_branches[level+1].add(branch//i) if branch - i > 0: part_1_branches[level+1].add(branch-i) for branch in part_2_branches[level]: if branch == i or str(branch) == str(i): part_2_branches[level+1] = set() # clear next level to prevent adding root again part2 += root break if branch % i == 0: part_2_branches[level+1].add(branch//i) if branch - i > 0: part_2_branches[level+1].add(branch-i) if str(i) == str(branch)[-len(str(i)):]: part_2_branches[level+1].add(int(str(branch)[:-len(str(i))])) print("Part 1:", part1, "\nPart 2:", part2) return [part1, part2] if __name__ == "__main__": with open('input', 'r') as f: main(f.read())
however what I notice is that the parse_input causes it to be the reason why it is slower by 20+ milliseconds. I find that even if I edited your solution like so to be slightly faster, it is still 10 milliseconds slower than mine:
code
def parse_input(): with open('input',"r") as fp: lines = fp.read().splitlines() roots = [int(line.split(':')[0]) for line in lines] node_lists = [[int(x) for x in line.split(': ')[1].split(' ')] for line in lines] return roots, node_lists def construct_tree(root, nodes): levels = [[] for _ in range(len(nodes)+1)] levels[0] = [(root, "")] # level nodes are tuples of the form (val, operation) where both are str # val can be numerical or empty string # operation can be *, +, || or empty string for indl, level in enumerate(levels[1:], start=1): node = nodes[indl-1] for elem in levels[indl-1]: if elem[0]=='': continue if (a:=elem[0])%(b:=node)==0: levels[indl].append((a/b, '*')) if (a:=elem[0]) - (b:=node)>0: levels[indl].append((a - b, "+")) return levels[-1] def construct_tree_concat(root, nodes): levels = [[] for _ in range(len(nodes)+1)] levels[0] = [(str(root), "")] # level nodes are tuples of the form (val, operation) where both are str # val can be numerical or empty string # operation can be *, +, || or empty string for indl, level in enumerate(levels[1:], start=1): node = nodes[indl-1] for elem in levels[indl-1]: if elem[0]=='': continue if elem[0][-len(str(node)):] == str(node): levels[indl].append((elem[0][:-len(str(node))], "||")) if (a:=int(elem[0]))%(b:=int(node))==0: levels[indl].append((str(int(a/b)), '*')) if (a:=int(elem[0])) - (b:=int(node))>0: levels[indl].append((str(a - b), "+")) return levels[-1] def solve_problem(): roots, node_lists = parse_input() valid_roots_part1 = [] valid_roots_part2 = [] for root, nodes in zip(roots, node_lists): top = construct_tree(root, nodes[::-1]) if any((x[0]==1 and x[1]=='*') or (x[0]==0 and x[1]=='+') for x in top): valid_roots_part1.append(root) top = construct_tree_concat(root, nodes[::-1]) if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or (x[0]=='' and x[1]=='||') for x in top): valid_roots_part2.append(root) return sum(valid_roots_part1),sum(valid_roots_part2) if __name__ == "__main__": print(solve_problem())
Wow I got thrashed by chatgpt. Strictly speaking that is correct, it is more akin to Tree Search. But even then not strictly because in tree search you are searching through a list of objects that is known, you build a tree out of it and based on some conditions eliminate half of the remaining tree each time. Here I have some state space (as chatgpt claims!) and again based on applying certain conditions, I eliminate some portion of the search space successively (so I dont have to evaluate that part of the tree anymore). To me both are very similar in spirit as both methods avoid evaluating some function on all the possible inputs and successively chops off a fraction of the search space. To be more correct I will atleast replace it with tree search though, thanks. And thanks for taking a close look at my solution and improving it.
idk why my gpt decided to be like that. I expected a long winded response with a little bit of ai hallucinations. I was flabbergasted, and just had to post it.
I seemingly realized that working forward through the list of integers was inefficient for me to do, and I was using multiprocessing to do it too! which my old solution took less than 15 seconds for my input. your solution to reverse the operations and eliminate paths was brilliant and made it solve it in milliseconds without spinning up my fans, lol
C
Big integers and overflow checking, what else is there to say 😅
Code
#include "common.h" /* returns 1 on sucess, 0 on overflow */ static int concat(uint64_t a, uint64_t b, uint64_t *out) { uint64_t mul; for (mul=1; mul<=b; mul*=10) ; return !__builtin_mul_overflow( mul, a, out) && !__builtin_add_overflow(*out, b, out); } static int recur(uint64_t expect, uint64_t acc, uint64_t arr[], int n, int p2) { uint64_t imm; return n < 1 ? acc == expect : acc >= expect ? 0 : recur(expect, acc + arr[0], arr+1, n-1, p2) || recur(expect, acc * arr[0], arr+1, n-1, p2) || (p2 && concat(acc, arr[0], &imm) && recur(expect, imm, arr+1, n-1, p2)); } int main(int argc, char **argv) { char buf[128], *tok, *rest; uint64_t p1=0, p2=0, arr[32], expect; int n; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while ((rest = fgets(buf, sizeof(buf), stdin))) { assert(strchr(buf, '\n')); expect = atoll(strsep(&rest, ":")); for (n=0; (tok = strsep(&rest, " ")); n++) { assert(n < (int)LEN(arr)); arr[n] = atoll(tok); } p1 += recur(expect, 0, arr, n, 0) * expect; p2 += recur(expect, 0, arr, n, 1) * expect; } printf("07: %"PRIu64" %"PRIu64"\n", p1, p2); return 0; }
Uiua
Credits to @mykl@lemmy.world for the approach of using
reduce
and also how to split the input by multiple characters.
I can happily say that I learned quite a bit today, even though the first part made me frustrated enough that I went searching for other approaches ^^Part two just needed a simple modification. Changing how the input is parsed and passed to the adapted function took longer than changing the function itself actually.
Run with example input here
PartOne ← ( &rs ∞ &fo "input-7.txt" ⊜□≠@\n. ≡◇(⊜□≠@:.) ≡⍜⊡⋕0 ≡⍜(°□⊡1)(⊜⋕≠@ .) ⟜(⊡0⍉) # own attempt, produces a too low number # ≡(:∩°□°⊟ # ⍣(⍤.◡⍣(1⍤.(≤/×)⍤.(≥/+),,)0 # ⊙¤⋯⇡ⁿ:2-1⊸⧻ # ⊞(⍥(⟜⍜(⊙(↙2))(⨬+×⊙°⊟⊡0) # ↘1 # )⧻. # ⍤.=0⧻. # ) # ∈♭◌ # )0) # reduce approach found on the programming.dev AoC community by mykl@lemmy.world ≡(◇(∈/(◴♭[⊃(+|×)]))⊡0:°⊂) °□/+▽ ) PartTwo ← ( &rs ∞ &fo "input-7.txt" ⊜(□⊜⋕¬∈": ".)≠@\n. ⟜≡◇⊢ ≡◇(∈/(◴♭[≡⊃⊃(+|×|⋕$"__")]):°⊂) °□/+▽ ) &p "Day 7:" &pf "Part 1: " &p PartOne &pf "Part 2: " &p PartTwo
Team Uiua in the house!
(╯°□°)╯︵ ┻━┻
Hell yeah!
┻━┻︵ (°□°)/ ︵ ┻━┻
Factor
spoiler
TUPLE: equation value numbers ; C: <equation> equation : get-input ( -- equations ) "vocab:aoc-2024/07/input.txt" utf8 file-lines [ split-words unclip but-last string>number swap [ string>number ] map <equation> ] map ; : possible-quotations ( funcs numbers -- quots ) dup length 1 - swapd all-selections [ unclip swap ] dip [ zip concat ] with map swap '[ _ prefix >quotation ] map ; : possibly-true? ( funcs equation -- ? ) [ numbers>> possible-quotations ] [ value>> ] bi '[ call( -- n ) _ = ] any? ; : solve ( funcs -- n ) get-input [ possibly-true? ] with filter [ value>> ] map-sum ; : part1 ( -- n ) { + * } solve ; : _|| ( m n -- mn ) [ number>string ] bi@ append string>number ; : part2 ( -- n ) { + * _|| } solve ;
Slow and dumb gets it done! I may revisit this when I give up on future days.
Haskell
I’m not very proud, I copied my code for part two.
import Control.Arrow hiding (first, second) import qualified Data.List as List import qualified Data.Char as Char parseLine l = (n, os) where n = read . takeWhile (Char.isDigit) $ l os = map read . drop 1 . words $ l parse :: String -> [(Int, [Int])] parse s = map parseLine . takeWhile (/= "") . lines $ s insertOperators target (r:rs) = any (target ==) (insertOperators' r rs) insertOperators' :: Int -> [Int] -> [Int] insertOperators' acc [] = [acc] insertOperators' acc (r:rs) = insertOperators' (acc+r) rs ++ insertOperators' (acc*r) rs insertOperators2 target (r:rs) = any (target ==) (insertOperators2' r rs) insertOperators2' :: Int -> [Int] -> [Int] insertOperators2' acc [] = [acc] insertOperators2' acc (r:rs) = insertOperators2' (acc+r) rs ++ insertOperators2' (acc*r) rs ++ insertOperators2' concatN rs where concatN = read (show acc ++ show r) part1 ls = filter (uncurry insertOperators) >>> map fst >>> sum $ ls part2 ls = filter (uncurry insertOperators2) >>> map fst >>> sum $ ls main = getContents >>= print . (part1 &&& part2) . parse
If you get the right answer, it’s ok 👍
Made a couple of attempts to munge the input data into some kind of binary search tree, lost some time to that, then threw my hands into the air and did a more naïve sort-of breadth-first search instead. Which turned out to be better for part 2 anyway.
Also, maths. Runs in just over a hundred milliseconds when usingAsParallel
, around half a second without.C#
List<(long, int[])> data = new List<(long, int[])>(); public void Input(IEnumerable<string> lines) { foreach (var line in lines) { var parts = line.Split(':', StringSplitOptions.TrimEntries); data.Add((long.Parse(parts.First()), parts.Last().Split(' ').Select(int.Parse).ToArray())); } } public void Part1() { var correct = data.Where(kv => CalcPart(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum(); Console.WriteLine($"Correct: {correct}"); } public void Part2() { var correct = data.AsParallel().Where(kv => CalcPart2(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum(); Console.WriteLine($"Correct: {correct}"); } public bool CalcPart(long res, Span<int> num, long carried = 0) { var next = num[0]; if (num.Length == 1) return res == carried + next || res == carried * next; return CalcPart(res, num.Slice(1), carried + next) || CalcPart(res, num.Slice(1), carried * next); } public bool CalcPart2(long res, Span<int> num, long carried = 0) { var next = num[0]; // Get the 10 logarithm for the next number, expand the carried value by 10^<next 10log + 1>, add the two together // For 123 || 45 // 45 ⇒ 10log(45) + 1 == 2 // 123 * 10^2 + 45 == 12345 long combined = carried * (long)Math.Pow(10, Math.Floor(Math.Log10(next) + 1)) + next; if (num.Length == 1) return res == carried + next || res == carried * next || res == combined; return CalcPart2(res, num.Slice(1), carried + next) || CalcPart2(res, num.Slice(1), carried * next) || CalcPart2(res, num.Slice(1), combined); }
you meant depth first, right? since you’re using recursion
That is true, I’ve evidently not had enough coffee yet this morning.
C#
public class Day07 : Solver { private ImmutableList<(long, ImmutableList<long>)> equations; public void Presolve(string input) { equations = input.Trim().Split("\n") .Select(line => line.Split(": ")) .Select(split => (long.Parse(split[0]), split[1].Split(" ").Select(long.Parse).ToImmutableList())) .ToImmutableList(); } private bool TrySolveWithConcat(long lhs, long head, ImmutableList<long> tail) { var lhs_string = lhs.ToString(); var head_string = head.ToString(); return lhs_string.Length > head_string.Length && lhs_string.EndsWith(head_string) && SolveEquation(long.Parse(lhs_string.Substring(0, lhs_string.Length - head_string.Length)), tail, true); } private bool SolveEquation(long lhs, ImmutableList<long> rhs, bool with_concat = false) { if (rhs.Count == 1) return lhs == rhs[0]; long head = rhs[rhs.Count - 1]; var tail = rhs.GetRange(0, rhs.Count - 1); return (SolveEquation(lhs - head, tail, with_concat)) || (lhs % head == 0) && SolveEquation(lhs / head, tail, with_concat) || with_concat && TrySolveWithConcat(lhs, head, tail); } public string SolveFirst() => equations .Where(eq => SolveEquation(eq.Item1, eq.Item2)) .Select(eq => eq.Item1) .Sum().ToString(); public string SolveSecond() => equations .Where(eq => SolveEquation(eq.Item1, eq.Item2, true)) .Select(eq => eq.Item1) .Sum().ToString(); }
python
45s on my machine for first shot, trying to break my will to brute force 😅. I’ll try improving on it in a bit after I smoke another bowl and grab another drink.
solution
import itertools import re import aoc def ltr(e): r = int(e[0]) for i in range(1, len(e), 2): o = e[i] n = int(e[i + 1]) if o == '+': r += n elif o == '*': r *= n elif o == '||': r = int(f"{r}{n}") return r def pl(l, os): d = [int(x) for x in re.findall(r'\d+', l)] t, ns = d[0], d[1:] ops = list(itertools.product(os, repeat=len(ns) - 1)) for o in ops: e = str(ns[0]) for i, op in enumerate(o): e += f" {op} {ns[i + 1]}" r = ltr(e.split()) if r == t: return r return 0 def one(): lines = aoc.get_lines(7) acc = 0 for l in lines: acc += pl(l, ['+', '*']) print(acc) def two(): lines = aoc.get_lines(7) acc = 0 for l in lines: acc += pl(l, ['+', '*', '||']) print(acc) one() two()
What a horrible way to name variables
a
e
o
, Killer Tofu. That’s all I can think of reading this code.It’s not a long lived project, it’s a puzzle, and once solved never needs to run again. My objective here is to get the correct answer, not win a style contest.
Can you provide a link to your solution? I’d like to check it out.
My initial comment was a bit harsh, I’m sorry for that. It was meant to be a bit of a joke. Anyway here’s my code. Do note that I don’t do the challenges timed so I have a bit more time to name my variables accordingly. Takes 35 seconds to run on a pc with a AMD Ryzen 5 5600
import sys from tqdm import tqdm input = sys.stdin.read() def all_operator_permutations(operator_count): if operator_count == 0: return [[]] smaller_permutations = all_operator_permutations(operator_count-1) return [ *[['+', *ops] for ops in smaller_permutations], *[['*', *ops] for ops in smaller_permutations], *[['||', *ops] for ops in smaller_permutations], ] def test_operators(ops, values): res = values.pop(0) for op in ops: match op: case '*': res *= values.pop(0) case '+': res += values.pop(0) case '||': res = int(f"{res}{values.pop(0)}") return res total_calibration_result = 0 for line in tqdm(input.splitlines()[:]): target, *tail = line.split(':') target = int(target) values = [int(val) for val in tail[0].split()] all_perms = all_operator_permutations(len(values) - 1) ops = all_perms.pop() while True: res = test_operators(ops, values.copy()) if res == target: total_calibration_result += target break if not all_perms: break ops = all_perms.pop() print(total_calibration_result)
Nim
Bruteforce, my beloved.
Wasted too much time on part 2 trying to make combinations iterator (it was very slow). In the end solved both parts with
3^n
andtoTernary
.Runtime: 1.5s
func digits(n: int): int = result = 1; var n = n while (n = n div 10; n) > 0: inc result func concat(a: var int, b: int) = a = a * (10 ^ b.digits) + b func toTernary(n: int, len: int): seq[int] = result = newSeq[int](len) if n == 0: return var n = n for i in 0..<len: result[i] = n mod 3 n = n div 3 proc solve(input: string): AOCSolution[int, int] = for line in input.splitLines(): let parts = line.split({':',' '}) let res = parts[0].parseInt var values: seq[int] for i in 2..parts.high: values.add parts[i].parseInt let opsCount = values.len - 1 var solvable = (p1: false, p2: false) for s in 0 ..< 3^opsCount: var sum = values[0] let ternary = s.toTernary(opsCount) for i, c in ternary: case c of 0: sum *= values[i+1] of 1: sum += values[i+1] of 2: sum.concat values[i+1] else: raiseAssert"!!" if sum == res: if ternary.count(2) == 0: solvable.p1 = true solvable.p2 = true if solvable == (true, true): break if solvable.p1: result.part1 += res if solvable.p2: result.part2 += res
Java
Today was pretty easy one but for some reason I spent like 20 minutes overthinking part 2 when all it needed was one new
else if
. I initially through the concatenation operator would take precedence even tho it clearly says “All operators are still evaluated left-to-right” in the instructions…I’m sure there are optimizations to do but using parallelStreams it only takes around 300ms total on my machine so there’s no point really
The code
import java.io.IOException; import java.nio.charset.StandardCharsets; import java.nio.file.Files; import java.nio.file.Path; import java.util.Arrays; import java.util.List; public class Day7 { public static void main(final String[] _args) throws IOException { final List<Equation> equations = Files.readAllLines(Path.of("2024\\07\\input.txt"), StandardCharsets.UTF_8).stream() .map(line -> line.split(":\\s")) .map(line -> new Equation( Long.parseLong(line[0]), Arrays.stream(line[1].split("\\s")) .map(Integer::parseInt) .toArray(Integer[]::new) ) ).toList(); final char[] part1Operators = {'+', '*'}; System.out.println("Part 1: " + equations.parallelStream() .mapToLong(equation -> getResultIfPossible(equation, part1Operators)) .sum() ); final char[] part2Operators = {'+', '*', '|'}; System.out.println("Part 2: " + equations.parallelStream() .mapToLong(equation -> getResultIfPossible(equation, part2Operators)) .sum() ); } private static Long getResultIfPossible(final Equation equation, final char[] operators) { final var permutations = Math.pow(operators.length, equation.values.length - 1); for (int i = 0; i < permutations; i++) { long result = equation.values[0]; int count = i; for (int j = 0; j < equation.values.length - 1; j++) { // If the result is already larger than the expected one, we can short circuit here to save some time if (result > equation.result) { break; } final char operator = operators[count % operators.length]; count /= operators.length; if (operator == '+') { result += equation.values[j + 1]; } else if (operator == '*') { result *= equation.values[j + 1]; } else if (operator == '|') { result = Long.parseLong(String.valueOf(result) + String.valueOf(equation.values[j + 1])); } else { throw new RuntimeException("Unsupported operator " + operator); } } if (result == equation.result) { return result; } } return 0L; } private static record Equation(long result, Integer[] values) {} }
Dart
Suspiciously easy, so let’s see how tomorrow goes… (edit: forgot to put the language! Dart for now, thinking about Uiua later)
import 'package:more/more.dart'; var ops = [(a, b) => a + b, (a, b) => a * b, (a, b) => int.parse('$a$b')]; bool canMake(int target, List<int> ns, int sofar, dynamic ops) { if (ns.isEmpty) return target == sofar; for (var op in ops) { if (canMake(target, ns.sublist(1), op(sofar, ns.first), ops)) return true; } return false; } solve(List<String> lines, dynamic ops) { var sum = 0; for (var line in lines.map((e) => e.split(' '))) { var target = int.parse(line.first.skipLast(1)); var ns = line.skip(1).map(int.parse).toList(); sum += (canMake(target, ns.sublist(1), ns.first, ops)) ? target : 0; } return sum; } part1(List<String> lines) => solve(lines, ops.sublist(0, 2)); part2(List<String> lines) => solve(lines, ops);