Yes, after I sent that suggestion, I realized that I could do a better
job of describing the approach.
So, I sat down and implemented the thing that way.
My implementation could do with some code cleanup, but as it stands
now, it looks like this performance wise:
timespacex '4e6 B input'
0.0232526 1883360
This was on a 1.2GHz laptop.
A rough outline of the code is this:
(1) Parse the raw text into numbers (four numbers per line), and sort
them (descending order by sensor y value to simplify finding candidate
points).
(I then combine them in pairs as complex numbers, and work with
coordinates in x j. y format.)
(2) Find the boundary edges, represent this as a three-column table
slope (1 or _1), y direction from sensor (1 or _1), y intercept
(3) Find a list of candidate points to consider:
(a) add the y direction to the y intercept to get a y offset
immediately outside the sensor's range
(b) find an intersection point for every pair of edges (difference
of y offsets for x average of y offsets for y)
There will be duplication here, so toss the duplicates.
(4) Filter these candidate
(a) discard any candidates with an x or y which is negative
(b) discard any candidates with an x or y which is too large
(c) project each candidate to the y axis using a positive or negative slope
(d) discard any candidate whose positive slope intercept is larger
than the smallest positive slope y intercept for any edge
(e) discard any candidate whose negative slope intercept is smaller
than the largest negative slope y intercept for any edge
And then: find the Manhattan distance from each remaining candidate to
each sensor and discard those which are too close to any sensor
Then convert the coordinate to the required index value.
So, B looked like:
B=: {{4e6 #.<.+. (x filter candidates) edges y}}
('filter' was an adverb with x, m and y as parameters.)
FYI,
--
Raul
On Thu, Dec 15, 2022 at 1:28 PM Jaume <greenni...@gmail.com> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
