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
