In my experience, if you are forced to use depth-first search in J, you
will not get good results. Languages which are efficient at manipulating
tiny amount of data always do better. If you have the memory,
breadth-first search can be stated simply in J in terms of the power
conjunction.
Here's a solution which does not satisfy the rules of the contest (you are
supposed to use their algorithm) and is not very fast, but is is my
opinion a more natural solution in J. You start with all the
permutations, throw away those that begin with 1, and then do one shift on
the remainder. Repeat until done, counting how many iterations you need.
If I knew how to find the first k such that (u^:k)-:(u^:_), I could do
this more efficiently.
perm=: [: >:[EMAIL PROTECTED] A. i.
head=: {. {. ]
tail=: ] {.~ {. - #
shift=:(|.@:head,tail)"1 f.
cut=: #~(1<{."1)
next=: [EMAIL PROTECTED]
run=:13 :'_2+#next&.>^:(<_) <perm y'
run 10
38
Unlike the other solutions on the Shootout web site, this can be done in
one line:
run f.
_2 + [: # [: (|.@:({. {. ]) , ] {.~ {. - #)"1@(#~ (1 < {."1))&.>^:(<_) [:
< [: >: [EMAIL PROTECTED] A. i.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
