/** 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
   }

   /** Removes a random move from the moves remaining and returns it. */
   removeRandomMove[] :=
   {
      if options == undef
         initialize[]

      return options.removeRandom[]
   }

   /** Picks a "smart" move from the moves remaining and returns it.  The
       "smartness" of the rule is determined by the implementation of
       DeducerMove.compareTo[other]
   */
   pickSmartMove[numToTest=100] :=
   {
      if options == undef
         initialize[]

      bestIndex = undef
      bestMove = undef
      len = numMovesRemaining[]
      num = min[numToTest, len]
      chosenIndex = 0

      for i=0 to num-1
      {
         if numToTest >= len
            chosenIndex = i      // We're exhausively testing all items
         else
            chosenIndex = random[0, len-1]   // We're testing random items

         move = options@chosenIndex

         if bestMove == undef
         {
            bestMove = move
            bestIndex = chosenIndex
         } else
         {
            cmp = bestMove.compareTo[move]
            // If other is better, replace it.
            // If both moves are the same, replace at random.
            if (cmp == -1) or (cmp == 0 and random[0,1] == 0)
            {
               bestMove = move
               bestIndex = chosenIndex
            }
         }
      }

      return options.remove[bestIndex]
   }

   /** 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.
   */
   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
{
   /** Compares the value of this move to another move in an attempt to pick a
       "smarter" move.  For example, if a Wordle guess has more different
       letters, it would probably be considered a "better" guess.

       The function should return -1 if "this" move is worse than other,
                                   0 if both moves are equally good,
                                   1 if this move is better than other.

       (This is what is returned by the <=> three-way comparison operator.)

       If you don't really have a heuristic as to which guess is "smarter",
       this can just always return 0.
   */
   compareTo[other is DeducerMove]  
   
   /** Returns a string representation of the move suitable for presenting to a
       human. */
   toString[]
}