Mexican Train
Mexican Train is a game played with dominoes. The object of the game is for a player to play all the tiles from his or her hand onto one or more chains, or trains, emanating from a central hub or “station”. The game's most popular name comes from a special optional train that belongs to all players. — Wikipedia
Tiles
The game is played with tiles. Each tile bears spots corresponding to a pair of numbers.
In the ‘doubletwelve’ game, the numbers range from zero (no spots) to twelve. Each tile’s combination is unique; e.g, there is only one tile with both 7 and 5 spots.
Write an expression that generates the pairs for the 91 tiles of the ‘double twelve’ game.
Generate and filter
Knowing we want all possible combinations suggests using cross
.
q){x cross x} til 3
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Above, we see that 0 1
and 1 0
are actually duplicates.
We can remove these by sorting each tile and selecting the unique items.
q)count distinct asc each {x cross x} til 1+ 12
91
q)mt0: {distinct asc each {x cross x} til 1+x} / make tiles (lambda)
q)mt1: distinct (asc') {x cross x} til 1+ / make tiles (composition)
x cross x
is an example of ‘over computation’ common with array languages.
It is sometimes more efficient to use a simple expression that does too many quick calculations than to evaluate a more elaborate expression that performs fewer.
With small values of x
above, the over computation is probably defensible.
But we notice the work increases as the square of x
.
It is at least a useful exercise to consider alternatives.
Apply a mask
One would be to generate a mask to screen out duplicates rather than sorting and applying distinct
.
A familiarity with function tables will help us here.
q)".X" {x >=/:\: x}til 5
"X...."
"XX..."
"XXX.."
"XXXX."
"XXXXX"
q)({x cross x}til 5) where raze{x >=/:\: x}til 5
0 0
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
til
s:
q).[@] ({x cross x};where raze{x >=/:\:x}::)@\:til 5
0 0
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
q)mt2:.[@] (({x cross x};where raze{x >=/:\:x}::)@\:) til 1+
q)count mt2 12
91
mt2
uses indexing instead of asc'
and distinct
, but now we have two operations scaling as the square of x
.
Not an improvement.
Explicit iteration
Another way of describing the 91 tiles: each number 0–13 paired with itself and every number less than it. That is 00, 11, 10, 22, 21, …
q){x,'til x+1} each til 4
,0 0
(1 0;1 1)
(2 0;2 1;2 2)
(3 0;3 1;3 2;3 3)
q)mt3:{raze {x,'til x+1} each til 1+x}
q)count mt3 12
91
x
has different values in different parts of the line.
How about a composition?
mt4:raze {x,'til x+1} each til 1+
Of course, {x,'til x+1} each
is a projection.
It could also be written as a derived function.
mt5:raze ({x,'til x+1}') til 1+
(til')1+
that we both do and do not apply.
mt6:raze .[,''] ((til')1+)\[1;] til 1+
Iterator syntax
In mt6
Scan is used in the ‘Zen monks’ Do form 1 f\
, with composition (til')1+
as f
.
We can’t compose a variadic derived function f\
in infix syntax as 1 f\
– but we can project it with bracket syntax as f\[1;]
, giving us ((til')1+)\[1;]
.
Strategy
At the start of play each player draws 15 tiles. In the first round, the player with the 1212 tile starts the game by laying it in the centre of the station hub. If no player has the 1212 tile, players continue in turn to draw tiles until the 1212 tile is drawn.
As a player you start your train with a tile 12X. (If you do not have in your hand a tile with a 12 spot, draw tiles until you do.)
Extend your train by adding a tile with the same number of spots as the exposed end of the train does. For example, your train might begin
12 9
9 5
5 5
5 4
5 8
..
A simple strategy:
Find in your hand the longest train that starts with a 12.
(Assume your hand contains at least one tile with a 12.)
q)STARTER: 2#GAMESIZE: 12
q)/ aliases
q)en: enlist
q)ee: enlist each
q)tiles: mt6 GAMESIZE
q)show HAND:15?tiles except en STARTER
4 2
4 0
1 0
11 7
8 7
12 6
10 8
9 9
8 2
12 10
10 3
11 2
9 0
1 1
8 3
xt:{[(train;hand)] / extend train
spot: last[train]@1; / end spot
$[count nt: hand where spot in'hand; / next tiles?
(train,/:ee spot align'nt)(;)'hand except/:ee nt; / new trains
en(train;hand)] } / old train
xxt: raze xt each / extend (train;hand) prs
can: xxt over en(en STARTER;HAND) / candidate chains
xxt
applies xt
to each (train;hand) pair and razes the results to produce a new list of (train;hand) pairs.
The Converge form of Over repeatedly applies xxt
to the seed train
en(en STARTER;HAND)
Finally, we drop the STARTER
tile, which was never ours.
best: 1_ first {x where c=max c:count each x} can[;0]
Exercises

Notice in
xt
the use of(;)'
to convert a pair of lists into a list of pairs. How else might you do that?Answer
{(x;y)}'

Write a version of
align
that usesreverse
.Answer
align: {$[x=first y;y;reverse y]} align: {("j"$x<>first y)reverse/y}

Call a train that cannot be extended dead. The composition
xxt
appliesxt
even to dead trains. Incorporate a flag in the (train;hand) argument and use it to avoid retrying dead trains. 
Modify
align
to act on the first tile in a listy
of tiles. Inxt
makent
a list of tiles. 
Where you find two or more candidate trains of the maximum length, prefer the one with more doublenumber tiles preceding the end.

Where you find two or more candidate trains of the maximum length, prefer the one from whose remaining hand the longest train can be formed.

Can you devise a different strategy for finding the longest train?