That's the kind of code I'm aspiring to write :D
Still some distance away.
Great job!
Missatge de Raul Miller <rauldmil...@gmail.com> del dia dv., 16 de des.
2022 a les 2:47:
> 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
>
--
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
