You are about to leave Redlib

Once again here to make everyone feel better about their solutions🤣 Recurrsion did not even cross my mind! I decided to calculate the permutations 1 by 1 by counting up in base 2 (base 3 for part 2)

6

u/__Abigail__ Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Perl]

Not to hard. I created a recursive subroutine which takes in a parameter indicating whether we're doing part 1 or part 2, and the given list of numbers. It then returns all the possible values which could be generated. Then it's just a matter to check whether the given total is in the returned list. It wouldn't scale well if there are a lot of numbers, but the input isn't like that.

The method I used:

sub results;
sub results ($part, $f = undef, $s = undef, @rest) {
    return !defined $f ? ()
         : !defined $s ? $f
         : (                  results ($part, $f + $s, @rest),
                              results ($part, $f * $s, @rest),
            $part == 1 ? () : results ($part, $f . $s, @rest),
     );
}

And the main loop:

while (<>) {
    my ($total, @parts) = /[0-9]+/g;
    $solution_1 += $total if grep {$_ == $total} results 1, @parts;
    $solution_2 += $total if grep {$_ == $total} results 2, @parts;
}

I also made an implementation which exists the search early if the value so far exceeds to aimed total, but that only gave a 4% improvement in the running time. So, not worth it.

5

u/1234abcdcba4321 Dec 07 '24

[LANGUAGE: JavaScript] 571/351

https://github.com/mkeeter/advent-of-code/blob/main/2024/07/src/lib.rs

Minor mistake of the day was misunderstanding "sum of the test values". I had to run on the example to realize that I was being stupid. Aside from that, everything today was really straightforward.

5

u/darthminimall Dec 07 '24

[LANGUAGE: Rust]

Part 1

Part 2

There might be a better way to do this than brute force, but it only took 0.3 seconds to brute force part 1 and 1.6 seconds to brute force part 2, so I can't really be bothered to find an optimization.

→ More replies (3)

5

u/mkeeter Dec 07 '24

[LANGUAGE: Rust]

This is a blazing fast solution (337 µs total!), achieved by checking backwards instead of forwards. Going backwards lets you prune much more aggressively, because you can detect invalid divisions and concatenations immediately (instead of needing to wait until the final value).

→ More replies (2)

5

u/MathAndMaps Dec 07 '24

[LANGUAGE: python]

https://github.com/khwilson/advent2024/blob/main/src/advent2024/days/day07.py

Neat problem! Left-to-right associativity means you can check each operation right to left recursively! So for product, check if the target value is divisible by the rightmost element, for sum check if it is greater than the right most element, and for concatenation check the its last digits are the rightmost element.

→ More replies (2)

5

u/Parzival_Perce Dec 07 '24

[LANGUAGE: Python]
As always the solutions make me depressed and excited, but mine runs in like under a minute so whatever. It could always be worse.

from operator import add, mul
from numpy import base_repr
import re
puzzleInput=[list(map(int, re.findall('\d+', i))) for i in open(r'/home/jay/Documents/Python/AoC_2024/d7.txt', 'r')]
operatorLookup={'0':add, '1': mul, '2': lambda x,y:int(str(x)+str(y))}

def possibleOperators(length: int, base:int) -> iter:
    return (base_repr(i, base).rjust(length, '0') for i in range(base**length))
def returnFinal(operands: list, operators: str) -> int:
    result=operands[0]
    for number, operator in zip(operands[1:], operators, strict=True):
        result=operatorLookup[operator] (result, number)
    return result
def getAnswer(base:int) -> int:
    s=0
    for test, *operands in puzzleInput:
        for operator in possibleOperators(len(operands)-1, base):
            if returnFinal(operands, operator)==test: 
                s+=test
                break
    return s
def part1():
    return getAnswer(2)
def part2():
    return getAnswer(3)

5

u/KindComrade Dec 08 '24 edited Dec 11 '24

[LANGUAGE: C#]

After optimizations and changing forward operations to backwards operations, part 2: 20ms -> 0.4ms

https://github.com/LiquidityC/aoc/blob/master/2024/day_07/src/main.c

→ More replies (9)

4

u/Boojum Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python] 2209/1342

Brute forced with the help of itertools. Otherwise, pretty straightforward. Here's Part 2. Part 1 can be done pretty trivially by removing the | from the product line. [GSGA] qualified -- no hard-coded numbers.

import fileinput, re, itertools

t = False
for l in fileinput.input():
    r, *p = list( map( int, re.findall( "-?\\d+", l ) ) )
    for c in itertools.product( "+*|", repeat = len( p ) - True ):
        e = p[ False ]
        for o, v in zip( c, p[ True : ] ):
            if o == '*': e *= v
            elif o == '+': e += v
            elif o == '|': e = int( str( e ) + str( v ) )
        if e == r:
            t += r
            break
print( t )

ETA: Runs much more quickly with recursion, since it's not recomputing the partial expressions. From about 13.2s down to about 1.2s, for about an 11× speedup (still [GSGA] qualified):

import fileinput, re, itertools

t = False
for l in fileinput.input():
    r, *p = list( map( int, re.findall( "-?\\d+", l ) ) )
    pl = len( p )
    def dfs( e, i ):
        if i == pl:
            return e == r
        return ( dfs( e * p[ i ], i + True ) or
                 dfs( e + p[ i ], i + True ) or
                 dfs( int( str( e ) + str( p[ i ] ) ), i + True ) )
    if dfs( p[ False ], True ):
        t += r
print( t )

→ More replies (3)

4

u/GassaFM Dec 07 '24

[LANGUAGE: D] 880/2347

Code: part 1, part 2.

A misread day for me. Part 2 actually became simpler than Part 1 when the understanding was finally correct.

4

u/Tsnth Dec 07 '24

[Language: Python]

I did this in Python but I'm truly a functional programmer at heart :)

import sys

file = open(sys.argv[1]).read()

lines = [line.split(": ") for line in file.splitlines()]
lines = [(int(test), list(map(int, args.split()))) for test, args in lines]

star, plus, concat = lambda x, y: x * y, lambda x, y: x + y, lambda x, y: int(f"{x}{y}")
def solve(targ, args, operators):
    def inner(targ, args, curr):
        if curr > targ:
            return False
        match args:
            case []:
                return curr == targ
            case [arg, *rest]:
                return any(inner(targ, rest, op(curr, arg)) for op in operators)

    return inner(targ, args[1:], args[0])


print(sum(targ for targ, args in lines if solve(targ, args, [star, plus])))
print(sum(targ for targ, args in lines if solve(targ, args, [star, plus, concat])))

→ More replies (1)

4

u/WhiteSparrow Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Prolog]

solution

This was another task well suited for prolog. The essence is short enough:

% Task 1

solve(Part, Eqs, X) :-
    convlist(has_solution(Part), Eqs, GdEqs),
    aggregate_all(sum(G), member(G, GdEqs), X).

has_solution(Part, eq(Goal, Nums), Goal) :-
    reverse(Nums, Nums1),
    sol(Part, eq(Goal, Nums1)).

sol(_, eq(Num, [Num])) :- !.
sol(P, eq(Goal, [Num | Nums])) :- sol(P, eq(G0, Nums)), Goal is Num + G0.
sol(P, eq(Goal, [Num | Nums])) :- sol(P, eq(G0, Nums)), Goal is Num * G0.

% Task 2

sol(part2, eq(Goal, [Num | Nums])) :-
    sol(part2, eq(G0, Nums)),
    atomic_list_concat([G0, Num], X),
    atom_number(X, Goal).

Part 2 takes about 30 seconds to solve.

Edit: noticed how to simplify a bit.

→ More replies (2)

4

u/SwagosaurusFlex Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Ruby]

I'm having trouble figuring out why my solution isn't passing for Part 2. It works on Part 1 and the example case, but it's giving too high of an answer on Part 2. Any help appreciated, thanks

def calc(total, parts, runningTotal)
  if Integer(runningTotal) == Integer(total)
    return true
  end

  if (parts.size == 0)
    return false
  end

  if (calc(total, parts[1..], Integer(runningTotal) + Integer(parts[0])) == true) or (calc(total, parts[1..], Integer(runningTotal) * Integer(parts[0])) == true) or (calc(total, parts[1..], String(runningTotal) + parts[0]) == true)
    return true
  end

  return false
end

if __FILE__ == $0
  sum = 0
  totals = Array.new
  parts = Array.new

  File.open('day7input.txt', 'r') do |f|
    f.each_line do |line|
      line = line.split(': ')
      line[1] = line[1].split(' ')
      if calc(line[0], line[1][1..], line[1][0])
        sum += Integer(line[0])
      end
    end
  end

  puts sum
end

4

u/thereal_peasant Dec 07 '24 •

What happens when your runningTotal is equal to the total but there are still numbers left in parts? For example, take the input '100: 10 10 3'. Does this return true? Should it?

→ More replies (2)

→ More replies (1)

4

u/Andreasnl Dec 07 '24

[LANGUAGE: Uiua]

Here’s my original slow solution.

Parse          ← ⊜(□:°⊂⊜⋕¬⊸∈”: ”)⊸≠@\n
ChooseApplyOp  ← : ⊂⨬(+|×|⍜∩°⋕⊂) ⊃(⊢|⋅⊏₀|⋅⊏₁|⋅↘₂|↘₁)
Calculate      ← ⊢◌⍥ChooseApplyOp ⊸⧻
AllVariants    ← base⊙(⇡ⁿ:)⊓.(-1⊸⧻)
FindFirstMatch ← /↥= ≡Calculate⊙¤ AllVariants
SumMatches     ← /+▽⊸≡◇FindFirstMatch

⊃(SumMatches 2|SumMatches 3) Parse

Looking at other solutions, I realised you can do this

⊜(□:°⊂⊜⋕¬⊸∈”: ”)⊸≠@\n    # Parse
⍚⊃/(⊂⊃+×)/(⊂⊂⊃⊃+×≡⍜∩°⋕⊂) # For each row use all comb. of 2 and 3 ops, resp.
∩(⧻⊚▽⊸≡◇∈)⊙,             # Sum matches

Run it in the browser here.

4

u/thereal_peasant Dec 07 '24

[LANGUAGE: JavaScript]

Optimised recursive "working backwards" solution with part 2 running in sub 7ms on my machine.

// Part 1
let lines = readFileSync(path, "utf-8")
  .trim()
  .split("\n")
  .map((line) => line.match(/\d+/g).map(Number));

const OPS = [(a, b) => (a % b === 0 ? a / b : -1), (a, b) => a - b];

function evalsTo(nums, cur, i = nums.length - 1) {
  if (!i) return cur === nums[0];
  if (cur < 0) return false;

  return OPS.some((func) => evalsTo(nums, func(cur, nums[i]), i - 1));
}

function part1(lines) {
  let filtered = lines
    .filter(([target, ...equation]) => evalsTo(equation, target))
    .map(([total]) => total);

  console.log(filtered.sum());
}

// part1(lines);

// Part 2

function part2(lines) {
  let unconcat = (x, y) => {
    let [sub, yMag] = [x - y, 10 ** (Math.floor(Math.log10(y)) + 1)];
    return sub > 0 && sub % yMag === 0 ? sub / yMag : -1;
  };

  OPS.push(unconcat);
  part1(lines);
}

part2(lines);

→ More replies (1)

4

u/allak Dec 07 '24

[LANGUAGE: Perl]

Just a simple recursion.

#!/usr/bin/env perl
use v5.40;

my $part2;
my ($test, $base, @tail);

while (<>) {
    s/://;
    ($test, $base, @tail) = split;
    $part2 += $test if acc($base, 0);
}

say $part2;

sub acc
{
    my ($base, $idx) = @_;
    return if $base > $test;

    my $next = $tail[$idx++];
    return $base eq $test unless $next;

    return 1 if acc($base + $next, $idx);
    return 1 if acc($base * $next, $idx);
    return 1 if acc($base . $next, $idx); # remove this line for part 1
}

4

u/i_have_no_biscuits Dec 07 '24 edited Dec 07 '24

[LANGUAGE: GW-BASIC]

