I guess, if I were implementing what I think you are trying to
implement, I might do it like this:
move_table=: <:(,|."1)(#~0<*/"1)~.,/,/_3&{.\@/:~"1(,|:"2)>|:((;|.)@(1++)+/)\i.5
flip=: ~: (i.15)&e.
legal_moves=: [ #~ 6 = 2 #. {
search=:3 :0
((15#1) flip y) search i.0 3
NB. x: board; y: moves
:
if. 1=+/x do. y return. end.
for_move. move_table legal_moves x do.
r=.(x flip move) search move,y
if. #r do. r return. end.
end.
i.0 3
)
solitaire=:3 :0
path=. search y
if. #path do. path else. 'No solution' end.
)
A few notes:
* This only returns one solution and many are possible. If I wanted
that to be randomized, I'd change the for line to read:
for_move. ({~ ?~@#) move_table legal_moves x do.
* Alternatively, if I did not do that, it might make sense to sort
legal_moves (legal_moves=: /:~legal_moves).
* I am not bothering to create explicit stack data structures, since
that seems unnecessary for this problem: I'm using J's call stack for
that purpose.
* I put the initial stage of the recursive case in search, since I
felt that documenting the calling pattern belonged there.
I hope this helps,
--
Raul
On Mon, Jun 5, 2017 at 7:08 AM, Michael Rice <[email protected]> wrote:
> 2) Is the move list associated with each board
> 3) Is the move path, also a list, you want returned (printed?) if you reach
> a winning board state, i.e., just one peg remaining on the board.
>
>
>
>
>
> On Mon, Jun 5, 2017 at 2:18 AM, Raul Miller <[email protected]> wrote:
>
>> What is the difference between 2 (a list of moves for the current
>> board) and 3 (a path list for the solution, initially empty) in this
>> description?
>>
>> Thanks,
>>
>> --
>> Raul
>>
>>
>> On Mon, Jun 5, 2017 at 12:39 AM, Michael Rice <[email protected]> wrote:
>> > The gap between J and most computer languages is pretty wide.
>> >
>> > Maybe this will help.
>> >
>> > The board, a noun, is represented by a 15 element binary array with 1s
>> for
>> > full positions and 0s for empty ones. It is initially all 1s. Id, a noun,
>> > is a 15x15 identity matrix.
>> >
>> > Function flip, given a board and position(s) that are to be flipped,
>> i.e.,
>> > not-ed, returns a new updated board with the position(s) not-ed. It first
>> > checks the size (#) of positions. If there's only one, it pulls the row
>> > with that position number from id, xors (:~) it with the board, and
>> returns
>> > the result. If there is more than one position, all the rows of id for
>> > those positions are first or-ed together, that result xor-ed with the
>> > board, and the result returned.
>> >
>> > There's to be a monadic function, solitaire, that initiates the search.
>> >
>> > solitaire 5 - begin the search with position 5 empty.
>> >
>> > There's also to be a function search, called by solitaire, with a single
>> > parameter, a list of
>> > 1) the current board
>> > 2) a list of moves for the current board
>> > 3) a path list for the solution, initially empty
>> > 4) a history stack (for back-tracking) composed of past boards and their
>> > lists of moves not yet explored, initially empty
>> >
>> > Recursive function search (depth first) always moves the move at the head
>> > of its given move list and saves the rest of the moves and the board
>> > associated with them in the history stack. When the search reaches a
>> board
>> > with no moves and just one peg remaining on the board, it prints the
>> > solution path. Otherwise it back-tracks to the last board and its
>> > associated list of remaining moves and moves the next move on the list.
>> If
>> > it reaches a state where there are no moves in its given move list and an
>> > empty history, "No solution" is printed.
>> >
>> > On Sun, Jun 4, 2017 at 11:45 AM, bill lam <[email protected]> wrote:
>> >
>> >> I have difficulty in reading your code, perhaps you want to
>> >> make everything looks functional. To that end, you may
>> >> replace the if/then with @. (agenda)
>> >> (+./ @: ({ & id))`({ & id)@.((< & 2) @: #)
>> >>
>> >> (untested and not sure if this is a simplication)
>> >>
>> >> Вс, 04 июн 2017, Michael Rice написал(а):
>> >> > Two things come to mind: 1) *reductio ad absurdum* and 2) a Dustin
>> >> Hoffman
>> >> > film, wherein he says to a man, "I going to explain something so
>> you'll
>> >> > understand it!" and then shoots him.
>> >> >
>> >> > I already had a function that does what I needed (see below) but was
>> >> musing
>> >> > about left/right parameter style, when one of the parameters remains
>> >> > constant and the other changes "functionally" in the program.
>> >> >
>> >> > Just looking at your first "simplification," I can see I have a lot of
>> >> > familiarization work to do. For example, what's the difference between
>> >> >
>> >> > 2 3 <@, 3 4 and 1 2 <@:, 3 4
>> >> >
>> >> > when the result is the same?
>> >> >
>> >> > Must be something subtle.
>> >> >
>> >> > =================
>> >> >
>> >> > Note: The moves marked with "<-" are moves to a known solution.
>> >> >
>> >> >
>> >> > NB. 15 position peg solitaire
>> >> > NB. The board (position 5 initially vacant)
>> >> >
>> >> > NB. 0
>> >> > NB. 1 2
>> >> > NB. 3 4 5
>> >> > NB. 6 7 8 9
>> >> > NB. 10 11 12 13 14
>> >> >
>> >> > move_table =: 36 3 $ 0 2 5 5 2 0 0 1 3 3 1 0 1 3 6 6 3 1 1 4 8 8 4
>> 1
>> >> 2 4
>> >> > 7 7 4 2 2 5 9 9 5 2 3 6 10 10 6 3 3 7 12 12 7 3 3 4 5 5 4 3 4 7 11 11
>> 7
>> >> 4 4
>> >> > 8 13 13 8 4 5 8 12 12 8 5 5 9 14 14 9 5 6 7 8 8 7 6 7 8 9 9 8 7 10 11
>> 12
>> >> 12
>> >> > 11 10 11 12 13 13 12 11 12 13 14 14 13 12
>> >> > id =: e. i. 15
>> >> > flip =: (~: 3 : 'if. ((< & 2) @: #) y do. ({ & id) y else. (+./ @:
>> ({
>> >> &
>> >> > id)) y end. ')
>> >> > legal_moves =: (#~ ((-: & 1 1 0)"1 @: ({~ & move_table)))
>> >> > board =: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
>> >> > board
>> >> > 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
>> >> > board =: board flip 5
>> >> > board
>> >> > 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 0 2 5 <-
>> >> > 3 4 5
>> >> > 12 8 5
>> >> > 14 9 5
>> >> > board =: board flip 0 2 5
>> >> > board
>> >> > 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 3 1 0 <-
>> >> > 7 4 2
>> >> > 9 5 2
>> >> > board =: board flip 3 1 0
>> >> > board
>> >> > 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 8 4 1
>> >> > 7 4 2
>> >> > 9 5 2
>> >> > 10 6 3
>> >> > 12 7 3
>> >> > 5 4 3 <-
>> >> > board =: board flip 5 4 3
>> >> > board
>> >> > 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 6 3 1 <-
>> >> > 11 7 4
>> >> > 13 8 4
>> >> > 12 8 5
>> >> > 14 9 5
>> >> > board =: board flip 6 3 1
>> >> > board
>> >> > 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 0 1 3 <-
>> >> > 12 7 3
>> >> > 11 7 4
>> >> > 13 8 4
>> >> > 12 8 5
>> >> > 14 9 5
>> >> > 8 7 6
>> >> > board =: board flip 0 1 3
>> >> > board
>> >> > 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1
>> >> > move_table legal_moves board
>> >> > 11 7 4 <-
>> >> > 13 8 4
>> >> > 12 8 5
>> >> > 14 9 5
>> >> > 8 7 6
>> >> > board =: board flip 11 7 4
>> >> > board
>> >> > 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1
>> >> > move_table legal_moves board
>> >> > 8 4 1
>> >> > 3 4 5 <-
>> >> > 12 8 5
>> >> > 14 9 5
>> >> > 9 8 7
>> >> > 13 12 11
>> >> > board =: board flip 3 4 5
>> >> > board
>> >> > 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1
>> >> > move_table legal_moves board
>> >> > 9 5 2 <-
>> >> > 13 8 4
>> >> > 9 8 7
>> >> > 13 12 11
>> >> > board =: board flip 9 5 2
>> >> > board
>> >> > 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1
>> >> > move_table legal_moves board
>> >> > 13 8 4
>> >> > 12 8 5
>> >> > 13 12 11 <-
>> >> > board =: board flip 13 12 11
>> >> > board
>> >> > 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1
>> >> > move_table legal_moves board
>> >> > 10 11 12 <-
>> >> > board =: board flip 10 11 12
>> >> > board
>> >> > 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1
>> >> > move_table legal_moves board
>> >> > 12 8 5 <-
>> >> > board =: board flip 12 8 5
>> >> > board
>> >> > 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1
>> >> > move_table legal_moves board
>> >> > 5 2 0
>> >> > 2 5 9 <-
>> >> > board =: board flip 2 5 9
>> >> > board
>> >> > 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
>> >> > move_table legal_moves board
>> >> > 14 9 5 <-
>> >> > board =: board flip 14 9 5
>> >> > board
>> >> > 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
>> >> > move_table legal_moves board
>> >> >
>> >> >
>> >> >
>> >> >
>> >> > On Sun, Jun 4, 2017 at 10:03 AM, Raul Miller <[email protected]>
>> >> wrote:
>> >> >
>> >> > > Like this?
>> >> > >
>> >> > > (#~ 5=2#.@:|])z
>> >> > > 3 4 5
>> >> > >
>> >> > > --
>> >> > > Raul
>> >> > >
>> >> > >
>> >> > > On Sun, Jun 4, 2017 at 9:43 AM, Michael Rice <[email protected]>
>> >> wrote:
>> >> > > > How about
>> >> > > > 1 0 1 0 1 0 (#~ ((-: & 0 1 0)"1 @: ({~ & z)))~ z
>> >> > > > ?
>> >> > > >
>> >> > > > Odd, that's the KISS way, the way that always works, and the one
>> way
>> >> I
>> >> > > > hadn't considered.
>> >> > > >
>> >> > > > On to your "simplifications."
>> >> > > >
>> >> > > > On Sat, Jun 3, 2017 at 10:16 PM, Louis de Forcrand <
>> [email protected]
>> >> >
>> >> > > wrote:
>> >> > > >
>> >> > > >> How about
>> >> > > >> 1 0 1 0 1 0 (#~ ((-: & 0 1 0)"1 @: ({~ & z)))~ z
>> >> > > >> ?
>> >> > > >> You can then "simplify":
>> >> > > >>
>> >> > > >> First the hook (and {~&z)
>> >> > > >> ([ #~ -:&0 1 0"1@:(z&{)@])~
>> >> > > >> ([ #~ -:&0 1 0"1@:(z&{)@])~
>> >> > > >>
>> >> > > >> Then ~ can be "distributed" over the resulting fork:
>> >> > > >> [~ #~ -:&0 1 0"1@:(z&{)@(]~)
>> >> > > >> ] #~ -:&0 1 0"1@:(z&{)@[
>> >> > > >>
>> >> > > >> You can keep going;
>> >> > > >> From bonding to forks:
>> >> > > >> ] #~ (] -: 0 1 0"_)"1@:(z { ])@[
>> >> > > >> Composition and -: commutativity:
>> >> > > >> ] #~ (0 1 0 -: ])"1@:(z { ]@[)
>> >> > > >> Because 1=#$0 1 0:
>> >> > > >> ] #~ (0 1 0 -:"1 ])@:(z { [)
>> >> > > >> Trains:
>> >> > > >> ] #~ (0 1 0 -:"1 ]@:(z { [))
>> >> > > >> ] #~ 0 1 0 -:"1 ]@:(z { ])
>> >> > > >> ] #~ 0 1 0 -:"1 z { [
>> >> > > >>
>> >> > > >> Can't get it any simpler.
>> >> > > >>
>> >> > > >> Cheers,
>> >> > > >> Louis
>> >> > > >>
>> >> > > >> > On 4 Jun 2017, at 03:45, Michael Rice <[email protected]>
>> >> wrote:
>> >> > > >> >
>> >> > > >> > z (#~ ((-: & 0 1 0)"1 @: ({~ & z))) 1 0 1 0 1 0
>> >> > > >>
>> >> > > >> ------------------------------------------------------------
>> >> ----------
>> >> > > >> For information about J forums see http://www.jsoftware.com/
>> >> forums.htm
>> >> > > >>
>> >> > > > ------------------------------------------------------------
>> >> ----------
>> >> > > > For information about J forums see http://www.jsoftware.com/
>> >> forums.htm
>> >> > > ------------------------------------------------------------
>> ----------
>> >> > > For information about J forums see http://www.jsoftware.com/
>> forums.htm
>> >> > >
>> >> > ------------------------------------------------------------
>> ----------
>> >> > For information about J forums see http://www.jsoftware.com/
>> forums.htm
>> >>
>> >> --
>> >> regards,
>> >> ====================================================
>> >> GPG key 1024D/4434BAB3 2008-08-24
>> >> gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3
>> >> gpg --keyserver subkeys.pgp.net --armor --export 4434BAB3
>> >> ----------------------------------------------------------------------
>> >> For information about J forums see http://www.jsoftware.com/forums.htm
>> >>
>> > ----------------------------------------------------------------------
>> > For information about J forums see http://www.jsoftware.com/forums.htm
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
