Great explanation of the math behind the correct answer, thank you for making it as not-scary as possible! Working to the same equation in 2 different ways really makes it seem less like "magic" too 🙏
This is an amazing video!! I’ve spent all my Friday evening trying to over-engineer and over-optimise the solution to this problem but kept reaching a dead end. Thanks a lot for the explanation and the simplification.
That was actually a great explanation! Watched it for part 2, then took a break for a few hours then tried to implement everything myself, worked like a breeze!
This is a very straightforward system of 2 equations with 2 unknown. I used a small generic linear equation solver, linear-solve in NodeJS for both cases. Runs in under 2ms. The only thing to watch out for is rounding issues. You get super near to integer numbers that you need to accept as close enough
excellent explanation, thanks 🙏 I solved it using sympy, remembering last year's hail problem it runs ~7s; your solution is instant ;-) # pa, pb is not price, but pushes def get_pushes2(ax, ay, bx, by, x, y): pa, pb = sympy.symbols("pa, pb") equations = [pa * ax + pb * bx - x, pa * ay + pb * by - y] sln = sympy.solve(equations) pushes_a, pushes_b = sln.values() if sympy.simplify(pushes_a).is_Integer and sympy.simplify(pushes_b).is_Integer: return True, pushes_a, pushes_b # not Integer solution return False, pushes_a, pushes_b
You have no idea how hard I made my life by expecting some cases of a and b being co-linear and that there WOULD be multiple solutions. That's why I originally ruled out this approach. I should have been smart enough to check a and b and treat those cases separately, in case they happen (which they never did).
I used an algebraic solution from the start. Part 1 worked fine but I got the wrong answer on part 2 until you emphasised that there is only one solution to each pair of equations (which I should have known). My mistake was to eliminate non integer results by checking that button A was an integer, but not button B. Of course there are some results where A is an integer but B isn't because Eric is a sneaky fellow.
Same! The linear algebra approach is 10x easier than pure algebra and only a couple more LoC. Just need to make sure that both a, b are integers before accepting them as solutions.
11:40 What do you mean it becomes harder? Isn't it impossible unless the prize point is on either slope and if it is just compare the cost of the buttons?
Great videos, always. Even when I managed to solve the problem, I learn something new every day when I watch your explanations. Why you leave exercises to the "reader" ? Reader of what ? the captions ? Are you reading too many text books ?
Nice solution! When the denominator is 0, wouldn't it mean that the vectors of the A and B directions are the same direction? Then we would have to check if you could get to the prize in an integer multiple of A or B and then pick the cheaper viable option.
yep. i go over this later in the video but deliberately chose not to handle this case because it would be a lot harder than the problem itself. the difficulty comes from the ability to mix A and B presses even if they're collinear due to only being able to press buttons an integer number of times so you'd have to solve diophantine equations i think
5:21 There could be infinite solutions or no solution. If the determinant is 0 (which my inputs never are), there could be (1) no solution the three vectors are colinear or (2) infinite solutions which we would have needed to find the best natural number solution.
Great explanation of the math behind the correct answer, thank you for making it as not-scary as possible! Working to the same equation in 2 different ways really makes it seem less like "magic" too 🙏
Great video, very clear explanation
This is an amazing video!! I’ve spent all my Friday evening trying to over-engineer and over-optimise the solution to this problem but kept reaching a dead end. Thanks a lot for the explanation and the simplification.
Nice explanation, thanks so much! I used sympy to solve the problem, but it's nice to understand the logic behind!
That was actually a great explanation! Watched it for part 2, then took a break for a few hours then tried to implement everything myself, worked like a breeze!
This is a very straightforward system of 2 equations with 2 unknown. I used a small generic linear equation solver, linear-solve in NodeJS for both cases. Runs in under 2ms. The only thing to watch out for is rounding issues. You get super near to integer numbers that you need to accept as close enough
excellent explanation, thanks 🙏
I solved it using sympy, remembering last year's hail problem
it runs ~7s; your solution is instant ;-)
# pa, pb is not price, but pushes
def get_pushes2(ax, ay, bx, by, x, y):
pa, pb = sympy.symbols("pa, pb")
equations = [pa * ax + pb * bx - x, pa * ay + pb * by - y]
sln = sympy.solve(equations)
pushes_a, pushes_b = sln.values()
if sympy.simplify(pushes_a).is_Integer and sympy.simplify(pushes_b).is_Integer:
return True, pushes_a, pushes_b
# not Integer solution
return False, pushes_a, pushes_b
Very nice explanation! Thanks for that. My linear algebra knowledge is quite rusty and I had some trouble with part2.
banger part 2 explanation
Py is really good at math caculation. I solved the problem in javascript, and I needed to take care of the issue of decimal precision.
You have no idea how hard I made my life by expecting some cases of a and b being co-linear and that there WOULD be multiple solutions. That's why I originally ruled out this approach. I should have been smart enough to check a and b and treat those cases separately, in case they happen (which they never did).
I used an algebraic solution from the start. Part 1 worked fine but I got the wrong answer on part 2 until you emphasised that there is only one solution to each pair of equations (which I should have known).
My mistake was to eliminate non integer results by checking that button A was an integer, but not button B.
Of course there are some results where A is an integer but B isn't because Eric is a sneaky fellow.
I solved this one using sympy, which helped a lot, but went back and rewrote it using actual general solutions for the intersection of lines
I used Cramer's rule to find the solutions. The end result is similar, but it's way easier to work out the equations.
Same! The linear algebra approach is 10x easier than pure algebra and only a couple more LoC. Just need to make sure that both a, b are integers before accepting them as solutions.
I tried with PuLP but got only the part one, part two was wrong
*Day 13 was a linear algebra problem the whole time...*
11:40 What do you mean it becomes harder? Isn't it impossible unless the prize point is on either slope and if it is just compare the cost of the buttons?
I solved it using Z3
Great videos, always. Even when I managed to solve the problem, I learn something new every day when I watch your explanations. Why you leave exercises to the "reader" ? Reader of what ? the captions ? Are you reading too many text books ?
oh. yep you're exactly right xD i've seen that phrase too many times in textbooks
Nice solution! When the denominator is 0, wouldn't it mean that the vectors of the A and B directions are the same direction? Then we would have to check if you could get to the prize in an integer multiple of A or B and then pick the cheaper viable option.
yep. i go over this later in the video but deliberately chose not to handle this case because it would be a lot harder than the problem itself. the difficulty comes from the ability to mix A and B presses even if they're collinear due to only being able to press buttons an integer number of times so you'd have to solve diophantine equations i think
@@hyper-neutrino Oh that's true. It wasn't obvious to me that it was possible to mix A and B presses even if they are collinear. I get it now.
5:21 There could be infinite solutions or no solution. If the determinant is 0 (which my inputs never are), there could be (1) no solution the three vectors are colinear or (2) infinite solutions which we would have needed to find the best natural number solution.
yep. i go over this later in the video but deliberately chose not to handle this case because it would be a lot harder than the problem itself
Great video, brilliant guy!
Does it turn into a mixed integer linear diophantine equation problem when the denominator is zero?
yes, i believe so
It also means that the movements button a and b do are collinear and effectively a Diophantine equation indeed.
2:57 what is open(0)?
It opens a file, in this case the file containing the puzzle input.
it opens file descriptor 0 which refers to STDIN. i use a utility to pipe my input file into the program as STDIN
@@hyper-neutrino ooh that is neat
Does Python have something similar to Perl’s ? Works as file argument or stdin
A =[ax,bx;by, by]
B=[p1,p2]
x,y = np.linalg.solve(A,B)
Thank me later😅