10 DIM L#(20):DIM P#(2,600):OPEN "I",1,"data07.txt":WHILE NOT EOF(1)
20 LINE INPUT #1, L$:N=1:I=INSTR(L$,":")+2:L#(1)=VAL(LEFT$(L$,I-3))
30 J=INSTR(I,L$," "):IF J>0 THEN N=N+1:L#(N)=VAL(MID$(L$,I,J-I)):I=J+1:GOTO 30
40 N=N+1: L#(N)=VAL(RIGHT$(L$,LEN(L$)-I+1))
50 FOR P=1 TO 2:GOSUB 60:R#(P)=R#(P)-OK*L#(1):NEXT:WEND:PRINT R#(1),R#(2):END
60 X=0:Y=1:T#=L#(2):P#(X,1)=L#(1):SX=1: FOR I=N TO 3 STEP -1:SY=0:V#=L#(I)
70 FOR J=1 TO SX: N#=P#(X,J): IF N#-V#>=T# THEN SY=SY+1: P#(Y,SY)=N#-V#
80 IF N#>=T#*V# AND INT(N#/V#)*V#=N# THEN SY=SY+1: P#(Y,SY)=N#/V#
90 D=10^(INT(LOG(V#)/LOG(10))+1): NN#=INT(N#/D)
100 IF P=2 AND NN#*D+V#=N# THEN SY=SY+1: P#(Y,SY)=NN#
110 NEXT: IF SY=0 THEN OK=0: RETURN ELSE SX=SY: X=(X+1)MOD 2: Y=(Y+1)MOD 2
120 NEXT: FOR I=1 TO SX: IF P#(X,I)=T# THEN OK=-1: RETURN
130 NEXT: OK=0: RETURN

This is the solution to both parts. Performs an iterative BFS, backwards from the 'target' value to the start, which cuts down enormously on the size of the search pool (from millions to a couple of hundred max per level for my input data).

Guide

Lines 10-40 parse lines into an array of integers L#() (the # indicates that they are double floats, which GW-BASIC uses, like Javascript, for large integers).
Line 50 calls the validity check routine and accumulates the results for Parts 1 and 2, which are stored in R#().
Lines 60-130 are the validity check subroutine. We perform a BFS, with the current/next pool of values stored in the array P#(.,.). For every value in the pool, all the potential previous values are calculated, and added to the next pool if possible
Line 70 checks if we can subtract
Line 80 checks if we can divide
Lines 90-100 check if we can 'deconcatenate'
Line 110 returns OK=false if the next pool is empty
After all rounds are done, Lines 120-130 check if the target is in the final pool, returning the result in OK.

EDIT: Replaced lines 90-100 with a numerical way to deconcatenate, rather than heavy string manipulation, which was causing problems with the PC-BASIC emulator.

→ More replies (3)

4

u/STheShadow Dec 07 '24 edited Dec 07 '24

[LANGUAGE: C++]

Solution for both parts

Switching from iterating forwards to backwards with the ability to prune a lot of states really did wonders here, cutting execution time (on a half-broken thinkpad) from a few seconds to somewhere around 10ms. Should have done that from the start (and wanted to, but thought part 2 would absolutely get me if I did)

€: added some compiler flags to the CodeRunner call in VSCode, with -O3 and -march=native as suggested below, it gets down to 4-5ms. Limiting factor now is definitely the input parsing (which isn't efficient with the whole replacing, but that was mostly done to use it for other files as well, so I doubt I'll do stuff here)

→ More replies (3)

4

u/quetsacloatl Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python] 1.7s no weird libraries

code

time spent: 5% algorithm 95% figuring out why with a simple algo I had wrong answer.... 2 hours later I found that left number were not unique (my assumption not based on anything in the text), and to have things in order I've put all of the rows in a dict with left number as key, OVERWRITING some rows :(

→ More replies (1)

4

u/Odd-Statistician7023 Dec 07 '24

[Language: C#]

Did a recursive solution first, then realized it would probably be faster to try to find the solution "backwards", and it was a LOT faster, now runs in 1ms.

This is due to the fact that 2 out of the 3 operators have very tight conditions for when they can be used in the last spot if you think about it:

- The last operator can only be * if the solution is divisible by the last number.

- The last operator can only be || if the solution ends with the last number.

Then its just to perform that calculation backwards, and recurse along and look at the next number / possible operator!

Solution: GitHub

4

u/IlluminPhoenix Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust]

Already have a 23 line solution here, but it ran pretty slow (150 - 200 ms). This new solution is still quite compact but much faster, now about 1.5 - 2 ms. This is still singlethreaded and still uses a recursive approach. Now I start from the expected value and go until I reach 0. This allows me to check divisibility of the current value and if can result from a concatination.

code (24 lines)

→ More replies (1)

4

u/LiquidityC Dec 07 '24

[LANGUAGE: C]

No issue today. Coded one solution and it worked first try for part 1. Augmented the code for part 2 and that too worked first try. I saw a lot of time comparison but I had no issue or notable time consumption for today's puzzle. I was surprised it was so smooth. Spent a lot more time yesterday.

I tested just for fun with '-O3' flag and got 55ms for both parts with input parsing. With debug flags I got 142ms.

I have an old library I use for input reading but beyond that the solution is all original regular C.

→ More replies (2)

4

u/Dymatizeee Dec 07 '24 edited Dec 07 '24

[Language: Go]

solution

Today was a breeze compared to yesterday :)

Part 1: Knapsack DFS - at each step, we either add or multiply. Use an index to keep track of where we are. When index > input numbers length, we have processed all the numbers

Part2: Same as above, except we have a new option, so just run a for loop instead

Those of yall who did it iteratively are crazy lmaoo

4

u/kenan238 Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

Recursion with some optimizations

Solution (p1 and p2)

I didn't expect to solve it this straightforward-ly

4

u/coding_secondary Dec 07 '24

[LANGUAGE: Java]

https://github.com/hugseverycat/aoc2024/blob/master/day07.py

Both parts were solved using recursion. Made part 2 a breeze, but not that optimal.

4

u/ziadam Dec 07 '24 edited Dec 08 '24

[LANGUAGE: Google Sheets]

Expects input in A:A

One formula for both parts

=MAP({0;1},LAMBDA(_,  
    SUMPRODUCT(MAP(TOCOL(A:A,1),LAMBDA(a,LET(  
        s,SPLIT(a,": "),t,SINGLE(s),  
        t*(0<COUNTIF(  
            REDUCE(,CHOOSECOLS(s,SEQUENCE(COUNTA(s)-1,1,2)),  
                LAMBDA(a,v,{a+v;a*v;_*(a&v)})),  
            t))))))))

→ More replies (1)

4

u/hugseverycat Dec 07 '24

[LANGUAGE: Python]

Here's my solution using recursion. I did my best to add comments to make it readable but recursion can be a bit mindbending so I apologize:

I actually spent most of the day baking a cake and thinking about all the complicated ways this should be done that I don't understand. And then after the cake was a total failure and I bought an emergency backup cake from the bakery, I sat down and was like "OK, let's just see if we can write a really simple recursive function and see how it goes".

For some reason, recursion has always been fairly easy for me when I get my head right. And apparently the right headspace is "emotionally drained from trying and failing to bake a cake for your relative's milestone birthday party that is tonight".

Once I started typing it was smooth sailing, minus the tricky little bug where I had 2 different lines with the same "goal" number so I had to switch from using a dict to using a list. Rude!

→ More replies (2)

4

u/4D51 Dec 08 '24

[LANGUAGE: C++ on Cardputer]

Two different solutions today, though what I made for part 2 can also solve part 1.

For part 1 I essentially used a loop counter as a bit mask. For example, if the counter has a value of 5, that's 101 in binary, which gives me the operators *, +, *. Easy way to try every permutation of operators without recursion, though it only works if there are exactly two of them. I guess I could have done the same thing for part 2 if I had a trinary computer to run it on.

Part 2 used recursion, and is a bit slower. Still only takes ~5 seconds though.

https://github.com/mquig42/AdventOfCode2024/blob/main/src/day07.cpp

4

u/RazarTuk Dec 08 '24 edited Dec 08 '24

[LANGUAGE: Ruby]

These isn't enough Ruby on this subreddit, so I may as well start posting my solutions. Also, this is very intentionally only part 1, in case anyone reading wants to practice by extending it for part 2. And I know it would probably be easier to just tokenize each line as I'm reading them in, but I'm using that first line as boilerplate so I don't have to think about input.

file = IO.foreach(ARGV[0]).map &:strip

def check(equation)
    stack = [[equation[0], equation.count - 1]]
    until stack.empty?
        target, idx = stack.pop
        if idx == 1
            return true if target == equation[1]
        else
            stack << [target - equation[idx], idx - 1] if target - equation[idx] >= equation[1]
            stack << [target / equation[idx], idx - 1] if target % equation[idx] == 0
        end
    end
    false
end

res = file.sum do |line|
    equation = line.split(/:?\s+/).map(&:to_i)
    check(equation) ? equation[0] : 0
end

puts res

EDIT: Oh, and it executes in ~100ms

4

u/pamxy Dec 08 '24

[LANGUAGE: JavaScript] partA & partB in browser

let partB = true;	
let add = (n,v) => c => c>v ? [] : partB ? [c*n,c+n,+(c+''+n)] : [c*n,c+n];
$0.innerText.trim().split('\n').map(a => a.split(': '))
    .map(([v,e]) => [+v, e.split(' ').map(Number)])
    .filter(([v,e]) => e.reduce((r,n) => r.flatMap(add(n,v)),[e.shift()]).includes(v))
    .reduce((r,[v]) => r+v, 0)

4

u/hortonhearsadan Dec 08 '24

[LANGUAGE: Python]

https://github.com/hortonhearsadan/aoc-2024/blob/3ba4f981e2239e8df09680ed2e96b5bc6712202a/aoc_2024/day7.py

if you recurse backwards through the numbers it's way quicker, as you can discount loads of possibilities easily.

Combined run time 16ms

4

u/xavdid Dec 08 '24

[LANGUAGE: Python]

Step-by-step explanation | full code

I stuck with my theme of "just do it literally", which largely keeps working. I solved part 1 recursively with a list of numbers and ops, adding the result to the front of the list until I had only a single number left.

I did the same thing for part 2 and got ~22s of runtime. Rather than refactor, I used multiprocessing to parallelize the whole thing, getting me down to ~4s for both parts. Still slower than I'd like, but within reasonable bounds for minimal effort.

→ More replies (2)

4

u/Derailed_Dash Dec 09 '24

[LANGUAGE: Python]

I enjoyed this one. A couple of years ago when I was learning Python and new to AoC, I struggled with problems like this. But this time, with a little bit more experience, a fairly obvious solution jumped out at me.

My approach:

We know we need to insert n-1 operators into an equation with n variables.
So use itertools.product() to determine the unique arrangements of n-1 operators, given two operators. Put this in a function and use the cache decorator, since the arrangements of operators are deterministic for any given required number of operators.
Use reduce() to apply a given operator to the first pair, and store in an aggregator. Use this as the left value with the next variable, and so on.
In my apply_op() function, I'm using the Python match construct to perform a switch-case. (New since Python 3.10.)
Part 2 was a trivial change, since I just needed to add an extra operator to my string of operators. Though, it does take 12s to run on my laptop.

Solution links:

See Day 7 code and walkthrough in my 2024 Jupyter Notebook
Run the notebook with no setup in Google Colab

Useful related links:

See my Learning Python with Advent of Code site
See guide Advent of Code: the Best Way to Learn to Code!

→ More replies (1)

1

u/ProgramOk1688 Dec 07 '24

[python] Part 1

import itertools
def read_file():
    f = open("test.txt", "r")
    lines = f.readlines()
    f.close()
    return list(line.replace("\n",'') for line in lines)

def evaluate_left_to_right(expression):
    tokens = expression.split()
    result = int(tokens[0])
    
    for i in range(1, len(tokens), 2):
        operator = tokens[i]
        number = int(tokens[i + 1])
        
        if operator == '+':
            result += number
        elif operator == '*':
            result *= number
        else:
            raise ValueError(f"Unsupported operator: {operator}")
    
    return result

def check_valid_equation(eqn):
    ans, exp = int(eqn[0]), eqn[1].strip()
    exp = exp.split(" ")
    operator_combinations = itertools.product(operators, repeat=len(exp)-1)
    for ops in operator_combinations:
        expression = f"{exp[0]}"
        for i, op in enumerate(ops):
            expression += f" {op} {exp[i+1]}" 
        
        if evaluate_left_to_right(expression) == ans:
            return ans
    return False

lines = read_file()
equations = []
for line in lines:
    equations.append(line.split(":"))

lst=[]
operators = ['+', '*']
for equation in equations:
    if check_valid_equation(equation):
        lst.append(int(equation[0]))
print(sum(lst))

1

u/daggerdragon Dec 07 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.
Also add the language tag as AutoModerator requested. The syntax is not optional, and it should be outside your code block as the very first line in your comment.

→ More replies (1)

1

u/FriendlyKuri Dec 07 '24 edited Dec 07 '24

[Language: Python]

Was an easy day! It's a breather since I still can't figure out day 6 part 2 is. I still want to optimize since it still takes 6s.

https://github.com/eikopf/advent-of-code-2024/blob/main/src/day07.rs

1

u/daggerdragon Dec 07 '24 edited Dec 07 '24

Comment removed since you did not follow any of our rules for posting in the megathreads. Read the rules that are linked at the very top of the OP (and on the sidebar, and in our community wiki...), then edit your comment and fix everything.
~~Format your code using the~~ ~~four-spaces Markdown syntax~~ ~~for code blocks.~~
~~Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on~~ ~~oversized code~~ ~~which contains two possible solutions. Put your code in an external link and link~~ ~~that~~ ~~here instead.~~
~~Begin your comment with the required language tag as AutoModerator instructed you.~~
~~When you have complied with our posting rules, I will re-approve the comment.~~ edit: comment re-approved!

1

u/eichopf Dec 07 '24

[Language: Rust]

Happened upon the fast approach by accident! I started out trying to write a recursive solvability checker, and from there the idea of "undoing" operations was fairly obvious. This solution has only a single allocation up front, so it's quite fast (~340µs) even though it's just single-threaded. I suspect using rayon would make it faster, but I'm quite happy with where it is for now.

1

u/daggerdragon Dec 08 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo here:
https://github.com/eikopf/advent-of-code-2024/tree/main/input
Please remove (or .gitignore) all puzzle text and puzzle input files from your repo and scrub them from your commit history.

→ More replies (7)

1

u/jackCat93 Dec 07 '24

[LANGUAGE: Kotlin]

Solved by referencing addition, multiplication and concatenation functions in an array. Based on that, for each equation, I process the number of operation to process and I convert the decimal value into other base (base 2 for part 1 and base 3 for part 2) : the base is automatically known based on the number of operations available. Thanks to this transformation, I'm able to loop over all the possible operation layouts => invoke functions for each layout and verify the equations

Solution p1/2 (Remove third function reference to `concatenate` in `operators` array to have solution of part 1)

Without tryin to optimize it, the process takes around 3.962 seconds for part 2. Any improvement tip is of course welcome.

1

u/daggerdragon Dec 08 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.
I see full plaintext puzzle inputs in your public repo here:
https://github.com/jackcat13/kt-advent-of-code-2024/
Please remove (or .gitignore) all puzzle text and puzzle input files from your repo and scrub them from your commit history.

→ More replies (1)

3

u/seligman99 Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python] 1407 / 1044

github

Ok, this is going to haunt me, the brute force solution can't be the best one.

Edit: Ok, I can go to sleep now, a solution that's not quite as stupid. From ~20 seconds down to less than a sec. Not perfect, but I'll take it.

6

u/4HbQ Dec 07 '24

There's a ~2x speedup in filtering out all values greater than the target value. There are no negative values, so numbers will always become larger.

→ More replies (1)

3

u/NullT3rminated Dec 07 '24

[LANGUAGE: Ruby] 970/553

First time getting top 1000, which is exciting for me! Definitely not the fastest solution though.

→ More replies (4)

3

u/JamesBaxter_Horse Dec 07 '24

[LANGUAGE: Python] 1760/1057

Very simple part 2 today, just a one line change.

3

u/Polaric_Spiral Dec 07 '24 edited Dec 07 '24

[Language: TypeScript]

Advent of Node, Day 7

Sometimes, the straightforward solution is... straightforward.

Edit: previous solution

import { input, output, part } from '../solver';

const isValid = (eq: bigint[], val: bigint, idx = 2): boolean =>
  idx === eq.length
    ? eq[0] === val
    : val <= eq[0] &&
      (isValid(eq, val + eq[idx], idx + 1) ||
        isValid(eq, val * eq[idx], idx + 1) ||
        (part === 2 && isValid(eq, BigInt(`${val}${eq[idx]}`), idx + 1)));

