I went one way ahead. Increased the range in 1, so the point would be on an
intersection, fewer points to check.
Ways one could check:
Go point by point, check if it's the good one.
Do something like in part 1, checking for an empty space checking line by
line.
Check the positions just beyond the range of all the sensors.
Check around the intersections of the scanning range of all the sensors.
(your suggestion)
Check the intersections of an extra range in all the sensors.
Find sensors with ranges r1 and r2 that are at a distance 1+r1+r2. The
point should be in the middle.
I implemented them all except the first, last (read about it afterwards)
and yours. I think they are (roughly) in the correct cpu burning level
(first the ones that require more computation).
I had the right point from my 2nd test, but I had a bad calculation.
Missatge de Raul Miller <rauldmil...@gmail.com> del dia dj., 15 de des.
2022 a les 19:04:
> I think your approach here, with a slight change, would be superior to
> the approach I used.
>
> In other words, treat the problem as defining a small set of lines
> bounding the scannable regions. These will all be diagonal lines,
> though they'll have two different orientations.
>
> The point you're looking for has to be adjacent to an intersection of
> two of those lines.
>
> --
> Raul
>
> On Thu, Dec 15, 2022 at 9:22 AM Jaume <greenni...@gmail.com> wrote:
> >
> > Hello all
> >
> > Once again with questions, now more on the performance side, mostly
> because
> > it's taking too long, and giving me a wrong answer some of the time.
> >
> > Talking about part 2. I'll share all of the code, so if you see anything
> > glaringly wrong please let me know.
> > read=:{{cutopen 1!:1 <y}}
> > filter=: 0". 'Sensoratx=,y:clbi'-.~]
> > init=: 3 : 0
> > map=:>filter each read y
> > sensors=:0 1 {"1 map
> > beacons=: 2 3{"1 map
> > $map
> > )
> > With init 'filename' we set up the rest.
> > In case you don't know we have to find the point thats outside the range
> of
> > all the sensors and still inside 0...4000000 in both coordinates.
> > Let's go to the last approach I took.
> > sol2=: 4 : 0
> > NB. range occ sensor,beacon
> > cx=:x
> > cy=:y
> > sensors= 0 1 {"1 y
> > beacons= 2 3 {"1 y
> > distances=:1+sensors d"1 beacons
> > param=:sensors,.((#distances), 1)$distances
> > digs=:x diag"1 param
> > dg=:digs
> > for_i. i.#digs do.
> > here=:testdiag dg
> > if. here do.
> > ccx=:{.here
> > ccy=:{:here
> > ccx,ccy,ccy+ccx*400000 return.
> > end.
> > dg=:}.dg
> > end.
> > 'none'
> > )
> > d=:[:+/[:|-
> > union=: ~.@,
> > unboxedunion=:([: > [) union [: > ]
> > intersect=: e. # [
> > remx=:([ >: [: {."1 ]) *. [ >: [: {:"1 ]
> > rem0=:(0 <: {."1) (*.) 0 <: {:"1
> > remove=: 4 : 0
> > mask=:rem0 y
> > mask=:mask*.x remx y
> > (>mask)#y
> > )
> > diag=: 4 : 0
> > cx=:x
> > cy=:y
> > range=:i.>:{:y NB. [2]->3->0 1 2
> > egnar=:i.->:{:y NB. [2]->-3->2 1 0
> > px=:0{y
> > py=:1{y
> > NB. (x-d,y)->(x,y+d)
> > NB. (x,y+d)->(x+d,y)
> > NB. (x+d,y)->(x,y-d)
> > NB. (x,y-d)->(x-d,y)
> > d1=:(px-egnar),.(py+range)
> > d2=:(px+range),.(py+egnar)
> > d3=:(px+egnar),.(py-range)
> > d4=:(px-range),.(py-egnar)
> > <~.x remove d1,d2,d3,d4
> > )
> > testpoint=: 3 : 0
> > dc=:1 y&d"1\sensors
> > *./dc>:distances
> > )
> > testdiag=: 3 : 0
> > excl=: }.y
> > rest=:]F.:unboxedunion excl
> > interest=:rest intersect > {.y
> > for_i. i.#interest do.
> > val=:testpoint i{interest
> > if.val do.
> > i{interest return.
> > end.
> > end.
> > 0
> > )
> >
> > So I create the limits that are just outside the range of each sensor,
> > intersect those, examine if the points have all the distances greater
> than
> > the distance each sensor reaches, and if so that's the point.
> > On the test it's blazingly fast:
> >
> > 20 sol2 map
> >
> > 14 11 5600011
> >
> > But on the real data it's amazingly slow... and according to AoC also
> wrong.
> >
> > 4000000 sol2 map
> >
> > 3270298 2638237 1308121838237 NB. too low!!!!
> > But.. AFAIK this answers checks the marks:
> >
> > |: dc
> >
> > 4298885 1215898 1684048 845656 3691920 1327934 1042406 682945 599242
> > 3471784 3639831 841599 1106070 4582032 3552311 2682122 967943 845585
> > 1809437 1835842 1806964 962164 663951 532696 2570491 706217 654163
> 1476664
> > 2198682 1669886 4144166 985137 1181113 4234...
> >
> > distances N.B. 1+ real distance
> >
> > 1595477 33564 434944 166994 803986 656108 285496 682945 599242 1465583
> > 700194 171415 143036 1694098 1742449 1433018 121373 226445 1150021 945766
> > 479064 383562 663951 429356 453359 185151 654163 455680 1350302 860094
> > 178581 92581 67993 126159 1178851 325282...
> >
> > |: dc>:distances
> >
> > 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 1 1
> > 1 1
> >
> >
> > So now I'm lost. I can't see the error and it's too slow to try new
> > alternatives.
> >
> >
> > I'm attaching my input, but do not give me the numeric answer please,
> that
> > would be trivial using any already working solution.
> >
> > Can you spot the error and or help me make this go faster?
> >
> > Thanks.
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
The fact that an opinion has been widely held is no evidence whatever that
it is not utterly absurd. -- Bertrand Russell
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
