mastermind.a68

     
   1  COMMENT
   2  
   3  @section Synopsis
   4  
   5  Break a unique code of `n' pegs and `m' colours you think of.
   6  
   7  COMMENT
   8  
   9  INT pegs = 4, colours = 6;
  10  
  11  MODE LIST = FLEX [1 : 0] COMBINATION, 
  12       COMBINATION = [pegs] COLOUR, 
  13       COLOUR = INT;
  14  
  15  OP +:= = (REF LIST u, COMBINATION v) REF LIST:
  16     # Add one combination to a list. #
  17     ([UPB u + 1] COMBINATION w; w[ : UPB u] := u; w[UPB w] := v; u := w);
  18  
  19  PROC gen = (REF COMBINATION part, INT peg) VOID:
  20       # Generate all unique [colours!/(colours-pegs)!] combinations. #
  21       IF peg > pegs
  22       THEN all combinations +:= part
  23       ELSE FOR i TO colours
  24            DO IF BOOL unique := TRUE;
  25                  FOR j TO peg - 1 WHILE unique
  26                  DO unique := part[j] ~= i
  27                  OD;
  28                  unique
  29               THEN part[peg] := i;
  30                    gen (part, peg + 1)
  31               FI
  32            OD
  33       FI;
  34  
  35  LIST all combinations;
  36  gen (LOC COMBINATION, 1);
  37  
  38  PROC break code = (LIST sieved) VOID:
  39       # Present a trial and sieve the list with the entered score. #
  40       CASE UPB sieved + 1
  41       IN # No elements. # printf ($l"Inconsistent scores"$),
  42          # One element. # printf (($l"Solution is "4(xd)$, sieved[1]))
  43       OUT printf (($l"["g(0)"]"x4(xd)": "$, UPB sieved, sieved[1]));
  44       # Read the score as a sequence of "w" and "b". #
  45           INT col ok := 0, pos ok := 0, STRING z := "";
  46           WHILE z = ""
  47           DO read ((z, new line))
  48           OD;
  49           FOR i TO UPB z
  50           DO (z[i] = "w" | col ok |: z[i] = "b" | pos ok) +:= 1 
  51           OD;
  52           (pos ok = pegs | stop);
  53       # Survivors are combinations with score as entered. #
  54           LIST survivors;
  55           FOR i FROM 2 TO UPB sieved
  56           DO INT col ok i := 0, pos ok i := 0;
  57              FOR u TO pegs
  58              DO FOR v TO pegs
  59                 DO IF sieved[1][u] = sieved[i][v]
  60                    THEN (u = v | pos ok i | col ok i) +:= 1 
  61                    FI
  62                 OD
  63              OD;
  64              (col ok = col ok i AND pos ok = pos ok i | survivors +:= sieved[i])
  65           OD;
  66       # Solution must be among the survivors. #
  67           break code (survivors) 
  68       ESAC;
  69  
  70  break code (all combinations)