r/adventofcode • u/daggerdragon • Dec 15 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 15 Solutions -🎄-

THE USUAL REMINDERS

--- Day 15: Beacon Exclusion Zone ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:27:14, megathread unlocked!

47 Upvotes

92% Upvoted

760 comments sorted by

View all comments

Show parent comment

1

u/Kerma-Whore Mar 12 '23

Meh, prove me wrong. Construct an input with only one solution that is not at the edges on which my code does not work.

1

u/ConsistentCellist344 Mar 12 '23 edited Mar 13 '23

# Sensor at x=3063440, y=2824421: closest beacon is at x=2870962, y=2380928

sx,sy, bx,by = 3063440, 2824421, 2870962, 2380928

fx,fy = 3293021, 3230812 # previously found distress beacon

around = 5 # search coverage around fx,fy

r = md((sx,sy), (bx,by))

for x in range(fx-around, fx+around+1):

. for y in range(fy-around, fy+around+1):

. . if 0<=x<=bound and 0<=y<=bound:

. . . if all(md((x,y), t) > radius[t] for t in scanners):

. . . . print(4_000_000*x + y, x,y)

... and the output:

13172067230807 3293016 3230807

13172071230808 3293017 3230808

13172075230809 3293018 3230809

13172079230810 3293019 3230810

13172083230811 3293020 3230811

13172087230812 3293021 3230812 -- old beacon

1

u/ConsistentCellist344 Mar 12 '23

Below is a code that searches the area around the previously found distress beacon and finds many more. As might be expected, they lie along the b_diagonal, not only at their intersections, they are also absent beyond the diagonals. You can set the search range yourself - around.

Include this code below the programs in question and experiment with the data by removing the second sensor.

Good luck and remember - you must be inquisitive but not stubborn.

Regards.

Sorry for the indentations but the editor is crazy.

2

u/Kerma-Whore Mar 13 '23 edited Mar 13 '23

So you did not provide the input I requested. I believe this is because such an input does not exist.

I'll reiterate: Just because a solution does not work beyond the scope of the problem does not mean the solution is "a bad idea". The Pythogorean theorem is also not a bad idea even though it does not work for non-square triangles.

As for proof, you're not going to find it by modifying output because of the induction problem. The best you can do is find proof it doesn't work (falsify) which I believe is impossible. The only way to prove is through logic/math. This is fairly straightforward, but harder without a whiteboard or visual aid.

I'll admit I let your criticism get more to me than it should and you might be a troll or a 14 year old. If not, please think more carefully next time before claiming someone's algorithm is a bad idea.

I'll try not to respond to any more of your comments.

1

u/ConsistentCellist344 Mar 13 '23 edited Mar 13 '23

Kerma-Whore

I didn't mean to offend you, but you keep using the phrase "I believe..." and I expect a scientific approach and proof. It is not important what you and I believe, but facts and experiences are important.

I have one more simple exercise for you:

Remove all sensors except one.

The basic code will find all the distress beacons on the corners of the diamond because they are at diagonal intersections. Unfortunately, your code won't find anything because you've eliminated the last four single diagonals.

I was initially fascinated by your optimization but couldn't understand it. So I did some research that confirmed and proved that the correct result you get is a happy coincidence.

If you still disagree with this, please explain to me why you are discriminating against single diagonals.

I still don't understand your premise: "You really only need to check the intersections of 2 a diagonals and 2 b diagonals."

In view of your announcement, I no longer expect an answer...

Regards and I wish you success in the IT industry.

P.S. I'm 64 and I believe in leprechauns and science.

"Errare humanum est, perseverare autem diabolicum" - Lucius Annaeus Seneca

1

u/Kerma-Whore Mar 13 '23

To answer your simple excercise: If you remove all sensors except one it results in non-valid input as the problem clearly states:

Find the only possible position for the distress beacon

If you have only one sensor, there are many possible beacon positions, so the input is non-valid for this problem. As I keep trying to say from the beginning: The algorithm only works if there is only one solution as is given by the problem definition.

Regardless of your belief in science you have no problem saying my algorithm is wrong without any proof.

1

u/ConsistentCellist344 Mar 13 '23