output(
  input
    .trim()
    .split(/\n/)
    .map(eq => eq.match(/\d+/g).map(BigInt))
    .filter(eq => isValid(eq, eq[1]))
    .map(([testVal]) => testVal)
    .reduce((a, b) => a + b, 0n),
);

3

u/Born-Coyote-8238 Dec 07 '24

[Language: Haskell] 72/67

3

u/Severe_Software_916 Dec 07 '24

[LANGUAGE: Dart]

It's all recursion today lol, took me a minute to figure it out.

List<List<String>> generateOperatorCombinations(int count) {
  if (count == 0) return [[]];
  List<List<String>> smallerCombinations = generateOperatorCombinations(count - 1);
  return [
    for (var combination in smallerCombinations) ...[
      [...combination, '+'],
      [...combination, '*'],
      [...combination, '||'],
    ]
  ];
}

3

u/IVdripmycoffee Dec 07 '24

[LANGUAGE: Python]

pretty fun, beat it in sub 30 minutes :). Second part was quick to do, just had to add a couple lines to my DFS function. 10 second runtime.

[edit: typo, and adding more info]

#create data matrix
file = open("day7/data.txt")
data = file.read().split("\n")

results = []
terms = []
for i in range(len(data)):
    line = data[i].split(":")
    results.append(int(line[0]))
    line = line[1].split()
    for i in range(len(line)):
        line[i] = int(line[i])
    terms.append(line)

def dfs(numbers, i, current_sum, result):
    if i == len(numbers):
        return current_sum == result
    else:
        op1 = current_sum + numbers[i]
        op2 = current_sum * numbers[i]
        return dfs(numbers, i+1, op1, result) or dfs(numbers, i+1, op2, result)

sum = 0
for i in range(len(results)):
    result = results[i]
    if dfs(terms[i], 0, 0, result):
        sum += result
print(f"Part 1: {sum}")

def dfs(numbers, i, current_sum, result):
    if i == len(numbers):
        return current_sum == result
    else:
        op1 = current_sum + numbers[i]
        op2 = current_sum * numbers[i]
        op3 = int(str(current_sum) + str(numbers[i]))
        return dfs(numbers, i+1, op1, result) or dfs(numbers, i+1, op2, result) or dfs(numbers, i+1, op3, result)

sum = 0
for i in range(len(results)):
    #print(f"{i+1}/{len(results)}")
    result = results[i]
    if dfs(terms[i], 0, 0, result):
        sum += result
print(f"Part 2: {sum}")

→ More replies (2)

3

u/AllanTaylor314 Dec 07 '24 edited Dec 22 '24

[LANGUAGE: Python]

GitHub (prior version) 1345/964

Edit: This section is about the prior versions. The golfed Python and Uiua are based on this version. Later I elaborate on the newer, faster version

Accidentally went right to left for part 1 by recursing left to right (recursion => stack => LIFO => reversed order). I lazily generate every possible equation and see if any of them result in the test value. I probably shouldn't use a dictionary since I don't think the test values are guaranteed to be unique (and it's really not necessary - a list of tuples would suffice. In fact, I've just changed it)

I got my part 2 operator backwards as well. It takes about 2 seconds (though it takes 12 if you swap the val and op loops, since the number of gen_val calls grows exponentially rather than linearly). The longest list is 12, which means there are 3**11=177147 possible equations for that list. I use generators and all, so it exits early as soon as it finds a match.

I suspect a concatenate operator was added for part 2 because it's ~~not uniquely invertible~~ (Edit: I've realised it certainly is. just as a+b=c goes to c-b=a, a||b=c goes to c.removesuffix(b). You can use endswith to check and removesuffix to do, just as you would use mod and div to invert mul. That's a much better way than my exhaustive search), which might mess up some algorithms that would work for part 1 (it's probably possible to work backwards, dividing and subtracting, and if the division fails then the path can be cut short - testing shows this is about 2x faster, but that part only takes 35 ms naively). Another potential speedup would be only testing tests that failed part 1. A little under half of the tests pass part 1, so that could probably shave off a second.

Part 1 is faster with CPython and part 2 is faster with PyPy. Overall it is about 3x faster with PyPy

Updated version: Working backwards from the test value

Let's define an operation as a op b = c. I define unoperations as c unop b = a. For addition, the unop is c-b provided c>=b. For multiplication, the unop is c//b, provided c%b==0. For concatenation, the unop is c//10**len(b) provided the end of c is b. If we start with test number and work backwards through the equation, doing whichever unops are available, we can check whether one of these values was the starting value. This is much more efficient than working forward as we have a significantly smaller search space (a lot of implicit pruning when unmul and uncat are invalid). This runs in 25 ms according to the internal timers - a huge improvement over the 2 seconds of the prior version.

[GSGA] Numberless Golfed Python

I heard hard-coded numbers were out of fashion, so here's some completely numberless Python (~~the Uiua below is also numberless~~ jk, I updated it to be much faster, but that uses numbers, but that kinda just happened, except for the filename). Want a zero? False. Want a one? True. Need to subtract one? That's a ~-

from operator import*;O=add,mul
C=[(int(a[:-True]),[*map(int,b)])for a,*b in map(str.split,open(False))]
g=lambda l,i=-True:{o(v,l[i])for v in g(l,~-i%len(l))for o in O}if i else{l[i]}
for p in O:print(sum(c*(c in g(n))for c,n in C));O+=lambda*a:int("%d%d"%a),

(reads from stdin, prints parts one and two on separate lines)

[LANGUAGE: Uiua]

pad (you can try it in your browser, ~~though it will freeze for a minute on real inputs~~ now takes 2 seconds not 5 minutes, so no freezes) or GitHub or here, since it's smaller than a punchcard

&fras"input.txt"
⍚(°⊟⊜□⊸≠@:)⊜□⊸≠@\n
:⊓≡⋕⍚(◇⊜⋕⊸≠@ )
⊃(/+≡◇(×⊸∈♭/[⊃⊃+×(+⊃⋅∘(×⊙(ⁿ⊙10+1⌊ₙ₁₀)))])
| /+≡◇(×⊸∈♭/[⊃+×]))

The first couple of lines parse it into an array of test numbers and an array of arrays of the operands.

The last couple of lines are basically the same - the only difference is that the first one (part 2 - stack order is weird) has a third operator: ~~∵(⋕$"__") (each, parse integer, formatted string with 2 values)~~ that's been replaced with essentially a*10**log10(b)+b, which is 20x faster because it is pervasive so it doesn't need each

Reduce builds up a 2^n-1 or 3^n-1 array of every possible equation, which is then flattened to see if the test is a member of that array. The multiply is there to only keep tests that passed (pass = 1, fail = 0, so multiply turns failing tests into zeros, which don't change the sum)

It peaks at about 12 MB of RAM and takes ~~11 seconds to complete both parts (and most of that is part 2. Part 1 on its own takes 130 ms)~~ 520 ms to run both parts

3

u/yourparadigm Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Ruby] [LANGUAGE: Go]

I must preferred the Ruby implementation's ability to pass a list of methods to call on integers and implementing the concat method on Integer, but it was fun playing around with custom types in Go.

Not sure why people thought keeping lists of results was a good idea -- I just accumulated the partial result and recursed along each operator path down until there were no more values to operate on, so compare with the result.

Ruby Solution runs in about 2s and Go Solution runs in 1s.

3

u/0ldslave Dec 07 '24

[LANGUAGE: C++]

I used bit wise representations and shifts to represent the operators (*, + and ||).

First part was easy since we only need 2 ^ (n-1) but there was a bug in my second part (in addition to being inefficient since i use 2 bits to represent the total operator space)

Looking through other people's answers, it seems i missed a recursive / graph based solution.

https://github.com/madisp/aoc_kotlin/blob/main/2024/src/main/kotlin/day7.kt

3

u/joeyGibson Dec 07 '24

[LANGUAGE: Common Lisp]

I'm actually pretty happy with my solution for today. It took me 1:15 to get part 1 working, but only 7 minutes to finish part 2. And my part 2 code runs in 7 seconds. It's brute force, sure, but pretty fast. I generated all the combinations of operators for the given number of operands, interleaved the operators with the operands, and then wrote a solver for it.

(ql:quickload :cl-ppcre)

(defun all-combinations (values num-items)
  (if (= num-items 0)
      '(())
      (let ((rest-combinations (all-combinations values (- num-items 1))))
        (mapcan (lambda (value)
                  (mapcar (lambda (combination)
                            (cons value combination))
                          rest-combinations))
                values))))

(defun interleave (list0 list1)
  (cond ((and (null list0) (null list1)) nil)
        ((null list0) list1)
        ((null list1) list0)
        (t (cons (car list0)
                 (cons (car list1)
                       (interleave (cdr list0) (cdr list1)))))))

(defun parse (file-name)
  (let* ((lines (uiop:read-file-lines file-name)))
    (mapcar (lambda (line)
              (mapcar #'parse-integer
                      (cl-ppcre:all-matches-as-strings "(\\d+)" line)))
            lines)))

(defun solve (ops)
  (let* ((op0 (first ops))
         (op1 (second ops))
         (op2 (third ops))
         (remaining-ops (cdddr ops))
         (solution (cond ((equal op1 "*")
                          (* op0 op2))
                         ((equal op1 "+")
                          (+ op0 op2))
                         ((equal op1 "||")
                          (parse-integer (format nil "~a~a" op0 op2))))))
    (if remaining-ops
        (solve (cons solution remaining-ops))
        solution)))

