On 5/25/07, Terrence Brannon <[EMAIL PROTECTED]> wrote:
Dont give up Raul.
What, am I the only person who can solve this?
Anyways, I sat down and worked through a simple approach.
Unfortunately, a 32 bit system can't handle it:
board=:10 10{.10 11$1 0
coords=:10 10#:I.,board
dirs=:0 2,1 1,1 _1,0 _2,_1 _1,:_1 1
adj=:coords e.&:(<"1)~ coords+"1/ dirs
NB.piecedelta=:0 2 3|:(0,+/\)"2 dirs{~6|(,-)(i.6)+/0,.|:".;._2]0 :0
piecedelta=:(0,+/\)"2 dirs{~0 2|:6|(,-)(i.6)+/0,.|:".;._2]0 :0
0 1 0 0 5 0 1 2 0 0
0 2 1 2 0 2 1 1 5 0
1 1 2 1 4 0 5 0 0 2 NB. replace last of 4 with middle of 1
)
piecedelta=: ((<4;a:;4)}~ (<1;a:;2){]) piecedelta
viable=: piecedelta (<@:+"1/ (*./"[EMAIL PROTECTED]) <"[EMAIL PROTECTED]) coords
pieces=:<@;"1 (i.10),"1&.>viable <@#"_2]2 4|:piecedelta +"1/ coords
boards=:([: (#~ (# = [EMAIL PROTECTED])"2@:(}."1)) ,/@:(,"2/))&.>/pieces
This gives me a limit error. And, if I replace that final pieces with
pieces {L:0 a. (to use less storage), I run out of memory. Both of
these happen when I try and combine 3 pieces.
So, since a 32 bit system can't approach this in a fully parallel
fashion, I'm going to need to partition the solution space.
I've been playing with partitinoning, and so far my approaches have
been much too slow.
Oh, I've also been a bit more selective about what I consider valid
representations for pieces. Basically, my code after piecedelta=:
currently looks like:(beware line wrap)
plausible=: piecedelta (<@:+"1/ (*./"[EMAIL PROTECTED]) <"[EMAIL PROTECTED])
coords
pieces=:a.{~L:0;<@;"1 (i.10)(,10#.])"1&.>plausible <@#"_2]2
4|:piecedelta +"1/ coords
permitting=:4 :0
keep=.y
xP=.{:"1 x
for_need.~.,{:"1 x do.
kP=.{:"1 keep
needy=.*./"1 kP [EMAIL PROTECTED] need
provide=.+./"1 xP e. need
bad=. *./"1 +./"1 (needy#kP) e."1/ provide#xP
keep=. keep #~ -. needy expand bad
end.
keep
)
pieces=:permitting~pieces
psel=: ([EMAIL PROTECTED]"2 </. [EMAIL PROTECTED]) pieces
NB. boards=:([: (#~ (# = [EMAIL PROTECTED])"1@:({:"1)) ,/@:(,"2/))&.>/pieces
comb2=:[: (#~ (# = [EMAIL PROTECTED])"1@:({:"1)) ,/@:(,"2/)
combine=:4 :0
if.x>:#psel do.y return.end.
r=.0 5 2$''
next=.x+1
blocks=:3333 (]-~/\"1@:<. [:(}:,. }.) 0+/\@, [#~ >[EMAIL PROTECTED]) #y
allow=.(pieces{~;psel}.~1+next)&permitting
for_block. blocks do.
r=.r,allow next combine (pieces{~psel{::~x) comb2 y{~(+i.)/block
end.
r
)
board=:a.i.L:0]1 combine pieces{~psel{::~0
But this is still far, far too slow to work.
I think I need better ways to prune my searches.
For example, if I could figure out how to do it quickly, I'd
flood fill starting at a random board position and count the
number of cells filled -- discarding boards with something
other than a multiple of 5.
Unfortunately, I don't know how to quickly flood fill even a
rectangular board, let alone one represented like this
one.
Anyways, currently, I'm stuck.
And, if you have any suggestions I'm all ears.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
