Challenge by Roger Hui, Wed Feb 3 12:04:30 HKT 2010.
As an simple test, try writing ktourw in
http://www.jsoftware.com/jwiki/Essays/Knight's_Tour#Warnsdorff
without control structures, then compare the result with ktourw.
if. becomes args u ^: test moreArgs
for. --> args&u \ changingArgs
I've written a depth first search, similar to ktour in the essay with
recursion instead of an explicit stack, without precomputed move
table. I've attempted to reuse storage according to Modification In
Place of jforc/modifying_an_array_m.htm.
Starting with the code below, I eliminate the for loop by replacing
for_newposition. position+"_ 1 offsets
do.
Block
end.
with
_3 (boxed;arg;list)&block \ ,position+"_ 1 offsets
Resulting program page faults madly which I can stop only because
I use nice j.
Given the function warnsdorff that counts how many available spaces
there are from each of the implied positions without control
structures, and if the page faults hadn't occurred, I'd insert
Warnsdorff's Algorithm by again changing the for loop to:
_3 (boxed;arg;list)&body \ , (/: board&warnsdorff) position+"_ 1
offsets
Observations:
o I haven't yet won the challenge.
o My pseudo-code plan contained control structures.
o printThenHalt is abrupt. I could catcht
or return the result back to main routine.
o KT 7 NB. takes about 5 seconds to answer. Dreadfully slow as is.
o Would you expect the huge memory use because of the
"slight code change" that I haven't included in detail?
KT =: 3 : 0 NB. Main routine, use: KT n
position =. 0 2 2 NB. Attempt to Reuse memory
level =. 1
board =. (,@Board $~ *: , 4 4&+) y NB. allocation
board =. level (<position) } board
knightTour board; position; level; y
'No solution'
)
Board =: [: -&1...@%@+:/~2|.(4#1)&,@#&0
increments =: 8 2 $ 2 _1 1 _2 _1 _2 _2 _1 _2 1 _1 2 1 2 2 1
typoTests =: 3 : 0
assert. (=/~i.8) -: =y NB. (i.8)(=@:[ -: =@:])increments
assert. 1 2 = /:~ ~.,|y
'pass'
)
typoTests increments
printThenHalt =: 3 : 0
(printThenHalt~ -&4...@#){:y
:
echo 'solution!'
echo _1+(<;~2+i.x){y
throw.
)
offsets =: 1,.increments
knightTour =: 3 : 0 NB. reuse memory
'board position level n' =. y
printThenHalt^:(level = *:n)board
level =. >:level
for_newposition. position+"_ 1 offsets
do.
if.
0 = board {~ <newposition-1 0 0
do.
board =. (({.position){board) ({.newposition)}board
board =. level (<newposition)}board
knightTour board;newposition;level;n
end.
end.
)
KT 5
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
