#Day 15

171 messages · Page 1 of 1 (latest)

broken cloak
lime niche
#

12 minutes late

broken cloak
#

i was in the shower

lime niche
#

Sounds fake, nobody in discord.js showers

honest forge
lime niche
#

Reading the question while at the gym. I think I get it

#

No doubt I'll fuck up programming it though

#

I suspect this is another case where ||maintaining a set is more efficient than actually drawing the arrays||

broken cloak
#

nice top 1000 today

image.png
vapid gull
#

@broken cloak did you use linear equations for part 2

broken cloak
#

no

vapid gull
#

how did you solve it

broken cloak
#

||for each sensor, take the points at d(S, B) + 1 away and check if any are outside the range of all the sensors, if not repeat with d(S, B) + 2 etc||

#

by doing this, my p2 is actually magnitudes faster than p1 meguFace

vapid gull
#

for p1 i was contemplating using ranges and the inclusion-exclusion principle but i figured that i could just do all 2mil or so values

broken cloak
#

yea i just did all the coords

#

it takes a bit to finish but its quick enough

vapid gull
#

yeah exactly

#

i was just praying part 2 wouldnt be something like now find it for y=0..2000000

broken cloak
#

it kinda was meguFace

vapid gull
#

well its the inverse of it

#

cause who woulda guessed that exactly one spot is left open

broken cloak
#

well

#

it was the backstory from the start meguFace

#

but no one reads that

vapid gull
#

ah

#

i did not read that

#

you wanna hear my solution for p2

broken cloak
#

ye

vapid gull
#

||i created a bunch of linear equations for the manhattan distance perimeters (imagine a diamond shape) and i tested all the linear equations against each other to find intersects and for each intersect i looked above below left and right of that point and test it against all sensors||

broken cloak
#

wait im not following

#

||so you make a bunch of lines in ℝ², you check when any of those lines intersect?||

vapid gull
#

yea

broken cloak
#

and how does that get you to the one spot

vapid gull
#

and at each intersection i check the 4 points around them

#

because i figured that since theres only one point on the map that it must be adjacent to the intersection of two beacons' perimeters

broken cloak
#

doesnt that fail if say, the one point is actually in the corner?

vapid gull
#

probably

#

just add corner checks 4head

broken cloak
#

i dont know if this is rigorous

#

@gleaming pawn daaaang you were so close

image.png
#

wait i read it wrong

#

you actually did get first meguFace

gleaming pawn
#

ye

#

only #228 on p2 though

#

had a very minor bug that took me like 10 minutes to find

#

I probably could've had at least top 10 if not another #1/#1

broken cloak
#

howd you do p2

#

and did ya bruteforce p1 too

gleaming pawn
#

i brute forced p1 using a set of coordinates

#

even though I knew it wouldn't transfer to p2

#

basically, I just brute-forced each row

#

for each row, use interval math to find all possible positions and if there's exactly one then return it

broken cloak
#

ah gotcha

gleaming pawn
#

instead of actually representing all of the coordinates, since these are sparse intervals (few intervals, large range), you need to optimize by doing math on the intervals themselves

broken cloak
#

i like my clever solution pizzaCat

gleaming pawn
#

combining overlapping intervals is quite easy, you just need to ||sort them and then go through linearly|| and finding the lone point is also trivial ||just do a linear search but if you are in an interval, jump to just past it||

gleaming pawn
broken cloak
gleaming pawn
#

ooh

#

yeah that's smart

broken cloak
#

keeps the number of points low

gleaming pawn
#

I suppose ||starting with the largest S-B distance|| would be best to quickly eliminate a large area?

broken cloak
#

uhh

#

||its for each (S, B), take the points at d(S, B) + k||

#

i didnt sort it or anything

gleaming pawn
#

ohh

#

wait

#

I see

#

that makes sense I misunderstood the first time

broken cloak
#

dim did something crazy with lines

#

i dont think it even works in general but it worked

gleaming pawn
#

there's definitely some hyper-optimized way to do it by being smart I just can't be bothered lol

#

I imagine that sub-1s dart guy is gonna need to do that

vapid gull
#

I think my linear equation solution is the fastest

#

@broken cloak wait so if I understand correctly you're just going around each permiter

#

perimeter

broken cloak
#

yeah

vapid gull
#

oh I considered doing that at first but felt it was gonna be super slow

#

cause I looked at the distance of each beacon to scanner and it was in the hundreds of thousands

#

I may have the fastest solution

broken cloak
#

maybe

vapid gull
#

it runs in O(beacons^2)

broken cloak
gleaming pawn
#

ahh

broken cloak
#

though they wrote all the helper code in previous years meguFace

gleaming pawn
#

yeah figured something like that was possible, that's quite nice

lime niche
#

what the fuck

#

I get a result of ||4,229,192|| and I'm like lol okay I'll put it in anyway and its TOO LOW

broken cloak
#

yeah

lime niche
#

But I knew why

#

So onto part 2

broken cloak
#

have fun

lime niche
#

brute force

#

||I'm 100% certain there's much smarter ways to skip ahead based on knowing the distances||

broken cloak
#

youre checking every coord?

lime niche
#

Mostly to see if this works at all lol

