Raul's code works fine until you try applying it to a "sparse" array.
This is the result of his transitive closure applied to the adjacency
matrix
for the example provided, the one with 7 nodes and 2 connected groups:
tc adjex12
1 0 1 1 1 1 1
0 1 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
1 0 1 1 1 1 1
... so it has "many" 1s cf "few" 0s, so it's hardly sparse in 1,
though it
is quite sparse in 0 !
FWIW, my loopy code working on a boxed list of bnodes works fine here.
Not elegant like the tc approach, which my boss showed me years ago in APL,
but gets the job donefor the 2000-node problem:
NB. example provided
ex12 =: ';'cut '0 <-> 2;1 <-> 1;2 <-> 0, 3, 4;3 <-> 2, 4;4 <-> 2, 3, 6;5
<-> 6;6 <-> 4, 5'
makelinks =: (".@:;@{:@:('>'&cut)) each
load'files'
input12 =: LF cut CR -.~ f =: fread '~user/aoc2017.12.txt'
NB. solve part 1
group =: 3 : 0
0 group makelinks y NB. default input is boxed input lines with CR removed
:
g =. y NB. graph is right arg for dyadic form
s =. ,x NB. origin node
next =. ,1
while. #next do.
s =. s, next =. s -.~ ~.; s { g
end.
s
)
NB. solve part 2
ngroups=: 3 : 0
g =. makelinks y
list =. i.#y NB. origin nodes to do
n =. 0 NB. initialis required count
while. #list do.
NB. could remove visited nodes from graph but fast enough as is !!!
gr =. ({.list) group g NB. apply dyadic form of part 1's verb
list =. list -. gr NB. this group's members can't be origin nodes
n =. >: n
end.
n
)
Better than problem 11, anyway!
Mike
On 13/12/2017 04:40, Jimmy Gauvin wrote:
HI all,
this AOC challenge is great for trying out J cool features, like sparse
arrays which I haven't used to date.
For part 1 I decided to try transitive closure on a sparse matrix.
Initializing the sparse array went ok but the transitive closure produced a
big bang and J just died on me, 8-(
So I went for a brute force approach : visiting all predecessors to node.
d12=: <&;:;.(_2) 1!:1 <'/day12inp'
d12c=:".&; each 4}. each d12
nodto =: 3 : 0
~. y , ; y { d12c
)
$nodto ^:_ (0)
169
There must be a nicer way to write this code.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
