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
