Here's a somewhat presentable implementation of part 2 for day 15.
it's a bit different from what I described in my previous email, but
most of the concepts are the same.
NUM=: '-',~.":i.10
parse=: 0 ". (#~ e.&NUM);._2
prep=: {{ 'S Be'=: _2 j./\ |: (\: 1{"1]) parse y }}
mhd=: +/@:|@+.@-
edge=: {{ |:(+/,-~/)@+. S(+,.-)j.D=:mhd/prep y }}
maybe=: {{~.(j.**&(=<.)**&(0&<)**&(x&>))/(-/,:&,+/)/-:1 _1+"2 y}}
filter=: {{ y #~ */D < S mhd/ y }}
B=: {{ 4e6#.<.+. filter x maybe edge y }}
timespacex'4e6 B input'
0.0143791 723680
'NUM' is characters which I care about: digits, space, the minus sign.
'parse' converts the text of the puzzle into a 4 column array of integers
'prep' further converts that into a row of sensor coordinates and a
row of beacon coordinates
'mhd' is manhattan distance
Note that I'm representing x,y coordinate pairs as x j. y complex
numbers, in 'prep', and I rely on this representation from there on
down.
-------------------
'edge' finds the y intercept of the bounding lines corresponding to
these sensor/beacon pairs. This array has three dimensions, and one
integer for each line.
The first dimension is indexed by _1^.slope of the bounding line. (In
other words 0 for slope of 1, 1 for slope of _1).
The second dimension is indexed by _1^.*y component of becon
coordinate - sensor coordinate. (In other words, 0 if the beacon y
coordinate is greater than the S y coordinate, _1 if it's less).
The final dimension corresponds to the sensor/beacon pair.
For example:
edge 'Sensor at x=2, y=0: closest beacon is at x=2, y=10;'
12
_8
8
_12
Here, the top two numbers have a positive slope (y increases with x),
and the bottom two numbers have a negative slope (y decreases when x
increases). The first number of each pair are offset from the sensor
in the same direction as the beacon. The second number of each pair is
offset in the opposite direction.
-------------------
'maybe' takes these lines and finds points that might be the result we
want based on where these lines intersect and which direction the
beacon is from the sensor. I add an offset to each y intercept based
on its direction from the corresponding sensor, then get potential x
coordinates (half of all positive slope values mine half of all
negative slope values) and the corresponding potential y coordinates
(average of those two values). (I factored out the divide by 2 to
happen all at once here).
Then I convert these coordinate pairs to complex, forcing obviously
invalid values (with non-integer coordinates or where they're outside
the search area) to zero, discarding duplicates. A lot of zeros get
discarded here (and the remaining zero will be discarded shortly).
-------------------
'filter' discards points which are too close to a sensor. It might be
slightly faster if I filtered the result down, one sensor at a time,
and I was going to do that (which is why I am assigning the
sensor-to-beacon distances to D in 'edge'). But this is probably fast
enough already...
And, finally, B assembles the result.
-------------------
There's a few problem specific quirks here -- for example, I rely on a
sensor never having a y coordinate which matches the y coordinate of a
beacon. I didn't encounter that issue, so I ignored it as a
possibility. So maybe the code itself doesn't entirely make sense. But
it was fairly straightforward to put together within these
constraints.
Anyways, ... maybe this will make sense to someone...
Thanks,
--
Raul
On Thu, Dec 15, 2022 at 3:51 PM Raul Miller <rauldmil...@gmail.com> wrote:
>
> 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
