Deducer.frink

Download or view Deducer.frink in plain text format


/** This file contains classes, interface definitions, and algorithms for
    implementing a general deducer system that can solve problems / games
    like Mastermind, Wordle, Jotto, etc.

    To implement a problem or game, you will need to implement DeducerProblem,
    DeducerRank, and DeducerMove for that problem.  Currently, this involves
    implementing 5 methods, 3 of which are trivial (two toString, one equals),
    and the other two consist of 1.) enumerating all possible plays for the game
    and 2.) ranking a move.

    The Deducer class contains methods to manage the state of a game, to
    eliminate possibilities, to return possible moves, and to perform moves.

    For a sample implementation of the Mastermind game using this framework,
    see mastermindDeducer.frink
*/

class Deducer
{
   /** A DeducerProblem that represents the current problem or game. */
   var problem

   /** The remaining options in the game.  This is undef before initialization
       and an array otherwise. */

   var options

   /** Construct a new Deducer for the specific problem type. */
   new[problem is DeducerProblem] :=
   {
      this.problem = problem
      this.options = undef
   }

   /** Apply a move and reduce the number of remaining options.  This takes a
       move and its associated rank and keeps only the remaining moves that
       return the same rank.  The move should be an appropriate DeducerMove
       for the DeducerProblem.  */

   doMove[move is DeducerMove, moveRank is DeducerRank] :=
   {
      if options == undef
         initialize[]

      res = new array

      // Now test each move and see if playing that move gives the same
      // rank as playing this move.  If so, keep it.
      for target = options
         if problem.rank[move, target].equals[moveRank]
            res.push[target]

      options = res      
   }

   /** Returns the number of remaining moves */
   numMovesRemaining[] :=
   {
      if options == undef
         initialize[]

      return length[options]
   }

   /** Returns the moves remaining as an array of DeducerMove. */
   movesRemaining[] :=
   {
      if options == undef
         initialize[]

      return options
   }

   /** Returns the remaining moves as an array of strings. */
   movesRemainingStr[] :=
   {
      if options == undef
         initialize[]

      res = new array
      for move = options
         res.push[move.toString[]]

      return res
   }

   /** Initialize all options. */
   initialize[] :=
   {
      options = toArray[problem.allPossibleMoves[]]
   }

   /** Resets back to starting state. */
   reset[] :=
   {
      options = undef
   }
}


/** The DeducerProblem class describes an interface that is used to describe
    a problem or game. */

interface DeducerProblem
{
   /** Rank/score a particular move with respect to target and return an object
       of type DeducerRank */

   rank[move is DeducerMove, target is DeducerMove]

   /** Return all possible moves as an array or enumerating expression of
       DeducerMove appropriate for this problem. */

   allPossibleMoves[]
}


/** The DeducerRank interface describes the methods for ranking a particular
    move.  For example, a Mastermind ranking would include the count of black
    and white pegs.  For Wordle, this would indicate which letters are green,
    which are yellow, and which are black. */

interface DeducerRank
{
   /** Compares this rank with another rank and returns true if they are equal.

       Or you could even make the ranking lazy if you wanted.
   */

   equals[other is DeducerRank]

   /** Returns a string representation of the rank for display to a human. */
   toString[]
}


/** This represents a move for the particular problem or game. */
interface DeducerMove
{
   /** Returns a string representation of the move suitable for presenting to a
       human. */

   toString[]
}


Download or view Deducer.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19908 days, 6 hours, 23 minutes ago.