Anonymous user
Morpion solitaire: Difference between revisions
→{{header|J}}
m (Install J initial solution) |
|||
Line 291:
=={{header|J}}==
With this program as the file m.ijs
<lang J>
NB. turn will be a verb with GRID as y, returning GRID. Therefor:
NB. morpion is move to the power of infinity---convergence.
morpion =: turn ^: _
NB. Detail:
NB. bitwise manipulation definitions for bit masks.
bit_and =: 2b10001 b.
bit_or =: 2b10111 b.
assert 0 0 0 1 -: 0 0 1 1 bit_and 0 1 0 1
assert 0 1 1 1 -: 0 0 1 1 bit_or 0 1 0 1
diagonal =: (<i.2)&|: NB. verb to extract the major diagonal of a matrix.
assert 0 3 -: diagonal i. 2 2
NB. choose to pack bits into groups of 3. 3 bits can store 0 through 5.
MASKS =: 'MARKED M000 M045 M090 M135'
(MASKS) =: 2b111 * 2b1000 ^ i. # ;: MASKS
bit_to_set =: 2&}.&.#:
MARK =: bit_to_set MARKED
GREEK_CROSS =: MARK * 10 10 $ 'x' = LF -.~ 0 :0
xxxx
x x
x x
xxxx xxxx
x x
x x
xxxx xxxx
x x
x x
xxxx
)
NB. frame pads the marked edges of the GRID
frame_top =: 0&,^:(0 ~: +/@:{.)
frame_bot =: frame_top&.:|.
frame_lef=:frame_top&.:|:
frame_rig=: frame_bot&.:|:
frame =: frame_top@:frame_bot@:frame_lef@:frame_rig
assert (-: frame) 1 1 $ 0
assert (3 3 $ 9 {. _5 {. 1) (-: frame) 1 1 $ 1
odometer =: (4 $. $.)@:($&1) NB. http://www.jsoftware.com/jwiki/Essays/Odometer
index_matrix =: ($ <"1@:odometer)@:$ NB. the computations work with indexes
assert (1 1 ($ <) 0 0) (-: index_matrix) (i. 1 1)
Note 'adverb Line'
m is the directional bit mask.
produces the bitmask with a list of index vectors to make a new line.
use Line: (1,:1 5) M000 Line ;._3 index_matrix GRID
Line is a Boolean take of the result.
Cuts apply Line to each group of 5.
However I did not figure out how to make this work without a global variable.
)
NB. the middle 3 are not
NB. used in this direction and 4 are already marked
Line =: 1 :'((((0 = m bit_and +/@:}.@:}:) *. (4 = MARKED bit_and +/))@:,@:({&GRID))y){.<(bit_to_set m)(;,)y'
l000 =: (1,:1 5)&(M000 Line;._3)
l045 =: (1,:5 5) M045 Line@:diagonal;._3 |.
l090 =: (1,:5 1)&(M090 Line;._3)
l135 =: (1,:5 5)&(M135 Line@:diagonal;._3)
compute_marks =: (l135 , l090 , l045 , l000)@:index_matrix NB. compute_marks GRID
choose_randomly =: {~ ?@:#
apply =: (({~ }.)~ bit_or (MARK bit_or 0&{::@:[))`(}.@:[)`]}
save =: 4 : '(x) =: y'
move =: (apply~ 'CHOICE' save choose_randomly)~
turn =: 3 : 0
TURN =: >: TURN
FI =. GRID =: frame y
MOVES =: _6[\;compute_marks GRID
GRID =: MOVES move :: ] GRID
if. TURN e. OUTPUT do.
smoutput (":TURN),' TURN {'
smoutput ' choose among' ; < MOVES
smoutput ' selected' ; CHOICE
smoutput ' framed input & ouput' ; FI ; GRID
smoutput '}'
end.
GRID
)
NB. argument y is a vector of TURN numbers to report detailed output.
play =: 3 : 0
OUTPUT =: y
RANDOM_STATE =: '(9!:42 ; 9!:44 ; 9!:0)' ; (9!:42 ; 9!:44 ; 9!:0)''
if. 0 < # OUTPUT do.
smoutput 'line angle bit keys for MARK 000 045 090 135: ',":bit_to_set"0 MARKED,M000,M045,M090,M135
smoutput 'RANDOM_STATE begins as' ; RANDOM_STATE
end.
NB. save the random state to replay a fantastic game.
TURN =: _1 NB. count the number of plays. Convergence requires 1 extra attempt.
GRID =: morpion GREEK_CROSS NB. play the game
TURN
)
NB. example
smoutput play''
</lang>
load the file into a j session to play an initial game and report the number of turns. We can play a game providing a vector of move numbers at which to report the output.
<pre>
load'/tmp/m.ijs'
60
play 3
line angle bit keys for MARK 000 045 090 135: 1 8 64 512 4096
┌──────────────────────┬──────────────────────┬─┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│RANDOM_STATE begins as│(9!:42 ; 9!:44 ; 9!:0)│2│┌─┬──┬─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
│ │ │ ││2│73│_1823777002250993298 _6838471509779976446 _8601563932981981704 _9084675764771521463 _513205540226054792 8272574653743672083 _9008275520901665952 542248839568947423 _149618965119662441 _7363052629138270...
│ │ │ │└─┴──┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
└──────────────────────┴──────────────────────┴─┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────...
3 TURN {
┌──────────────┬───────────────────────────────┐
│ choose among│┌────┬────┬────┬────┬────┬────┐│
│ ││4096│1 6 │2 7 │3 8 │4 9 │5 10││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││4096│3 7 │4 8 │5 9 │6 10│7 11││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││4096│6 1 │7 2 │8 3 │9 4 │10 5││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││4096│7 3 │8 4 │9 5 │10 6│11 7││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │0 4 │1 4 │2 4 │3 4 │4 4 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │0 7 │1 7 │2 7 │3 7 │4 7 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │1 4 │2 4 │3 4 │4 4 │5 4 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │1 7 │2 7 │3 7 │4 7 │5 7 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │3 1 │4 1 │5 1 │6 1 │7 1 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │3 10│4 10│5 10│6 10│7 10││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │4 1 │5 1 │6 1 │7 1 │8 1 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │4 10│5 10│6 10│7 10│8 10││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │6 4 │7 4 │8 4 │9 4 │10 4││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││512 │7 4 │8 4 │9 4 │10 4│11 4││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││64 │10 6│9 7 │8 8 │7 9 │6 10││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││64 │5 1 │4 2 │3 3 │2 4 │1 5 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │1 3 │1 4 │1 5 │1 6 │1 7 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │1 4 │1 5 │1 6 │1 7 │1 8 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │4 0 │4 1 │4 2 │4 3 │4 4 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │4 1 │4 2 │4 3 │4 4 │4 5 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │4 6 │4 7 │4 8 │4 9 │4 10││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │4 7 │4 8 │4 9 │4 10│4 11││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │7 0 │7 1 │7 2 │7 3 │7 4 ││
│ │├────┼────┼────┼────┼────┼────┤│
│ ││8 │7 1 │7 2 │7 3 │7 4 │7 5 ││
│ │└────┴────┴────┴────┴────┴────┘│
└──────────────┴───────────────────────────────┘
┌──────────┬───┬───┬───┬───┬───┬───┐
│ selected│512│1 4│2 4│3 4│4 4│5 4│
└──────────┴───┴───┴───┴───┴───┴───┘
┌──────────────────────┬───────────────────────────┬─────────────────────────────┐
│ framed input & ouput│0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0 0 0 0 0 0│
│ │0 0 0 0 1 1 1 1 0 0 0 0 0│0 0 0 0 513 1 1 1 0 0 0 0 0│
│ │0 0 0 0 1 0 0 1 0 0 0 0 0│0 0 0 0 513 0 0 1 0 0 0 0 0│
│ │0 0 0 0 1 0 0 1 0 0 0 0 0│0 0 0 0 513 0 0 1 0 0 0 0 0│
│ │0 1 1 1 1 0 0 1 1 1 1 0 0│0 1 1 1 513 0 0 1 1 1 1 0 0│
│ │0 1 0 0 0 0 0 0 0 0 1 0 0│0 1 0 0 513 0 0 0 0 0 1 0 0│
│ │0 1 0 0 0 0 0 0 0 0 1 0 0│0 1 0 0 0 0 0 0 0 0 1 0 0│
│ │0 1 1 1 1 0 0 521 9 9 9 9 0│0 1 1 1 1 0 0 521 9 9 9 9 0│
│ │0 0 0 0 1 0 0 513 0 0 0 0 0│0 0 0 0 1 0 0 513 0 0 0 0 0│
│ │0 0 0 0 1 0 0 513 0 0 0 0 0│0 0 0 0 1 0 0 513 0 0 0 0 0│
│ │0 0 0 0 9 9 9 521 9 0 0 0 0│0 0 0 0 9 9 9 521 9 0 0 0 0│
│ │0 0 0 0 0 0 0 513 0 0 0 0 0│0 0 0 0 0 0 0 513 0 0 0 0 0│
│ │0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0 0 0 0 0 0│
└──────────────────────┴───────────────────────────┴─────────────────────────────┘
}
62
</pre>
Explanation.
load'/tmp/m.ijs' Load the file played an initial game. This one played 60 moves.
play 3 Shows the state of the random generator at the start of the game, and then information about turn 3.
The pseudo-random generator can be reconstructed from information in the RANDOM_STATE variable, hence one can replay with full output superior games.
Curly braces enclose output pertaining to the (index origin 0) turn.
<pre>3 TURN {
...
}
</pre>
A list of the possible moves follows, along with the selection. Let's decode the selected move.
Given the key from first output line the move 512 is a 90 degree (vertical) line. The list of index origin 0 row column coordinates indeed shows 5 constant column with sequential rows. From the framed input and output grids shown, near the top of the fifth column, the 1 1 1 1 0 became 513 513 513 513 513. 513 is the number corresponding to one bits of MARK and 90 degrees. On a prior move, the 521's shows that thes marked points were used for 0 and 90 degree lines, included in the (difficult to see) 9's and 513's in proper direction. The final 62 shows the length of the game. Display the value of final grid with the sentence GRID . GRID is a pronoun.
<pre>
line angle bit keys for MARK 000 045 090 135: 1 8 64 512 4096
┌──────────┬───┬───┬───┬───┬───┬───┐
│ selected│512│1 4│2 4│3 4│4 4│5 4│
└──────────┴───┴───┴───┴───┴───┴───┘
┌──────────────────────┬───────────────────────────┬─────────────────────────────┐
│ framed input & ouput│0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0 0 0 0 0 0│
│ │0 0 0 0 1 1 1 1 0 0 0 0 0│0 0 0 0 513 1 1 1 0 0 0 0 0│
│ │0 0 0 0 1 0 0 1 0 0 0 0 0│0 0 0 0 513 0 0 1 0 0 0 0 0│
│ │0 0 0 0 1 0 0 1 0 0 0 0 0│0 0 0 0 513 0 0 1 0 0 0 0 0│
│ │0 1 1 1 1 0 0 1 1 1 1 0 0│0 1 1 1 513 0 0 1 1 1 1 0 0│
│ │0 1 0 0 0 0 0 0 0 0 1 0 0│0 1 0 0 513 0 0 0 0 0 1 0 0│
│ │0 1 0 0 0 0 0 0 0 0 1 0 0│0 1 0 0 0 0 0 0 0 0 1 0 0│
│ │0 1 1 1 1 0 0 521 9 9 9 9 0│0 1 1 1 1 0 0 521 9 9 9 9 0│
│ │0 0 0 0 1 0 0 513 0 0 0 0 0│0 0 0 0 1 0 0 513 0 0 0 0 0│
│ │0 0 0 0 1 0 0 513 0 0 0 0 0│0 0 0 0 1 0 0 513 0 0 0 0 0│
│ │0 0 0 0 9 9 9 521 9 0 0 0 0│0 0 0 0 9 9 9 521 9 0 0 0 0│
│ │0 0 0 0 0 0 0 513 0 0 0 0 0│0 0 0 0 0 0 0 513 0 0 0 0 0│
│ │0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0 0 0 0 0 0│
└──────────────────────┴───────────────────────────┴─────────────────────────────┘
}
</pre>
| |||