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 ‘double-twelve’ 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)

That 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

Factoring out the two tils:

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

Well, 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 0-0, 1-1, 1-0, 2-2, 2-1, …

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)

Now we are generating only and exactly the pairs we want.

q)mt3:{raze {x,'til x+1} each til 1+x}
q)count mt3 12
91

There is always a case for removing a nested lambda: x has different values in different parts of the line. How about a composition?

mt4:raze {x,'til x+1} each til 1+

Syntactic sugar for composition

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+

Finally we could use the ‘Zen monks’ pattern to replace the lambda with a composition (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 12-12 tile starts the game by laying it in the centre of the station hub. If no player has the 12-12 tile, players continue in turn to draw tiles until the 12-12 tile is drawn.

As a player you start your train with a tile 12-X. (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

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

We’ll use Converge to repeat a step until the result stabilises. The step takes a (train;hand) pair and returns a list of (train;hand) pairs.

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

Now we can generate candidate (train;hand) pairs.

xxt: raze xt each                                     / extend (train;hand) prs
can: xxt over en(en STARTER;HAND)                     / candidate chains

Above, 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)

until the trains stop growing.

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 uses reverse.

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 applies xt 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 list y of tiles. In xt make nt a list of tiles.
Where you find two or more candidate trains of the maximum length, prefer the one with more double-number 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?