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
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 ;
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]
]
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 matching ghc and ghcide versions, so I hadn’t bothered doing it on my Laptop yet.
I use neovim with haskell-tools.nvim plugin. For ghc, haskell-language-server and others I use nix 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 :)
Since all operations increase the accumulator, I tried putting a guard (a <= x) in apply, 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
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()
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)
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 using AsParallel, 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);
}
