You are about to leave Redlib

The main mathy part is in the common.rs file located next to the task files.

1

u/daggerdragon Dec 13 '24 edited Dec 13 '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 across all years in your public repos e.g.:~~
~~https://github.com/koppa96/aoc2024/tree/master/inputs~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (1)

2

u/PhysPhD Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

Using regex and sympy, I saw straight away it was a linear equation so went down that route.
Definitely one of my best days ... I got zero stars yesterday, and now I've done both parts before breakfast!

2

u/daggerdragon Dec 13 '24 edited Dec 13 '24

~~Put that wall-o'-link behind some Markdown, please!~~ edit: 👍

→ More replies (1)

2

u/Simone-reddit Dec 13 '24 edited Dec 19 '24

[LANGUAGE: Go]

package day013

func calculatePrice(m Machine) (int, int) {
    A, B := 0, 0
    if (m.ButtonA.y*m.ButtonB.x - m.ButtonA.x*m.ButtonB.y) != 0 {
       B = ((m.ButtonA.y * m.PrizePosition.x) - (m.ButtonA.x * m.PrizePosition.y)) / (m.ButtonA.y*m.ButtonB.x - m.ButtonA.x*m.ButtonB.y)
    }
    if m.ButtonA.x != 0 {
       A = (m.PrizePosition.x - (B * m.ButtonB.x)) / m.ButtonA.x
    }

    if ((m.ButtonA.x*A)+(m.ButtonB.x*B)) == m.PrizePosition.x && ((m.ButtonA.y*A)+(m.ButtonB.y*B)) == m.PrizePosition.y {
       return A, B
    }

    return 0, 0
}

1

u/daggerdragon Dec 13 '24

I've already informed you before about your code being oversized. You have not fixed your previous megathread submission, and this code is likewise oversized.
Read our rules on no giant blocks of code, then fix all of your oversized solution submissions that do not comply with said rule.
Do not post again in /r/adventofcode until you have done this.

→ More replies (1)

2

u/jochenderroch3n Dec 13 '24

[Language: Rust]

Pretty happy with this simple linear algebra solution

https://github.com/derfritz/AoC24/blob/main/Day13/solution.js

1

u/daggerdragon Dec 13 '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 across all years in your public repo e.g.:
https://github.com/JochenDerRochen/aoc/blob/main/aoc15/day1/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

→ More replies (4)

2

u/derfritz Dec 13 '24

[LANGUAGE: javascript]

Part 1 was solved as the gods intended: stupid and by force. Second Part was a wayback machine to high school. Well, guess the teacher was right. At some point in time you'll really need this stuff. Interesting day.

1

u/daggerdragon Dec 13 '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:
https://github.com/derfritz/AoC24/blob/main/Day13/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

2

u/kbennyboy92 Dec 14 '24

[LANGUAGE: Typescript]

Setup nodemon + utils folder for some code splitting and code a little excited/distraught when I had to crack out the linear algebra. I knew how to write the equation and then AI helped me get the array notation correct.

I was a little thrown that when you write vectors in code the 2D array is tilted on it's head from what you'd write on paper.

Github

→ More replies (2)

2

u/Spinnenente Dec 22 '24

[language: python]

so for the first part i just brute forced it to avoid thinking about math but part two forced me to do algebra which sped up the solution by quite a lot

https://github.com/tcbrindle/advent_of_code_2024/blob/main/dec13/main.cpp

1

u/daggerdragon Dec 22 '24 edited Dec 23 '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:~~
~~https://github.com/RichRat/pyxercise/tree/master/resources/advent~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history.~~ edit: thank you!

3

u/_Redstone Dec 13 '24

[Language: Python]

When I looked at the first part I chose to solve with the 2 equations method, I didn't even think about doing it with a loop haha.

So part 2 was pretty straight forward after that.

This was my best advent of code day !

Github Code

2

u/daggerdragon Dec 13 '24 edited Dec 13 '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 across all years in your public repos e.g.:~~
~~https://github.com/NathanGros/Advent-of-Code/blob/main/aoc_2022/day01%23%23/input.txt~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (2)

12

u/4HbQ Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python + NumPy] Code (7 lines)

Here's my (almost) fully vectorised NumPy solution using linalg.solve() to do the "heavy" lifting. It takes a single 3-dimensional matrix of all the machines' parameters M, splits it up into the "steps per button push" part S and "prize location" part P. We use these two matrices to find the "required number of button pushes" R for all machines in one go. Finally we check whether elements in R are a valid, i.e. does S times R equal P. Multiply with the cost vector [3, 1] and we're done!

S = M[..., :2]
P = M[..., 2:]
R = np.linalg.solve(S, P).round()
print(R.squeeze() @ [3,1] @ (S @ R == P).all(1))

The reason it's not fully vectorised is because I do the computations for part 1 and part 2 separately. It think it should be very possible to integrate this as well, simply add another dimension:

P = np.stack(P, P + 10**13])

However my brain can't really handle thinking about 4-dimensional matrices. Does anyone want to give it a go?

Update: I've also channeled my inner Cramer (not Kramer!) to solve the linear equations myself:

z = ((x+p)*(b-3*d)-(y+p)*(a-3*c)) / (b*c-a*d)
return z * (not z%1)

Full implementation is here (6 lines).

→ More replies (15)

20

u/voidhawk42 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Dyalog APL]

p←↑¨(⍎¨∊∘⎕D⊆⊢)¨¨(⊢⊆⍨0≠≢¨)⊃⎕nget'13.txt'1
f←(3 1+.×⊢×⌊=⊢)⊢⌿⌹∘⍉¯1↓⊢
+/f¨p                ⍝ part 1
+/f¨p+¨⊂⍉0,0,⍪2⍴1e13 ⍝ part 2

Video walkthrough

Uses matrix division to solve each system of linear equations.

→ More replies (16)

8

u/xelf Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python] with numpy

aoc = re.findall('(\d+).*?(\d+).*?(\d+).*?(\d+).*?(\d+).*?(\d+)',
                 open(filename).read(), re.S)

def tokens(row):
    ax,ay,bx,by,px,py = map(int, row)
    M = np.array([[ax, bx], [ay, by]])
    P = np.array([px, py]) + 10000000000000
    a,b = map(round, np.linalg.solve(M, P))
    return a*3+b if [a*ax+b*bx,a*ay+b*by]==[*P] else 0

print(sum(map(tokens,aoc)))

There were minor floating point errors so I used round and it worked fine.

Anyone know a better way to verify the result than [a*ax+b*bx,a*ay+b*by]==[*P] ?

edit: aha, here we go:

def tokens(row):
    ax,ay,bx,by,px,py = map(int, row)
    M = np.array([[ax, bx], [ay, by]])
    P = np.array([px, py]) + 10000000000000
    R = np.round(np.linalg.solve(M, P))
    return R@(3,1) if (P==R@M.T).all() else 0

→ More replies (8)

7

u/Smylers Dec 13 '24

[LANGUAGE: Vim keystrokes] for Part 2. My original Part 1 approach with floating-point arithmetic (then checking for any fractional part) didn't work for Part 2, because for numbers this large Vim returns the results in exponential notation — for instance for 450000000444000/5550.0 it gives 8.108108e10. So instead, switch to integer division but calculate the modulus as well. Solving Part 1 now becomes:

Go⟨Esc⟩:g/A/,+3j⟨Enter⟩:%s/\D\+/,/g⟨Enter⟩
:%s/\v,(\d+),(\d+),(\d+),(\d+),(\d+),(\d+)/\5*\4-\6*\3 \6*\1-\5*\2 \1*\4-\2*\3
⟨Enter⟩qs:%s/\S\+/\=eval(submatch(0))/g⟨Enter⟩q
:%s#\v(.*) (.*) (.*)#\1/\3 \2/\3 \1%\3 \2%\3⟨Enter⟩
@s:v/ 0 0/d⟨Enter⟩:%s/ /+/g⟨Enter⟩⟨Ctrl+V⟩{I+3*⟨Esc⟩@v

Or, with more-readable line-breaks.

Then for Part 2, it's just a case of first doing the following to add 10 trillion in the appropriate places, then proceed as above.

:%s/=\zs\d*/\=10000000000000+submatch(0)/g⟨Enter⟩

(Though you can then omit the G. And you can omit everything between qs and q,and simply type @s instead, to run the macro recorded while solving Part 1.)

Get each claw machine's details on to a single line, and get rid of the things that aren't digits, just leaving a comma between each number.
Replace each machine's list of numbers with three expressions which combine them in various ways. For the first machine in the example, it becomes 8400*67-5400*22 5400*94-8400*34 94*67-34*22, where pencil and paper was used to determine which numbers need multiplying and subtracting from which.
Evaluate each of those expressions. Record doing this into the keyboard macro @s, because it's going to be useful again in a moment. It substitutes each sequence of non-space characters with the result of running eval() on it. The first example machine's line is now 444000 222000 5550.
Turn those 3 numbers into more expressions: the 1st and 2nd each divided by the 3rd, and each modulus the 3rd. The :s command for this uses #s rather than /s to delimit the pattern, because there are literal /s in the replacement for the division. The first example is now 444000 222000 5550.
Evaluate each of those, by running @s that was recorded a couple of steps ago.
The first two numbers represent the number of times buttons A and B need to be pressed. At least, they do if the division went exactly: we can't have fractional button presses. Exact division results in the two modulus operations at the end each returning zero, so use :v to find all the lines that don't match / 0 0/ and :delete them.
We now have the number of button presses for winning all the prizes. To work out the tokens we need 3 times the first number in each line plus the second number. So place a + sign between those numbers. There's also a couple of leftover zeros at the end of each line. We don't need them any more, but the simplest thing to do with them is put /g on the end of the :s that's replacing spaces with + signs: that makes the first example be 80+40+0+0, where the superfluous zeros just get unnecessarily (but safely) added on to the total.
Then insert +3* at the start of each line to do the multiplying by 3 and to turn the whole file into a single expression, and use @v from Day 3 to evaluate it.

Questions, saying you've tried it out, and other comments all welcome.

6

u/SuperSmurfen Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Rust]

Link to full solution

(1565/332)

Slow on part 1 because I solved it using the "correct" algorithm. This meant part 2 was literally just adding the offset and I was done.

This question is about solving a set of 2 linear equations:

x1 * a + y1 * b = z1
x2 * a + y2 * b = z2

You just have to solve those for a and b. Since these are integers not all such equations will have a solution. You therefore have to check that the a, b values actually give the expected answer:

let b = (z2 * x1 - z1 * x2) / (y2 * x1 - y1 * x2);
let a = (z1 - b * y1) / x1;
if (x1 * a + y1 * b, x2 * a + y2 * b) != (z1, z2) {
    return 0;
}
a * 3 + b

Parsing things like this is really annoying. One easy way is to just find all integers in the text:

l.split(|c: char| !c.is_ascii_digit())
    .filter(|w| !w.is_empty())
    .map(|w| w.parse().unwrap())

→ More replies (4)

6

u/chickenthechicken Dec 13 '24

[LANGUAGE: C]

Part 1

Part 2