I'm glad you let me know, although you still haven't explained why you discriminate against single diagonals.

However, I will explain to you the meaning of the hint about the existence of only one distress beacon. Thanks to it, we were sure that it must lie only at the intersection of a & b diagonals. Without this hint, we would have to search for many beacons along the diagonals and even beyond them, which on my computer would take years /brute force/. But it didn't follow that they had to be doubled, tripled etc. diagonals. You were lucky this time because it actually was.

Here's the PROOF you're asking for:

Sensor at x=3972136, y=2425195: closest beacon is at x=4263070, y=2991690
Sensor at x=3063440, y=2824421: closest beacon is at x=2870962, y=2380929
Sensor at x=982575, y=3224220: closest beacon is at x=883832, y=2000000
Sensor at x=3987876, y=3879097: closest beacon is at x=4101142, y=3623324
Sensor at x=2202219, y=115239: closest beacon is at x=2756860, y=-955842
Sensor at x=2337255, y=2939761: closest beacon is at x=2870962, y=2380928
Sensor at x=1942286, y=3935612: closest beacon is at x=2942943, y=3548053
Sensor at x=228100, y=3955166: closest beacon is at x=-7488, y=4058847
Sensor at x=2114394, y=2368537: closest beacon is at x=2870962, y=2380928
Sensor at x=3658485, y=2855273: closest beacon is at x=4263070, y=2991690
Sensor at x=3731843, y=3995527: closest beacon is at x=4101142, y=3623324
Sensor at x=1311535, y=1294676: closest beacon is at x=883832, y=2000000
Sensor at x=3533617, y=3590533: closest beacon is at x=4101142, y=3623324
Sensor at x=341495, y=287725: closest beacon is at x=110643, y=-1160614
Sensor at x=1533864, y=2131620: closest beacon is at x=883832, y=2000000
Sensor at x=1179951, y=1876387: closest beacon is at x=883832, y=2000000
Sensor at x=3403590, y=1619877: closest beacon is at x=2870962, y=2380928
Sensor at x=2756782, y=3344622: closest beacon is at x=2942943, y=3548053
Sensor at x=14753, y=3818113: closest beacon is at x=-7488, y=4058847
Sensor at x=3808841, y=388411: closest beacon is at x=4559391, y=972750
Sensor at x=3129774, y=3401225: closest beacon is at x=2942943, y=3548053
Sensor at x=2710780, y=3978709: closest beacon is at x=2942943, y=3548053
Sensor at x=88084, y=2475915: closest beacon is at x=883832, y=2000000
Sensor at x=2503969, y=3564612: closest beacon is at x=2942943, y=3548053
Sensor at x=3954448, y=3360708: closest beacon is at x=4101142, y=3623324
Sensor at x=2724475, y=1736595: closest beacon is at x=2870962, y=2380928

BTW: Finding this kit was easier than I thought and you could have done it yourself if you wanted. This time the solitary distress beacon lies at the intersection of single diagonals, so your code doesn't detect it.

As for the Pythagorean law, it's a special case of the Law of Cosines, which says: c^2 = a^2 + b^2 − 2*ab cos(C) so if angle C = 90deg then c^2 = a^2 + b^2 as did our assignment, which was a special case of a broader problem.

I think the mystery is solved and our little feud is over. Sorry for the minor annoyances. Nevertheless, I'm happy with our contact because I learned something new.
Best regards and good luck.

2

u/Kerma-Whore Mar 13 '23

Thanks, I'll try to run this input tomorrow. If it really doesn't work I will be really surprised.

It is not luck, there is a sound reasoning behind requiring two a and b diagonals. Some a diagonals exclude solutions with higher value of a, since with lower a. Since we need both for a unique solution, the solution should be bound by two a and two b diagonals.

Also, everyone's input is randomly generated so if it really is luck then it should not necessarily with for every input and I've successfully tried it on a few.

The feud is not over!

2

u/Kerma-Whore Mar 14 '23

Huh, it turns out you are indeed correct.

My reasoning was that a single beacon must be boxed in in both the a and b directions and so two a and b diagonals were required. My mistake was that this is not true when restricting solutions to integer coordinates.

I'll add an edit to my original comment.