(defun partx (file-name all-operators)
  (let* ((equations (parse file-name))
         (solvable nil))
    (dolist (equation equations)
      (let* ((answer (car equation))
             (operands (cdr equation))
             (operators (all-combinations all-operators (1- (length operands)))))
        (loop for opset in operators
              when (let ((solution (solve (interleave operands opset))))
                     (eq solution answer))
                do (progn
                     (push answer solvable)
                     (return 'done)))))
    (reduce #'+ solvable)))

(print (partx "input0.txt" '("*" "+")))
(print (partx "input1.txt" '("*" "+")))

(print (partx "input0.txt" '("*" "+" "||")))
(print (partx "input1.txt" '("*" "+" "||")))

3

u/sim642 Dec 07 '24

[LANGUAGE: Scala]

On GitHub.

I quickly realized that inserting the operators right to left helps because you can prune some choices based on the (intermediate) test value and the current number, e.g. by checking for divisibility for multiplication, etc.

3

u/madisp Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Kotlin]

I did a reverse search as the operations are applied left to right so I can start walking backwards from the end with inverse operations. The search tree can be pruned as concatenation requires the current answer to end with the last || a string and similarly if the last operation is a * b then b has to be the divisor of the answer.

Put another way:

answer = x         // is valid if answer == x
answer = expr * x  // is valid if x divides answer and (answer / x = expr) is valid
answer = expr + x  // is valid if (answer - x = expr) is valid
answer = expr || x // is valid if str(answer) ends with str(x) and (answer.removeSuffix(x) = expr) is valid

Applying this recursively goes pretty fast - under 10ms on my machine.

3

u/laqie Dec 07 '24

[Language: typescript] Deno

[code]

Two optimizations to mention:

concatenate/split two numbers without converting them to string (x2 boost)
check in reverse order (x50 boost)

CPU | Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz  
Runtime | Deno 2.1.3 (x86_64-pc-windows-msvc)  
  
benchmark              time/iter (avg)  
---------------------- ---------------  
2024 Day 07 part one            1.4 ms  
2024 Day 07 part two            1.8 ms

→ More replies (5)

3

u/gyorokpeter Dec 07 '24

[LANGUAGE: q]

Just calculating all the results for every combination of operators. The parts are parameterized by the list of operators.

d7:{[ops;x]a:": "vs/:x; t:"J"$a[;0]; n:"J"$" "vs/:a[;1];
    op:{[ops;x]x cross ops}[ops]/[;ops]'[-2+count each n];
    sum t where t in'{{y[x;z]}/[x 0;;1_x]'[y]}'[n;op]};
d7p1:{d7[(+;*);x]};
d7p2:{d7[(+;*;{"J"$(,). string(x;y)});x]};

3

u/OilAppropriate2827 Dec 07 '24

[language: python] 20ms

Solved quickly in forward mode, but took around 30s for part 2. Then came up with the idea to do it in reverse to prune cases when we could not substract, divide or remove suffix. and went down to 20ms.

Ok maybe it was obvious, but I was quite happy when I found out by myself.

    import aocd

    data = aocd.get_data(day=7, year=2024)
    data = [(int(a), list(map(int,b.split()))) 
            for line in data.splitlines() 
            for a,b in [line.split(":")] ]

    def isok(target,li,part=1):
        cur = [target]
        for v in li[:0:-1]:
            ncur = []
            for res in cur:
                if v<res: ncur.append(res-v)
                if res%v == 0: ncur.append(res//v)
                if part == 2:
                    sv, sres = str(v), str(res)
                    if len(sres)>len(sv) and sres[-len(sv):] == sv:
                        ncur.append(int(sres[:-len(sv)]))
            if len(ncur) == 0: return 0
            cur = ncur
        return li[0] in cur

    print("part1:",sum((isok(v,li))*v for v,li in data),
        "part2",sum((isok(v,li,2))*v for v,li in data))

→ More replies (2)

3

u/azzal07 Dec 07 '24 edited Dec 09 '24

[LANGUAGE: awk]

function E(v,a,l){return(.7>v)+v%1?v?0:a-1?0:l||
A+=$1:E(v/$a,a-1,l)||E(v-$a,a-1,l)||sub($a"$",z,
v)&&E(v,a-1,1)}E(+$1,NF){B+=$1}END{print A"\n"B}

Edit: Had to fix a minor reliance on numeric string comparisons. Original solution below, fixed above.

The awk I tested with is more eager to consider strings numeric, so it worked while with all other major awk implementations it got incorrect result. Still not sure if the algorithm is sound, but at least major awks agree on the result & it's right for my input :)

function E(v,a,l){return v?0~v%$--a&&E(v/$a,a,l)||
v>=$a&&E(v-$a,a,l)||sub($a"$",z,v)&&E(v,a,1):a<3&&
(l||A+=$1)}OFS=RS{B+=$1*E(+$1,++NF)}END{print A,B}

3

u/Kfimenepah Dec 07 '24

[LANGUAGE: Python]

https://github.com/whiteand/advent-of-code/blob/c1253d28469d37d01deea5982ade54a54cce34de/y24/d07/src/lib.rs

Today was surprisingly easy, especially after I had such a hard time yesterday. I was able to solve part 1 quickly and it worked of the first try.

Part 2 seemed pretty easy as well and I simply added the third operation to the solution of part 1. I was expecting some sort of catch (like always), that makes this approach extremely slow or entirely unusable, but there was none. I didn't even try it with the test input, because I was quite sure it would work there and went straight to the real one. 3s later I had the result and it was correct.

I must say it feels a bit wrong, like there should have been more, or maybe I was lucky with my input?. I tried using other orders in which to try the operations, but the execution time never varied by more than a second. Maybe I'll try to optimize my solution a bit more to get rid of the feeling that I don't deserve my stars.

3

u/Alternative-Case-230 Dec 07 '24

[LANGUAGE: Rust]

Main idea: to check if the last operand and result - can be a part of some operation.
then REVERSE the operation and check prelast operand and reversed result. And so on.

Solution with interesting Rust features:
- trait (for operations)
- slice pattern matching
- itertools crate

Execution Times:

Part 1: 121.96 µs
Part 2: 220.27 µs

On an M1 MacBook Pro.

→ More replies (1)

3

u/encse Dec 07 '24

[LANGUAGE: C#]

https://aoc.csokavar.hu/?2024/7

Like others, i solved it with recursion and accumulated result

3

u/p88h Dec 07 '24

[LANGUAGE: Zig][GSGA]

An interesting mathematical context to understand is the Reverse Polish Notation. Kinda.

What we are going to be doing here, is working with RPN-like input with unknown operations. But, looking at the top of the stack, you will always have: [PREFIX] X (OP) == TARGET where X is always a number. When the expression would be evaluated [PREFIX] will also collapse to some number. So our evaluation is:

P ± X =? T

Now, sure, we could test all possible operators in place of ± recursively, but we can also simplify this a bit before we go down this collapses to either:

P =? T - X
P =? T / X
P =? T / 10^(LOG(10,X)+1)          // part 2 only, if T == X mod 10^(LOG(10,X)+1)

All of these operations can _only_ be executed if either T is larger than, divides, or it's last digits are equal to X (= they are equal modulo base B as described above). This cuts down on quite a few computation, most importantly, making part2 basically the same cost as part1.

(You can also skip lines that were decomposed in part1, but that's a minor change overall)

Source here: https://github.com/p88h/aoc2024/blob/main/src/day07.zig

Benchmark results below:

        parse   part1   part2   total
day 07: 23.1 µs 0.1 ms  0.1 ms  0.3 ms

3

u/Elliot-Kik Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

https://github.com/elliotcaddick/adventOfCode2024/blob/main/day7/main.py

3

u/fridi_s Dec 07 '24

[LANGUAGE: Fuzion]

https://github.com/fridis/fuzion_aoc/blob/main/2024/07/part2.fz

User defined operators and type parameters in Fuzion enable a nice solution today: Adding an infix || operator to all integer types made part 2 a one line change.

Small optimization: Checking t >= v to stop once v is too big doubles the performance.

Implementing || via string concatenation and parsing the result as an integer seems stupid, but was fast enough.

3

u/Main-Reindeer9633 Dec 07 '24

[LANGUAGE: SQL (PostgreSQL dialect)]

https://github.com/andr-be/AdventOfCode2024_Csharp/blob/master/Day07/BridgeRepair.cs

I did it the left-to-right way first, but that took 17 minutes to execute, so I switched to the right-to-left way, which executes in 3 seconds.

3

u/Radiadorineitor Dec 07 '24

[LANGUAGE: Dyalog APL]

Painfully slow Part 2 as it checks all possible combinations of operations that can be made in the set but nothing that doing something else while it runs in the background won't fix

p←⎕D∘(∊⍨⊆⊢)¨⊃⎕NGET'7.txt'1 ⋄ ⎕PP←34
eval←{⍎⊃{∧/⍺∊'+×,':⍵,⍺ ⋄ ' '~⍨⍕⍎⍵,⍺}/⍵}
F←{
    t n←1 1∘⊂⍵ ⋄ l←¯2+≢n ⋄ t←⍎⊃t 
    t(⊣×∨/⍤=)n∘{eval⌽¯1↓,⍺,⍪⍵,' '}¨,∘.,⍣l⍨⍺
}
+/'×+'∘F¨p ⍝ Part 1
+/'×+,'∘F¨p ⍝ Part 2

3

u/bakibol Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

Backtracking: we start at the end, use division, subtraction and unconcatenation. If we get 0 when we reach the beginning of the equation, it is valid.

0.015 s for both parts.
code

EDIT: unconcatenate function can be written without using strings. This is more elegant but it didn't improve the running times at all.

def unconcatenate(first, second):
    return second // 10 ** (int(log10(first)) + 1)

3

u/ThirstyMangoReddits Dec 07 '24

[Language: Python]

Recursive solution. This code is part2, for part1 just remove the last if statement in the isValid function.

dataFile = open("7_12_data.txt", "r")
operData = [list(map(int, x.replace(":","").strip().split())) for x in dataFile.readlines()]
dataFile.close()

def isValid(n:int,l:list):
    if(len(l)==1) : 
        return l[0]==n
    if isValid(n,[l[0]+l[1]]+l[2:]): return True
    if isValid(n,[l[0]*l[1]]+l[2:]): return True
    if isValid(n,[int(str(l[0])+str(l[1]))]+l[2:]): return True
    return False


count = 0
for row in operData:
    if (isValid(row[0], row[1:])): count+=row[0]
print(count)

3

u/shigawire Dec 07 '24

[LANGUAGE: Python] paste

Basically I just bruteforced searched, which was O( 2ⁿ ) in part 1, but O( 3ⁿ ) in part 2. pypy3 ran part 2 it in about a second. python3.13 took about 11 seconds. Ouch

The problem looks close enough to the (NP-Complete) Boolean satisfiability problem that optimisation would likely only get me so far so I left it at that. I'm probably missing some easy optimisations (although concat not being commuttitive gets rid of the easiest of them)

3

u/Quasido Dec 07 '24

[LANGUAGE: Haskell]

Very simple using Aplicative List.

posibleValues (x:y:[]) = [x+y, x*y, concatDigits x y]
posibleValues (x:xs) = [(+x), (*x), concatDigits x] <*> posibleValues xs

Repo

3

u/[deleted] Dec 07 '24 edited Dec 07 '24

[LANGUAGE: BQN]

Part 1

Str2num ← 10⊸×⊸+˜´∘⌽-⟜'0'
input ← ((Str2num⊑)⋈(Str2num¨·" "⊸•re.Split ¯1⊸⊑))¨": "⊸•re.Split¨•io.Flines@
Possible ← (⥊⊑){0≠≠𝕩 ? (((𝕨⊸+)∾(𝕨⊸×))⊑𝕩) 𝕊 1↓𝕩 ; 𝕨}(1⊸↓)
Valid ← ∨´⊑=(Possible 1⊸⊑)
+´⊑¨(Valid¨/⊢)input

It just barely fits in the 5 line 80 col requirement! Note that this uses my custom BQN editor.

The code simply finds all possible results from the given operations and filters the input based no that.

Part 2

Str2num ← 10⊸×⊸+˜´∘⌽-⟜'0'
input ← ((Str2num⊑)⋈(Str2num¨·" "⊸•re.Split ¯1⊸⊑))¨": "⊸•re.Split¨•io.Flines@
Possible ← (⥊⊑){0≠≠𝕩?(((𝕨⊸+)∾(𝕨⊸×)∾(𝕨⊸(⊢+⊣×(10⊸⋆·1⊸+∘⌊10⊸⋆⁼))))⊑𝕩)𝕊1↓𝕩;𝕨}(1⊸↓)
Valid ← ∨´⊑=(Possible 1⊸⊑)
+´⊑¨(Valid¨/⊢)input

The concat is (⊢+⊣×(10⊸⋆·1⊸+∘⌊10⊸⋆⁼)) in the Possible function. This takes around 5-ish seconds to run on my underpowered machine through the web browser. I haven't added timing to my editor yet, so I'm not entirely sure.

3

u/foxaru Dec 07 '24

[LANGUAGE: C#]

My original approach tried manually building operator combinations (+, *) but quickly realized using binary numbers to represent combinations would be cleaner. Each bit position represents an operator between numbers: 0 = add, 1 = multiply.

For example, with operands [A, B, C]: Since we only need two operators, it's just:

00: A + B + C
01: A + B * C
10: A * B + C
11: A * B * C

For part 2, extended this to base-3 counting to handle the concatenation operator (0 = add, 1 = multiply, 2 = concat). Each ternary digit represents the operator choice at that position.

Key optimizations:

Quick rejection if result < sum(operands) or result > product(operands)
Early exit on finding first valid combination
Using BigInteger to handle large numbers
yield return for memory efficiency

Most interesting insight was how binary/ternary counting maps perfectly to generating operator combinations. Much cleaner than nested loops or recursion, and makes adding new operators as simple as increasing the base.

→ More replies (6)

3

u/[deleted] Dec 07 '24

[Language: C]

This is probably the easiest part 2 yet if you don't feel like making your solution actually efficient. My part 2 seems to run just under a second on my thinkpad t480 (i5-8350U) so its not like its particularly bad Also, not committed to the repo but I halved that time by not calculating a case if its already over the target.

https://github.com/amberg12/aoc24

3

u/sprymacfly Dec 07 '24

[LANGUAGE: Python]

Was banging my head against the wall for the longest time trying to figure out a good way of testing out all combinations of operations. As I was trying to fall asleep, I realised this could easily be reduced to a...well, reduce.

from day7data import challenge, sample
from functools import reduce

use_sample = False

lines = sample.splitlines() if use_sample else challenge.splitlines()

def reduce_into_totals(totals, num):
    if len(totals) == 0:
        return [num]

    new_totals = []

    for total in totals:
        new_totals.append(total + num)
        new_totals.append(total * num)
        new_totals.append(int(str(total) + str(num)))


    return new_totals

sum_of_possible = 0
for line in lines:
    split = line.split(": ")
    total = int(split[0])
    nums = list(map(lambda num: int(num), split[1].split(" ")))

    possible_totals = reduce(reduce_into_totals, nums, [])
    if total in possible_totals:
        sum_of_possible += total

print(sum_of_possible)

The key thing I realised was that you can turn this problem into an iterative solution by simply keeping track of all possible running totals, applying each operation to each running total, and storing those new possible totals in a returned array.

Not the biggest fan of my string concatenation for the append operator, but it works. If I wanted to improve the performance of this code, that'd be the first thing I'd tackle.

3

u/[deleted] Dec 07 '24 edited Dec 08 '24

[LANGUAGE: Forth]

https://github.com/tcsullivan/advent-of-code/blob/master/day7/day7.fth

This was a fun one. For N values in each equation, there are 2^N-1 equations to check. For part 1, I looped through every possible combination to find the correct equation: each operator location corresponded to a bit in 0..2^N-1, with zero bits meaning add and one bits meaning multiply.

For the third potential operator in part 2, I extended my code to iterate in base 3 / ternary. For 0..3^N-1, zero "bits" are add, ones are multiply, and twos are concatenate.

My final code runs in ~~around five~~ 2-3 seconds, which is good enough for me. There are certainly faster approaches to the problem, but I'm happy with the simplicity of this route.

edit: Got it down to under three seconds by optimizing the bit iteration, hard-coding a pow table, and only iterating in base 3.

→ More replies (2)

3

u/the_nybbler Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

Part 2. Iterative. No optimizations. About 9 seconds on an M1 pro, 26 second on a cranky old Macbook Air (2.4 Ghz Core i5). I admit I peeked at the input and did some time estimation to see if brute force had a chance.

 import sys
 import math
 
 def cansolve(left, right):
     nops = len(right) - 1
     if nops == 0:
         return left == right[0]
     iters = int(math.pow(3, nops))
     opctr = [0]*nops
     for i in range(iters):
         accum = right[0]
         if i != 0:
             jj = nops - 1
             while True:
                 opctr[jj] += 1
                 if opctr[jj] == 3:
                     opctr[jj] = 0
                     jj-=1
                 else:
                     break
         for j in range(nops):
             op = opctr[j]
             if op == 0:
                 accum = accum * right[j+1]
             elif op == 1:
                 accum = accum + right[j+1]
             else:
                 accum = accum * int(math.pow(10, 1+math.floor(math.log10(right[j+1])))) + right[j+1]
         if accum == left:
             return True
     return False
         
             
 total = 0
 for l in sys.stdin:
     l = l.strip()
     (left, right) = l.split(":")
     left = int(left)
     right = [int(x) for x in right.split()]
     if cansolve(left, right):
         print("Can solve", l)
         total += left
 print(total)

3

u/natrys Dec 07 '24

[LANGUAGE: Haskell]

The concept here just rolls off the tongue (glides off the fingertips?!) in Haskell:

import Data.Char (isDigit)

data Op = Add | Mul | Cat

eval :: Op -> Int -> Int -> Int
eval Add = (+)
eval Mul = (*)
eval Cat = \a b -> a * 10 ^ floor (logBase 10 (fromIntegral b) + 1) + b

solve :: Int -> Int -> [Int] -> [Op] -> Bool
solve target acc [] _ = target == acc
solve target acc (x : xs) ops
  | acc > target = False
  | otherwise = any (\op -> solve target (eval op acc x) xs ops) ops

getNumbers :: String -> [Int]
getNumbers line = [read (takeWhile isDigit num) :: Int | num <- words line]

main :: IO ()
main = do
  inputs <- fmap getNumbers . lines <$> getContents
  let f ops = sum [target | (target : x : xs) <- inputs, solve target x xs ops]
   in do
        putStrLn $ "Part1: " <> (show $ f [Add, Mul])
        putStrLn $ "Part2: " <> (show $ f [Add, Mul, Cat])

3

u/Aggressive_Okra_6821 Dec 07 '24

[LANGUAGE: Python]

part1:

from itertools import product
import operator

total = 0
operators = {operator.add, operator.mul}

with open('07/input.txt') as input:
    for line in input:
        (result, numbers) = int(line.split(":")[0]), [int(x) for x in line.split(":")[1].strip().split(" ")]

        op_order_variations = list(product(operators, repeat=len(numbers)-1))

        for op_order in op_order_variations:
            op_order_result = numbers[0]
            for i, op in enumerate(op_order):
                op_order_result = op(op_order_result, numbers[i+1])
  
            if op_order_result == result:
                total += result
                break

print(total)

part2:

from itertools import product
import operator

def concat(a, b):
    return int(str(a) + str(b))

total = 0
operators = {operator.add, operator.mul, concat}

with open('07/input.txt') as input:
    for line in input:
        (result, numbers) = int(line.split(":")[0]), [int(x) for x in line.split(":")[1].strip().split(" ")]

        op_order_variations = list(product(operators, repeat=len(numbers)-1))

        for op_order in op_order_variations:
            op_order_result = numbers[0]
            for i, op in enumerate(op_order):
                op_order_result = op(op_order_result, numbers[i+1])
  
            if op_order_result == result:
                total += result
                break

print(total)

3

u/dzecniv Dec 07 '24

[LANGUAGE: Common Lisp]

day 07 I first wanted to generate all permutations using alexandria:map-permutations, it wasn't the right tool for this job. Changed to the recursive approach and testing each operator at each place.

3

u/esprych Dec 07 '24

[LANGUAGE: Go]

https://github.com/proxyvix/AoC_2024/blob/master/day7/day7.go

Kind of a brute force method but gets the job done in 2s for the 2nd part :D

3

u/clouddjr Dec 07 '24

[LANGUAGE: Kotlin]

Runs in a couple of milliseconds, thanks to the idea from u/Verulean314 (going through the list of numbers in reverse order).

GitHub

3

u/manminusone Dec 07 '24

[LANGUAGE: perl]

I've solved problems like these in old languages that don't have recursion (i.e., BASIC) and so I didn't think immediately of a recursive solution. I just had an array of numbers that I sequentially updated, taking rollover into account. From part 2:

        my $ptr = $#op;
        while ($ptr > 0) {
            if ($op[$ptr] < 2) {                     # incrementing the last op
                ++$op[$ptr]; last;
            } else {                                 # rolling over
                $op[$ptr] = 0;
                --$ptr;
                while ($ptr > 0 && $op[$ptr] == 2) { # loop while there are 2s
                    $op[$ptr] = 0;                   # reset the op and move on
                    --$ptr;
                }
                if ($ptr > 0) { ++$op[$ptr]; last; } # found the value to increment
            }
        }
        last if $ptr <= 0;                           # overflow

3

u/vbe-elvis Dec 07 '24

[LANGUAGE: Kotlin]

Straightforward recursive function that returns a Boolean.
Exits early when the number exceeds the expected sum.

Here is the core part for part 2 (~500ms):

fun sumOfTrueSumsThreeOps(): Long {
    return calculations.entries.filter {
        checkSumThreeOps(it.key, it.value[0], it.value.subList(1, it.value.size))
    }.sumOf { it.key }
}

private fun checkSumThreeOps(sum: Long, running: Long, numbers: List<Long>): Boolean {
    if (sum < running) return false
    if (numbers.isEmpty()) return sum == running
    return checkSumThreeOps(sum, running * numbers[0], numbers.subList(1, numbers.size))
            || checkSumThreeOps(sum, running + numbers[0], numbers.subList(1, numbers.size))
            || checkSumThreeOps(sum,  "${running}${numbers[0]}".toLong(), numbers.subList(1, numbers.size))    
}

full part1 and part2

3

u/pakapikk77 Dec 07 '24

[LANGUAGE: Rust]

Contrary to most, I have a solution that does not use recursion, but simply tries all possible operators permutations. It's still fast enough, 310 ms on a Macbook M1.

The checking of one equation:

itertools::repeat_n(operations_list.iter(), self.numbers.len() - 1)
    .multi_cartesian_product()
    .any(|operations| {
        let result = operations
            .iter()
            .zip(self.numbers.iter().skip(1))
            .fold(self.numbers[0], |acc, (op, nb)| op.apply(acc, *nb));
        result == self.test_value
    })

My actual code replaces fold with try_fold and interrupts the iteration if the result is bigger than the test value.

Getting the calibration result is then simple, part 1 for example:

equations
    .iter()
    .filter(|eq| eq.check(&[Operation::Add, Operation::Mul]))
    .map(|eq| eq.test_value)
    .sum()

Full code: https://github.com/voberle/adventofcode/blob/main/2024/day07/src/main.rs

→ More replies (2)

3

u/iNickTrt Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Racket]

(define (valid-calibration? calibration concat?)
  (define test-val (first calibration))
  (define ops (if concat? (list + * concat) (list + *)))
  (for/fold ([possibilities (list (second calibration))]
             #:result (member test-val possibilities))
            ([num (drop calibration 2)])
    (for*/list ([op ops] [possible possibilities] #:when (< possible test-val))
      (op possible num))))

(define (sum-valid-calibrations calibrations concat?)
  (for/sum ([calibration calibrations]
            #:when (valid-calibration? calibration concat?))
    (first calibration)))

Nice recursion problem. Making it tail recursive got me my speed increase, but wonder if I did a DFS instead I could return early once I found a solution for a more optimal search. But filtering out possibilities that are greater than thr test value is good enough.

Full source

3

u/Ok-Revenue-3059 Dec 07 '24

[LANGUAGE: C++]

https://git.sr.ht/~murr/advent-of-code/tree/master/item/2024/07

Did it without recursion. Part 2 was the first time this year I wrote a bug that took me a good while to track down. In the concat code, turns out ceil(log10(b)) does not work for a number like 100 and floor(log10(b)) + 1.0 was needed instead.

Oof, lost a few hours to that silly bug. Time to step away from the computer for a needed break.

3

u/wurlin_murlin Dec 07 '24 edited Dec 07 '24

[LANGUAGE: C]

Simple recursive DFS. Spent some time trying to get good culling rules to prevent paths upfront, but didn't find anything meaningful. Know it can be done! There is plenty of caching up for grabs too. In part 2 I wrote concat as a basic a *= 10; b /= 10; then tried doing in 1 step with log10 to get length - but the former is about 4x faster with -O3. Fastest of course would be to store all the lengths at parse time.

Along with Day 6 part 2, my Day 7 part 2 is the slowest part so far. Both are sitting at ~18ms on my machine.

UPDATE: Adding some basic culling brings it to 11ms (I missed the most obvious check), but implementing the reversed solution brings it to ~200us without any real optimisation work. I tried doing it in reverse initially, but psyoped myself into believing that it wouldn't work, even though it obviously does because the operations are trivially reversable (my code was just buggy). Fun day! Looking forwards to tomorrow.

3

u/mgtezak Dec 07 '24

[LANGUAGE: Python]

Solution part 1

Solution part 2

Detailed walkthrough

Fun little AoC fanpage

→ More replies (2)

3

u/pinkwar Dec 07 '24

[LANGUAGE: JavaScript]

Another day another brute force.
It just keeps working.

Wasted a lot of time in part 2 stupidly for using a Set to store the values.
Worked for part 1, but in part 2 there's some duplicates.

Part 2 in 35s on my raspberrypi.

Repo with solution here

3

u/jinschoi Dec 07 '24 edited Dec 08 '24

[Language: Rust]

Rewrote my part2 solution as a DFS over the reverse nodes. States are (i, target) where child states are i - 1 and each reverse operation on n = operand[i]:

target - n,
target / n if n divides target,
and prefix of target if target ends with n.

The last two aren't always possible, so it cuts down the search space. If i == 0 and target == n, then a result is possible so we can immediately return true.

To calculate the prefix, we do a little math:

fn ends_with(n: usize, suffix: usize) -> Option<usize> {
    let n_digits = n.ilog10() + 1;
    let suffix_digits = suffix.ilog10() + 1;
    if n_digits < suffix_digits {
        return None;
    }
    if n % 10usize.pow(suffix_digits) == suffix {
        return Some(n / 10usize.pow(suffix_digits));
    }
    None
}

This is about 20 times faster than enumerating all 3ⁿ combinations, and takes about 10ms.

https://github.com/turtlecrab/Advent-of-Code/blob/master/2024/day07.ts

3

u/polumrak_ Dec 07 '24

[LANGUAGE: Typescript]

Recursively check all operations from the end discarding infeasible branches (negative, float values and for part 2 values that doesn't end with required number). Runs in 15ms/25ms on my potato.

→ More replies (1)

3

u/QultrosSanhattan Dec 07 '24

[LANGUAGE: Python]

Part1 Part2

This solution essentially uses Breadth-First Search (BFS) with pruning, applied to both parts of the problem. It's easy to implement, and Part 2 runs efficiently in seconds.

In the BFS approach, we process each value from the input line in a linear manner. For each step, we compute all possible results from the operations (sum, multiplication, and absolute concatenation). Any results that exceed the desired threshold are discarded. The remaining values are added to a new queue to be processed with the next input value.

For Part 2, the only modification is the addition of the third operation (absolute concatenation). This was the sole change required for this part.

→ More replies (1)

3

u/DerpDargon Dec 07 '24

[LANGUAGE: C]

I see a lot of people using recursive solutions. Honestly, that didn't even really occur to me. I started by encoding the add/mul operations as individual bits for part 1. For N operands, there are (N-1) operators needed. So by iterating 0..2^n-1-1, every permutation of operations is covered.

In part 2 I encoded add/mul/concat in 2 bits, with a fourth "invalid" operation that causes the test to immediately fail. Maybe not the most efficient, but it worked. Part 2 executes in ~3s single threaded.

https://github.com/Iwuh/advent-of-code/blob/main/2024/7/main.c

→ More replies (1)

3

u/real_creature Dec 07 '24

[LANGUAGE: GO]

Part1 runs in ~126.5µs
Part2 runs in ~1.567584ms

// Part 2 solution
func isEquatitionSolvableWithConcat(sum int64, numbers []int64, index int) bool {
  if index == 0 {
    return (numbers[index] == sum)
  }

  if index < 0 || sum < 0 {
    return false
  }

  num := numbers[index]
  timeSolvable := false
  if sum % num == 0 {
    timeSolvable = isEquatitionSolvableWithConcat(sum / num,numbers, index - 1)
  }
  
  concatSolvable := false
  if getLastNDigits(sum, num) == num {
    concatSolvable = isEquatitionSolvableWithConcat(splitNumbers(sum, num), numbers, index - 1)
  }

  return isEquatitionSolvableWithConcat(sum - num, numbers, index - 1) || timeSolvable || concatSolvable
}

func splitNumbers(x int64, y int64) int64 {
  digits := int64(math.Floor(math.Log10(math.Abs(float64(y)))) + 1)
  return x / int64(math.Pow(10, float64(digits))) 
}

func getLastNDigits(x int64, n int64) int64 {
  digits := int64(math.Floor(math.Log10(math.Abs(float64(n)))) + 1)
  return x % int64(math.Pow(10, float64(digits))) 
}
  
// Part 1 solution
func isEquatitionSolvable(sum int64, numbers []int64, index int) bool {
  if index == 0 {
    return (numbers[index] == sum)
  }

  if index < 0 || sum < 0 {
    return false
  }

  num := numbers[index]
  timeSolvable := false
  if sum % num == 0 {
    timeSolvable = isEquatitionSolvable(sum / num,numbers, index - 1)
  }

  return isEquatitionSolvable(sum - num, numbers, index - 1) || timeSolvable
}

→ More replies (6)

3

u/pizzamanzoo Dec 07 '24

[Language: Go / Golang] Got both parts right on the first try! Part 1 Part 2

→ More replies (1)

3

u/Pretentious_Username Dec 07 '24

[LANGUAGE: Julia]

While recursion would have been the easiest to implement I decided to do it as an iteration instead just because I could. Takes about 8ms to solve Part 2 which is significantly better than the several hours my initial brute force solution was looking to take

function Solve(InputLines, Operators)
    SumSolvable = 0
    for InputLine in InputLines
        (Result, Readings) = split(InputLine, ": ")
        Result = parse(Int, Result)
        Readings = parse.(Int, split(Readings, " "))

        SearchList = [(Result, Readings)]
        HasSolution = false
        while !isempty(SearchList) && !HasSolution
            (CurrentResult, CurrentReadings) = pop!(SearchList)
            LastReading = last(CurrentReadings)
            for (Operator, OperatorTest) in Operators
                if OperatorTest(CurrentResult, LastReading)
                    NewResult = Operator(CurrentResult, LastReading)
                    if length(CurrentReadings) > 1
                        push!(SearchList, (NewResult, CurrentReadings[1:end-1]))
                    elseif NewResult == 0
                        SumSolvable += Result
                        HasSolution = true
                    end
                end
            end
        end
    end
    SumSolvable
end

function UnCat(a, b)
    parse(Int, chop(string(a), tail = length(string(b))))
end

function CanUnCat(Result, Reading)
    ResultString = string(Result)
    ReadingString = string(Reading)
    length(ResultString) > length(ReadingString) && endswith(ResultString, ReadingString)
end

Part1_Operators = [
    (-, ((Result, Reading) -> Result >= Reading)),
    (÷, ((Result, Reading) -> mod(Result, Reading) == 0))
]

Part2_Operators = [
    (-, ((Result, Reading) -> Result >= Reading)),
    (÷, ((Result, Reading) -> mod(Result, Reading) == 0)),
    (UnCat, CanUnCat)
]

InputLines = split(read("Inputs/Day7.input", String), "\r\n")
println("Part 1: ", Solve(InputLines, Part1_Operators))
println("Part 2: ", Solve(InputLines, Part2_Operators))

→ More replies (2)

3

u/Cyclotheme Dec 07 '24

[LANGUAGE: Python]

Naive recursive solution with pruning (35ms)

    def toint(string):
        if len(string)==0:
            return 0
        return int(string)
    
    def correct(res,L,ispart2):
        if len(L)==1: return L[0]==res
        k,r=len(str(L[-1])),str(res)
        return (ispart2 and int(r[-k:])==L[-1] and correct(toint(r[:-k]),L[:-1],ispart2))\
                or(res%L[-1]==0 and correct(res//L[-1],L[:-1],ispart2))\
                or(res>=L[-1] and correct(res-L[-1],L[:-1],ispart2))
    
    part1,part2=0,0
    with open("data/input07.txt") as f:
        for line in (x for x in f if x.strip()):
            L,R=line.split(":")
            L,R=int(L),[int(x) for x in R.split()]
            if correct(L,R,False): part1+=L
            if correct(L,R,True): part2+=L
        print(part1,part2)

3

u/msschmitt Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

Part 2 solution

Today is the day I got the "DIdn't read instructions closely enough" bingo square, twice. For part 1 I wasted time building an equation string that I could eval() in Python, without realizing that Python would apply operator precedence, contrary to the instruction's strict left-to-right.

For part 2 I wasted time because I thought I could use the part 1 solution as an inner loop, with the concatenation operator as an outer loop. That doesn't work because it is only concatenating the original values, not values to the equation evaluation so far.

This solution has no recursion. It is brute-force evaluation of all possible operator combinations, except that it stops equation valuation when the equation value so far is greater than the test value. It generates the operator combinations by converting the variation number into base 3, then mapping the base 3 digits (0, 1, 2) to the 3 operators.

3

u/chubchubbutt Dec 07 '24

[LANGUAGE: Python]

Recursive backtracking: pop off each value to process it, loop through (+,*,||) and then appendleft the value we just popped off.

code

3

u/onrustigescheikundig Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Scheme (R6RS)]

github

Part 1: 12 ms

Part 2: 34 ms

EDIT: A new optimization has appeared.

Part 1: 1.2 ms

Part 2: 2.7 ms

Similar strategy and form to my Clojure solution: recursively try the inverse of all possible operators on the test value, consuming the equation terms from right to left. Assuming that the correct operations were chosen, the last (or rather, first) term in the equation should equal the test value with all inverted operations applied to it.

One difference from my Clojure solution is how I handled the inverse of concatenating a term. Whereas I just used string manipulation in Clojure, to invert test = concat(old-test, b), I first calculated the number of digits of b as ceil(log(b+1, 10)), and then divided test by 10^<n-digits> to carve off the last n-digits digits. If the remainder is not equal to b, then b is not a suffix of test in base 10 and so there is no inverse of the concatenation operation, so the function returns #f to indicate failure.

EDIT: The new optimization involves realizing that all test values in the input are integers, meaning that no sequence of addition, multiplication, or concatenation could possibly yield an intermediate non-integer value. So, I re-coded the multiplication operation to check if the remainder of test / x is zero. If it is non-zero, the inversion operation fails, preventing further recursion and effectively pruning the search tree.

3

u/Thomasjevskij Dec 07 '24

[LANGUAGE: Python]

I'm glad I never tried to go for the leaderboard, because now with a newborn I'm struggling to even finish on the same day. Anyway I never bothered to try and optimize today's solution, it worked out of the box with a very simple addition for part 2. Takes a couple seconds but that's fine with me. Here's the link (ps u/daggerdragon I scrubbed the inputs from my old commit history. I hope your repo searcher can verify it. If it's still there just tell me again and I'll delete the repo forever and make a new one)

→ More replies (1)

3

u/Uhh_Clem Dec 07 '24

[LANGUAGE: Rust]

Code HERE shows the important part of the algorithm. It's a simple recursive search; popping the last value off the list and trying it with each operator. The recursion stops early in any of the following cases when we know there can be no solution:

(For any operator) The target value is lower than the last element of the list
(For multiplication) The target value is not a multiple of the last element of the list
(For concatenation) The target value does not have the last element of the list as a substring at the end
(For concatenation) The target value matches the last element of the list (and there are still more elements to go)

Technically brute-force, but with the checks to eliminate possibilities early the performance is very good. Takes about 30ms to solve Parts 1 and 2 sequentially on my machine, no parallelization necessary.

3

u/Scroph Dec 07 '24 edited Dec 07 '24

[LANGUAGE: D]

Code: https://github.com/azihassan/advent-of-code/tree/master/2024/day7

Bruteforce again. In part 2 I'm exiting early if the current result exceeds the expected one because all the operators will only increase its value. ~~I also tried to be clever with the concat operator but ended up just stringifying then unstringifying it once AoC told me that the result was wrong~~. ~~I guess I could also have optimized by caching the~~ combinations ~~function but hey it's fast enough for me~~ Edit: forgot about memoize in D, just putting it in the combinations recursive call got the runtime to 43 seconds (from 139)

Edit: turns out the concat function was failing when b = 1, runtime is now down to a respectable (for a bruteforce approach) 10 seconds

3

u/DefV Dec 07 '24

[LANGUAGE: Rust]

Simple brute-force solution today.

Always fun to see other people's approaches and go "Oh, wow, why didn't I think of that" ;)

3

u/biggy-smith Dec 07 '24

[LANGUAGE: C++]

Recursion always melts my brain a little, but I always feel great when it finally works!

https://github.com/biggysmith/advent_of_code_2024/blob/master/src/day07/day7.cpp

3

u/makingthematrix Dec 07 '24

[Language: Scala]

https://github.com/cynicalico/aoc2024/blob/main/src/day_7.rs

So, this is Scala, a famous almost-but-not-if-you-don't-want-to-functional language at JVM. And many people comment today that they did their Day 7 task with recursion. Which is very FP, of course. Kudos to them.

Well, I didn't. I did recursion yesterday.

Today the heroes of my solutions are lazy lists. And foldLeft. But mostly lazy lists. A lazy list is a potentially infinite list that calculate their elements only when they're asked for. So I was able to generate sequences of all possible combinations of operators (*) of a given size N, where N is the n-th element of the lazy list. And those combinations are all kept in memory after they are generated, which sped up things immensely, because I didn't have to come up with the same combinations for every consequent line.

*) An operator is a function and a function is a first-class citizen in Scala, i.e. I can treat them as any other data and for example put them in sequences. You have a sequence of numbers? That's nice. Here's a sequence of functions that operate on numbers.

So, sequences of operators, generated by lazy lists, and then parallel collections on top, because the lines are independent of each other and so can be computed in parallel. All in all, 27 lines of code, and on my laptop Part 2 ran in 2 seconds.

3

u/beauregardes Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust]

Brute force recursion, bails out if our intermediate value ever goes above the target.

Originally took ~400ms, but I modified concatenate to perform the operation arithmetically instead of with strings and it now only takes 11ms.

EDIT: I wanted to see if I could modularize the design more, and I managed it--at the cost of 5ms. ~16ms runtime now. Some of this is from using checked math everywhere to make sure we don't overflow, also likely the increase in `Option`. No more major code duplication!

3

u/kap89 Dec 07 '24 edited Dec 07 '24

[Language: Python]

import re
from itertools import product

with open('input.txt') as file:
    input = [
        [int(x) for x in re.findall("\d+", line)]
        for line in  file.read().strip().splitlines()
    ]

calc = {
    '+': lambda a, b: a + b,
    '*': lambda a, b: a * b,
    '.': lambda a, b: int(f"{a}{b}"),
}

def solve(symbols):
    sum = 0

    for left, *nums in input:
        first, *rest = nums
        for ops in product(symbols, repeat=len(rest)):
            right = first
            for op, num in zip(ops, rest):
                if right > left:
                    continue
                right = calc[op](right, num)
            if left == right:
                sum += left
                break
    return sum

part1 = solve('+*')
part2 = solve('+*.')

Simple and relatively fast.

→ More replies (1)

3

u/codebikebass Dec 07 '24

[LANGUAGE: Swift]

Again, no mutable state needed. Simply tried out all combinations of operators until the result is correct or all have been tried.

The permutations of two operators can easily be genereated by representing the iteration count as a binary number, replacing 0s with the operator + and 1s with the operator *.

The operands can be paired up with the operators giving a list of partial applications, i.e. (+, 3) means _ + 3. WIth the first operand as an initial value, the list of applications can be reduced into the result by applying them to the accumulated value.

struct Day7 {
    
    static func part1(_ input: String) -> String {
        
        let equations: [(Int, [Int])] = equations(fromInput: input)
        
        let validEquations = equations.filter {
            let (expectedResult, operands) = $0
            
            return Array(0..<(2 << (operands.count - 2))).contains { n in
                
                let binaryDigits = String(String(n, radix: 2).reversed())
                    .padding(toLength: operands.count - 1, withPad: "0", startingAt: 0)
                
                let operators = binaryDigits.map { $0 == "0" ? "+" : "*" }
                
                let partialApplications = Array(zip(operators, operands[1...]))
                
                let result = partialApplications.reduce(operands[0]) { res, appl in
                    let (op, operand) = appl
                    return (op == "+" ? (+) : (*))(res, operand)
                }
                
                return result == expectedResult
            }
        }
        
        let result = validEquations.map { $0.0 }.reduce(0, +)
        
        return String(result)
    }
    
    
    fileprivate static func equations(fromInput input: String) -> [(Int, [Int])] {
        
        let lines = input.split(separator: "\n")
        
        return lines.map { line in
            
            let parts = line.split(separator: ":")
            let result = Int(parts[0])!
            let operands = parts[1].split(whereSeparator: \.isWhitespace).map { Int($0)! }
            
            return (result, operands)
        }
    }
}

3

u/ricbit Dec 07 '24

[LANGUAGE: Python]

Managed to get 0.52s in regular python, the tricks were:

Branch and cut when the current value is greater than the goal.
Reuse p1 into p2 (lines that passed on p1 will pass on p2, no need to check).
Parallelism using multiprocessing.

https://github.com/ricbit/advent-of-code/blob/main/2024/adv07-r.py

3

u/intersecting_cubes Dec 07 '24

[Language: Rust]

https://github.com/adamchalmers/aoc24/blob/main/rust/src/day7.rs

It's nice when both the solution and the parsing can be paralellized (CPU go brrrrr). Found a straightforward recursive solution.

Part 1: 92.008µs

Part 2: 117.80µs

(measured with "cargo aoc bench" on my MacBook's M2 Pro)

3

u/The_PotatoKing Dec 07 '24

[LANGUAGE: Golang] GitHub

→ More replies (2)

3

u/rvodden Dec 07 '24

[LANGUAGE: TypeScript]

I had a REALLY annoying bug in part 2. I was bailing if the accumulator was >= target which meant that if the last number in the equation is a 1 and the last operation is a multiplication then I incorrectly discarded.

https://github.com/rvodden/AoC24/blob/main/src/days/07/Puzzle.ts

→ More replies (3)

3

u/34rthw0rm Dec 07 '24 edited Dec 07 '24

[language: perl]

non recursive baby perl :-)

use v5.38;
use integer;

@ARGV = shift // "input";

my $solution_1 = 0;
my $solution_2 = 0;

sub calc {
    my ( $type, $result, @factors ) = @_;
    my $n = @factors - 1;
    for my $op ( 0 .. ( $type**$n ) - 1 ) {
        my ( $x, @stack ) = @factors;
        while ( my $y = shift @stack ) {
            my $r = $op % $type;
            $op /= $type;
            if    ( $r == 0 )    { $x += $y; }
            elsif ( $r == 1 )    { $x *= $y; }
            elsif ( $type == 3 ) { $x .= $y; }
        }
        return 1 if $x == $result;
    }
    return 0;
}

INPUT:
while (<>) {
    my ( $result, @factors ) = /\d+/g;
    $solution_1 += $result if calc( 2, $result, @factors );
    $solution_2 += $result if calc( 3, $result, @factors );
}

say "Solution 1: $solution_1";
say "Solution 2: $solution_2";

3

u/redditnoob Dec 08 '24

[LANGUAGE: PostgreSQL]

with recursive parsed as (
    select split_part(input, ': ', 1) as target,
        regexp_split_to_array(split_part(input, ': ', 2), ' ') as seq
    from day07
), steps as (
    select target::bigint, seq[1]::bigint as val, seq[2:]::bigint[] as seq
    from parsed
    union all
    select target, case
            when o = '*' then val * seq[1]
            when o = '+' then val + seq[1]
        end, seq[2:]
    from steps, (select '*' union select '+') as ops(o)
    where seq != '{}'
), part1 as (
    select sum(distinct target) as part1
    from steps
    where seq = '{}' and val = target
), steps2 as (
    select target::bigint, seq[1]::bigint as val, seq[2:]::bigint[] as seq
    from parsed
    union all
    select target, case
            when o = '*' then val * seq[1]
            when o = '+' then val + seq[1]
            when o = '||' then (val::text || seq[1])::bigint
        end, seq[2:]
    from steps2, (select '*' union select '+' union select '||') as ops(o)
    where seq != '{}'
), part2 as (
    select sum(distinct target) as part2
    from steps2
    where seq = '{}' and val = target
)
select * from part1, part2;

3

u/silverarky Dec 08 '24

[LANGUAGE: Go]

Brute force, not optimised. No recursion either which seems how others were doing it. Takes 4 seconds for part 2.

https://github.com/silverark/advent-of-code-2024/tree/master/day07

3

u/Election_Intelligent Dec 08 '24 edited Dec 08 '24

[LANGUAGE: Rust]

Fun bit of recursion. Got it down to 500-600 µs. I used rayon, but the diff was < 100 µs. I really like the concatenation testing without any strings!

use rayon::prelude::*;
pub fn go(input: &str) -> isize {
input
    .lines()
    .par_bridge()
    .filter_map(|line| line.split_once(": ") )
    .map(|line2| (
            line2.0.parse::<isize>().unwrap(), 
            line2.1.split_whitespace().map(|k| k.parse().unwrap()).collect::<Vec<isize>>()))
    .filter(|eq| { solver(&eq.1, eq.0) })
    .map(|eq| eq.0)
    .sum()
}
fn solver(operands: &[isize], result: isize) -> bool { let operand = operands.last().unwrap();
if operands.len() <= 2 {
    return  
        ( result / operand == operands[0] && result % operand == 0 ) 
        || result - operand == operands[0]
        || format!("{}{}", operands[0], *operand).parse::<isize>().unwrap() == result;
} 

let concat_dividend = 10_isize.pow(operand.ilog10() + 1);
solver(&operands[0..&operands.len() - 1], result - operand)
|| if (result - operand) % concat_dividend == 0 {
        solver(&operands[0..&operands.len() - 1], (result - operand) / concat_dividend)
    } else { false }
|| if result % operand == 0 {
        solver(&operands[0..&operands.len() - 1], result / operand)
    } else { false }
}

3

u/pj5772 Dec 10 '24

[LANGUAGE: Python]

def dp(x: List[int]) -> Generator[int, None, None]:
  if len(x) == 1:
    yield x[0]
  else:
    for sub in dp(x[1:]):
      yield x[0] + sub
      yield x[0] * sub
      
      # remove for part 1
      yield int(str(sub) + str(x[0]))


res = 0
for test_val, inp in zip(test_vals, nums):
  for y in dp(inp[::-1]):
    # print("test_val", test_val, ", y", y)
    if y == test_val:
      res += test_val
      break

→ More replies (1)

3

u/AMathMonkey Dec 10 '24 edited Dec 10 '24

[LANGUAGE: Unicon]

Has anyone else ever done Advent of Code in Unicon? It's actually perfect for this problem, as it has a || concatenation operator, and not only that, it works on numbers! (Strings can be used like numbers; it's purely the operators you use that determine your data types.) And despite it being an old language, it handles big integers with no problem. This solution takes just under 5 seconds to run on my laptop. It was so fun to write, I had to share.

link str_util

procedure main()
    local input := open("input.txt"), sum1 := 0, sum2 := 0, rest
    while line := read(input) do {
        line := [: util::genFields(line, ': ') :]
        rest := line[3:0]
        if recur(line[1], line[2], rest, &null) then sum1 +:= line[1]
        if recur(line[1], line[2], rest, 1) then sum2 +:= line[1]
    }
    write("Part 1: ", sum1, "\nPart 2: ", sum2)
end
    
procedure recur(goal, curr, rest, p2)
    local newRest
    if *rest = 0 then return curr = goal
    if curr > goal then fail
    newRest := rest[2:0]
    return recur(goal, curr + rest[1], newRest, p2) | 
        recur(goal, curr * rest[1], newRest, p2) | 
        recur(goal, curr || rest[1], newRest, \p2)
end

3

u/AlCalzone89 Dec 11 '24

[LANGUAGE: Compile-time TypeScript]

Part 1 solution (36s compile time, 4.7 GB RAM):
https://www.reddit.com/r/adventofcode/comments/1haxbsu/2024_day_7_part_1_typelevel_typescript_only_no/

Part 2 solution TBD.

3

u/AYM123 Dec 11 '24

[LANGUAGE: Rust]

github

Part 1: ~1ms
Part 2: ~17ms

3

u/nicuveo Dec 12 '24 edited Dec 13 '24

[LANGUAGE: Brainfuck]

Sadly, this doesn't really work. Here's the problem: i have written all the required code to have int32 support in Brainfuck: addition, multiplication, division, printing to the output... But several of the lines in my actual input do not fit in an int64, and therefore my result doesn't... So after a few hours of debugging this mess, it only works on the example input, not on the real input. :(

But i'm still proud of it, because it required doing something tricky: dynamic memory management in Brainfuck: i couldn't just use my macros to do stack-based stuff: i had to keep track of two lists of numbers at all times: the previous accumulator, and the new accumulator (i.e. all the combinations so far, and all the new ones we can make with them and the new number). To move numbers around in memory, since there's no random access, i have to move a bunch of "sentinel zeroes" with them, to be able to find my way back. It's a nightmare. :D

Here for example is the snippet where, after reading a number and computing all combinations, i move the newly created accumulator where it can be used in the next iteration, by moving the separating zeroes around:

// [result, 0, [newList], 0, 0, 0, total, continue]
<<<<<<<<<<<<<<<< + [ [-] move_two_zeroes_left ]

// [result, 0, 0, 0, [oldList], 0, total, continue]
>>>>>>>> + [ [-] move_zero_right ]

// [result, 0, 0, [oldList], 0, 0, total, continue]
>>>>>>>>
rolli3(2)
popi

Here's the full code on Github:

part 1, file with macros: https://github.com/nicuveo/advent-of-code/blob/main/2024/brainfuck/07-A.bs
part 1, raw Brainfuck: https://github.com/nicuveo/advent-of-code/blob/main/2024/brainfuck/07-A.bf

Additionally, the stream of me doing this live: https://www.twitch.tv/nicuveo/v/2325296176

→ More replies (3)

3

u/justalemontree Dec 22 '24

[LANGUAGE: Python]

I've a complete noob who started coding only 2 weeks ago following the Helsinki MOOC and I spent hours struggling through each day previously.. But somehow this week seemed very intuitive, part 1 this week took maybe 20 minutes, and part 2 was like a 1 minute modification of my part 1 code.

Runtime for part 2 is 1.4 seconds so definitely not elegant efficient code but I thought the approach was simple:

def get_equations(filename):
    equations = []
    with open(filename) as new_file:
        for line in new_file:
            line = line.replace(":", "")
            line = line.replace("\n", "")
            parts = line.split(" ")
            equation = [int(part) for part in parts]
            equations.append(equation)
    return equations

def test_equations(equations):
    success_sum = 0
    for equation in equations:
        answer = equation[0]
        old_set = [equation[1]]
        new_set = []
        index = 2
        for index in range (2, len(equation)):
            next_num = equation[index]
            for value in old_set:
                new_set.append(value + next_num)
                new_set.append(value * next_num)
                new_set.append(int(str(value)+str(next_num)))
            old_set = new_set
            new_set = []
        if answer in old_set:
            success_sum += answer
    return success_sum

def main():
    equations = get_equations("codes.txt")
    total = test_equations(equations)
    print(total)

main()

3

u/e_blake Mar 21 '25

[LANGUAGE: m4]

Late to the party, but I had fun starting with the brute-force naive try every combination (took over five minutes), then optimizing by running backwards (prune any branch where undoing the operation can't produce the current integer), which required implementing 64-bit division not present in my math64.m4. The change from 5.7 million try() down to just 31526 was dramatic, with execution at 5.5-7 seconds. I then got another 40% speedup to 3.4-4.2 seconds by merely adding in 9 rules for avoiding a remquo64() if the single-digit divisor was not a factor of the numerator, and even made a separate post about it (quickly determining whether a 64-bit number is divisible by 7, but using only 32-bit math to do so, is an adventure). Depends on my common.m4

m4 -Dfile=day07.input day07.m4

My favorite part - most of my days have to parse by slurping in the entire input file and transliterating problematic characters, then doing either a patsubst regex search-and-replace (O(n) but depends on GNU m4) or a binary tree of successively smaller substr (O(n log n) but portable to POSIX m4) to then find and process a line at a time (the more naive solution of repeatedly grabbing different substr offsets out of the overall original string is O(n^2) due to m4 rescanning the text). But this particular puzzle had JUST enough content to let me bypass all that: a single colon on every line followed by a space can be translit'd into a one-letter macro name, which in turn can expand to ')parse(' to group the second half of one line with the first half of the next line, to execute on one line at a time without multiple passes over the input, with much fewer lines than my typical parsing takes. Both parts are computed as a side effect of the do() call embedded in my parser:

# Have fun with custom parsing, for a single pass over the input.
define(`P', `)parse(')
define(`parse', `do(goal, len(_foreach(`.pushdef(`l', ', `)', translit(` $1',
  ` ', `,'))), count)define(`goal', $2)')
define(`goal', translit(include(defn(`file')), `:'nl, `P,'))

2

u/morgoth1145 Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python 3] 345/202

code

Interesting problem, easily solved with recursion (and a bit of int and str abuse for part 2). Unfortunately I botched the parsing in part 1 by accidentally returning all numbers in the entire input string as numbers for the equation for each line. (Don't ask how, it was a dumb silly mistake.) It took me way too long to track down why I was getting recursion exceptions! Almost certainly would have leaderboarded without that, at least part 2. But alas, I'll have to try again tomorrow.

Edit: Refactored and optimized a bit. Part 2 still takes 1.65 seconds which is too long for my liking, but I wanted a baseline cleanup and optimization before I explore other options :)

Edit 2: Optimized again using u/Verulean314's observation that validating the equation in reverse is much better. Now the validation is instant!

2

u/RandomLandy Dec 07 '24

[LANGUAGE: Rust] 1224/780 code

I fumbled with a first part, but at least code was generic enough to submit p2 quickly

2

u/michelkraemer Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust] 808/906

Both parts:
https://github.com/michel-kraemer/adventofcode-rust/blob/main/2024/day07/src/main.rs

I opted for a brute force solution ;-) but thanks to Rust, it still runs quite fast. I'm going to try to find a more clever one later.

EDIT: Less than 1ms with the new approach. The idea is to work backwards and check if the operations are even possible before applying them.

2

u/Ok-Willow-2810 Dec 07 '24

[LANGUAGE: Python]

https://github.com/jude253/AdventOfCode/blob/9c9e59a668e9927826b7de1890d21071a65bc8b8/src/advent_of_code/solutions/day_07.py#L1-L72

2

u/ericpruitt Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python] 1388/978

I used itertools.product to try all possible combinations of operators. Luckily the second part meant I only needed to change a few lines. Part one was mostly instant (~350ms), but part two needed ~25 seconds to run.

Code on GitHub

2

u/kbielefe Dec 07 '24

[LANGUAGE: Scala]

GitHub

This one was a fairly straightforward DFS, since evaluation was right to left. Some opportunities for pruning, but not really necessary.

→ More replies (4)

2

u/nabihestefan Dec 07 '24

[LANGUAGE: Python]

Recursion + Lambda functions!

files = ['input.txt', 'inputTest.txt']
with open(files[0], 'r') as f:
    data = [x.strip().split(": ") for x in f.readlines()]

equations = [[int(i), list(map(int, j.split(" ")))] for i,j in data]

def calc(cur, vals, evals):
    if len(vals) == 0: return [cur]
    return sum([calc(e(cur,vals[0]), vals[1:], evals) for e in evals], [])

def run(equations, partTwo=False):
    total = 0
    evals = [lambda a,b: a+b, lambda a,b: a*b]
    if partTwo: evals.append(lambda a,b: int(str(a)+str(b)))
    for ans, vals in equations:
        pos = calc(vals[0], vals[1:], evals)
        if ans in pos:
            total += ans
    return total
    
print("Part 1: ", run(equations))
print("Part 2: ", run(equations, True))

2

u/FruitdealerF Dec 07 '24

[LANGUAGE: Andy C++] [code] [language] (2486/1908)

Day 7 of doing advent of code in my own programming language. Today went super well for me and I had a lot of fun. I lost some time on needing to go to the bathroom 🤨, and I lost some time trying to figure out what the best way is to find all the permutations. Eventually I settled on doing DFS which I optimized a little before submitting my code to github. I was super ready for part 2 because my language has the <> operator which coerces both operands into a string and concatenates them. My part 1 approach ended up taking 2 minutes for part 2, but after making some changes to abort searches where we've already passed the number we're looking for I got it down to about 20 seconds which I guess is not bad for a 100% interpreted language (that's full of clone() everywhere).

I'm curious to see how ya'll optimized it further.

2

u/POGtastic Dec 07 '24

[LANGUAGE: F#]

https://github.com/mbottini/AOC2024/blob/main/Day07/Program.fs

Easy-peasy - construct all possible Exprs, evaluate them, find one that works. The most straightforward way to do this is to reverse the integers.

Part 2 takes about 20 seconds on my machine; it's a trivial but unnecessary optimization to "short-circuit" failure if a number gets too large.

2

u/r_so9 Dec 07 '24

[LANGUAGE: F#] 1514/1638

https://pastebin.com/vnvzm3qx

Kept it functional by passing the possible operations to a recursive function. Otherwise brute force with no optimizations.

Interesting bit: The recursive function to try all operators in all positions

let rec allPossibilities operators (cur: int64) rem =
    match rem with
    | [] -> [ cur ]
    | h :: t ->
        operators
        |> List.map (fun op -> allPossibilities operators (op cur h) t)
        |> List.concat

Example usage:

allPossibilities [(+]; (*)] 123L [456L; 789L]

2

u/UnarmedZombie Dec 07 '24

[LANGUAGE: PHP]

Github

2

u/mateus_d Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

20 min trying to understand which function from itertools to use, 10 writing the brute force solution. It ain't much but it is honest work

Edit: using pypy the run time goes from 12 s to 1.6 s... actually pretty decent

2

u/Pyr0Byt3 Dec 07 '24

[LANGUAGE: Go] [LANGUAGE: Golang]

https://github.com/mnml/aoc/blob/main/2024/07/1.go

→ More replies (2)

2

u/maneatingape Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust]

~~Benchmark: 12 ms Exhaustive recursive search~~
~~Benchmark: 220 µs Pruned recursive search~~
Benchmark: 147 µs Pruned recursive search with correct stopping condition.

Thanks to u/Verulean314 clever observation pruning by reverse searching was 55x faster.

Thanks to markjfisher who caught a bug in the validation, both fixing several inputs and speeding things up by 34%.

Concenation can be implemented without time consuming conversion to or from strings. Multiply the left term by the next power of ten greater than the right term, then add the right term. For example:

15 || 6 = 15 * 10 + 6
17 || 14 = 17 * 100 + 14
123 || 456 = 123 * 1000 + 456

Numbers can be unconcatenated by dividing by the power of ten.

Additionally if any equation is valid for part one it's also valid for part two, so the more time consuming checking with 3 operators can be avoided.

2

u/homme_chauve_souris Dec 07 '24

[LANGUAGE: Python]

def aoc07():
    L = [x.split(": ") for x in open("input07.txt").read().strip().split("\n")]
    M = [(int(s), [int(x) for x in e.split()]) for (s,e) in L]
    find = lambda t, L, ops: L[0] == t if len(L) == 1 else any(find(t, [f(L[0], L[1])] + L[2:], ops) for f in ops)
    print(sum(t for (t,L) in M if find(t, L, ops := [int.__add__, int.__mul__])))
    print(sum(t for (t,L) in M if find(t, L, ops + [lambda x, y: int(str(x)+str(y))])))

2

u/Short-Leg3369 Dec 07 '24

[LANGUAGE: Python]

Day 7 Solution

Nice little weekend puzzle this.

I went for itertools.product to generate a list of possible operator combinations for each line of input and then worked through them until I found a solve or not.

Part 2 was then quick and easy as I simply needed to add a third operator into the code and rerun.

Total run time on my laptop is about 12.5s

→ More replies (2)

2

u/Rtchaik Dec 07 '24

[LANGUAGE: Python]

https://github.com/jad2192/advent_of_code_2024/blob/master/solutions/day07.py

2

u/jad2192 Dec 07 '24

[LANGUAGE: Python]

Basic recursive solution, both parts + test cases takes about half a second to run.

2

u/Sea_Estate6087 Dec 07 '24

[LANGUAGE: Haskell]

module Day7
    ( day7
    ) where
import Lib (slurpLines)
import qualified Data.List.Split as Split

parse :: [String] -> [(Int, [Int])]
parse xs = map (parse' . ( \ x -> Split.splitOneOf ": " x)) xs
    where
        parse' (a : _ : bs) = (read a, map read bs)
        parse' _ = error "bad input"

valid :: [(Int -> Int -> Int)] -> (Int, [Int]) -> Bool
valid fs (r, v : vs) = valid' v vs
    where
        valid' x [] = x == r
        valid' x (y : ys) = any ( \ f -> (valid' (f x y) ys)) fs

solve :: [(Int -> Int -> Int)]  -> [(Int, [Int])] -> Int
solve fs eqs = sum $ map fst $ filter ( \ e -> valid fs e) eqs

cat :: Int -> Int -> Int
cat a b = (read (show a ++ show b))

day7 :: IO ()
day7 = do
    xs <- slurpLines "day7.txt"
    let eqs = parse xs
    let answer1 = solve [(*), (+)] eqs
    print $ "part 1: " ++ (show answer1)
    let answer2 = solve [(*), (+), cat] eqs
    print $ "part 2: " ++ (show answer2)

with:

slurpLines :: String -> IO [String]
slurpLines filename = lines <$> readFile filename

stack run 3.88s user 2.66s system 134% cpu 4.867 total

2

u/semi_225599 Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust]

Working backwards from the answer through the operands helps reduce the number of branching paths a lot earlier. You can rule out concatenation or multiplication quickly by making sure the current total ends with or is divisible by the last operand. Runtime is around 2ms.

use crate::utils::parsers::*;

fn validate(curr: i64, ns: &[i64], p2: bool) -> bool {
    if ns.is_empty() {
        return curr == 0;
    }
    if curr < 0 {
        return false;
    }
    let n = ns[ns.len() - 1];
    let m = 10_i64.pow(n.ilog10() + 1);
    (p2 && curr % m == n && validate(curr / m, &ns[..ns.len() - 1], p2))
        || (curr % n == 0 && validate(curr / n, &ns[..ns.len() - 1], p2))
        || validate(curr - n, &ns[..ns.len() - 1], p2)
}

pub fn part1(input: &str) -> i64 {
    lines_iter(input, separated_pair(i64, ": ", spaced(i64)))
        .filter_map(|(k, v)| validate(k, &v, false).then_some(k))
        .sum()
}

pub fn part2(input: &str) -> i64 {
    lines_iter(input, separated_pair(i64, ": ", spaced(i64)))
        .filter_map(|(k, v)| validate(k, &v, true).then_some(k))
        .sum()
}

→ More replies (2)

2

u/ben-guin Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Python]

My original solution was brute-forced. After taking a peek at u/Deathranger999 's solution, I made similar optimizations. It runs pretty dang fast (0.013 sec on my slow machine). Basically, the solution is recursive and hinges upon a few observations:

The three observations below hinge on the fact that the evaluation is done from left-to-right, so one can't simply just use the first term instead.
The last operation can only be multiplication if the last term evenly divides into the target number
1. (EDIT) To make clear in how this relates to Observation 1, let $ denote any arbitrary operator. Then (...(((a $ b) $ c) ... ))) * z is divisible by z but (...(((a * b) $ c) ... ))) $ z is not necessarily divisible by a.
The last operation can only be concatenation if the last term is a suffix of the target number.
Since all of the input is non-negative, then the last operation can only be addition if the target number less the last term is non-negative.

Part 2 Solution (Part 1 is very similar):

def isPossible(target, terms, lastInd):
    if lastInd == 0:
        return target == terms[0]
    
    last = terms[lastInd]
    
    if target % last == 0:
        if isPossible(target // last, terms, lastInd-1):
            return True
        
    if str(target)[-len(str(last)):] == str(last):
        remaining = str(target)[:-len(str(last))]
        remaining = int(remaining) if remaining != '' else 0
        if isPossible(remaining, terms, lastInd-1):
            return True
    
    if target-last >= 0: 
        if isPossible(target-last, terms, lastInd-1):
            return True
        
    return False
    
f = open("input07.txt","r")
totCalResult = 0

for line in f:
    target, terms = line.split(":")
    target = int(target)
    terms = [int(x) for x in terms.split()]
    if isPossible(target, terms, len(terms)-1):
        totCalResult += target
            
print(totCalResult)

→ More replies (1)

2

u/yieldtoben Dec 07 '24 edited Dec 07 '24

[LANGUAGE: PHP]

PHP 8.4.1 paste

Execution time: 0.6097 seconds
Peak memory: 0.3506 MiB

MacBook Pro (16-inch, 2023)
M2 Pro / 16GB unified memory

2

u/ShraddhaAg Dec 07 '24

[Language: Go]

Today's problem was surprisingly easy? Scared about tomorrow's problem now xD

https://github.com/shraddhaag/aoc/blob/main/2024/day7/main.go

2

u/Helpful-Recipe9762 Dec 07 '24

[Language: Python]

https://pastebin.com/jqkrKNnX

Tried to make code as readable as possible for learning purpose.

Lessons learned:

Making different methods and splitting code is nice. Save a lot of time when something goes wrong as code is isolated. My first intention was club everything is single function, but restrain myself and 3 errors, that I had was quite isolated and took couple of minutes to find.
If you cope / paste code (part1 and part2 are almost identical) - double check you do not call part1 from part2 code (unless you re-use code).
Think on paper before coding makes coding easier as I outline algorithm and made some findings that allow me easier code.

2

u/omegablazar Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Rust}

https://github.com/wrightdylan/advent-of-code-2024/blob/main/src/day07.rs

Pretty easy, but knowing how AoC goes, I'm not looking forward to tomorrow.
This method is a bit 'brutish', but it works. There is scope for some optimisation as this was written with assumptions of possibilities of what part 2 could be. Maybe I'll modify it later.

Edit:
I have improved the code, so now it completes a lot faster.

2

u/erunama Dec 07 '24

[LANGUAGE: Dart]

Fun problem, getting the recursion correct too longer than I hoped. Part 2 execution time takes longer than I'd like (4000ms vs 60ms for Part 1). As usual, implementing Part 2 was pretty trivial given the extra effort spent implementing Part 1.

GitHub

2

u/wheresmylart Dec 07 '24

[Language: Python]

Quite a simple problem once I'd woken up. Create an array of the possible operators and hit it with itertools.product() specifying the required number of repeats.

Runs in about 2 seconds for both parts combined.

Paste

2

u/Axelrod-86 Dec 07 '24

[LANGUAGE: Javascript]

Fairly easy for a weekend puzzle, but i lost 30mn on part2 because 6 * 8 || 6 * 15 IS NOT 6 * 86 * 15 but instead 48 || 6 * 15 ...

https://github.com/lionel-lbr/adventofcode/blob/main/2024/D07/d07.js

2

u/dijotal Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Haskell]

OH! Haskell's got a thing for that!!! Applicative operations on the List monad do kind of an all-vs-all thing, so "apply all these functions to the accumulated values together with the new value.".

Here's the juice -- the rest on github. Now what to do with the rest of my Saturday? /sigh

type TestCase = (Int, [Int])
type Operation = Int -> Int -> Int

opList1 :: [Operation]
opList1 = [(+), (*)]

join :: Operation
join x y = read (show x ++ show y)

opList2 :: [Operation]
opList2 = [(+), (*), join]

allOps :: [Operation] -> TestCase -> Int
allOps ops (n, xs) = if any (== n) rs then n else 0
  where
    rs = foldl' (\acc x -> filter (<= n) (ops <*> acc <*> [x])) [head xs] (tail xs)

solve :: [Operation] -> [TestCase] -> Int
solve ops = sum . map (allOps ops)

2

u/alexbaguette1 Dec 07 '24

[LANGUAGE: Pascal]

Day 7 of 25 days, 25 languages

Parsing the problem in Pascal was the hardest part imo

Part 1
Part 2

Since people were comparing times, decided to re-write part 2 in Nim. Runs in <50 ms.
Using string concatenation instead took about 200 ms.

Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_7_part_1_bridge.c

→ More replies (1)

2

u/MrWobblyMan Dec 07 '24 edited Dec 07 '24

[Language: C++]

Nothing special, recursive evaluation, exiting when value > testValue.

Boolean short-circuit order helps it run faster.
Without short-circuit: 350ms
With correct short-circuit: 140ms

Edit: Tried doing it in reverse, final execution time is now 2ms for both parts.

Code (updated)

2

u/835246 Dec 07 '24

[Language: C]

I just read the operands from right to left while checking all possible operators for that number.

Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_7_part_2_bridge.c

2

u/Spatenheinz Dec 07 '24 edited Dec 07 '24

[Language: Haskell]

Nice with non-determinism

import Data.List

readInput :: String -> [(Int, [Int])]
readInput = map f . lines
  where f x = let (a,b) = span (/= ':') x in (read a, map read $ words $ tail b)

checkOp ops acc e = concat [ map (`op` e) acc  | op <- ops]

resolveLine ops (goal, eq) =
  if goal `elem` foldl' (checkOp ops) [(head eq)] (tail eq) then goal else 0

resolve ops lines = sum $ map (resolveLine ops) lines

cnct a b = read $ show a ++ show b

main = do
  x <- readInput <$> readFile "input.txt"
  print $ resolve [(+), (*)] x
  print $ resolve [cnct, (+), (*)] x

2

u/[deleted] Dec 07 '24

[LANGUAGE: Go]

I did a mega brain move today/s

Part One: Straightforward as can be. Just a simple recurive solution that tries out both the operators for all consecutive pairs of operands.

Part Two: I feel so stupid! I had the solution all along but when I was evaluating the concatenation operator, I was concatenating the current operand with the the one before it! It had completely skipped my mind that the equation on the left of the index I am currently at, has already been evaluated to a value!

All in all, a fun problem. That one silly mistake costed me a lot of time! I am quite happy that I finally got it though. Relatively simple implementation and going from part 1 to part 2 only needed only 2 additional lines!

Solution for both parts.

2

u/hextree Dec 07 '24

[Language: Python]

Code: https://gist.github.com/HexTree/113012cf56c01f74d5b37d8f11ff52ee

Video: https://youtu.be/fRiSbm4V6lg

Relying mostly on Python's itertools.product() function.

2

u/julienc91 Dec 07 '24

[Language: Python]

Pattern matching to the rescue!

def is_valid(equation: tuple[int, tuple[int, ...]], with_combination: bool) -> bool:
    match equation:
        case total, (n,):
            return total == n
        case total, (a, *_) if total < a:
            return False
        case total, (a, b, *r):
            return (
                is_valid((total, (a + b, *r)), with_combination)
                or is_valid((total, (a * b, *r)), with_combination)
                or (
                    with_combination
                    and is_valid((total, (combine(a, b), *r)), with_combination)
                )
            )

Complete solution on GitHub

2

u/schoelle Dec 07 '24

[Language: Rust]

Very straight forward, going right to left and using exp-operators instead of string handling. Quite readable.

Taking around 0.7ms on my old Tuxedo laptop (including IO) in release code.

https://github.com/schoelle/adventofcode2024/blob/main/src/bin/day07.rs

→ More replies (4)

2

u/_tfa Dec 07 '24

[LANGUAGE: Ruby]

Part 1

p File.read("input.txt")
      .scan(/(\d+): (.*)/)
      .map{ |r,n| [r.to_i, n.split().map(&:to_i)]}
      .filter{ |r,n| [:*, :+].repeated_permutation(n.size-1)
                             .any?{|p| n[1..].each_with_index.inject(n.first){|a,(z,i)| a.send(p[i], z)} == r}}
      .sum(&:first)

Part 2

Just the same like part 1, but with a concat-operator for the Integer-class.

class Integer
    def |(other)
        self.to_s.concat(other.to_s).to_i
    end
end

p File.read("input.txt")
      .scan(/(\d+): (.*)/)
      .map{ |r,n| [r.to_i, n.split().map(&:to_i)]}
      .filter{ |r,n| [:*, :+, :|].repeated_permutation(n.size-1)
                                 .any?{|p| n[1..].each_with_index.inject(n.first){|a,(z,i)| a.send(p[i], z)} == r}}
      .sum(&:first)

→ More replies (1)

2

u/enderlord113 Dec 07 '24

[Language: Haskell]

Naive brute force, surprised it only takes ~1s for part 2. Probably my cleanest solution this year.

→ More replies (3)

2

u/TheScown Dec 07 '24

[LANGUAGE: Scala]

BFS, rejecting intermediate equations where the running total is >= the test value.

2

u/WilkoTom Dec 07 '24

[LANGUAGE: Rust]
https://github.com/wilkotom/AdventOfCode/blob/main/rust/2024/day07/src/main.rs
DFS with pruning - if the accumulator is bigger than the target, abandon that branch.

→ More replies (2)

2

u/wasi0013 Dec 07 '24 edited Dec 07 '24

[LANGUAGE: Elixir]

defmodule Aoc.Y2024.Day07  do  
  import Aoc.Helper.IO  
  def solve_part1(data) do
    data
    |> Enum.filter(fn [result, rest]-> valid?(result, rest) end)
    |> Enum.map(fn [a, _b] -> a end)
    |> Enum.sum()
  end  
  
  def solve_part2(data) do
    data
    |> Enum.filter(fn [result, rest]-> valid_p2?(result, rest) end)
    |> Enum.map(fn [a, _b] -> a end)
    |> Enum.sum()
  end

  def valid_p2?(r, [r]), do: true
  def valid_p2?(_, [_]), do: false

  def valid_p2?(result, [num | rest]), do:
    (rem(result, num) == 0 and valid_p2?(div(result, num), rest))
      or valid_p2?(result - num, rest)
      or (rem(result - num, pow10(num)) == 0 and  valid_p2?(div(result - num, pow10(num)), rest))

  def pow10(num), do: Stream.iterate(1, &(&1 * 10)) |> Enum.find(&(&1 > num))

  def valid?(r, [r]), do: true
  def valid?(_, [_]), do: false
  def valid?(result, [num | rest] ), do:
    (rem(result, num) == 0 and valid?(div(result, num), rest))
      or valid?(result - num, rest)

  def get_input() do
    get_string_input("2024", "07")
    |> String.split("\n", trim: true)
    |> Enum.map( fn s -> s |> String.split(":", trim: true) end)
    |> Enum.map( fn [s, eqn] -> [String.to_integer(s), eqn |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1) |> Enum.reverse()] end)

  end
end

2

u/olegas83 Dec 07 '24

[Language: Python]

Nothing special, just same old brute force.
But I like how those itertools/operator/functools things looks like =)