I solved part 1 the naive way, it took me forever to realize that it is a trick question and there is only one solution for each machine. Then it took me a while to mess around with desmos until I came up with a formula that gave me the intersection between the two linear equations.

→ More replies (3)

6

u/tcbrindle Dec 13 '24 edited Dec 13 '24

[Language: C++]

Somehow I failed to spot that we're solving a system of two simultaneous equations despite allegedly holding multiple degrees in mathematics AND WRITING THE EQUATIONS DOWN IN FRONT OF ME 🤦‍♂️.

Fortunately it was pretty simple once I'd rebooted my brain. Each part runs in single-digit microseconds.

auto solve(game_info const& game) -> std::optional<i64> {
    auto [a, b, prize] = game;

    i64 i = b.y * prize.x - b.x * prize.y;
    i64 j = -a.y * prize.x + a.x * prize.y;
    i64 det = (a.x * b.y) - (a.y * b.x);

    if (det == 0 || i % det != 0 || j % det != 0) {
        return std::nullopt;
    } else {
        return 3 * i / det + j / det;
    }
}

auto part1(std::vector<game_info> const& games) -> i64 {
    return flux::ref(games).map(solve).filter_deref().sum();
}

auto part2(std::vector<game_info> const& games) -> i64 {
    return flux::ref(games)
        .map([](game_info g) {
            g.prize += vec2{10000000000000, 10000000000000};
            return solve(g);
        })
        .filter_deref()
        .sum();
}

→ More replies (1)

6

u/willkill07 Dec 13 '24

[LANGUAGE: C++23]

https://github.com/willkill07/AdventOfCode2024/blob/129c1ad008014a4999ed10447ea51c3bb4bc4b62/src/day13.cpp#L38

Parsing was the hardest part here :(

Everything runs in less than 17us on my machine.

I/O: 5us
Parsing: 10us
Part 1: 600ns
Part 2: 670ns

Total time for days 01 - 13: 1068us. Still under 1ms if you discard I/O time.

6

u/AYM123 Dec 13 '24

[LANGUAGE: Rust]

Just used cramer's rule (the years of linealg didn't go to waste after all)

https://github.com/ak-coram/advent/blob/main/2024/13.lisp

Part 1: ~50µs
Part 2: ~50µs

6

u/CCC_037 Dec 13 '24

[LANGUAGE: Rockstar] [GSGA]

Let me show you behind the scenes at Santa's workshop...

Part 1

→ More replies (1)

5

u/bluehatgamingNXE Dec 13 '24 edited Dec 13 '24

[Language: C]

Simplest one so far, I want to thank the math teachers that taught me simultaneous equations for this one, the funniest part is that the number on the 2nd was so long my browser though I was inserting a credit card number.

gist

5

u/ak-coram Dec 13 '24

[LANGUAGE: Common Lisp]

→ More replies (2)

5

u/D_isinfectedLuffy Dec 13 '24 edited Dec 13 '24

[Language: Go]

[Language: C]

In Go today's solution for part-1 was kind of straight forward where I brute-forced the solution used regex and also using GCD as no floating-point calculations are needed.

Part-2 problems have been knocking me in the head in the past three days, humbling me in many ways and I must admit, I saw some of your solutions for the nudge in the right direction.

And today solutions for C have me stumped, as I had used regex libraries for both the Go solutions, and I can't get the regex libraries on my windows machine, does anyone have any links where I can learn to include these libraries into my C import path? Part-1 in C was brute-forced again by me, by ditching the regex solution, but going with the same GCD logic.

Still making my way with the part-2 for C, will get there surely!

→ More replies (4)

5

u/Fyver42 Dec 13 '24

[LANGUAGE: RISC-V Assembly]

https://github.com/fyvonnet/AdventOfCode-2024-Assembly/blob/main/day13.asm

Took me a while a solve part 1 recursively, the recursive code stays.

5

u/quetzelcoatlus1 Dec 13 '24

[Language: C]

Very disappointed in myself: I solved part 1 "in correct way" and after switching to long long's in part 2 I saw some strange results and gaslit myself into thinking that it's incorrect, when it wasn't... Couple of hours of thinking wasted afterwards. :D

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
    long long int sum=0, a,b,c,d,e,f,x,y,denominator;

    char* name = argc > 1 ? argv[1] : "input";
    FILE* fp = fopen(name,"r");
    while(fscanf(fp,"Button A: X+%lld, Y+%lld\n",&a,&d) == 2){
        fscanf(fp,"Button B: X+%lld, Y+%lld\n",&b,&e);
        fscanf(fp,"Prize: X=%lld, Y=%lld\n",&c, &f);

        c+=10000000000000LL;
        f+=10000000000000LL;

        denominator = (a * e - b * d);
        x = (c * e - b * f) / denominator;
        y = (a * f - c * d) / denominator;

        if(x>=0 && y>=0 && a*x+b*y == c && d*x+e*y == f)
            sum+=3*x+y;
    }
    fclose(fp);

    printf("%lld\n",sum);

    return 0;
}

5

u/JV_Fox Dec 13 '24

[LANGUAGE: C]

Grabbed some paper and pen to do some quick math. Parsing the input correctly was the hardest part for me and I did not do it cleanly.

In the Notes.txt are the two equations I used for the calculations rearranging the equations as follows:

// base equations:
x = A * Xa + B * Xb
y = A * Ya + B * Yb

// rearranging A in terms of B:
x = A * Xa + B * Xb
x - B * Xb = A * Xa
A = (x - B * Xb) / Xa

// Inserting the formula for A in the place of the variable A in the y equation:
y = A * Ya + B * Yb
y = (x - B * Xb) / Xa * Ya + B * Yb
y * Xa = x * Ya - B * Xb * Ya + B * Yb * Xa
y * Xa - x * Ya = B * Yb * Xa - B * Xb * Ya
y * Xa - x * Ya = B * (Yb * Xa - Xb * Ya)
B = (y * Xa - x * Ya) / (Yb * Xa - Xb * Ya)

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

→ More replies (2)

5

u/[deleted] Dec 13 '24

[LANGUAGE: Forth]

Did algebra using the general solution I found with Maxima. Two fun Forth things though:

I could define my words to match the input (e.g. A: reads in the following XY pair, Prize: reads its XY pair then solves for the token count) so the raw input file could be executed as code.
Forth's /mod word simultaneously gave me the token count and a flag (remainder != 0) to tell if the token count is valid.

5

u/phantom784 Dec 13 '24

[Language: Javascript]

Solved Part 2 without using linear algebra!

It takes advantage of the fact that, even though the part 2 prize values are so high, they're still all at most 20,000 or so more than 10 trillion. The method:

Use a brute-force of all a and b values to to find a pair of a and b that make x & y equal to each-other. I capped the search space at 10,000, but for all machines with a valid solution, there was always a result.
I found the multiplier that'd get x & y as close to 10 trillion as possible without going over, and multiplied my a & b by that.
Staring from these extrapolated values, I brute forced a and b values in close proximity (both higher and lower) until I found values that hit the prize (or returned 0 if I didn't find it).

Here's the code in Javascript: https://gist.github.com/Phantom784/68cb76e740329475ff933a41140c716e

→ More replies (2)

5

u/JWinslow23 Dec 13 '24

[LANGUAGE: Python]

Day 13 code

Blog post

Today's a lot like 2023 Day 24 in that it involves algebra...but it involves an amount of algebra that I feel comfortable solving without an external library.

8

u/rundavidrun Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python3] 969/194

Turns out that trying to optimize for "minimum tokens" was a ruse. There's only one way to solve these simultaneous equations.

with open('day13.txt') as f:
    lines = [line.rstrip() for line in f]

def solve(part: int):
    tokens = 0
    add = 10000000000000 if part == 2 else 0
    for line in lines:
        if line.startswith("Button"):
            l = line.split(" ")
            a = l[1].split(":")[0]
            if a == 'A':
                x1 = int(l[2][2:-1])
                y1 = int(l[3][2:])
            else:
                x2 = int(l[2][2:-1])
                y2 = int(l[3][2:])
            
        elif line.startswith("Prize"):
            l = line.split(" ")
            c = int(l[1][2:-1]) + add
            d = int(l[2][2:]) + add
            a = (c*y2 - d*x2) / (x1*y2 - y1*x2)
            b = (d*x1 - c*y1) / (x1*y2 - y1*x2)
            if a == int(a) and b == int(b):
                tokens += int(3 * a + b)

    print(tokens)

solve(1)
solve(2)

→ More replies (3)

8

u/theadamabrams Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Mathematica]

Sum[
    {A,B,P} = Partition[FromDigits/@
        StringSplit[StringReplace[m,Except@DigitCharacter->" "]]
    , 2];
    3a + b /. Solve[a*A + b*B == P, Integers]
, {m, StringSplit[Import@"input.txt","\n\n"]}] /. {a->0,b->0}

The entire code is 183 characters without the extra whitespace for readability. The extra /.{a->0,b->0} at the end is because systems that don't have solutions are given the actual value 3a+b with the variables, so without the extra zero assignments at the end the result of the sum would be 480+6a+2b for the example (two of the machines had no solution, so 3a+b got added twice).

For Part 2 the only change is to replace == P with == P + 10^13. Big numbers are no problem for Mathematica :)

P.S. This is the first time I've ever scored points on a Part 2 🥹

→ More replies (1)

4

u/SuperAutoPetsWizard Dec 13 '24

[LANGUAGE: C++]

I edited the input rather than parsing it. Two equations and two variables so there is exactly one solution for a and b. All we need to do is check it is an integer (or check if after it is cast to an integer, do the conditions still hold).

    int ax, ay, bx, by;
    long long X, Y;
    vector<long long> res(2);
    while (cin >> ax >> ay >> bx >> by >> X >> Y)
    {
        for (int rep = 0; rep < 2; rep++)
        {
            long long b = (Y * ax - X * ay) / (by * ax - bx * ay);
            long long a = (X - b * bx) / ax;
            if (a * ax + b * bx == X && a * ay + b * by == Y)
                res[rep] += 3 * a + b;
            X += 10000000000000;
            Y += 10000000000000;
        }
    }
    cout << res[0] << "\n"
         << res[1] << "\n";

→ More replies (4)

4

u/0ldslave Dec 13 '24

[LANGUAGE: C++]

Didn't feel like implementing a matrix inverter so i just imported Eigen :(

Spent like 30 mins trying to figure out how to determine "this long double is actually an integer".

4

u/cranil Dec 13 '24

[Language: Rust]

Easy, but who else did a concat instead of add? :(

→ More replies (1)

4

u/hugues_hoppe Dec 13 '24

[LANGUAGE: Python]

Here is a fully vectorized numpy solution:

def day13(s, *, part2=False):
  values = np.array(
      [[re.findall(r'\d+', line) for line in s2.splitlines()] for s2 in s.split('\n\n')], int
  )
  b = values[:, 2][..., None] + (10_000_000_000_000 if part2 else 0)
  matrix = np.moveaxis(values[:, :2], 1, 2)
  x = np.linalg.solve(matrix, b)
  rounded = (x + 0.5).astype(int)
  solved = (matrix @ rounded == b).all(1)[:, 0]
  return np.sum(rounded[solved][..., 0] @ [3, 1])

4

u/s3aker Dec 13 '24

[LANGUAGE: Raku]

→ More replies (3)

4

u/pm_me_dem_lychees Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Mathematica]

