solving two equations for a and b worked easily as only one a and one b could be the answer. At last taking all the whole numbers and discarding floats gave the correct answer.
solving two linear equations on two unknowns only works because input is manipulated for it. extended euclidean algorithm is necessary for a generalized input. but you couldnt get lucky with linear algebra if u didnt at least try linear algebra.
@@harisimer wait a minute, if solving two linear equations don't work, than the prize could not be reached (collinear or parallel vectors cases) and we skip these cases
very nicely done! I ended up solving the system of equations by hand and ended up with this ruby code (took me over an hour though :)) pb, qb = (py * ax - px * ay).divmod(ax * by - ay * bx) return 0 unless qb == 0 pa, qa = (px - bx * pb).divmod(ax) return 0 unless qa == 0 pa * 3 + pb
I also made the 'mistake' of wasting time brute forcing part 1, i had a strong sus that part 2 would break it. I then assumed it would be too easy for a day 13 to trust a nonzero determinant, so I ended up checking for truly no/infinite solutions (detA = 0), neither of which even occurred. Didnt really make it any easier/harder, but confused me when debugging. Then for solving the unique solution I used A^{-1}b = x, failing to realize that non integer solutions obviously failed, so I used Math.floorDiv(d * p.x - b * p.y, detA) and Math.floorDiv(-c * p.x + a * p.y, detA) instead of rounding to keep exact longs and no floating point errors, then checked that solution solved the equation. Definitely could have made it on the leaderboard if a had a linear equation / lattice solver ahead of time. oh well.
instead of using the euclidian algorithm you could also just solve the equations for a and b and then see if it works. took me a little bit with pen and paper but worked fine and is then just a = ..., b=... and the if check if it works out
Yep same, if you work it out mathematically its actually a really easy question that most people in AoC could complete. But Neil did this as well right? The np.linalg.solve solves it in the same way I assume.
I also thought it will be extended euclidean problem when I saw the puzzle first. Small hint: put the mic away from the keyboard. The typing clicks are really annoying.
solving two equations for a and b worked easily as only one a and one b could be the answer. At last taking all the whole numbers and discarding floats gave the correct answer.
wow, didn't expect to see any algorithms today. Now I'm really proud I immediately recognized system of two ecuations with two unknowns.
solving two linear equations on two unknowns only works because input is manipulated for it.
extended euclidean algorithm is necessary for a generalized input. but you couldnt get lucky with linear algebra if u didnt at least try linear algebra.
@@harisimer wait a minute, if solving two linear equations don't work, than the prize could not be reached (collinear or parallel vectors cases) and we skip these cases
@Gusto2000 colinear cases can have solutions. A: 1,2 B:2,4 Prize 21,42. Or even A: 1,1 B: 1,1 Prize 1,1.
@@harisimer ok, Cramer's rule will give you some solution, but it won't be correct. Especially for the last one when it's 0+3*0. Right?
@@harisimer I guess I would expect such test cases from leetcode, but with aoc you have to yolo it first 😉
very nicely done! I ended up solving the system of equations by hand and ended up with this ruby code (took me over an hour though :))
pb, qb = (py * ax - px * ay).divmod(ax * by - ay * bx)
return 0 unless qb == 0
pa, qa = (px - bx * pb).divmod(ax)
return 0 unless qa == 0
pa * 3 + pb
10:52 jesus :D
I also made the 'mistake' of wasting time brute forcing part 1, i had a strong sus that part 2 would break it. I then assumed it would be too easy for a day 13 to trust a nonzero determinant, so I ended up checking for truly no/infinite solutions (detA = 0), neither of which even occurred. Didnt really make it any easier/harder, but confused me when debugging. Then for solving the unique solution I used A^{-1}b = x, failing to realize that non integer solutions obviously failed, so I used Math.floorDiv(d * p.x - b * p.y, detA) and Math.floorDiv(-c * p.x + a * p.y, detA) instead of rounding to keep exact longs and no floating point errors, then checked that solution solved the equation. Definitely could have made it on the leaderboard if a had a linear equation / lattice solver ahead of time. oh well.
symoy my beloved
instead of using the euclidian algorithm you could also just solve the equations for a and b and then see if it works. took me a little bit with pen and paper but worked fine and is then just a = ..., b=... and the if check if it works out
Yep same, if you work it out mathematically its actually a really easy question that most people in AoC could complete. But Neil did this as well right? The np.linalg.solve solves it in the same way I assume.
Mfw highschool math
I also thought it will be extended euclidean problem when I saw the puzzle first. Small hint: put the mic away from the keyboard. The typing clicks are really annoying.
Some of us enjoy the keyboard sounds!
That biktar guy is going on my nerves.
he didnt even do 12 and 13 in time
@harisimer Doesn't make him innocent.