Essays/moo

From J Wiki
Jump to: navigation, search

The "moo" (Mastermind) game is described in the Unix man pages:

NAME

moo - guessing game

SYNOPSIS

/usr/games/moo

DESCRIPTION

moo is a guessing game imported from England. The computer picks a number consisting of four distinct decimal digits. The player guesses four distinct digits being scored on each guess. A cow is a correct digit in an incorrect position. A bull is a correct digit in a correct position. The game continues until the player guesses the number (a score of four bulls).

load '~addons/general/misc/prompt.ijs'  NB. needs "prompt" from "misc"

display=: 1!:2&2

univ   =: (*./@(~:"1) # ]) @ (#: i.@(*/))

guess  =: ?@# { ]
score  =: ; prompt@(,&'   ')@":
solved =: (('b' $~ $@[) -: ])&>/@[
bull   =: +/@('b'&=)@(>@{:@[) = >@{.@[ +/@(="1) ]
bc     =: #@(>@{:@[) = ] +/@e."1 >@{.@[
prune  =: ((bull *. bc) # ]) ` (''"_) @. solved

s0     =: display@('no choices left'&[)
s1     =: display@('one choice left; it must be '&,)@":@,
sn     =: display@(,&' choices left')@":@#
state  =: s0`s1`sn@.(0 1 i. #) ` ] @. ('' -: ])

moo1   =: ([state)@(score@guess prune ])^:(1<#)
moo    =: moo1^:_ @ univ

The program above plays the guesser in the game of moo. The algorithm was described to me in 1976 by Fred Appleyard of I.P. Sharp Associates, Calgary: A universe of remaining choices is kept. At each round, the computer selects a guess at random from the universe, then prunes the universe according to the guess and its score of bulls and cows.

The definitions are divided into groups:

display displays the string argument on the screen.

univ generates the initial universe of choices given an integer list of the upper limits for each position. e.g. univ 4$10 or univ 10 11 12 .

score displays an integer list on the screen, solicits a score from the keyboard, and returns a list of the score and the guess individually boxed. guess selects a guess at random from the universe.  solved is 1 if the score is all b's.  bull scores each choice in the universe regarding bulls; bc regarding bulls and cows.  prune discards remaining choices from the universe inconsistent with the guess and its score.

state shows the size of the current universe.

moo plays the guesser in the game of moo. The argument is an integer list of the upper limits for each position. (e.g. moo 4$10 would be the game as described in the man page.) In each round, moo

  • checks that the universe contains more than one choice;
  • selects a guess at random and solicits its score;
  • prunes the universe; and
  • displays the state.

The following example shows the program in action on guessing the number 1 2 3 4.

   moo 4$10
6 7 0 3   c
1440 choices left
7 8 5 1   c
378 choices left
2 4 3 8   bcc
30 choices left
2 3 4 5   ccc
3 choices left
1 2 3 4   bbbb

   moo 4$10
7 6 9 0
360 choices left
8 4 1 5   cc
84 choices left
4 5 2 3   ccc
24 choices left
3 2 4 1   bccc
2 choices left
1 3 4 2   bccc
one choice left; it must be 1 2 3 4
1 2 3 4

If the target number can have duplicate digits, the scoring instructions needed to be amended to say: the number of bulls and cows for a digit must not exceed the number of times that that digit occurs in the target. For example, if the target is 1 4 3 3 and the guess is 0 4 4 4 , then the score should be b and not bcc .

And the following modifications to the program suffice:

univ   =: #: i.@(*/)
bc     =: #@(>@{:@[) = ] ([ +/@:([ <. -~) #@[ {. ])&(#/.~)"1 ],"1 >@{.@[



See also


Contributed by Roger Hui. Substantially the same text previously appeared in a post to the comp.lang.apl newsgroup on 1992-12-13.