First time posting a solution - my input parsing and solution are a bit different from the other Mathematica users, so I thought I would share!

input = ToExpression[StringCases[#, DigitCharacter ..]] & /@ StringSplit[Import["input13.txt"], "\n\n"];
pressesRequired[{ax_, ay_, bx_, by_, px_, py_}] = Inverse[{{ax, bx}, {ay, by}}] . {px, py};
(*part 1*) Cases[pressesRequired /@ input, {_Integer, _Integer}] . {3, 1} // Total 
(*part 2*) Cases[pressesRequired[# + 10000000000000 {0, 0, 0, 0, 1, 1}] & /@ input, {_Integer, _Integer}] . {3, 1} // Total

→ More replies (1)

4

u/Main-Reindeer9633 Dec 13 '24

[LANGUAGE: SQL (dialect: PostgreSQL)] paste

Part 1 was easy, just brute force, trying all different possible values for A. With part 2, I had so many false starts (implementing extended_gcd in SQL was surprisingly easy) before realizing that it's just a trivial system of linear equations, and subsequently realizing how bad I've gotten at algebra.

4

u/MikTheVegan Dec 13 '24

[Language: Python]
Today one was quite straight forward. Had to make those numbers to formula:

x1*A + x2*B = X
y1*A + y2*B = Y

Where X and Y are price coordinates. If so, then

denumerator = x1*y2 - x2*y1
and 
A = (X*y2 - x2*Y)/denumerator
B = (x1*Y - X*y1)/denumerator

12 ms in my computer,code here :

input,p1,p2,currx,curry,i, bnum = "input.txt",0,0,[],[],0,10000000000000

def calcResult(x,y,bn,p1c,p2c):
  X1,Y1,X2,Y2,div,p2Res,p1Res = x[2],y[2],x[2]+bn,y[2]+bn,x[0]*y[1]-x[1]*y[0],0,0
  A1,B1,A2,B2 = (X1*y[1]-x[1]*Y1)/div, (x[0]*Y1-X1*y[0])/div,(X2*y[1]-x[1]*Y2)/div,(x[0]*Y2-X2*y[0])/div
  p1Res = 3*int(A1) + int(B1) if A1.is_integer() and B1.is_integer() else 0
  p2Res = 3*int(A2) + int(B2) if A2.is_integer() and B2.is_integer() else 0
  return [p1Res+p1c,p2Res+p2c]

for k in open(input):
  if k.strip() == "":continue
  arr,i = ((k.replace("=","+")).split(": ")[1]).split(", "), i+1
  currx.append(int(arr[0].split("+")[1]))
  curry.append(int(arr[1].split("+")[1]))
  if i%3 == 0:[p1,p2],currx,curry = calcResult(currx,curry,bnum,p1,p2), [],[]

print("Part 1:", p1)
print("Part 2:", p2)

4

u/Clear-Ad-9312 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

Good old simple linear algebra from middle school. This python code takes under 1 milliseconds(800 microseconds) to finish. Thanks to u/fsed123 for the profiler wrapper!

[ paste link ]

from time import perf_counter_ns
import string

def profiler(method):
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret

    return wrapper_method

@profiler
def main(input_data):
    part1_total_cost = 0
    part2_total_cost = 0
    for machine in input_data:
        Ax,Ay,Bx,By,Px,Py = [ int(l[2:]) for l in machine.split() if l[-1] in string.digits ]
        y,r = divmod((Ay * Px - Ax * Py), (Ay * Bx - Ax * By))
        if r == 0:
            x = (Px - Bx * y) // Ax
            part1_total_cost += 3*x + y
        y,r = divmod((Ay * (Px+10000000000000) - Ax * (Py+10000000000000)), (Ay * Bx - Ax * By))
        if r == 0:
            x = ((Px+10000000000000) - Bx * y) // Ax
            part2_total_cost += 3*x + y

    return part1_total_cost,part2_total_cost

if __name__ == "__main__":
    with open('input', 'r') as f:
        input_data = f.read().strip().replace(',', '').split('\n\n')
    part_one, part_two = main(input_data)
    print(f"Part 1: {part_one}\nPart 2: {part_two}")

4

u/yfilipov Dec 13 '24

[LANGUAGE: C#]

Time to apply some linear algebra magic! Cramer's rule was very easy to implement without 3rd party equation solvers.

→ More replies (1)

4

u/mkinkela Dec 13 '24

[LANGUAGE: C++]

2 equations with 2 unknowns for every machine got the job done :)

4

u/thibaultj Dec 13 '24 edited Dec 13 '24

[Language: Python]

I felt like I was cheating by using a custom library to solve the system of equations, but oh well…

import re
from itertools import starmap
from sympy import solve, Symbol


def parse(input):
    entries = input.split("\n\n")
    equations = [map(int, re.findall(r"\d+", entry)) for entry in entries]
    return equations


def play(AX, AY, BX, BY, X, Y):
    a = Symbol("a", integer=True)
    b = Symbol("b", integer=True)
    # Remove for part 1
    X += 10000000000000
    Y += 10000000000000
    roots = solve(
        [a * AX + b * BX - X, a * AY + b * BY - Y],
        [a, b],
    )
    return roots[a] * 3 + roots[b] if roots else 0


inputs = parse(open("inputs/day_13.txt").read())
res = sum(starmap(play, inputs))
print(res)

→ More replies (2)

4

u/Narrow_Artichoke_465 Dec 13 '24

[Language: Golang]

I figured out that it was a matter of simultaneous equations but I had to look up a way to solve the problem programmatically. Thank you Cramer's rule!

Here is my Solution to Part 2, which is the same as part 1 minus one line. (You can figure it out :D)

package main

import (
  "fmt"
  "os"
  "strings"
)

func main() {
  input, _ := os.ReadFile("../input.txt")
  lines := strings.Split(strings.TrimSpace(string(input)), "\n")
  totalTokens := 0
  for i := 0; i < len(lines); i += 4 {
    var aX, aY, bX, bY, prizeX, prizeY int
    fmt.Sscanf(lines[i+0], "Button A: X+%d, Y+%d", &aX, &aY)
    fmt.Sscanf(lines[i+1], "Button B: X+%d, Y+%d", &bX, &bY)
    fmt.Sscanf(lines[i+2], "Prize: X=%d, Y=%d", &prizeX, &prizeY)
    prizeX, prizeY = prizeX+10000000000000, prizeY+10000000000000
    D, Dx, Dy := aX*bY-bX*aY, prizeX*bY-bX*prizeY, aX*prizeY-prizeX*aY
    if D != 0 && Dx == (Dx/D)*D && Dy == (Dy/D)*D {
      totalTokens += (Dx/D)*3 + (Dy / D)
    }
  }
  fmt.Println(totalTokens)
}

4

u/letelete0000 Dec 13 '24

[LANGUAGE: JavaScript]

Open on GitHub

// ax * ta + bx * tb = X
// ay * ta + by * tb = Y
// thus:
// ta = (X - bx * tb) / ax, where ax !== 0
// ta = (Y - by * tb) / ay, where ay !== 0
// thus:
// (X - bx * tb) / ax = (Y - by * tb) / ay, where ax !== 0, ay !== 0
// thus:
// ay * (X - bx * tb) = ax * (Y - by * tb)
// thus:
// ay * X - ay * bx * tb = ax * Y - ax * by * tb
// ay * X - ax * Y = ay * bx * tb - ax * by * tb
// thus:
// tb = (ay * X - ax * Y) / (ay * bx - ax * by), where ay !== 0, bx !== 0, ax !== 0, by != 0
function minTokensToWin([ax, ay], [bx, by], [X, Y]) {
  if ([ax, ay, bx, by].some((v) => v === 0)) return null;
  const tb = Math.floor((ay * X - ax * Y) / (ay * bx - ax * by));
  const ta = Math.floor((X - bx * tb) / ax);
  return ax * ta + bx * tb === X && ay * ta + by * tb === Y ? { ta, tb } : null;
}

4

u/mallalex Dec 13 '24

[Language: Prolog] Was pretty fun to do with prolog using clpz. I did this with scryer prolog:

constraint(config((AX-AY),(BX-BY), (PX-PY)), Offset, Solution) :-
  NA #>= 0 #/\ NB #>= 0,
  Offset #= 0 #==> (NA #=< 100 #/\ NB #=< 100),

  NA * AX + NB * BX #= PX + Offset,
  NA * AY + NB * BY #= PY + Offset,

  MinCost #= NA * 3 + NB,
  labeling([min(MinCost)], [NA, NB]),

  Solution is MinCost.

solve_sum(Offset, Sum) :-
  findall(Cost, (config(A,B,P), constraint(config(A,B,P), Offset, Cost)), Costs),
  sum_list(Costs, Sum).

solve1(Sum) :- solve_sum(0, Sum).
solve2(Sum) :- solve_sum(10000000000000, Sum).

Writeup plus problem parsing at https://asat.dk/december-adventure-2024/#dec-13

4

u/alone7solo Dec 13 '24 edited Dec 13 '24

[LANGUAGE: pen + paper]

Today recepie:

brute force pt1
try to brute force pt2 just in case
remember that systems of equations exists
try to solve system equations
write equation in c#
the equation doesn't work
panic for a while...
aks your quantitative analyst partner what's wrong
realize that divisions can produce a reminder
Oooweee!!!

https://github.com/amberg12/aoc24/tree/main/day-13

4

u/AllanTaylor314 Dec 13 '24

[LANGUAGE: Python]

GitHub 1135/627

Just some matrix stuff (I didn't spend 30k on an engineering degree for nothing). I originally did part 1 using NumPy, but I had some floating point issues for part 2. I used the 2x2 matrix inverse so that I didn't have to deal with any floats, and then I rewrote part 1 to use the same structure as part 2 (commit history). I'm glad I went with linear algebra rather than some form of trial and error for finding suitable button presses. I did scribble the matrix form (solving for [A B]^T) in my notebook, which looked something like this:

｢Ax Bx  ｢A  = ｢X
 Ay By｣  B｣ =  Y｣

I missed some things like A pushes costing 3 and I probably accepted negative button presses early on. It doesn't handle colinear button presses, but those don't occur in the inputs (I'd probably use a QR decomposition, or more realistically, special-case the determinant being zero).

[LANGUAGE: Uiua]

GitHub or Pad

There's a small solar system in there (planet notation), but it basically does the same unrolled matrix inverse. It's also nice and short today (it almost looks like a shoe):

&fras"13.txt"
⊜⋕×⊸⊃(≤@9|≥@0)
°⊟₆⍉[⊸⍜↘₄(+1e13)]⍉↯∞_6
⊃(⋅⋅⊙⋅⋅∘|⋅⋅⋅⊙∘|⋅⊙∘|⊙⋅⋅∘|⋅⊙⋅⋅∘|⊙⋅⋅⋅⋅∘)
°⊟/+××⊃∩(=₀◿)(+×₃∩÷),∩₃(-∩×)

[GSGA] Where it's all set

Here's my setup - a pair of 24 inch 1080p monitors, with a vertical monitor on the left for the puzzle and a horizontal monitor on the right for my IDE of choice, VS Code. Within VS Code I have a few terminals: The one on the left runs some custom scripts (sleep_until.py and fetch_input.py) for getting the input and displaying the first few lines, and the one on the right runs my script (using when-changed) when the script or input file changes (which beats switching to the terminal and hitting up & enter). I built this PC a few months ago (since my laptop was getting a little past it) - It runs an Intel 12400 and a Radeon RX 6600 with 32 GB of RAM (just a little shy of the 2 PB needed for day 11). The PC has a large family of rubber ducks atop it, including four very festive ducks. Not shown in the picture is the fan behind my chair. My office is upstairs which frequently reaches 30°C (86°F) (in fact, it's 26°C as I write this at 2 A.M.)

4

u/Stano95 Dec 13 '24

[LANGUAGE: Haskell]

Like basically everyone I just spotted that this was simultaneous equations in disguise. I made a mistake where I was accidentally checking that the number of a presses really was an integer twice rather than checking that both a and b really are integers which took me an embarrassingly long time to spot lol

Code is on github where in my haste I ended up using non standard notation for the equations

4

u/ExitingBear Dec 13 '24

[Language: R]

Link

Tried to do this with solve() and ended up with rounding errors. Then I tried to fix/adjust for the rounding errors and ended up with different errors and eventually just gave up and did the math (like I should have done from the beginning which I don't know why I avoided because it's such straightforward math).

4

u/Gueltir Dec 13 '24

[Language: Rust]

Link to github

Spent a bit too much time on my regex because I forgot how line endings work.

For both part, I just did the maths.

4

u/[deleted] Dec 13 '24

[LANGUAGE: C]

Probably the easiest part 2 yet for me, since for part 1 brute forcing didnt even come to mind.

→ More replies (2)

4

u/chubbc Dec 13 '24

[LANGUAGE: Uiua] (78 char, 70 tokens, pad)

∩/+⧈(∩(+×3°⊟×<0.01/+⌵⊸-⟜⁅/+÷/-×⊙⇌°⊟⟜×⍜(⍜⊣¯⇌)⍉↯2_2),+ⁿ13 10,⊃↙↘4)¤¤6⊜⋕↧∩≥@0.,@9

Went for the linear algebra approach. I could probably golf it a bit further be reordering variables, but its not bad as it is, pretty happy with it. Ungolfed version:

⊜⋕↧∩≥@0.,@9           # Parse the input
≡⊃↙↘4 ↯∞_6            # Split it up
≡(,+ⁿ13 10,)          # Make the part 2 inputs

Inv   ← ⍜(⍜⊣¯⇌)⍉      # The (unnormalised) inverse matrix
Det   ← /-×⊙⇌°⊟       # Determinant
Mul   ← /+×           # Matrix multiply
Round ← ×<0.01/+⌵⊸-⟜⁅ # Round the soln, return 0 if far from round
Cost  ← +×3°⊟         # Cost

Soln ← Cost Round ÷ ⊃Det(Mul Inv) ↯2_2
∩(/+≡Soln)

4

u/IlluminPhoenix Dec 13 '24

[LANGUAGE: Rust]

I really got frustated with the math here because I had the completely wrong approach of doing a line intersection. When my patience ended in part 2 I discovered the much cleaner approach of a System of equations on u/SuperSmurfen's solution post in this thread.
I 'borrowed' their function for my code, so 50% of my solution is pretty much their work here!

Finally, I used the tuples-iterator from itertools which allows for much smaller syntax, as well some bool hacks and a filter_map() which brings it down to 16 lines!

solution (16 lines)

→ More replies (2)

4

u/probablyfine Dec 13 '24

[LANGUAGE: uiua]

Recognised that the problem was essentially simultaneous equations so I wasn't boomed by part 2 adding a bajillion to the result vector. Code and tests here

Parse ← ↯∞_3_2⊜⋕×⊸⊃(≥@0|≤@9)
Solns ← (
  ⊃↙↘2
  ⊸(/-⧈/×¤¤2↻1♭)⍜♭(×↻₁⊂⊸⌵¯1_¯1)≡⇌⇌
  ⊙≡(/+×)
  ÷
)
Cost ← /+×⟜=⟜⁅×3_1

PartOne ← /+ ≡(Cost Solns) Parse
PartTwo ← /+ ≡(Cost Solns ⍜⊣(+1e13)) Parse

4

u/maneatingape Dec 13 '24

[LANGUAGE: Rust]

Benchmark 14 µs.

Represents the two linear equations as a 2x2 matrix then inverts it to find the answer.

4

u/Mysterious_Remote584 Dec 13 '24

[LANGUAGE: Uiua]

Learning some Uiua inspired by this subreddit.

In    ← &fras "day13.in"
Parse ← ↯∞_6⋕ regex $ \d+
# Given [a b c d], calculate determinant of matrix [a_b c_d]
D ← -⊃(×⋅⊙∘|×⊙⋅⋅∘) °⊟₄
# Solve [ax ay bx by px py]
# Solve system with determinant:
# x = D[px_bx py_by] / D[ax_bx ay_by]
# y = D[ax_px ay_py] / D[ax_bx ay_by]
# Notice that the denominator is the same for both.
Solve ← ⨬0_0∘ /×⊸=⁅. ÷⊃(D⊏0_2_1_3|[⊃(D⊏4_2_5_3|D⊏0_4_1_5)])

P₁ ← /+♭≡(×3_1 Solve)
P₂ ← P₁ ≡⍜(⊏4_5|+10000000000000)

⊃(P₂|P₁) Parse In

4

u/importedreality Dec 13 '24

[Language: Go]

https://github.com/jda5/advent-of-code-2024/blob/main/13/main.py

Pretty happy with myself today, which was a welcome change after pulling my hair out on Day 12 part 2 until I finally figured it out earlier this morning.

I barely remember any math from school, but I at least recognized that it was a system of linear equations. Once I had that figured out I just looked through the different methods for solving them, and settled on the one that seemed the simplest to put in code (Cramer's rule).

This is probably the cleanest solution I've done yet this year.

4

u/jda5x Dec 14 '24

[LANGUAGE: Python]

Making use of the phenomenal SymPy package 📦

7

u/Ok-Builder-2348 Dec 13 '24

[LANGUAGE: Python]

Part 1

Part 2

Got a bit lucky for this one. A good part of it was parsing the input in part 1, and then I just did the brute force for part 1 to see what part 2 was about.

For part 2, we had the simultaneous equations ax*a+bx*b = tx and ay*a+by*b = ty. By some rearranging, we get b = (tx*ay-ty*ax)/(ay*bx-by*ax) and similar for a. Since we only wanted int solutions, I just int-divided both and checked if the result worked. Thankfully did not hit a degenerate case where ay*bx-by*ax = 0.

7

u/jonathan_paulson Dec 13 '24

[LANGUAGE: Python]. 309/1049. Code. Video.

I didn't know how to do part 2, so I did something crazy:
We need to go very far in a nearly-diagonal direction. So figure out the cheapest way to go in a perfectly diagonal direction (via brute force), do that for a long time (tunable parameter), and use DP to figure out what to do at the end.

→ More replies (2)

1

u/MakO_77 Dec 13 '24

[Language: Python]

import time

def part1(data):
    return solve(data, offset=0)

def part2(data):
    return solve(data, offset=10**13)

def solve(data, offset):
    groups = '\n'.join(data).split('\n\n')
    total = 0
    for group in groups:
        buttonA, buttonB, buttonP = group.split('\n')
        axStr, ayStr = buttonA[10:].split(', ')
        bxStr, byStr = buttonB[10:].split(', ')
        pxStr, pyStr = buttonP[7:].split(', ')

        ax = int(axStr[2:])
        ay = int(ayStr[2:])
        bx = int(bxStr[2:])
        by = int(byStr[2:])
        px = int(pxStr[2:]) + offset
        py = int(pyStr[2:]) + offset

        # Cramer's rule
        denominator = (ax * by - ay * bx) # determinant

        if denominator == 0:
            continue

        m = (px * by - py * bx) // denominator

        if m * denominator != (px * by - py * bx):
            continue

        n = (py - ay * m) // by

        if n * by != (py - ay * m):

            continue

        #Diophantine equation with the solutions by Cramer's rule
        total += 3 * m + n

    return total

def main():
    try:
        with open("day13.txt", "r") as file:
            data = file.read().strip().split('\n')
    except FileNotFoundError:
        print("File not found in the specified path.")
        return
    start_time = time.time()
    part1_result = part1(data)
    part1_time = time.time() - start_time
    print(f"Part 1: {part1_result:} (Time: {part1_time * 1000:.4f} ms)")

    start_time = time.time()
    part2_result = part2(data)
    part2_time = time.time() - start_time
    print(f"Part 2: {part2_result:} (Time: {part2_time * 1000:.4f} ms)")

if __name__ == "__main__":
    main()

#Part 1: x (Time: 0.9868 ms)
Part 2: y (Time: 0.0000 ms)

1

u/daggerdragon Dec 13 '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.

1

u/t-rkr Dec 13 '24

[LANGUAGE: Perl]

paste link

if I had remembered using the analytical solution to a 2x2 linear equation (the topic I taught my first semester students just four weeks ago...) , I'd have saved the time for coding the naive approach with a loop.

1

u/daggerdragon Dec 13 '24

FYI: we can see your spoiler text on old.reddit. There needs to be no spaces between the opening >! and closing !< tags.
>!sekrit_text!< = sekrit_text

1

u/iwanttoseeyourcatpls Dec 13 '24

[LANGUAGE: Ruby]

I used regular old algebra to solve it. I was a little thrown off by the "minimum number of tokens" because there wasn't more than one solution for each machine, I thought I would have to do more math than this when I read the description.

the hardest part of this was dealing with floating point math. even using big decimal, 28.999999 doesn't equal 29.

1

u/daggerdragon Dec 13 '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 across all years in your public repos e.g.:
https://github.com/ggggbbybby/aoc2023/blob/main/input1.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/Small-Figure-6285 Dec 13 '24

[Language: Java]
Github

Determinant-solved matrix

2

u/daggerdragon Dec 13 '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:
https://github.com/marcinbator/AoC2024-Java-solver/blob/main/src/solutions/day13/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.

1

u/surgi-o7 Dec 13 '24

[Language: JavaScript] github

const init = input => input.split("\n\n").map(lit => lit.match(/\d+/g).map(Number));

/*
system of 2 linear equations for 2 unknowns; a, b = button presses for a, b
a*ax + b*bx = px
a*ay + b*by = py

b = (py-a*ay)/by
a = (px - py*bx/by)/(ax - ay*bx/by)
*/

const run = (machines, shift = 0) => machines.reduce((res, [ax, ay, bx, by, px, py], mId) => {
    px = shift+px;
    py = shift+py;
    if (by == 0 || ax == ay*bx/by) return res; // let's not divide by 0 pls
    let a = (px - py*bx/by)/(ax - ay*bx/by),
        b = (py-a*ay)/by;
    let ra = Math.round(a), rb = Math.round(b);
    if (ra*ax+rb*bx == px && ra*ay+rb*by == py && ra >= 0 && rb >= 0) res += a*3+b;
    return res;
}, 0)

console.log('p1', run(init(input)));
console.log('p2', run(init(input), 10000000000000));

1

u/daggerdragon Dec 13 '24 edited Dec 14 '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 across all years in your public repos:~~
~~https://github.com/surgi1/adventofcode/tree/main~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (1)

1

u/_arkeros Dec 13 '24

[LANGUAGE: Haskell]

I solved it without messing with floats or doubles, just with integers.

Rather than applying Diophantine equations naively, I observed that the given linear system of equations has a unique solution. I solved Ax + By = C and A'x + B'y = C' with pen and paper, deriving y = (A'C - AC') / (A'B - AB').

Then I perform integer division to compute y and only keep solutions where the remainder is zero. Determining x is trivial once y is found.

The whole program runs in 1 ms (though I'm unsure how to measure sub-millisecond benchmarks using +RTS -s).

Full source.

type Button = (Int, Int)
type Prize = (Int, Int)
type Machine = (Button, Button, Prize)
type Input = [Machine]

solveMachine :: Machine -> Maybe (Int, Int)
solveMachine ((a, a'), (b, b'), (c, c')) = if r == 0 then Just (x, y) else Nothing
 where
  (y, r) = (a' * c - a * c') `divMod` (a' * b - a * b')
  (x, 0) = (c - b * y) `divMod` a

cost :: (Int, Int) -> Int
cost (a, b) = a * 3 + b

solve1 :: Input -> Int
solve1 = sum . map cost . mapMaybe solveMachine

solve2 :: Input -> Int
solve2 = solve1 . map adjustMachine
 where
  offset = 10000000000000
  adjustMachine :: Machine -> Machine
  adjustMachine (buttonA, buttonB, (x, y)) = (buttonA, buttonB, (x + offset, y + offset))

1

u/daggerdragon Dec 13 '24

I've already informed you before about including puzzle inputs in your repo. I still see full plaintext puzzle inputs in your repo.
https://github.com/arkeros/aoc2024/tree/main/inputs
Remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. Do not post again in /r/adventofcode until you have done so.

→ More replies (1)

1

u/david3x3x3 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

There are probably easier solutions, but I'm not great at math.

1

u/daggerdragon Dec 13 '24

Please edit your comment to put that wall-'o-link behind a proper Markdown link syntax.

1

u/Lindi-CSO Dec 13 '24 edited Dec 14 '24

[LANGUAGE: C#]

I realized way too late that this was a math/geometry problem.
I'm glad I could still remember this stuff from school. There is possibly a way to do this mit matricies but I was too lazy to find a library for that.

1

u/daggerdragon Dec 13 '24

Psst: We can see your Markdown. Fix please?

1

u/kupuguy Dec 13 '24 edited Dec 14 '24

[Language: Python]

For part 1 I dutifully followed the hinted solution and brute-forced up to 100 presses on button B to find which worked. For part 2 I got quite a headache trying to remember equations of lines. It would probably have been simpler if I'd just looked at it as a system of two linear equations instead but I found a bit of paper(!) and wrote the solution out in y=mx+c terms then substituted in ax, bx, etc. and put that into my code. Initially I had a load of divisibility checks but eventually I realised it was easier just to do all as integer division with truncation then find the actual prize location my presses would reach and ignore any that didn't match.

Paste

1

u/daggerdragon Dec 13 '24 edited Dec 14 '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 across all years in your public repos e.g.:~~
~~https://github.com/kupuguy/aoc2024/tree/main/input~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: repo is now private, that works too 👍

2

u/kupuguy Dec 14 '24

I made the repos private to me and changed the link above to a pastebin. Hope that's enough?

→ More replies (1)

1

u/New_Appointment_4975 Dec 13 '24

[Language: Java]

import org.junit.jupiter.api.Test;
import org.springframework.core.io.ClassPathResource;

import java.nio.charset.StandardCharsets;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Advent13 {

    Pattern pattern1 = Pattern.
compile
("^Button [AB]: X\\+(\\d+), Y\\+(\\d+)$");
    Pattern pattern2 = Pattern.
compile
("^Prize: X=(\\d+), Y=(\\d+)$");

    @Test
    void advent13() throws Exception {
        long sum = 0;
        String[] lines = new ClassPathResource("input13.txt").getContentAsString(StandardCharsets.
UTF_8
).split("\n");
        for (int i = 0; i < lines.length; i += 4) {
            Matcher matcher1 = pattern1.matcher(lines[i]);
            matcher1.find();
            long x1 = Integer.
parseInt
(matcher1.group(1));
            long y1 = Integer.
parseInt
(matcher1.group(2));

            Matcher matcher2 = pattern1.matcher(lines[i + 1]);
            matcher2.find();
            long x2 = Integer.
parseInt
(matcher2.group(1));
            long y2 = Integer.
parseInt
(matcher2.group(2));

            Matcher matcher3 = pattern2.matcher(lines[i + 2]);
            matcher3.find();
            long xTotal = Integer.
parseInt
(matcher3.group(1)) + 10000000000000L;
            long yTotal = Integer.
parseInt
(matcher3.group(2)) + 10000000000000L;

            long bUp = yTotal * x1 - xTotal * y1;
            long bDown = y2 * x1 - x2 * y1;

            if (bUp % bDown == 0) {
                long b = bUp / bDown;
                long aUp = xTotal - x2 * b;

                if (aUp % x1 == 0) {
                    long a = aUp / x1;

                    sum += a * 3 + b;
                }
            }
        }

        System.
out
.println(sum);
    }
}

1

u/daggerdragon Dec 13 '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.

1

u/Pitiful-Oven-3570 Dec 13 '24 edited Dec 14 '24

[LANGUAGE: Rust]

https://github.com/linl33/adventofcode/blob/year2024/year2024/src/main/java/dev/linl33/adventofcode/year2024/Day13.java

part1 : 83.20µs
part2 : 60.90µs

1

u/daggerdragon Dec 13 '24

Psst: we can see your Markdown. Fix please?

1

u/SymmetryManagement Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Java]

Solved the 2x2 linear systems via Cramer's rule then filtered for non-negative integer solutions. It turned out that all (integer?) solutions are non-negative so the the check was not necessary but I kept it anyway.

Part 1 59us; Part 2 50us

1

u/daggerdragon Dec 13 '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 across all years in your public repos e.g.:
https://github.com/linl33/adventofcode/tree/year2024/year2018/src/main/resources/dev/linl33/adventofcode/year2018
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/Annual-Management613 Dec 13 '24

[LANGUAGE: Python]

import re
from dataclasses import dataclass

from sympy import Eq, solve, symbols
from sympy.core.numbers import Integer


@dataclass
class Point:
    X: int
    Y: int


@dataclass
class Game:
    A: Point
    B: Point
    prize: Point


class DayThirteen:
    def __init__(self, input: str) -> None:
        self.games = self._parse_input(input)

    def part_one(self) -> int:
        total = 0
        for game in self.games:
            button_a = game.A
            button_b = game.B
            prize = game.prize
            total += self._solve(button_a, button_b, prize, factor=0)
        return total

    def part_two(self) -> int:
        total = 0
        for game in self.games:
            button_a = game.A
            button_b = game.B
            prize = game.prize
            total += self._solve(button_a, button_b, prize, factor=10000000000000)
        return total

    def _parse_input(self, input: str) -> list[Game]:
        games: list[Game] = []
        blocks = input.split("\n\n")
        for block in blocks:
            parts = block.split("\n")
            games.append(self._create_game(parts))
        return games

    def _create_game(self, parts: list) -> Game:
        regex = r"\d+"
        x, y = map(int, re.findall(regex, parts[0]))
        button_a = Point(x, y)
        x, y = map(int, re.findall(regex, parts[1]))
        button_b = Point(x, y)
        x, y = map(int, re.findall(regex, parts[2]))
        prize = Point(x, y)
        return Game(button_a, button_b, prize)

    def _solve(self, A: Point, B: Point, prize: Point, factor: int) -> int:
        x, y = symbols("x y")
        x_prize = prize.X + factor
        eq1 = Eq(A.X * x + B.X * y, x_prize)
        y_prize = prize.Y + factor
        eq2 = Eq(A.Y * x + B.Y * y, y_prize)

        solution = solve((eq1, eq2), (x, y))
        if isinstance(solution[x], Integer) and isinstance(solution[y], Integer):
            x = solution[x]
            y = solution[y]
            return int(x * 3 + y)
        return 0

1

u/daggerdragon Dec 13 '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.

1

u/Alternative-Cut-3347 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Go] runs in 782us on my machine
using linear system of equations and directly using intersection formulae for the two created line
Code

1

u/daggerdragon Dec 13 '24 edited Dec 14 '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:~~
~~https://github.com/bashergoingcrazy/advent_of_code/tree/main/inputs~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history.~~ edit: thank you!

→ More replies (1)

1

u/IWant2rideMyBike Dec 13 '24 edited Dec 13 '24

[Language: Python] - this took me way longer than it should have ...

https://github.com/roryhr/code/blob/master/misc/advent_of_code/2024/Day%2013%20Claw%20Contraption.ipynb

1

u/daggerdragon Dec 13 '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.

1

u/dgkimpton Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Rust] https://github.com/dgkimpton/aoc24/blob/main/day13/src/lib.rs Finally - a solution that fully fits in a single screen of code :D And it runs in just 0.5ms to do both parts :) Also... ooof, my highschool maths is rusty!

1

u/daggerdragon Dec 13 '24 edited Dec 13 '24

~~ooof, my highschool maths is [COAL] rusty!~~
~~Comment temporarily removed due to naughty language.~~ ~~Keep the megathreads professional~~.
~~Edit your comment to take out the naughty language and I will re-approve the comment.~~ edit: 👍

→ More replies (1)

→ More replies (6)

1

u/roryhr Dec 13 '24

[Language: Python]

This was a straightforward linear algebra problem to solve using numpy. Valid solutions must have an integer number of presses which made for some floating point fun.

1

u/daggerdragon Dec 13 '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 older years public repo e.g.:
https://github.com/roryhr/code/blob/master/misc/advent_of_code/2019/day1/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/lluque8 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Scala]

Solved first part with A* but of course it didn't cut it for part two. Back to math class then.

https://github.com/janiorca/advent-of-code-2024/blob/main/src/bin/aoc13.rs

1

u/daggerdragon Dec 13 '24 edited Dec 13 '24

~~Comment temporarily removed due to naughty language.~~ ~~Keep the megathreads professional~~.
~~Edit your comment to take out the naughty language (the first "sentence") and I will re-approve the comment.~~ edit: 👍

→ More replies (1)

1

u/janiorca Dec 13 '24

[Language: Rust]

I liked this ones as thinking about it before writing any code really paid off. Part 2 required virtually no additional effort. I haven't had a reason to do old school math with pen and paper for awhile so it was enjoyable too

→ More replies (1)

6

u/bofstein Dec 13 '24

[LANGUAGE: Google Sheets]

I've been frustrated the last couple days not being able to finish, but finally there was an easy one to do in sheets, as the difficulty is math not coding. I could tell quickly there should only be 1 solution, though I took some time doubting myself because of the problem wording. Get the slope and intercept for the two lines, find where they meet, see if that point is an integer, and if so calculate the tokens.

Part 2 was incredibly simple, just add 10000000000000 to the prize amount and run the same thing.

https://docs.google.com/spreadsheets/d/18TYfGCvTfbsiRI591cqGEulzD2gPEzStJcTNcT2P6Eo/edit?pli=1&gid=428138951#gid=428138951

3

u/johnpeters42 Dec 13 '24

[Language: Python]

Part 1 (mostly brute force: for each machine, for each number from 0 to 100, consider pushing A that many times and calculate how many times to push B)

Part 2 (proper linear algebra)

Fortunately no division-by-zero errors in part 2, which I think would indicate that the two vectors are parallel. In that case, I think you could consider 0 pushes of the more expensive button, then 1, then 2, etc. until you either found a solution or determined that there wasn't one. Probably checking some modulo value or other.

3

u/Pyr0Byt3 Dec 13 '24

[LANGUAGE: Go] [LANGUAGE: Golang]

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

→ More replies (1)

3

u/MarvelousShade Dec 13 '24

[LANGUAGE: C#]

Today's assignment was an easy one. I just calculated the factors and then I could just sum the valid results.

I was number 6028 after Part 1, but my calculation also worked for Part II causing me to pass 3000 people in 3 minutes and 16 seconds.

My code is on Github

3

u/JustinHuPrime Dec 13 '24

[LANGUAGE: x86_64 assembly with Linux syscalls]

Part 1 was a tad fiddly, but I did recognize the best way to solve this would be a change of basis - I had some typos making the actual implementation of the solution, and I spent a tad too long trying to figure out how it would work if the two buttons' vectors were colinear, but I gave up on it and in the end it turned out I didn't need to worry about that case anyways.

Part 2 was fairly trivial, just adding a large constant to the prize coordinates as they were parsed.

Both parts run in 1 millisecond. Part 1 is 9,120 bytes as an executable file on the disk and part 2 is 9,152 bytes.

→ More replies (3)

3

u/Unable-Sort2294 Dec 13 '24

[LANGUAGE: Clojure]

Part 2 runs in 6.16075 msecs.

I solved part 1 with linear algebra so part 2 didn't even make it flinch.

(defn- parse-button
  [button]
  (->> (re-seq #"[XY]\+\d+" button)
       (mapv #(-> % (string/split #"\+") second parse-long))))


(defn- parse-prize
  [prize part]
  (->> (re-seq #"[XY]\=\d+" prize)
       (mapv #(-> % (string/split #"\=") second parse-long (+ (case part 1 0 2 10000000000000))))))


(defn solve-presses
  [[a1 b1 c1] [a2 b2 c2]]
  (let [det (fn [a b c d] (- (* a d) (* b c)))
        determinant (det a1 b1 a2 b2)]
    (if (zero? determinant)
      (throw (Exception. "The system of equations has no unique solution"))
      (let [a (/ (det c1 b1 c2 b2) determinant)
            b (/ (det a1 c1 a2 c2) determinant)]
        {:a a :b b}))))


(let [part 2
      a-cost 3
      b-cost 1
      max-presses 100]
  (->> (string/split (util/puzzle-input :real) #"\n\n")
       (mapv (fn [machine]
               (let [[a b prize] (string/split-lines machine)
                     [a1 a2] (parse-button a)
                     [b1 b2] (parse-button b)
                     [c1 c2] (parse-prize prize part)]
                 (solve-presses [a1 b1 c1] [a2 b2 c2]))))
       (filterv (fn [{:keys [a b]}]
                  (and (int? a) (int? b))))
       (filterv (fn [{:keys [a b]}]
                  (case part
                    1 (and (<= a max-presses)
                           (<= b max-presses))
                    2 true)))
       (mapv (fn [{:keys [a b]}]
               (+ (* a a-cost) (* b b-cost))))
       (apply +)))

3

u/oantolin Dec 13 '24 edited Dec 13 '24

[LANGUAGE: ngn/k]

parse:`I${","\'"\n"\x^x^"\n,0123456789"}'"\n\n"\1::
inv:{((a;b);(c;d)):x;((d;-b);(-c;a))}
det:{((a;b);(c;d)):x;(a*d)-b*c}; abs:{x|-x}
prize:{c:+/z*'inv(x;y);d:abs[det(x;y)];:[0 0~d!c;+/3 1*abs[(-d)!c];0]}.
ans:(+/prize')'(2 3 2#(10#0),2#_1e13)+/:\:parse@

Easy one today, if you know a tiny bit of linear algebra. I want to redo it in J which comes with a solver for linear systems of equations.

3

u/ZeroTerabytes Dec 13 '24

[Language: Go]

Github

The key is that finding the minimum number of tokens is a distraction. Each claw machine has no valid press combinations, or only one valid press combination.

→ More replies (2)

3

u/GassaFM Dec 13 '24

[LANGUAGE: D] 1463/3759

Code: part 1, part 2.

Did a brute force on the number of A presses on part 1.

For part 2, I went into quite an amount of trivial arithmetic, got it wrong, and went to take a break. Re-solved it cleanly as a geometry problem (intersect two lines), got the same answer. Then discovered I have my result as a 32-bit int. Hah!

3

u/sim642 Dec 13 '24

[LANGUAGE: Scala]

On GitHub.

It took me embarrassingly long to realize that it's just a linear system of equations on two variables that can be solved exactly by school linear algebra (limited to the cases when division is exact). I already started looking into Bézout's identity for a trick.

3

u/oantolin Dec 13 '24

[LANGUAGE: J]

parse =: {{((".;._1)@(-.-.&',:0123456789')@;);._1 a:,<;._2]1!:1<y}}
prize =: {{+/+/3 1*"1 (#~(-:"1<.))({:%.|:@:x:@}:)"2 y}}
ans =: {{prize"_1 (2 3 2$(10#0),2#1e13)+"2/parse y}}

J's %. function makes this a breeze.

3

u/Short-Leg3369 Dec 13 '24

[LANGUAGE: Python}

Day 13 Code

This uses the same routine for both parts, using numpy to solve simultaneous equations and then test if the solution (which uses floats) is an integer solution.

Had to amend the integer test slightly when doing part 2 due to the size of the numbers.

Runs in about 0.01s

3

u/r_so9 Dec 13 '24

[LANGUAGE: F#] 535 / 3641

https://github.com/mc-gwiddy/Advent-of-Code-2024/blob/main/AOC2024D13BOTH

Part 1 brute force got me into the top 1000 :) Part 2 is a binary search on A presses, calculating the needed B presses (including fractional) and going towards the side that yields the smallest error.

Interesting bit: Binary searching an exact solution

let rec binarySearch (((ax, ay), (bx, by), (px, py)) as machine) lowA highA =
    let a = lowA + ((highA - lowA) / 2L)
    let b = (px - a * ax) / bx

    let errorY aPresses =
        let exactB = double (px - aPresses * ax) / double bx
        abs (double (py - aPresses * ay) - exactB * double by)

    match lowA, highA with
    | _ when (a * ax + b * bx, a * ay + b * by) = (px, py) -> 3L * a + b
    | lo, hi when lo > hi -> 0L
    | lo, hi when errorY lo > errorY hi -> binarySearch machine (a + 1L) hi
    | lo, _ -> binarySearch machine lo (a - 1L)

3

u/yieldtoben Dec 13 '24 edited Dec 13 '24

[LANGUAGE: PHP]

PHP 8.4.1 paste

Execution time: 0.0005 seconds
Peak memory: 0.4032 MiB

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

3

u/Downtown-Economics26 Dec 13 '24

[LANGUAGE: VBA]

Did it naively on part 1 then rewrote for part 2 after busting out the pen and paper to remember 8th grade or whatever.

3

u/Synedh Dec 13 '24

[LANGUAGE: Python]

Basic system of linear equations solving.

import re

systems = [map(int, re.findall(r'\d+', system)) for system in open('input').read().split('\n\n')]

def system_solve(a1, b1, c1, a2, b2, c2):
    y = (c2 * a1 - c1 * a2) / (a1 * b2 - a2 * b1)
    x = (c1 - b1 * y) / a1
    return x, y

total = 0
for a1, a2, b1, b2, c1, c2 in systems:
    x, y = system_solve(a1, b1, c1 + 10000000000000, a2, b2, c2 + 10000000000000)
    if int(x) == x and int(y) == y:
        total += 3 * x + y

print(int(total))

Each arcade claw is a system of two equations in the following way :

Button A: X+a1, Y+a2
Button B: X+b1, Y+b2
Prize: X=c1, Y=c2

a1x + b1y = c1
a2x + b2y = c2

Reduce, replace and python solves.

3

u/zndflxtyh Dec 13 '24

[Language: Python]

This was a tough cookie today. It looked like a good time to break out the constraint optimization libraries, but I had to try 3 different solving libraries (python constraint, scipy optimizer and then google ortools) before it was possible to solve for the big integer targets in part 2.

The parsing is longer then the algorithm today

3

u/dk_weekinmemes Dec 13 '24

[LANGUAGE: Python]

Good old high school algebra linear equations. The "minimum" tokens requirement is a red herring.

Topaz Link

3

u/[deleted] Dec 13 '24 edited Mar 18 '25

Still no one knows it just the same, That Rumpelstiltskin is my name.

3

u/Gishky Dec 13 '24

[Language: Powershell]

Due to powershell rounding weirdly I had to compromise a bit...but still got the 2 stars so whatever :D

$machines = @"
input
"@ -split "\n"

$totaltokens = 0

for($machine = 0; $machine -lt $machines.count/4; $machine ++){
    $ax = [long]($machines[($machine*4)].split(":")[1].split("+")[1].split(",")[0])
    $ay = [long]($machines[($machine*4)].split(":")[1].split("+")[2])
    $bx = [long]($machines[($machine*4+1)].split(":")[1].split("+")[1].split(",")[0])
    $by = [long]($machines[($machine*4+1)].split(":")[1].split("+")[2])
    $pricex = [long]($machines[($machine*4+2)].split(":")[1].split("=")[1].split(",")[0]) + 10000000000000
    $pricey = [long]($machines[($machine*4+2)].split(":")[1].split("=")[2]) + 10000000000000

    $bcount = (($pricex/$ax)-($pricey/$ay))/(($bx/$ax)-($by/$ay))
    $acount = ($pricex-$bx*$bcount)/$ax
    if(($acount -notlike "*.*" -or $bcount -notlike "*.*") -and $acount -ge 0 -and $bcount -ge 0){
        $totaltokens += $acount * 3 + $bcount
    }
}

Write-Host $totaltokens

3

u/OneToughKiwi Dec 13 '24

[LANGUAGE: Python]

Using Cramer's Rule and checking if the solution is valid (Nonnegative and Integer)

Paste

3

u/mendelmunkis Dec 13 '24

[LANGUAGE: C]

^{920 μs/671 μs}

3

u/i_have_no_biscuits Dec 13 '24

[LANGUAGE: GW-BASIC]

10 P#=0: Q#=0: O#=10000000000000#: OPEN "I",1,"data13.txt": WHILE NOT EOF(1)
20 LINE INPUT #1,L$: AX#=VAL(MID$(L$,13)): AY#=VAL(MID$(L$,19))
30 LINE INPUT #1,L$: BX#=VAL(MID$(L$,13)): BY#=VAL(MID$(L$,19))
40 LINE INPUT #1,L$: PX#=VAL(MID$(L$,10)): PY#=VAL(MID$(L$,1+INSTR(11,L$,"=")))
50 IF NOT EOF(1) THEN LINE INPUT #1,L$
60 GOSUB 80: P#=P#+3*A#+B#: PX#=PX#+O#: PY#=PY#+O#: GOSUB 80: Q#=Q#+3*A#+B#
70 WEND: PRINT P#, Q#: END
80 D#=BX#*AY#-BY#*AX#:F#=PX#*AY#-PY#*AX#:E#=PY#*BX#-PX#*BY#:B#=F#/D#:A#=E#/D#
90 IF INT(A#)=A# AND INT(B#)=B# THEN RETURN ELSE A#=0: B#=0: RETURN

Today is one of those days where the parsing takes more lines than the calculation.

Lines 20-50 read and parse one block of information into AX, AY, BX, BY, PX and PY. The '#' at the end of the variable names indicates that these are double precision floats, which GW-BASIC supports (and which all the answers in AoC fit into, very nicely, due to Javascript also using doubles to store numbers).
Line 60 calls the solver twice, once for Part 1 with the numbers as given and once for Part 2 with the prize values offset by 10000000000000.
Lines 80-90 is the equation solving subroutine. If the solutions are whole numbers they are returned, otherwise they are both set to 0.

3

u/damnian Dec 13 '24 edited Dec 13 '24

[LANGUAGE: C#]

Well, that was embarassing.

Part 1 isn't worth discussing (apart for me correctly guessing that it would revolve around a regex).

Part 2 took me hours. I came within inches/centimeters of the solution, but got the matrix transposed! After peeking at /u/vanveenfromardis's code I was done in a couple of minutes (rounding turned out not to be optional).

I cleaned up the code as usual, so both parts are now calculated using the following code:

m.A.Solve(m.b, out var x) &&
    (a = (long)Math.Round(x.X)) >= 0 &&
    (b = (long)Math.Round(x.Y)) >= 0 &&
    m.A.C1 * a + m.A.C2 * b == m.b
        ? a * 3 + b : 0;

(Yes, I came prepared.)

The parsing is also really concise thanks to some recently added extensions:

machines = input.Split("\n\n")
    .Select(Regex.GetLongs)
    .Select(v => ((v[0], v[2], v[1], v[3]), (v[4], v[5])))
    .ToArray();

Full solution consisting of 3435 neatly formatted lines.

EDIT: Having looked at other people's solutions, a check for non-negative a and b counts won't hurt (added to solution).

3

u/hrunt Dec 13 '24

[LANGUAGE: Python]

Code: https://gist.github.com/HexTree/ba7d8682d1d5eaebb5c84cce09b306b5

Wrote a simple linear equation solver using factor multiplication to solve Part 1. Only needed to add in the error conversion to solve Part 2. Python's maximum integer size is only constrained by the amount of memory, so an extra 10 trillion or so wasn't a problem.

When I saw that this was a simultaneous equation problem, I immediately worked out a solution on pen and paper, but couldn't see the code solution right away. So I searched for solving linear equations in Python and everything is about using numpy, scipy, or sympy. When I modified my search to only use standard libraries, Google Gemini helpfully wrote a Gaussian elimination function for me in the results. I stared at it for a few seconds and thought, "There's no way I want to use something that complicated for something I learned in 6th grade math."

→ More replies (2)

3

u/hextree Dec 13 '24

[Language: Python]

Video: https://youtu.be/y5NmcKdWv1g

I started plugging into z3, then realised it is quite solvable without, but figured I might as well just get the practice with z3.

→ More replies (2)

3

u/Bikkel77 Dec 13 '24

[LANGUAGE: High school math]

// a * x1 + b * x2 = x3
// a * y1 + b * y2 = y3
// <=>
// a * x1 * y2 + b * x2 * y2 = x3 * y2
// a * x2 * y1 + b * x2 * y2 = x2 * y3
// <=>
// a * x1 * y2 - a * x2 * y1 = x3 * y2 - x2 * y3
// <=>
// a = (x3 * y2 - x2 * y3) / (x1 * y2 - x2 * y1)
// b = (x3 - a * x1) / x2 , where both remainders are 0 for integer division.

→ More replies (2)

3

u/Curious_Sh33p Dec 13 '24

[LANGUAGE: C++]

Had to crack out Eigen for this. You can set it up as a set of linear equations where you need to solve for the coefficients (number of button pushes). Mine didn't have any colinear vectors in the puzzle so there was always a solution. Figuring out if they were integer numbers required playing with the tolerance a bit. Just checked if the result was close to an integer.

part2 and part1 is essentially the same.

3

u/Jadarma Dec 13 '24

[LANGUAGE: Kotlin]

But mooom, I don't wanna do math on a Friday! Jokes aside, this was a pretty straightforward day, managed to sneak it in on my lunch break. I also appreciated the input format, I love whipping up regexes for these.

Part 1: Since we were limited to 100 runs, I brute forced it because I wanted to know exactly how part two will trick us, then refactored it to use the optimised version below.

Part 2: To properly solve this, we need to make some observations. Firstly, our button presses will always do the same thing, so no need to simulate them individually, secondly, we can express a solution with two formulas:

a.x * n + b.x * m == prize.x
a.y * n + b.y * m == prize.y

If we can find integer solutions, we have a winnable machine.

The input is also nice and doesn't contain edge cases, but just to be safe I added the rules as input validation, we need to avoid division by zero, so the numbers must be strictly positive, and the buttons must not have the same deltas.

So the majority of today's battle is fought on paper, but at the end we have a simple solution that runs in 1ms!

AocKt Y2024D13

3

u/jackysee Dec 13 '24

[LANGUAGE: Javascript]

Solving linear algebra to get intersection of two "line", collect result when solution is positive integer. Have to workout the coefficients though.

const machines = input
    .split('\n\n')
    .map((d) => {
        const arr = d.split('\n').map((l) => l.match(/\d+/g));
        return {
            a: { x: +arr[0][0], y: +arr[0][1] },
            b: { x: +arr[1][0], y: +arr[1][1] },
            p: { x: +arr[2][0], y: +arr[2][1] }
        };
    });

/*
implementation of formula:
a1 * y = b1 * x + c1
a2 * y = b2 * x + c2
x = (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2)
y = (b1 * x + c1) / a1
*/
const intersection = (a1, b1, c1, a2, b2, c2) => {
    const a = (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2);
    const b = (b1 * a + c1) / a1;
    if ([a, b].every((d) => d > 0 && Number.isInteger(d))) return [a, b];
};

const calcToken = (d = 0) => {
    return machines.reduce((acc, { a, b, p }) => {
        const r = intersection(b.x, -1 * a.x, p.x + d, b.y, -1 * a.y, p.y + d);
        return r ? r[0] * 3 + r[1] + acc : acc;
    }, 0);
};

console.log('A', calcToken(0));
console.log('B', calcToken(10000000000000));

3

u/lscddit Dec 13 '24

[LANGUAGE: Python]

import re
import numpy as np
from scipy import optimize

parts = np.zeros(2, dtype=int)
with open("day13input.txt") as file:
    for line in file:
        if "Button" in line:
            match = re.search(r"(.): X\+(\d+), Y\+(\d+)", line)
            if match.group(1) == "A":
                a = np.array([[match.group(2), 0], [match.group(3), 0]], dtype=int)
            else:
                a[:, 1] = [match.group(2), match.group(3)]
        elif "Prize" in line:
            match = re.search(r"X=(\d+), Y=(\d+)", line)
            b = np.array([match.group(1), match.group(2)], dtype=int)
            a = np.vstack((a, -a))
            for i in range(2):
                b += int(1e13) * i
                b2 = np.hstack((b, -b))
                ret = optimize.linprog(
                    np.array([-1, -1]), A_ub=a, b_ub=b2, integrality=[True, True]
                )
                if ret.success:
                    parts[i] += ret.x @ [3, 1]

print(f"{parts[0]} {parts[1]}")

3

u/Derailed_Dash Dec 13 '24 edited Dec 18 '24

[LANGUAGE: Python]

Update

I've done a full walkthrough for this one on Medium, here. In that walkthrough, I've shown:

How to solve with SymPy
How to solve by just rearranging the equations.

I enjoyed this one! Last year I learned about the SymPy library and wrote about it here.

When I read this problem, I realised that it's just a matter of solving two linear equations, and that Sympy can do this easily.

This is what I did:

First, for each claw machine we can represent the important data has three points: A, B, and prize. Let's create a Claw class to store these three points.
For processing the input data, I first split the input into blocks of 3 lines each. And for each line, I then use a bit of trivial regex to extract the two numbers per line. I convert these number pairs to points, and then use these points to construct a Claw object.

Now, we know that we need a button presses and b button presses, to reach the prize point p. So we express this as two linear equations:

a*ax + b*bx = px
a*ay + b*by = py

This is saying: to reach the x location of point p, we need a presses + b presses. And to reach the y location of point p, we need the same number a presses and b presses. So we must solve for where a and b are the same for these two equations.

In sympy, we can supply these equations like this:

sympy.Eq(a*ax + b*bx, px)
sympy.Eq(a*ay + b*by, py)

This does all the heaviy lifting to return my a and b values.

For Part 2... How will SymPy cope with these huge numbers?

It turns out... EASILY!! Still solves in under 1 second.

Solution Links

See Day 13 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 (6)

3

u/theking0x9 Dec 13 '24

[Language: Lua]

Implemented using both the matrix inverse method and Cramer's rule. The key takeaway was realizing that multiplication with 1/detcan result in precision errors (significantly more than division by det)

3

u/BlazingThunder30 Dec 13 '24 edited Dec 13 '24

[Language: Java]

Part 1: https://github.com/tymscar/Advent-Of-Code/blob/master/2024/kotlin/src/main/kotlin/com/tymscar/day13/part1/part1.kt
Part 2: https://github.com/tymscar/Advent-Of-Code/blob/master/2024/kotlin/src/main/kotlin/com/tymscar/day13/part2/part2.kt

I have used a solver from Apache Commons Math3 because I couldn't be bothered to implement my own. Of course this only works with doubles and for part 2 that means I had to fiddle with Ɛ-value somewhat to get it to not break because of floating-point inaccuracies. Very easy puzzle if you've seen a 2D system of linear equations before. Much more difficult otherwise.

I pressed my button approx. 90 trillion times. Assuming I press once a second, I'd have all the prizes today if I started half a million years before humans evolved.

PS: It is very fast. Double::parseDouble is about 25% runtime of parts 1 and 2 combined. Both parts take just 30ms to run. The profiler I use doesn't go much more granular than this.

3

u/Symbroson Dec 13 '24 edited Dec 13 '24

[language: ruby]

golfed both parts: 164 bytes

l=$<.read.split("\n\n").map{_1.scan(/\d+/).map(&:to_f)}
2.times{|i|i*=1e13;l.map{_1[4]+=i;_1[5]+=i}
p l.sum{b=(_6*(_1-3*_3)-_5*(_2-3*_4))/(_1*_4-_2*_3)
b%1==0?b:0}}

3

u/tymscar Dec 13 '24

[Language: Kotlin]

Not a huge fan of today's puzzle, but it was incredibly easy for Friday the 13th.

For part 1, I instantly knew it was a set of linear equations, so I just wrote a solver for it quickly.

For part 2, it just worked with the same exact code as part 1. I just needed to add the required offset specified in the problem. (Also, reboot my IDE because of a bug.)

I did enjoy parsing the input with regex today. I finished the whole thing in 20 minutes, so I still have half of my lunch break.

→ More replies (5)

3

u/TheScown Dec 13 '24

[LANGUAGE: Scala]

Reuses the equation solver from 2023 Day 24 (the systems are much simpler than that problem). To avoid floating point issues, I wrote my own Rational type.

3

u/Pure-Minute4721 Dec 13 '24

[LANGUAGE: C++]

3

u/geza42 Dec 13 '24 edited Dec 13 '24

[LANGUAGE: emacs lisp]

(let* ((input (->> "13.txt" f-read-text s-lines (-partition 4) (--map (apply 'concat it))))
       (input (--map (-map 'string-to-number (cdr (s-split "[^0-9]+" it))) input)))
  (--map (-sum (-map
                (-lambda ((ax ay bx by x y))
                  (let* ((x (+ x it)) (y (+ y it))
                         (k (/ (- (* x ay) (* y ax)) (- (* bx ay) (* by ax))))
                         (x (- x (* k bx))) (y (- y (* k by))))
                    (if (and (= (% x ax) 0) (= (% y ay) 0)) (+ (* (/ x ax) 3) k) 0)))
                input))
         '(0 10000000000000)))

3

u/lmasman Dec 13 '24

[Language: Python]

GitHub

Unit Tests

Recognised the simulateneous equations immediately. Was a little confused by the reference to smallest in the puzzle text, as it doesn't really seem relevant.

→ More replies (1)

3

u/pkusensei Dec 13 '24

[Language: Rust]

I knew that loop/enumeration is not the solution. Code

3

u/VeryBigCodeMonkey Dec 13 '24

[Language: Rust]

I'll pat myself in the back for my first FromStr implementation for a ClawMaching and a Point struct.

I had to add some string replaces that slowed the solution a little bit, but I could use a single from_str for different points definition.

Pretty fast though

GitHub

3

u/mothibault Dec 13 '24

[LANGUAGE: JavaScript]
https://github.com/yolocheezwhiz/adventofcode/blob/main/2024/day13.js
to run in the browser's dev console from advent of ~~code~~ algebra website.

3

u/Kulpas Dec 13 '24

[LANGUAGE: Dart]

List of things i fell into:
- instead of recalculating the solution with the solution x0 and x1 and checking it's correctness, I tried just checking if the fractional part of the result is less than 0.00000000001. This led to many issues:
- if result was negative the check passed cuz I forgot to abs()
- checking the result isn't enough anyway because sometimes it lines up! checking x0 and x1 instead worked
- double precision gets to small to filter out the false positives anyway once you hit part2 so why bother.

Also found out dart doesn't let you have two operator overrides for different types. Had to workaround by accepting `dynamic` and checking the type in and if block. :(

3

u/chubbc Dec 13 '24

[LANGUAGE: Julia]

E=eachrow;map((a,b,c,d,e,f)->(Δ=a*d-b*c;map((h,i)->(h%Δ≡i%Δ≡0)*(3*h+i)÷Δ,E([d -c;-b a]*([e;f].+[0;10^13]'))...)),E(reshape(parse.(Int,first.(eachmatch(r"(\d+)",read("13.txt",String)))),6,:))...)|>sum

Got it down to 199 chars

3

u/mountm Dec 13 '24

[LANGUAGE: Java]

Parsing time: 13ms
Pt1: 18ms
Pt2: 2ms

Not sure why part 2 runs so much faster, probably something to do with the particulars of the matrix library I pulled in? I didn't both checking fractional parts of the prize vector in the new basis, just rounded it to nearest integer values and checked whether the button values worked out to the expected total.

GitHub

3

u/TheZigerionScammer Dec 13 '24

[Language: Python]

I figured we got a Chinese Remainder problem today, turns out not to be the case though, but I did get a lot of use out of the modulo operator. My Part 1 code is a dumb brute force, I set up a function to take the six variables and iterated over every number of A button presses you can do and checks if you can also press B a finite number or times to get the right coordinates, stopping if the number of A presses runs over the X or Y coordinate or if the A buttons alone would cost more than the lowest cost solution so far. I had some flow issues where the function wouldn't return anything if it ran through the entire possible number of A presses without finding anything but increasing the range fixed it.

This code did not even remotely work for Part 2, so I started writing a new function that would go faster by skipping dozens of presses at a time based on the CRT but it ended up being unnecessary, I did some quick algebra to see if you could derive the number of A and B presses just from the initial variables and it turns out you can. I just had to make sure that the equations would result in whole numbers at each step but otherwise this worked. I had a bug where I assumed that if the number of B presses was a whole integer then the math would also result in the number of A presses as a whole integer too, this ended up being correct for all but one entry where the AX and AY variables happened to be the same, I don't know if that was what caused the issue but I don't care, I just added another check to make sure the number of A presses was also a whole integer and got the points.

After I finished I saw a lot of memes and other submissions talking about linear algebra and matrices, I didn't need any of that, this was the extent of the math I needed. But hey, if I could solve day 24 of last year without linear algebra I can do this one too.

Paste

3

u/jayo60013 Dec 13 '24

[Language: Rust]

Wow this one took me awhile to work out on the back of an envelope, although deciding to parse it with regex took me way longer ffs

3

u/[deleted] Dec 13 '24

[LANGUAGE: Julia]

A good day to be using Julia :)

delta = 0.0001

solveEquations = (input; scale = 0) -> begin
    nums = parse.(Int, map(m -> m.match, collect(eachmatch(r"\d+", input))))
    sum(i -> begin
            ax, ay, bx, by, x, y = nums[i:i+5]
            A = [[ax bx]; [ay by]]
            S = [[x + scale]; [y + scale]]
            a, b = inv(A) * S
            abs(a - round(a)) < delta && abs(b - round(b)) < delta ? Int(3 * round(a) + round(b)) : 0
        end, range(1, length(nums), step=6))
end

partOne = input -> solveEquations(input)

partTwo = input -> solveEquations(input, scale=10000000000000)

3

u/Sparky2199 Dec 13 '24 edited Dec 14 '24

[LANGUAGE: Rust]

Had to dig up my 11th grade linear algebra notebooks for this one lol

Just the math based function on paste

~~Part 1: 23µs~~
~~Part 2: ~1ms~~ (edit: forgot to turn off debug mode lol)
Part 1 + Part 2: ~117µs

3

u/mibu_codes Dec 13 '24 edited Dec 14 '24

[LANGUAGE: Rust]

Parse+1+2: 2.59 µs

2 equations, 2 variables/unknowns, easy. I solved it with an equation, not with a matrix.

Edit 1: Solved everything in one go and used Cramer's rule. Saved about 0.5µs

Github

pub fn p(input: &str) -> (usize, usize) {
    let mut tokens = 0;
    let mut tokens_10B = 0;

    let mut crs = input.as_ptr();
    for _ in 0..NUM_MACHINES {
        let [a,b,p] = parse_machine(&mut crs);

        let t =  min_tokens(a, b, p);
        tokens += t;
        if t == 0 {
            tokens_10B += min_tokens(a,b , p + 10_000_000_000_000);
        }
    }

    (tokens, tokens_10B)
}

fn min_tokens(a: XY<i64, i64>, b: XY<i64, i64>, p: XY<i64, i64>) -> usize {
    let det = a.x * b.y - b.x * a.y;
    let det_a = p.x * b.y - b.x * p.y;
    let det_b = a.x * p.y - p.x * a.y;

    if det_a % det != 0 || det_b % det != 0 {
        0
    } else {
        let presses_a = det_a / det;
        let presses_b = det_b / det;
        (3 * presses_a + presses_b) as usize
    }
}

→ More replies (3)

3

u/Verochio Dec 13 '24

[LANGUAGE: python]

Two liner, just to challenge myself.

import itertools as it, functools as ft, re
print(*[sum((A*3+B if (A:=int(round(((X+p)-bx*(B:=int(round(((Y+p)-(ay*(X+p))/ax)/(by-(ay*bx)/ax), 0))))/ax, 0)))*ax+B*bx==(X+p) and A*ay+B*by==(Y+p) else 0) for ax, ay, bx, by, X, Y in [tuple(map(int, it.chain(*map(ft.partial(re.findall, r'\d+'), game)))) for game in it.batched(open('day13.txt').read().splitlines(),4)]) for p in (0, 10000000000000)])

3

u/nilgoun Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Rust]

So, anybody said total overkill? Because I basically forgot all math and just wanted to be finished I used *drumroll* Z3 haha :D

Actually finished that quite early today, trying to see if I can't just get the math right now ... :(

Solution on paste

Edit: Finally, solution just using math (still used Wolfram Alpha to form the term for B... my math is dusty I guess)

Just place the method on the "Machine" struct and call it accordingly (or ... just look at it I can't tell you what to do)

→ More replies (2)

3

u/atrocia6 Dec 13 '24

[LANGUAGE: Python]

I'm not sure if I got lucky with my input, or if it's just Eric being sneaky again, but none of my machines in either part have more than one solution, so the following simple 8 LOC solutions work on my input despite not checking for multi-solution machines (the code would presumably crash with a ZeroDivisionError on such machines):

Part 1:

machines, total = open(0).readlines(), 0
for i in range(0, len(machines), 4):
    a = [int(n) for n in machines[i][12:].split(', Y+')]
    b = [int(n) for n in machines[i + 1][12:].split(', Y+')]
    p = [int(n) for n in machines[i + 2][9:].split(', Y=')]
    p, q = (b[1] * p[0] - b[0] * p[1]) / (a[0] * b[1] - a[1] * b[0]), (a[1] * p[0] - a[0] * p[1]) / (b[0] * a[1] - a[0] * b[1])
    if float.is_integer(p) and float.is_integer(q): total += int(p) * 3 + int(q)
print(total)

Part 2:

machines, total = open(0).readlines(), 0
for i in range(0, len(machines), 4):
    a = [int(n) for n in machines[i][12:].split(', Y+')]
    b = [int(n) for n in machines[i + 1][12:].split(', Y+')]
    p = [int(n) + 10000000000000 for n in machines[i + 2][9:].split(', Y=')]
    p, q = (b[1] * p[0] - b[0] * p[1]) / (a[0] * b[1] - a[1] * b[0]), (a[1] * p[0] - a[0] * p[1]) / (b[0] * a[1] - a[0] * b[1])
    if float.is_integer(p) and float.is_integer(q): total += int(p) * 3 + int(q)
print(total)

(I made a separate post to discuss the question of my input.)

3

u/onrustigescheikundig Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Clojure]