Morpion solitaire: Difference between revisions
mNo edit summary |
(→{{header|Wren}}: Minor tidy and fixed problem with 'mvprintw' now requiring a format specifier.) |
||
(10 intermediate revisions by 8 users not shown) | |||
Line 12: | Line 12: | ||
There are several variations of the game, this task deals with the 5 point "touching" version also known as "5T". |
There are several variations of the game, this task deals with the 5 point "touching" version also known as "5T". |
||
Morpion solitaire is played on a (theoretically) infinite grid. It begins with 36 points marked in a Greek cross: |
|||
<pre> |
<pre> |
||
...XXXX... |
...XXXX... |
||
Line 56: | Line 56: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Console play with ncurses. Length and touching rules can be changed at the begining of source code. 'q' key to quit, space key to toggle auto move, anykey for next move. Play is random. I got nowhere near the record 177 moves, but did approach the worst-possible (20) quite often. |
Console play with ncurses. Length and touching rules can be changed at the begining of source code. 'q' key to quit, space key to toggle auto move, anykey for next move. Play is random. I got nowhere near the record 177 moves, but did approach the worst-possible (20) quite often. |
||
< |
<syntaxhighlight lang="c">#include <ncurses.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <unistd.h> |
#include <unistd.h> |
||
Line 280: | Line 280: | ||
endwin(); |
endwin(); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{libheader|goncurses}} |
{{libheader|goncurses}} |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 552: | Line 552: | ||
gc.CBreak(false) |
gc.CBreak(false) |
||
gc.Echo(true) |
gc.Echo(true) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Line 563: | Line 563: | ||
=={{header|J}}== |
=={{header|J}}== |
||
With this program as the file m.ijs |
With this program as the file m.ijs |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
NB. turn will be a verb with GRID as y, returning GRID. Therefor: |
NB. turn will be a verb with GRID as y, returning GRID. Therefor: |
||
NB. morpion is move to the power of infinity---convergence. |
NB. morpion is move to the power of infinity---convergence. |
||
Line 671: | Line 671: | ||
NB. example |
NB. example |
||
smoutput play'' |
smoutput play'' |
||
</syntaxhighlight> |
|||
</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. |
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> |
<pre> |
||
Line 803: | Line 803: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
See:[[Morpion solitaire/Julia]] |
See:[[Morpion solitaire/Julia]] |
||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
{{libheader|nim-ncurses}} |
|||
<syntaxhighlight lang="nim">import os, random, sequtils |
|||
import ncurses |
|||
const |
|||
LineLength = 5 |
|||
Disjoint = 0 |
|||
type |
|||
State {.pure.} = enum Blank, Occupied, DirNS, DirEW, DirNESW, DirNWSE, NewlyAdded, Current |
|||
States = set[State] |
|||
Board = seq[seq[States]] |
|||
Move = tuple[m, s, seqnum, x, y: int] |
|||
const Ofs = [(0, 1, DirNS), (1, 0, DirEW), (1, -1, DirNESW), (1, 1, DirNWSE)] |
|||
func set(board: var Board; value: State; x0, y0, x1, y1: int) = |
|||
for i in y0..y1: |
|||
for j in x0..x1: |
|||
board[i][j] = {value} |
|||
func initBoard(): Board = |
|||
let height, width = 3 * (LineLength - 1) |
|||
result = newSeqWith(height, newSeq[States](width)) |
|||
result.set(Occupied, LineLength - 1, 1, 2 * LineLength - 3, height - 2) |
|||
result.set(Occupied, 1, LineLength - 1, width - 2, 2 * LineLength - 3) |
|||
result.set(Blank, LineLength, 2, 2 * LineLength - 4, height - 3) |
|||
result.set(Blank, 2, LineLength, width - 3, 2 * LineLength - 4) |
|||
func expand(board: var Board; dw, dh: int) = |
|||
# -1: expand low index end, +1: expand high index end. |
|||
let |
|||
height = board.len |
|||
width = board[0].len |
|||
nw = width + ord(dw != 0) |
|||
nh = height + ord(dh != 0) |
|||
var nboard = newSeqWith(nh, newSeq[States](nw)) |
|||
let dw = -ord(dw < 0) |
|||
let dh = -ord(dh < 0) |
|||
for i in 0..<nh: |
|||
if i + dh notin 0..<height: continue |
|||
for j in 0..<nw: |
|||
if j + dw notin 0..<width: continue |
|||
nboard[i][j] = board[i + dh][j + dw] |
|||
board = move(nboard) |
|||
proc show(board: Board) = |
|||
for i, row in board: |
|||
for j, cell in row: |
|||
let str = if Current in cell: "X " |
|||
elif NewlyAdded in cell: "0 " |
|||
elif Occupied in cell: "+ " |
|||
else: " " |
|||
mvprintw(cint(i + 1), cint(j + 2), str) |
|||
refresh() |
|||
proc testPosition(board: Board; y, x: int; rec: var Move) = |
|||
let height = board.len |
|||
let width = board[0].len |
|||
if Occupied in board[y][x]: return |
|||
for m, (dx, dy, dir) in Ofs: # 4 directions. |
|||
for s in (1 - LineLength)..0: # offset line. |
|||
var k = -1 |
|||
while k < LineLength: |
|||
inc k |
|||
if s + k == 0: continue |
|||
let xx = x + dx * (s + k) |
|||
let yy = y + dy * (s + k) |
|||
if xx < 0 or xx >= width or yy < 0 or yy >= height: break |
|||
if Occupied notin board[yy][xx]: break # No piece at position. |
|||
if dir in board[yy][xx]: break # This direction taken. |
|||
if k != LineLength: continue |
|||
# Position ok. |
|||
# Rand to even each option chance of being picked. |
|||
if rand(rec.seqnum) == 0: |
|||
rec.m = m; rec.s = s; rec.x = x; rec.y = y |
|||
inc rec.seqnum |
|||
proc addPiece(board: var Board; rec: Move) = |
|||
let (dx, dy, dir) = Ofs[rec.m] |
|||
board[rec.y][rec.x] = board[rec.y][rec.x] + {Current, Occupied} |
|||
for k in 0..<LineLength: |
|||
let xx = rec.x + dx * (k + rec.s) |
|||
let yy = rec.y + dy * (k + rec.s) |
|||
board[yy][xx].incl NewlyAdded |
|||
if k >= Disjoint or k < LineLength - Disjoint: |
|||
board[yy][xx].incl dir |
|||
proc nextMove(board: var Board): bool {.discardable.} = |
|||
var rec: Move |
|||
let maxi = board.high |
|||
let maxj = board[0].high |
|||
# Wipe last iteration new line markers. |
|||
for row in board.mitems: |
|||
for cell in row.mitems: |
|||
cell = cell - {NewlyAdded, Current} |
|||
# Randomly pick one of next legal move. |
|||
for i in 0..maxi: |
|||
for j in 0..maxj: |
|||
board.testPosition(i, j, rec) |
|||
# Didn't find any move, game over. |
|||
if rec.seqnum == 0: return false |
|||
board.addPiece(rec) |
|||
rec.x = if rec.x == maxj: 1 |
|||
elif rec.x != 0: 0 |
|||
else: -1 |
|||
rec.y = if rec.y == maxi: 1 |
|||
elif rec.y != 0: 0 |
|||
else: -1 |
|||
if rec.x != 0 or rec.y != 0: board.expand(rec.x, rec.y) |
|||
result = true |
|||
proc play() = |
|||
randomize() |
|||
var board = initBoard() |
|||
var waitKey = true |
|||
let win {.used.} = initscr() |
|||
noecho() |
|||
cbreak() |
|||
var move = 0 |
|||
while true: |
|||
mvprintw(0, 0, "Move %d", move) |
|||
inc move |
|||
board.show() |
|||
if not board.nextMove(): |
|||
board.nextMove() |
|||
board.show() |
|||
break |
|||
if not waitKey: sleep(100) |
|||
let ch = getch() |
|||
if ch == ord(' '): |
|||
waitKey = not waitKey |
|||
if waitKey: timeout(-1) |
|||
else: timeout(0) |
|||
elif ch == ord('q'): |
|||
break |
|||
timeout(-1) |
|||
getch() |
|||
nocbreak() |
|||
onecho() |
|||
endwin() |
|||
play()</syntaxhighlight> |
|||
{{out}} |
|||
Intermediate state: |
|||
<pre>Move 20 |
|||
+ |
|||
+++++ |
|||
+ ++ |
|||
+ ++ ++ + |
|||
+++++ +0+++ |
|||
+ + 0 + |
|||
+ + X + |
|||
++++0+++++ |
|||
+0 ++ |
|||
++ + |
|||
+++++ |
|||
+ |
|||
</pre> |
|||
=={{header|Perl}}== |
|||
Picks a move at random from all possible moves at each step. A sample game is shown. |
|||
The largest score found so far (from just random play) is 92, also shown below. |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use List::Util qw( none ); |
|||
local $_ = <<END; |
|||
.............XXXX............. |
|||
.............X..X............. |
|||
.............X..X............. |
|||
..........XXXX..XXXX.......... |
|||
..........X........X.......... |
|||
..........X........X.......... |
|||
..........XXXX..XXXX.......... |
|||
.............X..X............. |
|||
.............X..X............. |
|||
.............XXXX............. |
|||
END |
|||
$_ = tr/X/ /r . $_ . tr/X/ /r; # expand to 30x30 |
|||
tr/./ /; # and convert dots to spaces |
|||
my @moves; |
|||
my %used; |
|||
my $count = 0; |
|||
while( 1 ) |
|||
{ |
|||
# print s/\A(?: +\n)*|(?:^ +\n)*\z//gmr, "count $count\n"; # uncomment for each step |
|||
tr/O/X/; |
|||
my @try; # find valid moves |
|||
for my $i ( 0, 29 .. 31 ) |
|||
{ |
|||
my $gap = qr/.{$i}/s; |
|||
while( / (?=$gap(X)$gap(X)$gap(X)$gap(X))/g ) # add to top |
|||
{ |
|||
my $cand = join ' ', map $-[$_], 0 .. 4; |
|||
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand; |
|||
} |
|||
while( /X(?=$gap(.)$gap(.)$gap(.)$gap(.))/g ) # add inside/bottom downward |
|||
{ |
|||
"$1$2$3$4" =~ tr/X// == 3 or next; |
|||
my $cand = join ' ', map $-[$_], 0 .. 4; |
|||
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand; |
|||
} |
|||
} |
|||
@try ? $count++ : last; |
|||
my $pick = $try[rand @try]; #pick one valid move |
|||
push @moves, $pick; |
|||
for my $pos (split ' ', $pick) |
|||
{ |
|||
substr $_, $pos, 1, 'O'; |
|||
} |
|||
$used{$1} = 1 while $pick =~ /(?=\b(\d+ \d+)\b)/g; |
|||
} |
|||
print join(' ', map s/ .* /->/r =~ s!\d+! ($& % 31).','.int $& / 31 !ger, @moves) |
|||
=~ s/.{60}\K /\n/gr, "\n"; |
|||
tr/O/X/; |
|||
print $_, "move count: $count\n";</syntaxhighlight> |
|||
This runs on a 30x30 grid (as advised by Talk page). |
|||
Each move is shown as the end points of a line, startcolumn,startrow->endcolumn,endrow where row and column numbers |
|||
are zero-based. To replay a game, just add all five points from each line to the grid. The final grid is also shown in full. |
|||
Uncommenting the early print will show each step with the latest line added as the 'O' character. |
|||
{{out}} |
|||
<pre> |
|||
10,15->14,19 13,16->13,20 10,13->10,17 15,16->19,16 15,10->19,14 |
|||
12,10->16,10 19,12->19,16 16,16->16,20 9,16->13,16 12,16->16,20 |
|||
16,13->20,13 10,13->14,13 13,9->13,13 16,9->16,13 16,9->12,13 |
|||
13,19->17,19 14,10->10,14 19,15->15,19 20,13->16,17 13,9->17,13 |
|||
13,11->17,11 |
|||
X X |
|||
XXXXX |
|||
XXXXX |
|||
XX XX X |
|||
XXXXX XXXXX |
|||
X X |
|||
X XX |
|||
XXXXX XXXXX |
|||
X XX XX |
|||
XX X |
|||
XXXXX |
|||
X X |
|||
move count: 21 |
|||
</pre> |
|||
<pre> |
|||
13,16->13,20 16,15->16,19 15,10->19,14 16,13->20,13 10,16->14,16 |
|||
13,10->17,10 12,19->16,19 10,15->14,19 14,10->10,14 10,13->14,13 |
|||
15,16->19,16 19,13->19,17 16,15->12,19 17,16->13,20 10,13->10,17 |
|||
13,16->17,20 10,17->14,17 19,15->15,19 16,11->16,15 17,13->13,17 |
|||
13,9->13,13 13,9->17,13 15,15->15,19 14,17->18,17 14,13->18,17 |
|||
13,13->17,17 14,13->14,17 15,14->11,18 9,16->13,20 13,12->9,16 |
|||
11,14->11,18 12,13->16,17 12,14->16,14 14,13->10,17 13,13->9,17 |
|||
9,12->13,16 11,15->15,19 10,15->14,15 12,14->12,18 13,18->17,18 |
|||
10,12->14,16 9,15->13,19 15,13->11,17 9,12->13,12 15,11->15,15 |
|||
20,15->16,19 17,16->17,20 15,13->19,17 14,15->18,15 16,16->12,20 |
|||
17,12->17,16 13,12->17,12 18,9->14,13 13,10->17,14 12,11->16,11 |
|||
17,9->13,13 14,16->18,20 18,13->18,17 14,9->10,13 16,14->20,14 |
|||
21,12->17,16 12,10->12,14 11,9->15,13 14,8->14,12 14,8->10,12 |
|||
11,10->11,14 10,9->14,13 10,9->14,9 20,12->16,16 20,11->20,15 |
|||
20,11->16,15 17,12->21,12 16,10->20,14 17,8->17,12 17,8->21,12 |
|||
19,10->15,14 17,8->13,12 18,9->18,13 19,9->15,13 19,9->19,13 |
|||
15,9->19,9 17,11->21,11 15,8->19,12 16,8->20,12 13,8->17,8 13,8->9,12 l |
|||
15,7->15,11 10,9->10,13 16,7->16,11 9,10->13,10 9,9->13,13 8,9->12,13 |
|||
XX |
|||
XXXXX |
|||
XXXXXXXXXXXX |
|||
XXXXXXXXXXX |
|||
XXXXXXXXXXXX |
|||
XXXXXXXXXXXXX |
|||
XXXXXXXXXXX |
|||
XXXXXXXXXXX |
|||
XXXXXXXXXXXX |
|||
XXXXXXXXXXX |
|||
XXXXXXXXXXX |
|||
XXXXXXX |
|||
XXXXXX |
|||
XX XX |
|||
move count: 92 |
|||
</pre> |
|||
A faster, shorter version without the single step display. |
|||
Uses the same kind of block shift/or technology I used in "Forest fire" and have used |
|||
for Conway's Life. |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use feature 'bitwise'; |
|||
use List::Util 'none'; |
|||
local $_ = <<END; |
|||
.............XXXX............. |
|||
.............X..X............. |
|||
.............X..X............. |
|||
..........XXXX..XXXX.......... |
|||
..........X........X.......... |
|||
..........X........X.......... |
|||
..........XXXX..XXXX.......... |
|||
.............X..X............. |
|||
.............X..X............. |
|||
.............XXXX............. |
|||
END |
|||
$_ = tr/X./ /r . tr/./ /r . tr/X./ /r; # expand to 30x30 and spaces |
|||
my($count, @moves, %used) = 0; |
|||
while( 1 ) |
|||
{ |
|||
my @try; # valid moves |
|||
for my $i ( 1, 30 .. 32 ) # directions 1 - 30 / 31 | 32 \ |
|||
{ |
|||
my $combined = tr/X \n/A\0/r |. |
|||
(substr $_, $i) =~ tr/X \n/B\0/r |. |
|||
(substr $_, 2 * $i) =~ tr/X \n/D\0/r |. |
|||
(substr $_, 3 * $i) =~ tr/X \n/H\0/r |. |
|||
(substr $_, 4 * $i) =~ tr/X \n/P\0/r; |
|||
while( $combined =~ /[OW\[\]\^]/g ) # exactly four Xs and one space |
|||
{ |
|||
my $cand = join ' ', map $-[0] + $_ * $i, 0 .. 4; |
|||
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand; |
|||
} |
|||
} |
|||
@try ? $count++ : last; |
|||
my $pick = $try[rand @try]; #pick one valid move |
|||
push @moves, $pick; |
|||
for my $pos (split ' ', $pick) |
|||
{ |
|||
substr $_, $pos, 1, 'X'; |
|||
} |
|||
@used{ $pick =~ /(?=\b(\d+ \d+)\b)/g } = (1) x 4; |
|||
} |
|||
print join(' ', map s/ .* /->/r =~ s!\d+! ($& % 31).','.int $& / 31 !ger, |
|||
@moves) =~ s/.{60}\K /\n/gr, "\n"; |
|||
print $_, "move count: $count\n";</syntaxhighlight> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 809: | Line 1,201: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(module rules racket/base |
(module rules racket/base |
||
(require racket/match) |
(require racket/match) |
||
Line 909: | Line 1,301: | ||
p |
p |
||
(define bmp (pict->bitmap p)) |
(define bmp (pict->bitmap p)) |
||
(send bmp save-file "images/morpion.png" 'png))</ |
(send bmp save-file "images/morpion.png" 'png))</syntaxhighlight> |
||
'''Intermission:''' The <code>render</code> submodule just does drawing, and is not part of the solving. But the <code>main</code> module uses it, so we put it in here: |
'''Intermission:''' The <code>render</code> submodule just does drawing, and is not part of the solving. But the <code>main</code> module uses it, so we put it in here: |
||
< |
<syntaxhighlight lang="racket">(module render racket |
||
(require racket/match |
(require racket/match |
||
racket/draw |
racket/draw |
||
Line 1,013: | Line 1,405: | ||
[(hash-has-key? p# k) #\.] |
[(hash-has-key? p# k) #\.] |
||
[else #\space]))) |
[else #\space]))) |
||
(printf "~s~%~a points ~a lines~%" l (hash-count p#) (length l))))</ |
(printf "~s~%~a points ~a lines~%" l (hash-count p#) (length l))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,045: | Line 1,437: | ||
<br>This program allows the <tt> D </tt> or <tt> T </tt> forms of the game, and allows any board size (grid size) of three or higher. |
<br>This program allows the <tt> D </tt> or <tt> T </tt> forms of the game, and allows any board size (grid size) of three or higher. |
||
<br>The default games is <tt> 5T </tt> |
<br>The default games is <tt> 5T </tt> |
||
<syntaxhighlight lang="rexx">/*REXX program plays Morpion solitaire (with grid output), the default is the 5T version*/ |
|||
signal on syntax; signal on noValue /*handle possible REXX program errors. */ |
|||
/* [↓] handle the user options (if any)*/ |
|||
prompt= /*null string is used for ERR return.*/ |
|||
quiet= 0 /*flag: suppresses output temporarily.*/ |
|||
oFID= 'MORPION' /*filename of the game's output file. */ |
|||
arg game player seed . /*see if a person wants to play. */ |
|||
if game=='' | game=="," then game= '5T' /*Not specified? Then use the default.*/ |
|||
if player=='' | player=="," then player= /* " " " " " " */ |
|||
if isInt(seed) then call random ,,seed /*Is integer? Then use for RANDOM seed*/ |
|||
TorD= 'T (touching) ───or─── D (disjoint).' /*the valid game types (T or D). */ |
|||
sw= linesize() - 1 /*SW = screen width ─or─ linesize. */ |
|||
gT= right(game, 1) /*T = touching ─or─ D = disjoint.*/ |
|||
if \datatype(gT,'U') | verify(gT, "GT")\==0 then call err 'game not G or T' /*error?*/ |
|||
gS= left( game, length(game) - 1) /*gS=Game Size (line length for a win)*/ |
|||
if \isInt(gS) then call err "game size isn't an integer:" gS /*error?*/ |
|||
gS= gS / 1 /*normalize the value of GS. */ |
|||
if gS<3 then call err "grid size is too small for Morpion solitaire :" gS /*error? */ |
|||
/*handle the defaults/configuration. */ |
|||
indent= left('', max(0, sw - gS - 10) % 2) /*indentation used for board display. */ |
|||
indent= ' ' |
|||
empty= 'fa'x /*the empty grid point symbol (glyph). */ |
|||
@.= empty /*the field (grid) is infinite in size*/ |
|||
CBLF= player \== '' /*playing with a carbon─based lifeform?*/ |
|||
if CBLF then oFID= player /*oFID: the fileID for the game LOG. */ |
|||
oFID= oFID'.LOG' /*full name for the LOG's filename. */ |
|||
prompt= 'enter X,Y point and an optional character for placing on board (or Quit):' |
|||
prompt= right(prompt, sw, '─') /*right justify the prompt message. */ |
|||
call GreekX /*draw the (initial) Greek cross. */ |
|||
do #=1 for 1500 /*───play a game of Morpion solitaire. */ |
|||
<lang rexx>/*REXX program to play Morpion solitaire, the default is the 5T version.*/ |
|||
if CBLF then do |
|||
signal on syntax; signal on novalue /*handle REXX program errors. */ |
|||
if Gshots\=='' then do; parse var Gshots shot Gshots |
|||
quiet=0; oFID='MORPION' |
|||
parse var shot gx ',' gy |
|||
call mark gx,gy |
|||
if game=='' | game==',' then game='5T' /*Not specified? Then use default*/ |
|||
iterate |
|||
end |
|||
TorD='T (touching) ───or─── D (disjoint).' /*valid games types (T | D).*/ |
|||
if Gshots=='' then leave /*#*/ |
|||
call t prompt; pull stuff; stuff= translate(stuff, , ',') |
|||
if \datatype(gT,'U') | verify(gT,gT)\==0 then call err 'game gT not' gT |
|||
stuff= space(stuff); parse var stuff px py p |
|||
gS=left(game,length(game)-1) /*gS=Game Size (line len for win)*/ |
|||
_= px; upper _; if abbrev('QUIT', _, 1) then exit /*quitting? */ |
|||
if \datatype(gS,'W') then call err "game size isn't numeric:" gS |
|||
if stuff=='' then do; call display; iterate |
|||
gS=gS/1 |
|||
end |
|||
if gS<3 then call err "grid size is too small:" gS |
|||
call mark px,py,p |
|||
sw=linesize()-1 |
|||
end /*if CBLF*/ |
|||
indent=left('',max(0,sw-gS-10)%2) /*indentation used board display.*/ |
|||
else do; quiet= 1; shot= translate( word(Gshots, turn), , ',') |
|||
if shot=='' then do 50 |
|||
xr= loX -1 + random(0, hiX - loX + 2) |
|||
yr= loY -1 + random(0, hiY - loY + 2) |
|||
if @.xr.yr\==empty then iterate |
|||
if \neighbor(xr, yr) then iterate |
|||
shot= xr yr |
|||
prompt='enter X,Y point and an optional character for placing on board', |
|||
end /*50*/ |
|||
'(or Quit):'; prompt=right(prompt,sw,'─') /*right justify it.*/ |
|||
call mark word(shot, 1), word(shot, 2) |
|||
call GreekCross |
|||
end /*else*/ |
|||
jshots=Gshots |
|||
end /*#*/ |
|||
do turns=1 for 1000 |
|||
if CBLF then do |
|||
call t prompt; pull stuff; stuff=translate(stuff,,',') |
|||
parse var stuff px py p |
|||
_=px; upper _; if abbrev('QUIT',_,1) then exit |
|||
if stuff=='' then do; call display; iterate; end |
|||
call mark px,py |
|||
end /*if CBLF*/ |
|||
else do; quiet=1 |
|||
shot=translate(word(Gshots,turn),,',') |
|||
if shot=='' then do 50 |
|||
xr=loX-1+random(0,hiX-loX+2) |
|||
yr=loY-1+random(0,hiY-loY+2) |
|||
if @.xr.yr\==empty then iterate |
|||
if \neighbor(xr,yr) then iterate |
|||
shot=xr yr |
|||
end |
|||
call mark word(shot,1),word(shot,2) |
|||
end |
|||
end /*turns*/ |
|||
call t '* number of wins =' wins |
|||
exit wins /*stick a fork in it, we're done.*/ |
|||
/*───────────────────────────────error handling subroutines and others.─*/ |
|||
err: if \quiet then do; call t; call t |
|||
call t center(' error! ',max(40,linesize()%2),"*"); call t |
|||
do j=1 for arg(); call t arg(j); call t; end; call t |
|||
end |
|||
if prompt=='' then exit 13; return |
|||
novalue: syntax: prompt=; quiet=0 |
|||
call err 'REXX program' condition('C') "error",, |
|||
condition('D'),'REXX source statement (line' sigl"):",, |
|||
sourceline(sigl) |
|||
t: say arg(1); call lineout oFID,arg(1); return |
|||
Gshot: Gshots=Gshots arg(1)','arg(2); return |
|||
tranGC: if gC=='' then return arg(1); return translate(arg(1),copies(gC,12),'┌┐└┘│─╔╗╚╝║═') |
|||
/*─────────────────────────────────────GREEKCROSS subroutine────────────*/ |
|||
GreekCross: wins=0; loX=-1; hiX=0; LB=gS-1 /*Low Bar*/ |
|||
lintel=LB-2; turn=1; loY=-1; hiY=0; ht=4+3*(LB-2) /*─ ─ */ |
|||
Gshots=; nook=gS-2; Hnook=ht-nook+1; TB=ht-LB+1 /*Top Bar*/ |
|||
/*─ ─ */ |
|||
do y=1 for ht; _top='╔'copies('═',lintel)'╗' ; _top=tranGC(_top) |
|||
_bot='╚'copies('═',lintel)'╝' ; _bot=tranGC(_bot) |
|||
_hib='╔'copies('═',lintel)'╝'left('',lintel)'╚'copies('═',lintel)'╗' ; _hib=tranGC(_hib) |
|||
_lob='╚'copies('═',lintel)'╗'left('',lintel)'╔'copies('═',lintel)'╝' ; _lob=tranGC(_lob) |
|||
_sid='║' ; _sid=tranGC(_sid) |
|||
select |
|||
when y==1 then do x=1 for LB; call place x+LB-1,y,substr(_bot,x,1); end |
|||
when y==ht then do x=1 for LB; call place x+LB-1,y,substr(_top,x,1); end |
|||
when y==LB then do x=1 for ht; if x>LB & x<TB then iterate; call place x,y,substr(_lob,x,1); end |
|||
when y==TB then do x=1 for ht; if x>LB & x<TB then iterate; call place x,y,substr(_hib,x,1); end |
|||
when y>LB & y<TB then do x=1 by ht-1 for 2; call place x,y,_sid; end |
|||
otherwise do x=LB by TB-LB for 2; call place x,y,_sid; end |
|||
end /*select*/ |
|||
end /*y*/ |
|||
@abc='abcdefghijklmnopqrstuvwxyz'; @chars='0123456789'translate(@abc)||@abc |
|||
@chars=@chars'()[]{}<>«»' /*can't contain "empty", ?, blank*/ |
|||
call display |
call display |
||
call t '* number of wins =' wins |
|||
call Gshot nook , nook ; call Gshot nook , Hnook |
|||
exit wins /*stick a fork in it, we're all done. */ |
|||
call Gshot Hnook , nook ; call Gshot Hnook , Hnook |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
call Gshot gS , LB ; call Gshot gS , TB |
|||
Gshot: if arg()==2 then Gshots= space(Gshots arg(1)','arg(2) ); return |
|||
call Gshot ht-LB , LB ; call Gshot ht-LB , TB |
|||
isInt: return datatype( arg(1), 'W') /*is int? */ |
|||
isNum: return datatype( arg(1), 'N') /*is num? */ |
|||
t: say arg(1); call lineout oFID,arg(1); return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
call Gshot TB+1 , 1 ; call Gshot TB+1 , ht |
|||
?win: arg z; L= length(z) |
|||
return |
|||
if L>gS then do; if gT=='D' then return 0 /*longlines ¬ kosker for D*/ |
|||
/*─────────────────────────────────────DISPLAY subroutine───────────────*/ |
|||
parse var z z1 '?' z2 /*could be xxxxx?xxxx */ |
|||
display: call t; do y=hiY to loY by -1; _=indent /*start at a high Y.*/ |
|||
return length(z1)>=4 | length(z2)>=4 |
|||
end |
|||
return L==gS |
|||
if !==empty then do /*grid transformation*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
if xo then !='|' |
|||
display: call t; do y=hiY to loY by -1; _c= /*start at a high Y. */ |
|||
do x=loX to hiX; != @.x.y; _c= _c || ! /*build an "X" grid line. */ |
|||
end /*x*/ |
|||
call t indent _c /*display a grid line. */ |
|||
end /*y*/ |
|||
if xo & yo then !='┼' |
|||
end |
|||
_=_ || ! |
|||
end /*x*/ |
|||
call t _ /*...and display it.*/ |
|||
end /*y*/ |
|||
if wins==0 then call t copies('═',sw) |
if wins==0 then call t copies('═', sw) |
||
else call t right(' |
else call t right('(above) the board after' wins "turns.", sw, '═') |
||
call t |
call t |
||
return |
return |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*─────────────────────────────────────PLACE subroutine─────────────────*/ |
|||
err: if \quiet then do; call t; call t |
|||
place: parse arg xxp,yyp /*place a marker (point) on grid.*/ |
|||
call t center(' error ', max(40, sw % 2), "*"); call t |
|||
loX=min(loX,xxp); hiX=max(hiX,xxp) |
|||
do j=1 for arg(); call t arg(j); call t; end; call t |
|||
loY=min(loY,yyp); hiY=max(hiY,yyp); @.xxp.yyp=arg(3) |
|||
end |
|||
return |
|||
if prompt=='' then exit 13; return |
|||
/*─────────────────────────────────────MARK subroutine──────────────────*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
mark: parse arg xx,yy,pointChar /*place marker, check for errors.*/ |
|||
GreekX: wins= 0; loX= 1; hiX= 0; LB= gS - 1 /*Low cross Beam. */ |
|||
if pointChar=='' then pointChar=word(substr(@chars,turn,1) '+',1) |
|||
turn= 1; loY= 1; hiY= 0; HT= 4 + 3*(LB-2) /*─ ─ */ |
|||
xxcyy=xx','yy; _.1=xx; _.2=yy |
|||
Lintel= LB - 2; Gshots=; TB= HT - LB + 1 /*Top cross Beam. */ |
|||
$= '0f'x; @@.= /*─ ─ */ |
|||
do y=1 for HT; ToB= $ || copies($, Lintel) || $ /*ToB: Top Or Bot.*/ |
|||
beam= $ || copies($, Lintel)$ || left('', Lintel)$ || copies($, Lintel) || $ |
|||
select /*$: Greek cross glyph*/ |
|||
when y==1 | y==HT then do x=1 for LB; call place x+LB-1,y,substr(ToB, x, 1) |
|||
end |
|||
when y==LB | y==TB then do x=1 for HT; if x>LB & x<TB then iterate |
|||
call place x,y,substr(beam, x, 1) |
|||
end |
|||
when y>LB & y<TB then do x=1 by HT-1 for 2; call place x,y,$; end |
|||
otherwise do x=LB by TB-LB for 2; call place x,y,$; end |
|||
end /*select*/ |
|||
end /*y*/ |
|||
@abc= 'abcdefghijklmnopqrstuvwxyz'; @chars= '1234567890'translate(@abc) || @abc |
|||
do j=1 for 2; XorY=substr('XY',j,1) /*make sure X and Y are integers.*/ |
|||
@@.63= '@' ; @@.64= "æÆα"; @@.67= 'ß' ; @@.68= "¢" ; @@.69= '^' |
|||
@@.70= 'Σ' ; @@.71= "ƒ" ; @@.72= 'ñÑπ'; @@.75= "σΘφ"; @@.78= '₧' |
|||
if \datatype(_.j,'N') then do; call err XorY "isn't numeric:" _.j ; return 0; end |
|||
@@.79= '$δ'; @@.81= "¥" ; @@.82= '#%&*=+\;' |
|||
if \datatype(_.j,'W') then do; call err XorY "isn't an integer:" _.j; return 0; end |
|||
do j=60 to 99; @chars= @chars || @@.j |
|||
end |
|||
end /*j*/ |
|||
@chars= @chars'()[]{}<>«»' /*can't contain "empty", ?, blank.*/ |
|||
call display |
|||
return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
mark: parse arg xx,yy,pointChar /*place marker, check for errors. */ |
|||
if pointChar=='' then pointChar= word( substr(@chars, turn, 1) "+", 1) |
|||
xxcyy= xx','yy; _.1= xx; _.2= yy |
|||
do j=1 for 2; XorY= substr('XY', j, 1) /*make sure X and Y are integers. */ |
|||
if _.j=='' then do; call err XorY "wasn't specified." ;return 0; end |
|||
if \isNum(_.j) then do; call err XorY "isn't numeric:" _.j ; return 0; end |
|||
if \isInt(_.j) then do; call err XorY "isn't an integer:" _.j; return 0; end |
|||
end /*j*/ |
|||
xx= xx / 1; yy= yy / 1 /*normalize integers: + 7 or 5.0*/ |
|||
if pointChar==empty |, |
|||
if pointChar==empty |, |
|||
pointChar=='?' then do; call err 'illegal point character:' pointChar; return 0; end |
|||
pointChar=='?' then do; call err 'illegal point character:' pointChar; return 0 |
|||
end |
|||
if @.xx.yy\==empty then do; call err 'point' xxcyy "is already occupied."; return 0 |
|||
call place xx,yy,'?' |
|||
end |
|||
newWins=countWins() |
|||
if \neighbor(xx,yy) then do; call err "point" xxcyy "is a bad move." ; return 0 |
|||
end |
|||
call place xx,yy,'?' |
|||
newWins= seeIfWin() |
|||
if newWins==0 then do; call err 'point' xxcyy "isn't a good move." |
|||
call t "move" turn ' ('xx","yy') with "'pointChar'"' |
|||
@.xx.yy= empty; return 0 |
|||
end |
|||
return 1 |
|||
call t "move" turn ' ('xx","yy') with "'pointChar'"' |
|||
/*─────────────────────────────────────NEIGHBOR subroutine──────────────*/ |
|||
wins= wins + newWins; @.xx.yy= pointChar |
|||
neighbor: parse arg a,b; am=a-1; ap=a+1 |
|||
call display; turn= turn + 1 |
|||
return 1 |
|||
return @.am.b \== empty | @.am.bm \== empty |, |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@.ap.b \== empty | @.am.bp \== empty |, |
|||
neighbor: parse arg a,b; am= a - 1; ap= a + 1; bm= b - 1; bp= b + 1 |
|||
@. |
return @.am.b\==empty | @.am.bm\==empty | @.ap.b\==empty | @.am.bp \== empty |, |
||
@.a.bm\==empty | @.ap.bm\==empty | @.a.bp\==empty | @.ap.bp\==empty |
|||
/*─────────────────────────────────────COUNTALINE subroutine────────────*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
countAline: arg z ; L=length(z) |
|||
noValue: syntax: prompt=; quiet= 0 |
|||
call err 'REXX program' condition('C') "error", condition('D'), , |
|||
"REXX source statement (line" sigl"):", sourceline(sigl) |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
place: parse arg xxp,yyp /*place a marker (point) on grid.*/ |
|||
loX= min(loX, xxp); hiX= max(hiX, xxp) |
|||
loY= min(loY, yyp); hiY= max(hiY, yyp); @.xxp.yyp= arg(3) |
|||
return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
seeIfWin: y=yy; z= @.xx.yy /*count horizontal/vertical/diagonal wins.*/ |
|||
do x=xx+1; if @.x.y==empty then leave; z= z||@.x.y; end |
|||
do x=xx-1 by -1; if @.x.y==empty then leave; z= @.x.y||z; end |
|||
if ?win(z) then return 1 /*────────count wins in horizontal line. */ |
|||
x= xx; z= @.xx.yy |
|||
do y=yy+1; if @.x.y==empty then leave; z= z||@.x.y; end |
|||
do y=yy-1 by -1; if @.x.y==empty then leave; z= @.x.y||z; end |
|||
if ?win(z) then return 1 /*────────count wins in vertical line. */ |
|||
x= xx; z= @.xx.yy |
|||
do y=yy+1; x= x + 1; if @.x.y==empty then leave; z= z||@.x.y; end |
|||
x= xx |
|||
do y=yy-1 by -1; x=x-1; if @.x.y==empty then leave; z= @.x.y||z; end |
|||
if ?win(z) then return 1 /*──────count diag wins: up & >, down & < */ |
|||
x= xx; z= @.xx.yy |
|||
do y=yy+1; x= x - 1; if @.x.y==empty then leave; z= z||@.x.y; end |
|||
x= xx |
|||
do y=yy-1 by -1; x=x+1; if @.x.y==empty then leave; z= z||@.x.y; end |
|||
return ?win(z) /*──────count diag wins: up & <, down & > */</syntaxhighlight> |
|||
This REXX program makes use of '''LINESIZE''' REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console). |
|||
<br>The '''LINESIZE.REX''' REXX program is included here ──► [[LINESIZE.REX]].<br> |
|||
{{out|output|text= when running 1,500 trials, the highest win was a meager 47 (four games, all different), and one of them is shown below.}} |
|||
if L>gS then do; if gT=='D' then return 0 /*longlines ¬ kosker for D*/ |
|||
<pre> |
|||
parse var z z1 '?' z2 /*could be xxxxx?xxxx */ |
|||
···☼☼☼☼··· |
|||
···☼··☼··· |
|||
···☼··☼··· |
|||
return L==gS |
|||
☼☼☼☼··☼☼☼☼ |
|||
/*─────────────────────────────────────COUNTWINS subroutine─────────────*/ |
|||
☼········☼ |
|||
countWins: eureka=0; y=yy /*count horizontal/vertical/diagonal wins.*/ |
|||
☼········☼ |
|||
z=@.xx.yy |
|||
☼☼☼☼··☼☼☼☼ |
|||
···☼··☼··· |
|||
···☼··☼··· |
|||
eureka=eureka+countAline(z) /*─────────count wins in horizontal line. */ |
|||
···☼☼☼☼··· |
|||
═══════════════════════════════════════════════════════════════════════════════ |
|||
move 1 (11,4) with "1" |
|||
x=xx |
|||
z=@.xx.yy |
|||
do y=yy+1; if @.x.y==empty then leave; z=z||@.x.y; end |
|||
do y=yy-1 by -1; if @.x.y==empty then leave; z=@.x.y||z; end |
|||
eureka=eureka+countAline(z) /*─────────count wins in vertical line. */ |
|||
··········· |
|||
x=xx |
|||
···☼☼☼☼···· |
|||
z=@.xx.yy |
|||
···☼··☼···· |
|||
···☼··☼···· |
|||
x=xx |
|||
☼☼☼☼··☼☼☼☼· |
|||
do y=yy-1 by -1; x=x-1; if @.x.y==empty then leave; z=@.x.y||z; end |
|||
☼········☼· |
|||
eureka=eureka+countAline(z) /*───────count diag wins: up&>, down&< */ |
|||
☼········☼· |
|||
☼☼☼☼··☼☼☼☼1 |
|||
···☼··☼···· |
|||
···☼··☼···· |
|||
···☼☼☼☼···· |
|||
═══════════════════════════════════════════════(above) the board after 1 turns. |
|||
move 2 (4,5) with "2" |
|||
x=xx |
|||
z=@.xx.yy |
|||
··········· |
|||
···☼☼☼☼···· |
|||
x=xx |
|||
···☼··☼···· |
|||
do y=yy-1 by -1; x=x+1; if @.x.y==empty then leave; z=z||@.x.y; end |
|||
···☼··☼···· |
|||
return eureka+countAline(z) /*───────count diag wins: up&<, down&> */</lang> |
|||
☼☼☼☼··☼☼☼☼· |
|||
This REXX program makes use of '''LINESIZE''' REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console). |
|||
☼········☼· |
|||
<br>The '''LINESIZE.REX''' REXX program is included here ──► [[LINESIZE.REX]].<br> |
|||
☼··2·····☼· |
|||
☼☼☼☼··☼☼☼☼1 |
|||
···☼··☼···· |
|||
···☼··☼···· |
|||
···☼☼☼☼···· |
|||
═══════════════════════════════════════════════(above) the board after 2 turns. |
|||
'''output''' when running 1,500 trials, the highest win was a meager 44 (four games, all different), and |
|||
one of them is shown below. |
|||
<pre style="height:100ex"> |
|||
·╞···╔══╗··· |
|||
·|···║··║··· |
|||
·|···║··║··· |
|||
·|╔══╝··╚══╗ |
|||
·|║········║ |
|||
·├║········║ |
|||
·|╚══╗··╔══╝ |
|||
·|···║··║··· |
|||
·|···║··║··· |
|||
·|···╚══╝··· |
|||
─┼────┴────╨ |
|||
·|·········· |
|||
═══════════════════════════════════════════════════════════════════════════════ |
|||
move 1 (3,3) with "0" |
|||
... previous 46 moves elided ... above is the initial board (grid) ... |
... previous 46 moves elided ... above is the initial board (grid) ... |
||
--- the next line means: 47th move, position=9,9 marked with an "k" --- |
--- the next line means: 47th move, position=9,9 marked with an "k" --- |
||
move 47 (9,9) with "k" |
move 47 (9,9) with "k" |
||
···iQagP···· |
|||
· |
·j·d☼☼☼☼F··· |
||
··hO☼NL☼ck·· |
|||
· |
·CZ1☼bK☼3MD· |
||
X☼☼☼☼57☼☼☼☼f |
|||
· |
·☼YHASGBJR☼· |
||
· |
·☼UT8I·9·e☼· |
||
· |
·☼☼☼☼46☼☼☼☼· |
||
· |
V··0☼W·☼2··· |
||
· |
····☼··☼···· |
||
· |
····☼☼☼☼E··· |
||
─┼────┴────╨── |
|||
·|············ |
|||
═════════════════════════════════════════════════════ count of (above) wins = 47 |
═════════════════════════════════════════════════════ count of (above) wins = 47 |
||
Line 1,281: | Line 1,682: | ||
* number of wins = 47 |
* number of wins = 47 |
||
</pre> |
</pre> |
||
=={{header|Wren}}== |
|||
{{trans|C}} |
|||
{{libheader|ncurses}} |
|||
{{libheader|Wren-dynamic}} |
|||
{{libheader|Wren-fmt}} |
|||
An embedded program so we can use the ncurses library. |
|||
<syntaxhighlight lang="wren">/* Morpion_solitaire.wren */ |
|||
import "random" for Random |
|||
import "./dynamic" for Flags, Struct |
|||
import "./fmt" for Conv |
|||
class Ncurses { |
|||
foreign static initscr() |
|||
foreign static cbreak() |
|||
foreign static nocbreak() |
|||
foreign static echo() |
|||
foreign static noecho() |
|||
foreign static refresh() |
|||
foreign static getch() |
|||
foreign static mvprintw(y, x, str) |
|||
foreign static timeout(delay) |
|||
foreign static endwin() |
|||
} |
|||
class C { |
|||
foreign static usleep(usec) |
|||
} |
|||
// optional settings |
|||
var lineLen = 5 |
|||
var disjoint = 0 |
|||
var fields = [ |
|||
"blank", "occupied", "dirNS", "dirEW", |
|||
"dirNESW", "dirNWSE", "newlyAdded", "current" |
|||
] |
|||
var State = Flags.create("State", fields, true) |
|||
var ofs = [ |
|||
[0, 1, State.dirNS], |
|||
[1, 0, State.dirEW], |
|||
[1, -1, State.dirNESW], |
|||
[1, 1, State.dirNWSE] |
|||
] |
|||
var Move = Struct.create("Move", ["m", "s", "seq", "x", "y"]) |
|||
var rand = Random.new() |
|||
var board |
|||
var width |
|||
var height |
|||
var allocBoard = Fn.new { |w, h| |
|||
var buf = List.filled(h, null) |
|||
for (i in 0...h) buf[i] = List.filled(w, 0) |
|||
return buf |
|||
} |
|||
var boardSet = Fn.new { |v, x0, y0, x1, y1| |
|||
for (i in y0..y1) { |
|||
for (j in x0..x1) board[i][j] = v |
|||
} |
|||
} |
|||
var initBoard = Fn.new { |
|||
width = height = 3 * (lineLen - 1) |
|||
board = allocBoard.call(width, height) |
|||
boardSet.call(State.occupied, lineLen-1, 1, 2*lineLen-3, height-2) |
|||
boardSet.call(State.occupied, 1, lineLen-1, width-2, 2*lineLen-3) |
|||
boardSet.call(State.blank, lineLen, 2, 2*lineLen-4, height-3) |
|||
boardSet.call(State.blank, 2, lineLen, width-3, 2*lineLen-4) |
|||
} |
|||
// -1: expand low index end; 1: expand high index end |
|||
var expandBoard = Fn.new { |dw, dh| |
|||
var dw2 = (dw == 0) ? 0 : 1 |
|||
var dh2 = (dh == 0) ? 0 : 1 |
|||
var nw = width + dw2 |
|||
var nh = height + dh2 |
|||
var nbuf = allocBoard.call(nw, nh) |
|||
dw = -Conv.btoi(dw < 0) |
|||
dh = -Conv.btoi(dh < 0) |
|||
for (i in 0...nh) { |
|||
if (i + dh < 0 || i + dh >= height) continue |
|||
for (j in 0...nw) { |
|||
if (j + dw < 0 || j + dw >= width) continue |
|||
nbuf[i][j] = board[i+dh][j+dw] |
|||
} |
|||
} |
|||
board = nbuf |
|||
width = nw |
|||
height = nh |
|||
} |
|||
var showBoard = Fn.new { |
|||
for (i in 0...height) { |
|||
for (j in 0...width){ |
|||
var temp |
|||
if (board[i][j] & State.current != 0) { |
|||
temp = "X " |
|||
} else if (board[i][j] & State.newlyAdded != 0) { |
|||
temp = "O " |
|||
} else if (board[i][j] & State.occupied != 0) { |
|||
temp = "+ " |
|||
} else { |
|||
temp = " " |
|||
} |
|||
Ncurses.mvprintw(i + 1, j * 2, temp) |
|||
} |
|||
} |
|||
Ncurses.refresh() |
|||
} |
|||
// test if a point can complete a line, or take that point |
|||
var testPosition = Fn.new { |y, x, rec| |
|||
if (board[y][x] & State.occupied != 0) return |
|||
for (m in 0..3) { // 4 directions |
|||
var dx = ofs[m][0] |
|||
var dy = ofs[m][1] |
|||
var dir = ofs[m][2] |
|||
var s = 1 - lineLen |
|||
while (s <= 0) { // offset line |
|||
var k = 0 |
|||
while (k < lineLen) { |
|||
if (s + k == 0) { |
|||
k = k + 1 |
|||
continue |
|||
} |
|||
var xx = x + dx * (s + k) |
|||
var yy = y + dy * (s + k) |
|||
if (xx < 0 || xx >= width || yy < 0 || yy >= height) break |
|||
// no piece at position |
|||
if (board[yy][xx] & State.occupied == 0) break |
|||
// this direction taken |
|||
if (board[yy][xx] & dir != 0) break |
|||
k = k + 1 |
|||
} |
|||
if (k == lineLen) { |
|||
// position ok |
|||
// random integer to even each option's chance of being picked |
|||
rec.seq = rec.seq + 1 |
|||
if (rand.int(rec.seq) == 0) { |
|||
rec.m = m |
|||
rec.s = s |
|||
rec.x = x |
|||
rec.y = y |
|||
} |
|||
} |
|||
s = s + 1 |
|||
} |
|||
} |
|||
} |
|||
var addPiece = Fn.new { |rec| |
|||
var dx = ofs[rec.m][0] |
|||
var dy = ofs[rec.m][1] |
|||
var dir = ofs[rec.m][2] |
|||
board[rec.y][rec.x] = board[rec.y][rec.x] | (State.current | State.occupied) |
|||
for (k in 0...lineLen) { |
|||
var xx = rec.x + dx * (k + rec.s) |
|||
var yy = rec.y + dy * (k + rec.s) |
|||
board[yy][xx] = board[yy][xx] | State.newlyAdded |
|||
if (k >= disjoint || k < lineLen-disjoint) { |
|||
board[yy][xx] = board[yy][xx] | dir |
|||
} |
|||
} |
|||
} |
|||
var nextMove = Fn.new { |
|||
var rec = Move.new(0, 0, 0, 0, 0) |
|||
// wipe last iteration's new line markers |
|||
for (i in 0...height) { |
|||
for (j in 0...width) { |
|||
board[i][j] = board[i][j] & ~(State.newlyAdded | State.current) |
|||
} |
|||
} |
|||
// randomly pick one of next legal moves |
|||
for (i in 0...height) { |
|||
for (j in 0...width) testPosition.call(i, j, rec) |
|||
} |
|||
// didn't find any move, game over |
|||
if (rec.seq == 0) return false |
|||
addPiece.call(rec) |
|||
if (rec.x == width-1) { |
|||
rec.x = 1 |
|||
} else if (rec.x != 0) { |
|||
rec.x = 0 |
|||
} else { |
|||
rec.x = -1 |
|||
} |
|||
if (rec.y == height-1) { |
|||
rec.y = 1 |
|||
} else if (rec.y != 0) { |
|||
rec.y = 0 |
|||
} else { |
|||
rec.y = -1 |
|||
} |
|||
if (rec.x != 0 || rec.y != 0) expandBoard.call(rec.x, rec.y) |
|||
return true |
|||
} |
|||
initBoard.call() |
|||
Ncurses.initscr() |
|||
Ncurses.noecho() |
|||
Ncurses.cbreak() |
|||
var ch = 0 |
|||
var move = 0 |
|||
var waitKey = true |
|||
while (true) { |
|||
Ncurses.mvprintw(0, 0, "Move %(move)") |
|||
move = move + 1 |
|||
showBoard.call() |
|||
if (!nextMove.call()) { |
|||
nextMove.call() |
|||
showBoard.call() |
|||
break |
|||
} |
|||
if (!waitKey) C.usleep(100000) |
|||
if ((ch = Ncurses.getch()) == 32) { // spacebar pressed |
|||
waitKey = !waitKey |
|||
if (waitKey) { |
|||
Ncurses.timeout(-1) |
|||
} else { |
|||
Ncurses.timeout(0) |
|||
} |
|||
} |
|||
if (ch == 113) break // 'q' pressed |
|||
} |
|||
Ncurses.timeout(-1) |
|||
Ncurses.nocbreak() |
|||
Ncurses.echo() |
|||
Ncurses.endwin()</syntaxhighlight> |
|||
<br> |
|||
We now embed the above script in the following C program, build and run it. |
|||
<syntaxhighlight lang="c">/* gcc Morpion_solitaire.c -o Morpion_solitaire -lncurses -lwren -lm */ |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <ncurses.h> |
|||
#include <unistd.h> |
|||
#include "wren.h" |
|||
/* C <=> Wren interface functions */ |
|||
void C_initscr(WrenVM* vm) { |
|||
initscr(); |
|||
} |
|||
void C_cbreak(WrenVM* vm) { |
|||
cbreak(); |
|||
} |
|||
void C_nocbreak(WrenVM* vm) { |
|||
nocbreak(); |
|||
} |
|||
void C_echo(WrenVM* vm) { |
|||
echo(); |
|||
} |
|||
void C_noecho(WrenVM* vm) { |
|||
noecho(); |
|||
} |
|||
void C_refresh(WrenVM* vm) { |
|||
refresh(); |
|||
} |
|||
void C_getch(WrenVM* vm) { |
|||
int ch = getch(); |
|||
wrenSetSlotDouble(vm, 0, (double)ch); |
|||
} |
|||
void C_mvprintw(WrenVM* vm) { |
|||
int y = (int)wrenGetSlotDouble(vm, 1); |
|||
int x = (int)wrenGetSlotDouble(vm, 2); |
|||
const char *str = wrenGetSlotString(vm, 3); |
|||
mvprintw(y, x, "%s", str); |
|||
} |
|||
void C_timeout(WrenVM* vm) { |
|||
int delay = (int)wrenGetSlotDouble(vm, 1); |
|||
timeout(delay); |
|||
} |
|||
void C_endwin(WrenVM* vm) { |
|||
endwin(); |
|||
} |
|||
void C_usleep(WrenVM* vm) { |
|||
useconds_t usec = (useconds_t)wrenGetSlotDouble(vm, 1); |
|||
usleep(usec); |
|||
} |
|||
WrenForeignMethodFn bindForeignMethod( |
|||
WrenVM* vm, |
|||
const char* module, |
|||
const char* className, |
|||
bool isStatic, |
|||
const char* signature) { |
|||
if (strcmp(module, "main") == 0) { |
|||
if (strcmp(className, "Ncurses") == 0) { |
|||
if (isStatic && strcmp(signature, "initscr()") == 0) return C_initscr; |
|||
if (isStatic && strcmp(signature, "cbreak()") == 0) return C_cbreak; |
|||
if (isStatic && strcmp(signature, "noecho()") == 0) return C_noecho; |
|||
if (isStatic && strcmp(signature, "nocbreak()") == 0) return C_nocbreak; |
|||
if (isStatic && strcmp(signature, "echo()") == 0) return C_echo; |
|||
if (isStatic && strcmp(signature, "refresh()") == 0) return C_refresh; |
|||
if (isStatic && strcmp(signature, "getch()") == 0) return C_getch; |
|||
if (isStatic && strcmp(signature, "mvprintw(_,_,_)") == 0) return C_mvprintw; |
|||
if (isStatic && strcmp(signature, "timeout(_)") == 0) return C_timeout; |
|||
if (isStatic && strcmp(signature, "endwin()") == 0) return C_endwin; |
|||
} else if (strcmp(className, "C") == 0) { |
|||
if (isStatic && strcmp(signature, "usleep(_)") == 0) return C_usleep; |
|||
} |
|||
} |
|||
return NULL; |
|||
} |
|||
static void writeFn(WrenVM* vm, const char* text) { |
|||
printf("%s", text); |
|||
} |
|||
void errorFn(WrenVM* vm, WrenErrorType errorType, const char* module, const int line, const char* msg) { |
|||
switch (errorType) { |
|||
case WREN_ERROR_COMPILE: |
|||
printf("[%s line %d] [Error] %s\n", module, line, msg); |
|||
break; |
|||
case WREN_ERROR_STACK_TRACE: |
|||
printf("[%s line %d] in %s\n", module, line, msg); |
|||
break; |
|||
case WREN_ERROR_RUNTIME: |
|||
printf("[Runtime Error] %s\n", msg); |
|||
break; |
|||
} |
|||
} |
|||
char *readFile(const char *fileName) { |
|||
FILE *f = fopen(fileName, "r"); |
|||
fseek(f, 0, SEEK_END); |
|||
long fsize = ftell(f); |
|||
rewind(f); |
|||
char *script = malloc(fsize + 1); |
|||
fread(script, 1, fsize, f); |
|||
fclose(f); |
|||
script[fsize] = 0; |
|||
return script; |
|||
} |
|||
static void loadModuleComplete(WrenVM* vm, const char* module, WrenLoadModuleResult result) { |
|||
if( result.source) free((void*)result.source); |
|||
} |
|||
WrenLoadModuleResult loadModule(WrenVM* vm, const char* name) { |
|||
WrenLoadModuleResult result = {0}; |
|||
if (strcmp(name, "random") != 0 && strcmp(name, "meta") != 0) { |
|||
result.onComplete = loadModuleComplete; |
|||
char fullName[strlen(name) + 6]; |
|||
strcpy(fullName, name); |
|||
strcat(fullName, ".wren"); |
|||
result.source = readFile(fullName); |
|||
} |
|||
return result; |
|||
} |
|||
int main(int argc, char **argv) { |
|||
WrenConfiguration config; |
|||
wrenInitConfiguration(&config); |
|||
config.writeFn = &writeFn; |
|||
config.errorFn = &errorFn; |
|||
config.bindForeignMethodFn = &bindForeignMethod; |
|||
config.loadModuleFn = &loadModule; |
|||
WrenVM* vm = wrenNewVM(&config); |
|||
const char* module = "main"; |
|||
const char* fileName = "Morpion_solitaire.wren"; |
|||
char *script = readFile(fileName); |
|||
WrenInterpretResult result = wrenInterpret(vm, module, script); |
|||
switch (result) { |
|||
case WREN_RESULT_COMPILE_ERROR: |
|||
printf("Compile Error!\n"); |
|||
break; |
|||
case WREN_RESULT_RUNTIME_ERROR: |
|||
printf("Runtime Error!\n"); |
|||
usleep(10000000); // allow time to read it |
|||
timeout(-1); |
|||
nocbreak(); |
|||
echo(); |
|||
endwin(); |
|||
break; |
|||
case WREN_RESULT_SUCCESS: |
|||
break; |
|||
} |
|||
wrenFreeVM(vm); |
|||
free(script); |
|||
return 0; |
|||
}</syntaxhighlight> |
Latest revision as of 11:11, 4 January 2024
Task Requirements
The task is to get the computer to play a game of Morpion solitaire. For this task, it is acceptable for the computer to make randomly selected valid moves, rather than playing the strongest move each time. Use the standard version, with 5 point lines that allows parallel lines to touch at the endpoints.
(Proposed additional requirement): Provide sample output. Preferably the output should be a record of moves suitable for replay using Pentasol. Alternately, ASCII art can be used; however, games rendered in this manner may not provide enough information to replay the game. Please see the discussion on game notation and rendering for more information.
Playing Morpion Solitaire
There are several variations of the game, this task deals with the 5 point "touching" version also known as "5T".
Morpion solitaire is played on a (theoretically) infinite grid. It begins with 36 points marked in a Greek cross:
...XXXX... ...X..X... ...X..X... XXXX..XXXX X........X X........X XXXX..XXXX ...X..X... ...X..X... ...XXXX...
- A move is made by adding one point anywhere that creates a new line of 5 points (without spaces) and drawing a line through them. (Moves are commonly marked with the number of the move for visual clarity. Creating a record of the game in game notation is a better way to validate a game.)
- Any two lines not running in the same direction may cross.
- Any two lines running in the same direction are allowed to touch at the ends but not overlap (i.e. share at most a single point).
- The game ends when you run out of legal moves. (The game score is the number of legal moves played.)
The rules to morpion solitaire are here.
Background
A short history of the 5T game:
- 170 - Bruneau, by hand in 1976
- 117 and 122 - Juillé in 1995 and 1999
- 143 - Zimmer in 2003
- 144 - Cazenave in 2007
- 172 - Rosin in 2010
- 171 and 172 - Tishchenko in 2011
- 177 and 178 - Rosin in 2011
For an up to date list of Morpion 5T Records see here. The shortest game possible is 20 moves.
The game is NP-hard in the general case and has a huge search space and is a test case for research into searching methods.
Theoretical bounds have been placed on the longest 5T game. The lower bound of 170 and upper bound of either 324 or 704 according to two different papers (see talk page).
C
Console play with ncurses. Length and touching rules can be changed at the begining of source code. 'q' key to quit, space key to toggle auto move, anykey for next move. Play is random. I got nowhere near the record 177 moves, but did approach the worst-possible (20) quite often.
#include <ncurses.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
/* option: how long a line is. Options probably should have been made into
* commandline args, if I were not lazy. Also, if line_len is set to 3,
* the game may keep going indefinitely: best use auto mode. */
int line_len = 5;
/* option: whether two lines are allowed to be in the same direction and
* connected end to end. Note: two lines crossing are always ok. */
int disjoint = 0;
int **board = 0, width, height;
#define for_i for(i = 0; i < height; i++)
#define for_j for(j = 0; j < width; j++)
enum {
s_blank = 0,
s_occupied = 1 << 0,
s_dir_ns = 1 << 1,
s_dir_ew = 1 << 2,
s_dir_ne_sw = 1 << 3,
s_dir_nw_se = 1 << 4,
s_newly_added = 1 << 5,
s_current = 1 << 6,
};
int irand(int n)
{
int r, rand_max = RAND_MAX - (RAND_MAX % n);
while ((r = rand()) >= rand_max);
return r / (rand_max / n);
}
int** alloc_board(int w, int h)
{
int i;
int **buf = calloc(1, sizeof(int *) * h + sizeof(int) * h * w);
buf[0] = (int*)(buf + h);
for (i = 1; i < h; i++)
buf[i] = buf[i - 1] + w;
return buf;
}
/* -1: expand low index end; 1: exten high index end */
void expand_board(int dw, int dh)
{
int i, j;
int nw = width + !!dw, nh = height + !!dh;
/* garanteed to fragment heap: not realloc because copying elements
* is a bit tricky */
int **nbuf = alloc_board(nw, nh);
dw = -(dw < 0), dh = -(dh < 0);
for (i = 0; i < nh; i++) {
if (i + dh < 0 || i + dh >= height) continue;
for (j = 0; j < nw; j++) {
if (j + dw < 0 || j + dw >= width) continue;
nbuf[i][j] = board[i + dh][j + dw];
}
}
free(board);
board = nbuf;
width = nw;
height = nh;
}
void array_set(int **buf, int v, int x0, int y0, int x1, int y1)
{
int i, j;
for (i = y0; i <= y1; i++)
for (j = x0; j <= x1; j++)
buf[i][j] = v;
}
void show_board()
{
int i, j;
for_i for_j mvprintw(i + 1, j * 2,
(board[i][j] & s_current) ? "X "
: (board[i][j] & s_newly_added) ? "O "
: (board[i][j] & s_occupied) ? "+ " : " ");
refresh();
}
void init_board()
{
width = height = 3 * (line_len - 1);
board = alloc_board(width, height);
array_set(board, s_occupied, line_len - 1, 1, 2 * line_len - 3, height - 2);
array_set(board, s_occupied, 1, line_len - 1, width - 2, 2 * line_len - 3);
array_set(board, s_blank, line_len, 2, 2 * line_len - 4, height - 3);
array_set(board, s_blank, 2, line_len, width - 3, 2 * line_len - 4);
}
int ofs[4][3] = {
{0, 1, s_dir_ns},
{1, 0, s_dir_ew},
{1, -1, s_dir_ne_sw},
{1, 1, s_dir_nw_se}
};
typedef struct { int m, s, seq, x, y; } move_t;
/* test if a point can complete a line, or take that point */
void test_postion(int y, int x, move_t * rec)
{
int m, k, s, dx, dy, xx, yy, dir;
if (board[y][x] & s_occupied) return;
for (m = 0; m < 4; m++) { /* 4 directions */
dx = ofs[m][0];
dy = ofs[m][1];
dir = ofs[m][2];
for (s = 1 - line_len; s <= 0; s++) { /* offset line */
for (k = 0; k < line_len; k++) {
if (s + k == 0) continue;
xx = x + dx * (s + k);
yy = y + dy * (s + k);
if (xx < 0 || xx >= width || yy < 0 || yy >= height)
break;
/* no piece at position */
if (!(board[yy][xx] & s_occupied)) break;
/* this direction taken */
if ((board[yy][xx] & dir)) break;
}
if (k != line_len) continue;
/* position ok; irand() to even each option's chance of
being picked */
if (! irand(++rec->seq))
rec->m = m, rec->s = s, rec->x = x, rec->y = y;
}
}
}
void add_piece(move_t *rec) {
int dx = ofs[rec->m][0];
int dy = ofs[rec->m][1];
int dir= ofs[rec->m][2];
int xx, yy, k;
board[rec->y][rec->x] |= (s_current | s_occupied);
for (k = 0; k < line_len; k++) {
xx = rec->x + dx * (k + rec->s);
yy = rec->y + dy * (k + rec->s);
board[yy][xx] |= s_newly_added;
if (k >= disjoint || k < line_len - disjoint)
board[yy][xx] |= dir;
}
}
int next_move()
{
int i, j;
move_t rec;
rec.seq = 0;
/* wipe last iteration's new line markers */
for_i for_j board[i][j] &= ~(s_newly_added | s_current);
/* randomly pick one of next legal moves */
for_i for_j test_postion(i, j, &rec);
/* didn't find any move, game over */
if (!rec.seq) return 0;
add_piece(&rec);
rec.x = (rec.x == width - 1) ? 1 : rec.x ? 0 : -1;
rec.y = (rec.y == height - 1) ? 1 : rec.y ? 0 : -1;
if (rec.x || rec.y) expand_board(rec.x, rec.y);
return 1;
}
int main()
{
int ch = 0;
int move = 0;
int wait_key = 1;
init_board();
srand(time(0));
initscr();
noecho();
cbreak();
do {
mvprintw(0, 0, "Move %d", move++);
show_board();
if (!next_move()) {
next_move();
show_board();
break;
}
if (!wait_key) usleep(100000);
if ((ch = getch()) == ' ') {
wait_key = !wait_key;
if (wait_key) timeout(-1);
else timeout(0);
}
} while (ch != 'q');
timeout(-1);
nocbreak();
echo();
endwin();
return 0;
}
Go
package main
import (
gc "github.com/rthornton128/goncurses"
"log"
"math/rand"
"time"
)
// optional settings
const (
lineLen = 5
disjoint = 0
)
var (
board [][]int
width int
height int
)
const (
blank = 0
occupied = 1 << (iota - 1)
dirNS
dirEW
dirNESW
dirNWSE
newlyAdded
current
)
var ofs = [4][3]int{
{0, 1, dirNS},
{1, 0, dirEW},
{1, -1, dirNESW},
{1, 1, dirNWSE},
}
type move struct{ m, s, seq, x, y int }
func btoi(b bool) int {
if b {
return 1
}
return 0
}
func allocBoard(w, h int) [][]int {
buf := make([][]int, h)
for i := 0; i < h; i++ {
buf[i] = make([]int, w)
}
return buf
}
func boardSet(v, x0, y0, x1, y1 int) {
for i := y0; i <= y1; i++ {
for j := x0; j <= x1; j++ {
board[i][j] = v
}
}
}
func initBoard() {
height = 3 * (lineLen - 1)
width = height
board = allocBoard(width, height)
boardSet(occupied, lineLen-1, 1, 2*lineLen-3, height-2)
boardSet(occupied, 1, lineLen-1, width-2, 2*lineLen-3)
boardSet(blank, lineLen, 2, 2*lineLen-4, height-3)
boardSet(blank, 2, lineLen, width-3, 2*lineLen-4)
}
// -1: expand low index end; 1: expand high index end
func expandBoard(dw, dh int) {
dw2, dh2 := 1, 1
if dw == 0 {
dw2 = 0
}
if dh == 0 {
dh2 = 0
}
nw, nh := width+dw2, height+dh2
nbuf := allocBoard(nw, nh)
dw, dh = -btoi(dw < 0), -btoi(dh < 0)
for i := 0; i < nh; i++ {
if i+dh < 0 || i+dh >= height {
continue
}
for j := 0; j < nw; j++ {
if j+dw < 0 || j+dw >= width {
continue
}
nbuf[i][j] = board[i+dh][j+dw]
}
}
board = nbuf
width, height = nw, nh
}
func showBoard(scr *gc.Window) {
for i := 0; i < height; i++ {
for j := 0; j < width; j++ {
var temp string
switch {
case (board[i][j] & current) != 0:
temp = "X "
case (board[i][j] & newlyAdded) != 0:
temp = "0 "
case (board[i][j] & occupied) != 0:
temp = "+ "
default:
temp = " "
}
scr.MovePrintf(i+1, j*2, temp)
}
}
scr.Refresh()
}
// test if a point can complete a line, or take that point
func testPosition(y, x int, rec *move) {
if (board[y][x] & occupied) != 0 {
return
}
for m := 0; m < 4; m++ { // 4 directions
dx := ofs[m][0]
dy := ofs[m][1]
dir := ofs[m][2]
var k int
for s := 1 - lineLen; s <= 0; s++ { // offset line
for k = 0; k < lineLen; k++ {
if s+k == 0 {
continue
}
xx := x + dx*(s+k)
yy := y + dy*(s+k)
if xx < 0 || xx >= width || yy < 0 || yy >= height {
break
}
// no piece at position
if (board[yy][xx] & occupied) == 0 {
break
}
// this direction taken
if (board[yy][xx] & dir) != 0 {
break
}
}
if k != lineLen {
continue
}
// position ok
// rand.Intn to even each option's chance of being picked
rec.seq++
if rand.Intn(rec.seq) == 0 {
rec.m, rec.s, rec.x, rec.y = m, s, x, y
}
}
}
}
func addPiece(rec *move) {
dx := ofs[rec.m][0]
dy := ofs[rec.m][1]
dir := ofs[rec.m][2]
board[rec.y][rec.x] |= current | occupied
for k := 0; k < lineLen; k++ {
xx := rec.x + dx*(k+rec.s)
yy := rec.y + dy*(k+rec.s)
board[yy][xx] |= newlyAdded
if k >= disjoint || k < lineLen-disjoint {
board[yy][xx] |= dir
}
}
}
func nextMove() bool {
var rec move
// wipe last iteration's new line markers
for i := 0; i < height; i++ {
for j := 0; j < width; j++ {
board[i][j] &^= newlyAdded | current
}
}
// randomly pick one of next legal moves
for i := 0; i < height; i++ {
for j := 0; j < width; j++ {
testPosition(i, j, &rec)
}
}
// didn't find any move, game over
if rec.seq == 0 {
return false
}
addPiece(&rec)
if rec.x == width-1 {
rec.x = 1
} else if rec.x != 0 {
rec.x = 0
} else {
rec.x = -1
}
if rec.y == height-1 {
rec.y = 1
} else if rec.y != 0 {
rec.y = 0
} else {
rec.y = -1
}
if rec.x != 0 || rec.y != 0 {
expandBoard(rec.x, rec.y)
}
return true
}
func main() {
rand.Seed(time.Now().UnixNano())
initBoard()
scr, err := gc.Init()
if err != nil {
log.Fatal("init", err)
}
defer gc.End()
gc.Echo(false)
gc.CBreak(true)
ch := gc.Key(0)
move := 0
waitKey := true
for {
scr.MovePrintf(0, 0, "Move %d", move)
move++
showBoard(scr)
if !nextMove() {
nextMove()
showBoard(scr)
break
}
if !waitKey {
time.Sleep(100000 * time.Microsecond)
}
if ch = scr.GetChar(); ch == ' ' {
waitKey = !waitKey
if waitKey {
scr.Timeout(-1)
} else {
scr.Timeout(0)
}
}
if ch == 'q' {
break
}
}
scr.Timeout(-1)
gc.CBreak(false)
gc.Echo(true)
}
Icon and Unicon
The example provided goes beyond the basic requirement to play out a random game. It provides a flexible framework to explore the challenge of morpion solitaire.
J
With this program as the file m.ijs
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 $ _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)
NB. find all possible moves
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
NB. save the random state to replay a fantastic game.
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.
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''
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.
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
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 move transitioning from given state to the next.
3 TURN { ... }
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.
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│ └──────────────────────┴───────────────────────────┴─────────────────────────────┘ }
The distribution of 4444 games is strongly bimodal with a narrow peak around 22 moves, and a broader peak of same count at 65 moves. The longest game scored 81, and 120 minimum 20 move games found.
Java
Julia
Nim
import os, random, sequtils
import ncurses
const
LineLength = 5
Disjoint = 0
type
State {.pure.} = enum Blank, Occupied, DirNS, DirEW, DirNESW, DirNWSE, NewlyAdded, Current
States = set[State]
Board = seq[seq[States]]
Move = tuple[m, s, seqnum, x, y: int]
const Ofs = [(0, 1, DirNS), (1, 0, DirEW), (1, -1, DirNESW), (1, 1, DirNWSE)]
func set(board: var Board; value: State; x0, y0, x1, y1: int) =
for i in y0..y1:
for j in x0..x1:
board[i][j] = {value}
func initBoard(): Board =
let height, width = 3 * (LineLength - 1)
result = newSeqWith(height, newSeq[States](width))
result.set(Occupied, LineLength - 1, 1, 2 * LineLength - 3, height - 2)
result.set(Occupied, 1, LineLength - 1, width - 2, 2 * LineLength - 3)
result.set(Blank, LineLength, 2, 2 * LineLength - 4, height - 3)
result.set(Blank, 2, LineLength, width - 3, 2 * LineLength - 4)
func expand(board: var Board; dw, dh: int) =
# -1: expand low index end, +1: expand high index end.
let
height = board.len
width = board[0].len
nw = width + ord(dw != 0)
nh = height + ord(dh != 0)
var nboard = newSeqWith(nh, newSeq[States](nw))
let dw = -ord(dw < 0)
let dh = -ord(dh < 0)
for i in 0..<nh:
if i + dh notin 0..<height: continue
for j in 0..<nw:
if j + dw notin 0..<width: continue
nboard[i][j] = board[i + dh][j + dw]
board = move(nboard)
proc show(board: Board) =
for i, row in board:
for j, cell in row:
let str = if Current in cell: "X "
elif NewlyAdded in cell: "0 "
elif Occupied in cell: "+ "
else: " "
mvprintw(cint(i + 1), cint(j + 2), str)
refresh()
proc testPosition(board: Board; y, x: int; rec: var Move) =
let height = board.len
let width = board[0].len
if Occupied in board[y][x]: return
for m, (dx, dy, dir) in Ofs: # 4 directions.
for s in (1 - LineLength)..0: # offset line.
var k = -1
while k < LineLength:
inc k
if s + k == 0: continue
let xx = x + dx * (s + k)
let yy = y + dy * (s + k)
if xx < 0 or xx >= width or yy < 0 or yy >= height: break
if Occupied notin board[yy][xx]: break # No piece at position.
if dir in board[yy][xx]: break # This direction taken.
if k != LineLength: continue
# Position ok.
# Rand to even each option chance of being picked.
if rand(rec.seqnum) == 0:
rec.m = m; rec.s = s; rec.x = x; rec.y = y
inc rec.seqnum
proc addPiece(board: var Board; rec: Move) =
let (dx, dy, dir) = Ofs[rec.m]
board[rec.y][rec.x] = board[rec.y][rec.x] + {Current, Occupied}
for k in 0..<LineLength:
let xx = rec.x + dx * (k + rec.s)
let yy = rec.y + dy * (k + rec.s)
board[yy][xx].incl NewlyAdded
if k >= Disjoint or k < LineLength - Disjoint:
board[yy][xx].incl dir
proc nextMove(board: var Board): bool {.discardable.} =
var rec: Move
let maxi = board.high
let maxj = board[0].high
# Wipe last iteration new line markers.
for row in board.mitems:
for cell in row.mitems:
cell = cell - {NewlyAdded, Current}
# Randomly pick one of next legal move.
for i in 0..maxi:
for j in 0..maxj:
board.testPosition(i, j, rec)
# Didn't find any move, game over.
if rec.seqnum == 0: return false
board.addPiece(rec)
rec.x = if rec.x == maxj: 1
elif rec.x != 0: 0
else: -1
rec.y = if rec.y == maxi: 1
elif rec.y != 0: 0
else: -1
if rec.x != 0 or rec.y != 0: board.expand(rec.x, rec.y)
result = true
proc play() =
randomize()
var board = initBoard()
var waitKey = true
let win {.used.} = initscr()
noecho()
cbreak()
var move = 0
while true:
mvprintw(0, 0, "Move %d", move)
inc move
board.show()
if not board.nextMove():
board.nextMove()
board.show()
break
if not waitKey: sleep(100)
let ch = getch()
if ch == ord(' '):
waitKey = not waitKey
if waitKey: timeout(-1)
else: timeout(0)
elif ch == ord('q'):
break
timeout(-1)
getch()
nocbreak()
onecho()
endwin()
play()
- Output:
Intermediate state:
Move 20 + +++++ + ++ + ++ ++ + +++++ +0+++ + + 0 + + + X + ++++0+++++ +0 ++ ++ + +++++ +
Perl
Picks a move at random from all possible moves at each step. A sample game is shown. The largest score found so far (from just random play) is 92, also shown below.
use strict;
use warnings;
use List::Util qw( none );
local $_ = <<END;
.............XXXX.............
.............X..X.............
.............X..X.............
..........XXXX..XXXX..........
..........X........X..........
..........X........X..........
..........XXXX..XXXX..........
.............X..X.............
.............X..X.............
.............XXXX.............
END
$_ = tr/X/ /r . $_ . tr/X/ /r; # expand to 30x30
tr/./ /; # and convert dots to spaces
my @moves;
my %used;
my $count = 0;
while( 1 )
{
# print s/\A(?: +\n)*|(?:^ +\n)*\z//gmr, "count $count\n"; # uncomment for each step
tr/O/X/;
my @try; # find valid moves
for my $i ( 0, 29 .. 31 )
{
my $gap = qr/.{$i}/s;
while( / (?=$gap(X)$gap(X)$gap(X)$gap(X))/g ) # add to top
{
my $cand = join ' ', map $-[$_], 0 .. 4;
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand;
}
while( /X(?=$gap(.)$gap(.)$gap(.)$gap(.))/g ) # add inside/bottom downward
{
"$1$2$3$4" =~ tr/X// == 3 or next;
my $cand = join ' ', map $-[$_], 0 .. 4;
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand;
}
}
@try ? $count++ : last;
my $pick = $try[rand @try]; #pick one valid move
push @moves, $pick;
for my $pos (split ' ', $pick)
{
substr $_, $pos, 1, 'O';
}
$used{$1} = 1 while $pick =~ /(?=\b(\d+ \d+)\b)/g;
}
print join(' ', map s/ .* /->/r =~ s!\d+! ($& % 31).','.int $& / 31 !ger, @moves)
=~ s/.{60}\K /\n/gr, "\n";
tr/O/X/;
print $_, "move count: $count\n";
This runs on a 30x30 grid (as advised by Talk page). Each move is shown as the end points of a line, startcolumn,startrow->endcolumn,endrow where row and column numbers are zero-based. To replay a game, just add all five points from each line to the grid. The final grid is also shown in full. Uncommenting the early print will show each step with the latest line added as the 'O' character.
- Output:
10,15->14,19 13,16->13,20 10,13->10,17 15,16->19,16 15,10->19,14 12,10->16,10 19,12->19,16 16,16->16,20 9,16->13,16 12,16->16,20 16,13->20,13 10,13->14,13 13,9->13,13 16,9->16,13 16,9->12,13 13,19->17,19 14,10->10,14 19,15->15,19 20,13->16,17 13,9->17,13 13,11->17,11 X X XXXXX XXXXX XX XX X XXXXX XXXXX X X X XX XXXXX XXXXX X XX XX XX X XXXXX X X move count: 21
13,16->13,20 16,15->16,19 15,10->19,14 16,13->20,13 10,16->14,16 13,10->17,10 12,19->16,19 10,15->14,19 14,10->10,14 10,13->14,13 15,16->19,16 19,13->19,17 16,15->12,19 17,16->13,20 10,13->10,17 13,16->17,20 10,17->14,17 19,15->15,19 16,11->16,15 17,13->13,17 13,9->13,13 13,9->17,13 15,15->15,19 14,17->18,17 14,13->18,17 13,13->17,17 14,13->14,17 15,14->11,18 9,16->13,20 13,12->9,16 11,14->11,18 12,13->16,17 12,14->16,14 14,13->10,17 13,13->9,17 9,12->13,16 11,15->15,19 10,15->14,15 12,14->12,18 13,18->17,18 10,12->14,16 9,15->13,19 15,13->11,17 9,12->13,12 15,11->15,15 20,15->16,19 17,16->17,20 15,13->19,17 14,15->18,15 16,16->12,20 17,12->17,16 13,12->17,12 18,9->14,13 13,10->17,14 12,11->16,11 17,9->13,13 14,16->18,20 18,13->18,17 14,9->10,13 16,14->20,14 21,12->17,16 12,10->12,14 11,9->15,13 14,8->14,12 14,8->10,12 11,10->11,14 10,9->14,13 10,9->14,9 20,12->16,16 20,11->20,15 20,11->16,15 17,12->21,12 16,10->20,14 17,8->17,12 17,8->21,12 19,10->15,14 17,8->13,12 18,9->18,13 19,9->15,13 19,9->19,13 15,9->19,9 17,11->21,11 15,8->19,12 16,8->20,12 13,8->17,8 13,8->9,12 l 15,7->15,11 10,9->10,13 16,7->16,11 9,10->13,10 9,9->13,13 8,9->12,13 XX XXXXX XXXXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXXX XXXXXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXX XXXXXXX XXXXXX XX XX move count: 92
A faster, shorter version without the single step display. Uses the same kind of block shift/or technology I used in "Forest fire" and have used for Conway's Life.
use strict;
use warnings;
use feature 'bitwise';
use List::Util 'none';
local $_ = <<END;
.............XXXX.............
.............X..X.............
.............X..X.............
..........XXXX..XXXX..........
..........X........X..........
..........X........X..........
..........XXXX..XXXX..........
.............X..X.............
.............X..X.............
.............XXXX.............
END
$_ = tr/X./ /r . tr/./ /r . tr/X./ /r; # expand to 30x30 and spaces
my($count, @moves, %used) = 0;
while( 1 )
{
my @try; # valid moves
for my $i ( 1, 30 .. 32 ) # directions 1 - 30 / 31 | 32 \
{
my $combined = tr/X \n/A\0/r |.
(substr $_, $i) =~ tr/X \n/B\0/r |.
(substr $_, 2 * $i) =~ tr/X \n/D\0/r |.
(substr $_, 3 * $i) =~ tr/X \n/H\0/r |.
(substr $_, 4 * $i) =~ tr/X \n/P\0/r;
while( $combined =~ /[OW\[\]\^]/g ) # exactly four Xs and one space
{
my $cand = join ' ', map $-[0] + $_ * $i, 0 .. 4;
none { $used{$_} } $cand =~ /(?=\b(\d+ \d+)\b)/g and push @try, $cand;
}
}
@try ? $count++ : last;
my $pick = $try[rand @try]; #pick one valid move
push @moves, $pick;
for my $pos (split ' ', $pick)
{
substr $_, $pos, 1, 'X';
}
@used{ $pick =~ /(?=\b(\d+ \d+)\b)/g } = (1) x 4;
}
print join(' ', map s/ .* /->/r =~ s!\d+! ($& % 31).','.int $& / 31 !ger,
@moves) =~ s/.{60}\K /\n/gr, "\n";
print $_, "move count: $count\n";
Phix
Focuses on playing back the 178-record, see: Morpion solitaire/Phix
Racket
#lang racket
(module rules racket/base
(require racket/match)
(provide game-cross
available-lines
add-line
line-dx.dy)
(define (add-points points# x y . more)
(define p+ (hash-set points# (cons x y) #t))
(if (null? more) p+ (apply add-points p+ more)))
;; original cross
(define (game-cross)
(let ((x1 (for/fold ((x (hash))) ((i (in-range 3 7)))
(add-points x 0 i i 0 9 i i 9))))
(for/fold ((x x1)) ((i (in-sequences (in-range 0 4) (in-range 6 10))))
(add-points x 3 i i 3 6 i i 6))))
;; add an edge
(define (make-edge points#)
(for*/hash ((k (in-hash-keys points#))
(dx (in-range -1 2))
(dy (in-range -1 2))
(x (in-value (+ (car k) dx)))
(y (in-value (+ (cdr k) dy)))
(e (in-value (cons x y)))
#:unless (hash-has-key? points# e))
(values e #t)))
(define (line-dx.dy d)
(values (match d ['w -1] ['nw -1] ['n 0] [ne 1])
(match d ['n -1] ['ne -1] ['nw -1] ['w 0])))
(define (line-points e d)
(define-values (dx dy) (line-dx.dy d))
(match-define (cons x y) e)
(for/list ((i (in-range 5)))
(cons (+ x (* dx i))
(+ y (* dy i)))))
(define (line-overlaps? lp d l#)
(for/first ((i (in-range 3))
(p (in-list (cdr lp)))
#:when (hash-has-key? l# (cons d p)))
#t))
(define (four-points? lp p#)
(= 4 (for/sum ((p (in-list lp)) #:when (hash-has-key? p# p)) 1)))
;; returns a list of lines that can be applied to the game
(define (available-lines p# l# (e# (make-edge p#)))
(for*/list ((ep (in-sequences (in-hash-keys e#) (in-hash-keys p#)))
(d (in-list '(n w ne nw)))
(lp (in-value (line-points ep d)))
#:unless (line-overlaps? lp d l#)
#:when (four-points? lp p#))
(define new-edge-point (for/first ((p (in-list lp)) #:when (hash-ref e# p #f)) p))
(list ep d lp new-edge-point)))
;; adds a new line to points# lines# returns (values [new points#] [new lines#])
(define (add-line line points# lines#)
(match-define (list _ dir ps _) line)
(for/fold ((p# points#) (l# lines#)) ((p (in-list ps)))
(values (hash-set p# p #t) (hash-set l# (cons dir p) #t)))))
(module player racket/base
(require racket/match
(submod ".." rules))
(provide play-game
random-line-chooser)
(define (random-line-chooser p# l# options)
(list-ref options (random (length options))))
;; line-chooser (points lines (Listof line) -> line)
(define (play-game line-chooser (o# (game-cross)))
(let loop ((points# o#)
(lines# (hash))
(rv null))
(match (available-lines points# lines#)
[(list) (values points# (reverse rv) o#)]
[options
(match-define (and chosen-one (list (cons x y) d _ new-edge-point))
(line-chooser points# lines# options))
(define-values (p# l#) (add-line chosen-one points# lines#))
(loop p# l# (cons (vector x y d new-edge-point) rv))]))))
;; [Render module code goes here]
(module main racket/base
(require (submod ".." render)
(submod ".." player)
pict
racket/class)
(define p (call-with-values (λ () (play-game random-line-chooser)) render-state))
p
(define bmp (pict->bitmap p))
(send bmp save-file "images/morpion.png" 'png))
Intermission: The render
submodule just does drawing, and is not part of the solving. But the main
module uses it, so we put it in here:
(module render racket
(require racket/match
racket/draw
pict
(submod ".." rules))
(provide display-state
render-state)
(define (min/max-point-coords p#)
(for/fold ((min-x #f) (min-y #f) (max-x #f) (max-y #f))
((k (in-hash-keys p#)))
(match-define (cons x y) k)
(if min-x
(values (min min-x x) (min min-y y) (max max-x x) (max max-y y))
(values x y x y))))
(define (draw-text/centered dc x y t ->x ->y)
(define-values (w h b v) (send dc get-text-extent t))
(send dc draw-text t (- (->x x) (* w 1/2)) (- (->y y) (* h 1/2))))
(define ((with-stored-dc-context draw-fn) dc w h)
(define old-brush (send dc get-brush))
(define old-pen (send dc get-pen))
(define old-font (send dc get-font))
(draw-fn dc w h)
(send* dc (set-brush old-brush) (set-pen old-pen) (set-font old-font)))
(define red-brush (new brush% [style 'solid] [color "red"]))
(define white-brush (new brush% [style 'solid] [color "white"]))
(define cyan-brush (new brush% [style 'solid] [color "cyan"]))
(define cyan-pen (new pen% [color "cyan"]))
(define black-pen (new pen% [color "black"]))
(define green-pen (new pen% [color "green"] [width 3]))
(define black-brush (new brush% [style 'solid] [color "black"]))
(define (render-state p# ls (o# (hash)))
(define-values (min-x min-y max-x max-y) (min/max-point-coords p#))
(define C 24)
(define R 8)
(define D (* R 2))
(define Rp 4)
(define (draw dc w h)
(define (->x x) (* C (- x min-x -1/2)))
(define (->y y) (* C (- y min-y -1/2 )))
(send dc set-brush cyan-brush)
(send dc set-pen cyan-pen)
(send dc set-font (make-object font% R 'default))
(for ((y (in-range min-y (add1 max-y))))
(send dc draw-line (->x min-x) (->y y) (->x max-x) (->y y))
(for ((x (in-range min-x (add1 max-x))))
(send dc draw-line (->x x) (->y min-y) (->x x) (->y max-y))))
(send dc set-pen black-pen)
(for ((l (in-list ls)))
(match-define (vector x y d (cons ex ey)) l)
(define-values (dx dy) (line-dx.dy d))
(define x1 (+ x (* 4 dx)))
(define y1 (+ y (* 4 dy)))
(send* dc (draw-line (->x x) (->y y) (->x x1) (->y y1))))
(for* ((y (in-range min-y (add1 max-y)))
(x (in-range min-x (add1 max-x))))
(define k (cons x y))
(cond [(hash-has-key? o# k)
(send dc set-brush red-brush)
(send dc draw-ellipse (- (->x x) R) (- (->y y) R) D D)]
[(hash-has-key? p# k)
(send dc set-brush white-brush)
(send dc draw-ellipse (- (->x x) R) (- (->y y) R) D D)]))
(send dc set-brush black-brush)
(for ((l (in-list ls))
(i (in-naturals 1)))
(match-define (vector _ _ d (cons ex ey)) l)
(define-values (dx dy) (line-dx.dy d))
(define R.dx (* R dx 0.6))
(define R.dy (* R dy 0.6))
(send* dc
(set-pen green-pen)
(draw-line (- (->x ex) R.dx) (- (->y ey) R.dy) (+ (->x ex) R.dx) (+ (->y ey) R.dy))
(set-pen black-pen))
(draw-text/centered dc ex ey (~a i) ->x ->y)))
(define P (dc (with-stored-dc-context draw) (* C (- max-x min-x -1)) (* C (- max-y min-y -1))))
(printf "~s~%~a points ~a lines~%" ls (hash-count p#) (length ls))
P)
(define (display-state p# l (o# (hash)))
(define-values (min-x min-y max-x max-y) (min/max-point-coords p#))
(for ((y (in-range min-y (add1 max-y)))
#:when (unless (= y min-y) (newline))
(x (in-range min-x (add1 max-x))))
(define k (cons x y))
(write-char
(cond [(hash-has-key? o# k) #\+]
[(hash-has-key? p# k) #\.]
[else #\space])))
(printf "~s~%~a points ~a lines~%" l (hash-count p#) (length l))))
- Output:
Here is the text output of one run, and if you're (I'm) lucky, there's a picture attached:
(#(9 6 n (9 . 2)) #(4 3 w (4 . 3)) #(7 9 w (7 . 9)) #(8 3 w (5 . 3)) #(3 9 n (3 . 5)) #(0 7 n (0 . 7)) #(6 3 n (6 . -1)) #(7 0 w (7 . 0)) #(3 3 n (3 . -1)) #(4 6 w (4 . 6)) #(2 6 ne (4 . 4)) #(6 9 n (6 . 5)) #(0 4 ne (2 . 2)) #(9 4 nw (7 . 2)) #(8 6 w (5 . 6)) #(4 9 nw (2 . 7)) #(7 9 nw (5 . 7)) #(7 6 nw (5 . 4)) #(2 7 ne (4 . 5)) #(7 3 nw (5 . 1)) #(5 7 n (5 . 5)) #(7 5 w (7 . 5)) #(5 6 ne (7 . 4)) #(6 7 nw (3 . 4)) #(0 7 ne (2 . 5)) #(7 7 nw (7 . 7)) #(6 8 ne (10 . 4)) #(2 6 n (2 . 4)) #(5 7 ne (8 . 4)) #(5 4 w (1 . 4)) #(1 4 ne (4 . 1)) #(7 7 w (4 . 7)) #(4 9 n (4 . 8)) #(7 4 n (7 . 1)) #(7 4 nw (5 . 2)) #(11 4 w (11 . 4)) #(7 9 n (7 . 8)) #(5 3 n (5 . -1)) #(7 2 w (4 . 2)) #(8 6 nw (6 . 4)) #(7 8 w (5 . 8)) #(3 10 ne (3 . 10)) #(5 9 nw (1 . 5)) #(4 3 ne (8 . -1)) #(-1 7 ne (-1 . 7)) #(1 6 n (1 . 2)) #(6 1 w (2 . 1)) #(10 4 nw (8 . 2)) #(3 5 w (-1 . 5)) #(8 6 n (8 . 5)) #(-1 4 ne (-1 . 4)) #(5 5 ne (9 . 1)) #(3 6 nw (-1 . 2)) #(3 3 ne (7 . -1)) #(7 -1 w (4 . -1)) #(7 10 nw (7 . 10)) #(3 2 w (0 . 2)) #(3 5 nw (-1 . 1)) #(-1 5 n (-1 . 3)) #(3 7 w (1 . 7)) #(3 9 nw (2 . 8)) #(1 9 ne (1 . 9)) #(4 2 n (4 . -2))) 99 points 63 lines
REXX
This REXX program is an attempt to play (badly, and with random moves) the game of Morpion solitaire by a computer.
The program also allows a carbon-based life form (er, that is, a human) to play.
This is a work in progress and currently doesn't log the moves in the manner asked for by this task.
The moves are marked by 0123456789ABC...XYZabc...xyz()[]{}<>«» and thereafter by a plus sign (+) on the board which is shown in 2D.
This allows 73 unique moves to be shown on the board (or grid), but all moves are also logged to a file.
Currently, the computer tries to start the game (with sixteen moves) by the assumptions I made, which clearly aren't worth a tinker's dam.
This program allows the D or T forms of the game, and allows any board size (grid size) of three or higher.
The default games is 5T
/*REXX program plays Morpion solitaire (with grid output), the default is the 5T version*/
signal on syntax; signal on noValue /*handle possible REXX program errors. */
/* [↓] handle the user options (if any)*/
prompt= /*null string is used for ERR return.*/
quiet= 0 /*flag: suppresses output temporarily.*/
oFID= 'MORPION' /*filename of the game's output file. */
arg game player seed . /*see if a person wants to play. */
if game=='' | game=="," then game= '5T' /*Not specified? Then use the default.*/
if player=='' | player=="," then player= /* " " " " " " */
if isInt(seed) then call random ,,seed /*Is integer? Then use for RANDOM seed*/
TorD= 'T (touching) ───or─── D (disjoint).' /*the valid game types (T or D). */
sw= linesize() - 1 /*SW = screen width ─or─ linesize. */
gT= right(game, 1) /*T = touching ─or─ D = disjoint.*/
if \datatype(gT,'U') | verify(gT, "GT")\==0 then call err 'game not G or T' /*error?*/
gS= left( game, length(game) - 1) /*gS=Game Size (line length for a win)*/
if \isInt(gS) then call err "game size isn't an integer:" gS /*error?*/
gS= gS / 1 /*normalize the value of GS. */
if gS<3 then call err "grid size is too small for Morpion solitaire :" gS /*error? */
/*handle the defaults/configuration. */
indent= left('', max(0, sw - gS - 10) % 2) /*indentation used for board display. */
indent= ' '
empty= 'fa'x /*the empty grid point symbol (glyph). */
@.= empty /*the field (grid) is infinite in size*/
CBLF= player \== '' /*playing with a carbon─based lifeform?*/
if CBLF then oFID= player /*oFID: the fileID for the game LOG. */
oFID= oFID'.LOG' /*full name for the LOG's filename. */
prompt= 'enter X,Y point and an optional character for placing on board (or Quit):'
prompt= right(prompt, sw, '─') /*right justify the prompt message. */
call GreekX /*draw the (initial) Greek cross. */
do #=1 for 1500 /*───play a game of Morpion solitaire. */
if CBLF then do
if Gshots\=='' then do; parse var Gshots shot Gshots
parse var shot gx ',' gy
call mark gx,gy
iterate
end
if Gshots=='' then leave /*#*/
call t prompt; pull stuff; stuff= translate(stuff, , ',')
stuff= space(stuff); parse var stuff px py p
_= px; upper _; if abbrev('QUIT', _, 1) then exit /*quitting? */
if stuff=='' then do; call display; iterate
end
call mark px,py,p
end /*if CBLF*/
else do; quiet= 1; shot= translate( word(Gshots, turn), , ',')
if shot=='' then do 50
xr= loX -1 + random(0, hiX - loX + 2)
yr= loY -1 + random(0, hiY - loY + 2)
if @.xr.yr\==empty then iterate
if \neighbor(xr, yr) then iterate
shot= xr yr
end /*50*/
call mark word(shot, 1), word(shot, 2)
end /*else*/
end /*#*/
call display
call t '* number of wins =' wins
exit wins /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Gshot: if arg()==2 then Gshots= space(Gshots arg(1)','arg(2) ); return
isInt: return datatype( arg(1), 'W') /*is int? */
isNum: return datatype( arg(1), 'N') /*is num? */
t: say arg(1); call lineout oFID,arg(1); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
?win: arg z; L= length(z)
if L>gS then do; if gT=='D' then return 0 /*longlines ¬ kosker for D*/
parse var z z1 '?' z2 /*could be xxxxx?xxxx */
return length(z1)>=4 | length(z2)>=4
end
return L==gS
/*──────────────────────────────────────────────────────────────────────────────────────*/
display: call t; do y=hiY to loY by -1; _c= /*start at a high Y. */
do x=loX to hiX; != @.x.y; _c= _c || ! /*build an "X" grid line. */
end /*x*/
call t indent _c /*display a grid line. */
end /*y*/
if wins==0 then call t copies('═', sw)
else call t right('(above) the board after' wins "turns.", sw, '═')
call t
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
err: if \quiet then do; call t; call t
call t center(' error ', max(40, sw % 2), "*"); call t
do j=1 for arg(); call t arg(j); call t; end; call t
end
if prompt=='' then exit 13; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
GreekX: wins= 0; loX= 1; hiX= 0; LB= gS - 1 /*Low cross Beam. */
turn= 1; loY= 1; hiY= 0; HT= 4 + 3*(LB-2) /*─ ─ */
Lintel= LB - 2; Gshots=; TB= HT - LB + 1 /*Top cross Beam. */
$= '0f'x; @@.= /*─ ─ */
do y=1 for HT; ToB= $ || copies($, Lintel) || $ /*ToB: Top Or Bot.*/
beam= $ || copies($, Lintel)$ || left('', Lintel)$ || copies($, Lintel) || $
select /*$: Greek cross glyph*/
when y==1 | y==HT then do x=1 for LB; call place x+LB-1,y,substr(ToB, x, 1)
end
when y==LB | y==TB then do x=1 for HT; if x>LB & x<TB then iterate
call place x,y,substr(beam, x, 1)
end
when y>LB & y<TB then do x=1 by HT-1 for 2; call place x,y,$; end
otherwise do x=LB by TB-LB for 2; call place x,y,$; end
end /*select*/
end /*y*/
@abc= 'abcdefghijklmnopqrstuvwxyz'; @chars= '1234567890'translate(@abc) || @abc
@@.63= '@' ; @@.64= "æÆα"; @@.67= 'ß' ; @@.68= "¢" ; @@.69= '^'
@@.70= 'Σ' ; @@.71= "ƒ" ; @@.72= 'ñÑπ'; @@.75= "σΘφ"; @@.78= '₧'
@@.79= '$δ'; @@.81= "¥" ; @@.82= '#%&*=+\;'
do j=60 to 99; @chars= @chars || @@.j
end /*j*/
@chars= @chars'()[]{}<>«»' /*can't contain "empty", ?, blank.*/
call display
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
mark: parse arg xx,yy,pointChar /*place marker, check for errors. */
if pointChar=='' then pointChar= word( substr(@chars, turn, 1) "+", 1)
xxcyy= xx','yy; _.1= xx; _.2= yy
do j=1 for 2; XorY= substr('XY', j, 1) /*make sure X and Y are integers. */
if _.j=='' then do; call err XorY "wasn't specified." ;return 0; end
if \isNum(_.j) then do; call err XorY "isn't numeric:" _.j ; return 0; end
if \isInt(_.j) then do; call err XorY "isn't an integer:" _.j; return 0; end
end /*j*/
xx= xx / 1; yy= yy / 1 /*normalize integers: + 7 or 5.0*/
if pointChar==empty |,
pointChar=='?' then do; call err 'illegal point character:' pointChar; return 0
end
if @.xx.yy\==empty then do; call err 'point' xxcyy "is already occupied."; return 0
end
if \neighbor(xx,yy) then do; call err "point" xxcyy "is a bad move." ; return 0
end
call place xx,yy,'?'
newWins= seeIfWin()
if newWins==0 then do; call err 'point' xxcyy "isn't a good move."
@.xx.yy= empty; return 0
end
call t "move" turn ' ('xx","yy') with "'pointChar'"'
wins= wins + newWins; @.xx.yy= pointChar
call display; turn= turn + 1
return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
neighbor: parse arg a,b; am= a - 1; ap= a + 1; bm= b - 1; bp= b + 1
return @.am.b\==empty | @.am.bm\==empty | @.ap.b\==empty | @.am.bp \== empty |,
@.a.bm\==empty | @.ap.bm\==empty | @.a.bp\==empty | @.ap.bp\==empty
/*──────────────────────────────────────────────────────────────────────────────────────*/
noValue: syntax: prompt=; quiet= 0
call err 'REXX program' condition('C') "error", condition('D'), ,
"REXX source statement (line" sigl"):", sourceline(sigl)
/*──────────────────────────────────────────────────────────────────────────────────────*/
place: parse arg xxp,yyp /*place a marker (point) on grid.*/
loX= min(loX, xxp); hiX= max(hiX, xxp)
loY= min(loY, yyp); hiY= max(hiY, yyp); @.xxp.yyp= arg(3)
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
seeIfWin: y=yy; z= @.xx.yy /*count horizontal/vertical/diagonal wins.*/
do x=xx+1; if @.x.y==empty then leave; z= z||@.x.y; end
do x=xx-1 by -1; if @.x.y==empty then leave; z= @.x.y||z; end
if ?win(z) then return 1 /*────────count wins in horizontal line. */
x= xx; z= @.xx.yy
do y=yy+1; if @.x.y==empty then leave; z= z||@.x.y; end
do y=yy-1 by -1; if @.x.y==empty then leave; z= @.x.y||z; end
if ?win(z) then return 1 /*────────count wins in vertical line. */
x= xx; z= @.xx.yy
do y=yy+1; x= x + 1; if @.x.y==empty then leave; z= z||@.x.y; end
x= xx
do y=yy-1 by -1; x=x-1; if @.x.y==empty then leave; z= @.x.y||z; end
if ?win(z) then return 1 /*──────count diag wins: up & >, down & < */
x= xx; z= @.xx.yy
do y=yy+1; x= x - 1; if @.x.y==empty then leave; z= z||@.x.y; end
x= xx
do y=yy-1 by -1; x=x+1; if @.x.y==empty then leave; z= z||@.x.y; end
return ?win(z) /*──────count diag wins: up & <, down & > */
This REXX program makes use of LINESIZE REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).
The LINESIZE.REX REXX program is included here ──► LINESIZE.REX.
- output when running 1,500 trials, the highest win was a meager 47 (four games, all different), and one of them is shown below.
···☼☼☼☼··· ···☼··☼··· ···☼··☼··· ☼☼☼☼··☼☼☼☼ ☼········☼ ☼········☼ ☼☼☼☼··☼☼☼☼ ···☼··☼··· ···☼··☼··· ···☼☼☼☼··· ═══════════════════════════════════════════════════════════════════════════════ move 1 (11,4) with "1" ··········· ···☼☼☼☼···· ···☼··☼···· ···☼··☼···· ☼☼☼☼··☼☼☼☼· ☼········☼· ☼········☼· ☼☼☼☼··☼☼☼☼1 ···☼··☼···· ···☼··☼···· ···☼☼☼☼···· ═══════════════════════════════════════════════(above) the board after 1 turns. move 2 (4,5) with "2" ··········· ···☼☼☼☼···· ···☼··☼···· ···☼··☼···· ☼☼☼☼··☼☼☼☼· ☼········☼· ☼··2·····☼· ☼☼☼☼··☼☼☼☼1 ···☼··☼···· ···☼··☼···· ···☼☼☼☼···· ═══════════════════════════════════════════════(above) the board after 2 turns. ... previous 46 moves elided ... above is the initial board (grid) ... --- the next line means: 47th move, position=9,9 marked with an "k" --- move 47 (9,9) with "k" ···iQagP···· ·j·d☼☼☼☼F··· ··hO☼NL☼ck·· ·CZ1☼bK☼3MD· X☼☼☼☼57☼☼☼☼f ·☼YHASGBJR☼· ·☼UT8I·9·e☼· ·☼☼☼☼46☼☼☼☼· V··0☼W·☼2··· ····☼··☼···· ····☼☼☼☼E··· ═════════════════════════════════════════════════════ count of (above) wins = 47 * number of wins = 47
Wren
An embedded program so we can use the ncurses library.
/* Morpion_solitaire.wren */
import "random" for Random
import "./dynamic" for Flags, Struct
import "./fmt" for Conv
class Ncurses {
foreign static initscr()
foreign static cbreak()
foreign static nocbreak()
foreign static echo()
foreign static noecho()
foreign static refresh()
foreign static getch()
foreign static mvprintw(y, x, str)
foreign static timeout(delay)
foreign static endwin()
}
class C {
foreign static usleep(usec)
}
// optional settings
var lineLen = 5
var disjoint = 0
var fields = [
"blank", "occupied", "dirNS", "dirEW",
"dirNESW", "dirNWSE", "newlyAdded", "current"
]
var State = Flags.create("State", fields, true)
var ofs = [
[0, 1, State.dirNS],
[1, 0, State.dirEW],
[1, -1, State.dirNESW],
[1, 1, State.dirNWSE]
]
var Move = Struct.create("Move", ["m", "s", "seq", "x", "y"])
var rand = Random.new()
var board
var width
var height
var allocBoard = Fn.new { |w, h|
var buf = List.filled(h, null)
for (i in 0...h) buf[i] = List.filled(w, 0)
return buf
}
var boardSet = Fn.new { |v, x0, y0, x1, y1|
for (i in y0..y1) {
for (j in x0..x1) board[i][j] = v
}
}
var initBoard = Fn.new {
width = height = 3 * (lineLen - 1)
board = allocBoard.call(width, height)
boardSet.call(State.occupied, lineLen-1, 1, 2*lineLen-3, height-2)
boardSet.call(State.occupied, 1, lineLen-1, width-2, 2*lineLen-3)
boardSet.call(State.blank, lineLen, 2, 2*lineLen-4, height-3)
boardSet.call(State.blank, 2, lineLen, width-3, 2*lineLen-4)
}
// -1: expand low index end; 1: expand high index end
var expandBoard = Fn.new { |dw, dh|
var dw2 = (dw == 0) ? 0 : 1
var dh2 = (dh == 0) ? 0 : 1
var nw = width + dw2
var nh = height + dh2
var nbuf = allocBoard.call(nw, nh)
dw = -Conv.btoi(dw < 0)
dh = -Conv.btoi(dh < 0)
for (i in 0...nh) {
if (i + dh < 0 || i + dh >= height) continue
for (j in 0...nw) {
if (j + dw < 0 || j + dw >= width) continue
nbuf[i][j] = board[i+dh][j+dw]
}
}
board = nbuf
width = nw
height = nh
}
var showBoard = Fn.new {
for (i in 0...height) {
for (j in 0...width){
var temp
if (board[i][j] & State.current != 0) {
temp = "X "
} else if (board[i][j] & State.newlyAdded != 0) {
temp = "O "
} else if (board[i][j] & State.occupied != 0) {
temp = "+ "
} else {
temp = " "
}
Ncurses.mvprintw(i + 1, j * 2, temp)
}
}
Ncurses.refresh()
}
// test if a point can complete a line, or take that point
var testPosition = Fn.new { |y, x, rec|
if (board[y][x] & State.occupied != 0) return
for (m in 0..3) { // 4 directions
var dx = ofs[m][0]
var dy = ofs[m][1]
var dir = ofs[m][2]
var s = 1 - lineLen
while (s <= 0) { // offset line
var k = 0
while (k < lineLen) {
if (s + k == 0) {
k = k + 1
continue
}
var xx = x + dx * (s + k)
var yy = y + dy * (s + k)
if (xx < 0 || xx >= width || yy < 0 || yy >= height) break
// no piece at position
if (board[yy][xx] & State.occupied == 0) break
// this direction taken
if (board[yy][xx] & dir != 0) break
k = k + 1
}
if (k == lineLen) {
// position ok
// random integer to even each option's chance of being picked
rec.seq = rec.seq + 1
if (rand.int(rec.seq) == 0) {
rec.m = m
rec.s = s
rec.x = x
rec.y = y
}
}
s = s + 1
}
}
}
var addPiece = Fn.new { |rec|
var dx = ofs[rec.m][0]
var dy = ofs[rec.m][1]
var dir = ofs[rec.m][2]
board[rec.y][rec.x] = board[rec.y][rec.x] | (State.current | State.occupied)
for (k in 0...lineLen) {
var xx = rec.x + dx * (k + rec.s)
var yy = rec.y + dy * (k + rec.s)
board[yy][xx] = board[yy][xx] | State.newlyAdded
if (k >= disjoint || k < lineLen-disjoint) {
board[yy][xx] = board[yy][xx] | dir
}
}
}
var nextMove = Fn.new {
var rec = Move.new(0, 0, 0, 0, 0)
// wipe last iteration's new line markers
for (i in 0...height) {
for (j in 0...width) {
board[i][j] = board[i][j] & ~(State.newlyAdded | State.current)
}
}
// randomly pick one of next legal moves
for (i in 0...height) {
for (j in 0...width) testPosition.call(i, j, rec)
}
// didn't find any move, game over
if (rec.seq == 0) return false
addPiece.call(rec)
if (rec.x == width-1) {
rec.x = 1
} else if (rec.x != 0) {
rec.x = 0
} else {
rec.x = -1
}
if (rec.y == height-1) {
rec.y = 1
} else if (rec.y != 0) {
rec.y = 0
} else {
rec.y = -1
}
if (rec.x != 0 || rec.y != 0) expandBoard.call(rec.x, rec.y)
return true
}
initBoard.call()
Ncurses.initscr()
Ncurses.noecho()
Ncurses.cbreak()
var ch = 0
var move = 0
var waitKey = true
while (true) {
Ncurses.mvprintw(0, 0, "Move %(move)")
move = move + 1
showBoard.call()
if (!nextMove.call()) {
nextMove.call()
showBoard.call()
break
}
if (!waitKey) C.usleep(100000)
if ((ch = Ncurses.getch()) == 32) { // spacebar pressed
waitKey = !waitKey
if (waitKey) {
Ncurses.timeout(-1)
} else {
Ncurses.timeout(0)
}
}
if (ch == 113) break // 'q' pressed
}
Ncurses.timeout(-1)
Ncurses.nocbreak()
Ncurses.echo()
Ncurses.endwin()
We now embed the above script in the following C program, build and run it.
/* gcc Morpion_solitaire.c -o Morpion_solitaire -lncurses -lwren -lm */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ncurses.h>
#include <unistd.h>
#include "wren.h"
/* C <=> Wren interface functions */
void C_initscr(WrenVM* vm) {
initscr();
}
void C_cbreak(WrenVM* vm) {
cbreak();
}
void C_nocbreak(WrenVM* vm) {
nocbreak();
}
void C_echo(WrenVM* vm) {
echo();
}
void C_noecho(WrenVM* vm) {
noecho();
}
void C_refresh(WrenVM* vm) {
refresh();
}
void C_getch(WrenVM* vm) {
int ch = getch();
wrenSetSlotDouble(vm, 0, (double)ch);
}
void C_mvprintw(WrenVM* vm) {
int y = (int)wrenGetSlotDouble(vm, 1);
int x = (int)wrenGetSlotDouble(vm, 2);
const char *str = wrenGetSlotString(vm, 3);
mvprintw(y, x, "%s", str);
}
void C_timeout(WrenVM* vm) {
int delay = (int)wrenGetSlotDouble(vm, 1);
timeout(delay);
}
void C_endwin(WrenVM* vm) {
endwin();
}
void C_usleep(WrenVM* vm) {
useconds_t usec = (useconds_t)wrenGetSlotDouble(vm, 1);
usleep(usec);
}
WrenForeignMethodFn bindForeignMethod(
WrenVM* vm,
const char* module,
const char* className,
bool isStatic,
const char* signature) {
if (strcmp(module, "main") == 0) {
if (strcmp(className, "Ncurses") == 0) {
if (isStatic && strcmp(signature, "initscr()") == 0) return C_initscr;
if (isStatic && strcmp(signature, "cbreak()") == 0) return C_cbreak;
if (isStatic && strcmp(signature, "noecho()") == 0) return C_noecho;
if (isStatic && strcmp(signature, "nocbreak()") == 0) return C_nocbreak;
if (isStatic && strcmp(signature, "echo()") == 0) return C_echo;
if (isStatic && strcmp(signature, "refresh()") == 0) return C_refresh;
if (isStatic && strcmp(signature, "getch()") == 0) return C_getch;
if (isStatic && strcmp(signature, "mvprintw(_,_,_)") == 0) return C_mvprintw;
if (isStatic && strcmp(signature, "timeout(_)") == 0) return C_timeout;
if (isStatic && strcmp(signature, "endwin()") == 0) return C_endwin;
} else if (strcmp(className, "C") == 0) {
if (isStatic && strcmp(signature, "usleep(_)") == 0) return C_usleep;
}
}
return NULL;
}
static void writeFn(WrenVM* vm, const char* text) {
printf("%s", text);
}
void errorFn(WrenVM* vm, WrenErrorType errorType, const char* module, const int line, const char* msg) {
switch (errorType) {
case WREN_ERROR_COMPILE:
printf("[%s line %d] [Error] %s\n", module, line, msg);
break;
case WREN_ERROR_STACK_TRACE:
printf("[%s line %d] in %s\n", module, line, msg);
break;
case WREN_ERROR_RUNTIME:
printf("[Runtime Error] %s\n", msg);
break;
}
}
char *readFile(const char *fileName) {
FILE *f = fopen(fileName, "r");
fseek(f, 0, SEEK_END);
long fsize = ftell(f);
rewind(f);
char *script = malloc(fsize + 1);
fread(script, 1, fsize, f);
fclose(f);
script[fsize] = 0;
return script;
}
static void loadModuleComplete(WrenVM* vm, const char* module, WrenLoadModuleResult result) {
if( result.source) free((void*)result.source);
}
WrenLoadModuleResult loadModule(WrenVM* vm, const char* name) {
WrenLoadModuleResult result = {0};
if (strcmp(name, "random") != 0 && strcmp(name, "meta") != 0) {
result.onComplete = loadModuleComplete;
char fullName[strlen(name) + 6];
strcpy(fullName, name);
strcat(fullName, ".wren");
result.source = readFile(fullName);
}
return result;
}
int main(int argc, char **argv) {
WrenConfiguration config;
wrenInitConfiguration(&config);
config.writeFn = &writeFn;
config.errorFn = &errorFn;
config.bindForeignMethodFn = &bindForeignMethod;
config.loadModuleFn = &loadModule;
WrenVM* vm = wrenNewVM(&config);
const char* module = "main";
const char* fileName = "Morpion_solitaire.wren";
char *script = readFile(fileName);
WrenInterpretResult result = wrenInterpret(vm, module, script);
switch (result) {
case WREN_RESULT_COMPILE_ERROR:
printf("Compile Error!\n");
break;
case WREN_RESULT_RUNTIME_ERROR:
printf("Runtime Error!\n");
usleep(10000000); // allow time to read it
timeout(-1);
nocbreak();
echo();
endwin();
break;
case WREN_RESULT_SUCCESS:
break;
}
wrenFreeVM(vm);
free(script);
return 0;
}