#

Given that they tell us there is only one point not in range of any sensor, I assume the smart way to do this is to know that it's therefore ||exactly one unit of distance further away fron one of the sensors, so test those points?||

lime niche
#

YAY I DID IT

#

I remain on our leaderboard

#

Pretty happy with my progress given I don't code regularly or for a job

sharp zealot
#

for fucks sake... test runs through, real is too low nkoBreath

#

|| p1: is it not fair to assume that i only need to consider the min-max range of the X value of beacons? ||

lime niche
#

Uhh I'm not sure I understand the question but no I don't think thats correct

#

||The beacons don't have a range. All you know is the closest beacon to every sensor, and can calculate the distance||

sharp zealot
#

|| well, my idea is to go through the scan line and for each point check if the manhatten dist between that point and each scanner is leq manhatten from the point than it's assigned beacon + the point is not a beacon itself ||

lime niche
#

||Yes that's correct||

sharp zealot
#

that works for test input, but not for real angy

lime niche
#

Hmmmm

#

Oh now I understand you question

#

||Yes you only need to check that one line, incrementing on the x-axis||

sharp zealot
#

|| apparently my range of that is wrong with using min max X of beacons tho || at least for real vs. test

lime niche
#

The error I made on part 1 was ||not correctly accounting the limits for how far left and right you could potentially be from a beacon||

sharp zealot
#

|| StixilSigh so i need the leftmost and rightmost beacon and still add scanner dist || or some bs

lime niche
#

||Basically yeah. I did mix max of all provided coordinates, not just beacons, then added a max dist||

#

Sounds like the same error I had

sharp zealot
#

runtime do be abysmal tho

lime niche
#

Absolutely terrible lol

sharp zealot
#

ffs...

#

yeah, was that

sharp zealot
#

ok, that aint working for p2 firL 4mio x 4mio x 19 is apparently a lot

lime niche
#

yeah I had to readapt lol

pale nebula
#

Ouch, today I firstly got 4861077 and the answer was too high, so I fixed something and got 4861075... which was too low meguFace

fervent temple
#

lol, I did that too (different number though of course)

pale nebula
#

Now I'm struggling to understand what's the problem ahahah Nvm, it was quite easy actually

sharp zealot
#

oh wow, looking at the visualisation reddit, that's smart, that's so fuckin smart

warm delta
pale nebula
vapid hollow
#

I think I'm doing it wrong...

image.png
sharp zealot
#

sounds about right

#

(this is the point at which you rethink your approach)

lime niche
#

yee

vapid hollow
lime niche
#

Comp's spoilers further up tell you the better approach

vapid hollow
#

Yeah, saw it earlier, tried and... I'm running out of space in Map?
Basically I'm ||counting how many times outer edges of sensor range overlaps using Map<coordinates, count>||
||Till 7th sensor it's working, but on 8th I'm getting Value undefined out of range for undefined options property undefined||

#

||Wait, I'm not using condition with limited search space, hold on||

lime niche
#

||You need to find the coordinate where no sensor ranges overlap within 0,0 to 4000000,4000000||

#

||Since there is only one possible answer, you know that it must be exactly one unit of distance further away from a sensor than the distance recorded by that sensor||

vapid hollow
lime niche
#

The first part sounds right but I don't understand the ||most overlaps part||

vapid hollow
lime niche
#

||Purely hypothetically, the empty spot could be right in the corner of the square and not be next to the range of ANY other sensor. Nothing says its in the centre||

vapid hollow
#

...kurwa.
No idea then xd
Really wanted to finish it before day 16 arrives on aoc, but guess I won't make it

lime niche
#

Diagram to show what I mean

SPOILER_image.png
vapid hollow
#

Yeah yeah, I get it

lime niche
#

||There may be a more effective way, but for every point +1 dist from a sensor, I checked if it was in range of the regular recorded distance any other sensor. You could exit early as soon as it is in range of any of them||

vapid gull
#

there is a more efficient method

#

which is what i did

#

||since there is only one solution on the grid, you know that this solution is either in one of the four corners or just outside of the point where two scanners intersect||

#

||you can treat the four edges of the diamond that the manhattan distance creates as four separate lines (y=mx+b or whatever) and find the points of intersection of all the lines from different sensors||

#

||for every point of interest, look above, below, to the right and left of that point||

#

||and run the actual test to see if that coordinate is out of range of all beacons||

#

runs in O(beacons^3)

lime niche
#

ahh also very smart

sharp zealot
#

|| i also saw an intermediate to those, which i found smart as well - walk the peremiters of all the rectangles and check manhatten to the 19 scanners, as it is guaranteed to be on those walks and it reduces the search space immensely, finding the one no other scanners reach||

lime niche
#

Thats how I did it

regal prairie
#

my solution takes forever unless i run with optimizations lmao

#

then it takes four seconds which is still waful

#

im bashing through all 4000000 tho

broken cloak
regal prairie
broken cloak
#

you know ghci isnt just unoptimized, its interpreted bytecode meguFace

regal prairie
#

oops

broken cloak
#

its slower than unoptimized

regal prairie
#

ok that kinda makes sense

#

i was a bit confused about why it was not solving it