Re: [QUIZ] Magic Fingers (#120)

Note:
This didn't seem to get through the first time I sent it. And now that I look
at the online archives, I see my solution to last weeks isn't there either.
Perhaps the list didn't like the fact that I attached zip files, which I did
merely for the convenience of the person that puts the solutions on
rubyquiz.com so they won't have to copy-paste. I'll resend my 119 solution
in a bit, which was long and ugly, but did handle things like parentheses.

---------------------------

Here's another long-winded solution from me. I'm not sure its correct, but for
a few small examples (2 & 3 fingers per hand), it seems to know when a win is
unavoidable given perfect play. There are 2 main classes that do the important
work:

State: This holds two Arrays, one for each player (@players). Each of those hold
       two numbers - how many fingers are on each hand. These are kept sorted,
       because it doesn't matter if you have 3-left and 2-right or 2-right and
       3-left. State also has a @turn, which designates who moves next, a
       @parent, for back-tracing through a state tree, and a @best_outcome,
       which holds a value assigned by StateTree. Only @players and @turn are
       taken into account by ==, eql?, and hash. State's each_reachable_state
       method yields for each state reachable from itself, using the touch and
       clap rules.

StateTree: This class holds a @root State, and a recursive best_outcome method.
           This method will be called for each reachable state from its
           argument. Whichever leads to the best outcome for that State's
           player (@turn) is returned.

Then there's a few other classes and modules, like Outcome, which holds
constants P1Win, P2Win, and Loop; and Game, which creates a StateTree, runs
best_outcome, and prints the results. The number of fingers per hand can be
changed from 5 in constants.rb.

There are some commented-out simple examples in magic_fingers.rb, which seem
to work:

> Game.new([1,1], [0,4]).analyze
Player 1, with perfect play, can win:
1: ----|  |---- *
2: -----  ||||-

1: ----|  |----
2: -----  ----- *

> Game.new([4,4], [1,1]).analyze
Player 1, with perfect play, can win:
1: -||||  ||||- *
2: ----|  |----

1: -||||  ||||-
2: -----  |---- *

1: -----  ||||- *
2: -----  |----

1: -----  ||||-
2: -----  ----- *

> Game.new([0,1], [3,3]).analyze
No matter how well Player 1 plays, Player 2 can win. For example:
1: -----  |---- *
2: --|||  |||--

1: -----  |----
2: --|||  ||||- *

1: -----  ----- *
2: --|||  ||||-

However, for the regular game:

> Game.new.analyze
Player 1 can stay in a loop.

So my program thinks player 1 can forever repeat a loop of game states,
but can't force a win. This contradicts my initial guess, but I don't
know if its correct, so I think I have a bug.

Here's the code:

#!/usr/bin/env ruby
# constants.rb

Left,    Right   = 0, 1 # hand array indices
Player1, Player2 = 0, 1 # player array indices
FingersPerHand   = 5


#!/usr/bin/env ruby
# outcome.rb

require 'constants'

module Outcome
  # Order important: from best-for-player-1 to best-for-player-2
  Outcome::P1Win   = 0
  Outcome::Loop    = 1
  Outcome::P2Win   = 2

  # Given an array of outcomes, return the one that is best for the given
  # player.
  def Outcome.best(player, outcomes)
    (player == Player1) ? outcomes.min : outcomes.max
  end
end


#!/usr/bin/env ruby
# state.rb

require 'constants'
require 'set'

# Represents one state of the game, which includes how many fingers are on each
# player's hands, and whose turn it is. States can also have parents, and a
# best_outcome can be assigned to them, though this class doesn't do anything
# with that itself. The player's hands are always sorted, since it doesn't
# matter having 3-left and 2-right is equivalent to 2-left and 3-right. When
# comparing states with ==, eql?, or their hashes, only @players and @turn are
# taken into account.
class State
  attr_reader :players, :turn, :parent, :best_outcome
  attr_writer :best_outcome

  # player_1 and player_2 are Arrays of number-of-fingers on each hand.
  def initialize(player_1, player_2, turn, parent = nil)
    @players = [player_1, player_2]
    @turn = turn
    @parent = parent
    @best_outcome = nil

    for player in @players do
      State.normalize(player)
    end

    self
  end

  def hand_alive?(player_num, hand_num)
    @players[player_num][hand_num] > 0
  end

  def player_alive?(player_num)
    hand_alive?(player_num, Left) or hand_alive?(player_num, Right)
  end

  # true if at least one player is dead.
  def end_state?
    not player_alive?(Player1) or not player_alive?(Player2)
  end

  # Return the winner. This should only be called on end states (otherwise,
  # it'll always return Player1).
  def winner
    player_alive?(Player1) ? Player1 : Player2
  end

  # Turn the given player's hand into a fist if it has >= FingesPerHand
  # fingers up, and sort the hands.
  def State.normalize(player)
    for hand_num in [Left, Right] do
      player[hand_num] = 0 if player[hand_num] >= FingersPerHand
    end
    player.sort!
  end

  # Return a nice string representation of a player.
  def player_string(player_num)
    player = @players[player_num]
    '-' * (FingersPerHand-player[Left]) +
      '|' * player[Left] +
      '  ' +
      '|' * player[Right] +
      '-' * (FingersPerHand-player[Right])
  end

  # Return a nice string representation of this state (including both player
  # strings).
  def to_s
    s = "1: #{player_string(Player1)}"
    s << ' *' if @turn == Player1
    s << "\n2: #{player_string(Player2)}"
    s << ' *' if @turn == Player2
    s
  end

  # Equality only tests the players' hands and the turn.
  def ==(other)
    @players == other.players and @turn == other.turn
  end

  # Both eql? and hash are defined so that Sets/Hashes of states will only
  # differentiate states based on @players and @turn.
  def eql?(other); self == other; end
  def hash; [@players, @turn].hash; end

  # Yield once for each ancestor state, starting from the oldest and ending on
  # this state.
  def each_ancestor
    ancestors = [self]
    while not ancestors.last.parent.nil?
      ancestors << ancestors.last.parent
    end
    ancestors.reverse_each { |a| yield a }
  end

  # Have one player (the toucher) touch the other player (the touchee).
  # Also, the touchee is then normalized.
  def State.touch(toucher, toucher_hand, touchee, touchee_hand)
    touchee[touchee_hand] += toucher[toucher_hand]
    State.normalize(touchee)
  end

  # Yield each state reachable from self.
  def each_reachable_state
    reachable = Set[] # use a Set instead of yielding as we find them to remove
                      # yielding duplicates.
    player = @players[@turn]
    opponent_num = (@turn + 1) % 2
    opponent = @players[opponent_num]

    # Touch rules.
    for player_hand in [Left, Right] do
      for opponent_hand in [Left, Right] do
        if hand_alive?(@turn, player_hand) and
            hand_alive?(opponent_num, opponent_hand)
          op = opponent.clone # because touch modifies it
          State.touch(player, player_hand, op, opponent_hand)
          if @turn == Player1
            reachable << State.new(player, op, opponent_num, self)
          else
            reachable << State.new(op, player, opponent_num, self)
          end
        end
      end
    end

    # Clap rules.
    for source_hand in [Left, Right] do
      target_hand = (source_hand == Left ? Right : Left)
      # The first line is the number that can be removed from the source.
      # The second is the number that can be added to the target without killing
      # it.
      max_transfer = [player[source_hand] - 1,
                     (FingersPerHand - player[target_hand] - 1)].min
      (1..max_transfer).each do |i|
        p = player.clone
        p[source_hand] -= i
        p[target_hand] += i
        State.normalize(p)
        if @turn == Player1
          reachable << State.new(p, opponent.clone, opponent_num, self)
        else
          reachable << State.new(opponent.clone, p, opponent_num, self)
        end
      end
    end

    reachable.each { |r| yield r }
  end
end


#!/usr/bin/env ruby
# state_tree.rb

require 'constants'
require 'state'
require 'outcome'

# Represents a tree of States in parent-child relationships.
class StateTree
  attr_reader :root, :p1_win_node, :p2_win_node, :loop_node

  def initialize(root = State.new([1,1], [1,1], Player1))
    @root = root
    @old_nodes = Set[@root]
    @p1_win_node = @p2_win_node = nil
    self
  end

  # Determine the best outcome at the given node, for that node's player.
  #
  # If Outcome::P1Win is returned, @p1_win_node will hold one way for player 1
  # to win. Likewise for Outcome::P2Win.
  #
  # Because @old_nodes is filled up as it runs, it can only be called once.
  # Can't clear out @old_nodes at the end of the method, since its recursive,
  # and the next level up depends on it. Could just create a wrapper method
  # to do that, though.
  def best_outcome(node = @root)
    reachable_outcomes = []

    node.each_reachable_state do |reached|
      if @old_nodes.include?(reached)
        if reached.best_outcome.nil?
          reachable_outcomes << Outcome::Loop
        else
          reachable_outcomes << reached.best_outcome
        end
      elsif reached.end_state?
        # Note that end states are never added to @old_nodes, because @old_nodes
        # is only used for loop-checking, and loops shouldn't include end
        # states.
        if reached.winner == Player1
          @p1_win_node = reached
          reachable_outcomes << Outcome::P1Win
        else
          @p2_win_node = reached
          reachable_outcomes << Outcome::P2Win
        end
      else
        @old_nodes << node
        reachable_outcomes << best_outcome(reached)
      end
    end

    node.best_outcome = Outcome.best(node.turn, reachable_outcomes)
  end
end


#!/usr/bin/env ruby
# game.rb

require 'constants'
require 'outcome'
require 'state'
require 'state_tree'

class Game
  # Constructor. p1_start and p2_start are Arrays containing the number of
  # fingers on each of their hands at the start of the game.
  def initialize(p1_start = [1,1], p2_start = [1,1])
    @state_tree = StateTree.new(State.new(p1_start, p2_start, Player1))
    self
  end

  # Print out an analysis of the game.
  def analyze
    outcome = @state_tree.best_outcome

    if outcome == Outcome::P1Win
      puts 'Player 1, with perfect play, can win:'
      @state_tree.p1_win_node.each_ancestor do |state|
        puts "#{state}\n\n"
      end
    elsif outcome == Outcome::P2Win
      puts 'No matter how well Player 1 plays, Player 2 can win. For example:'
      @state_tree.p2_win_node.each_ancestor do |state|
        puts "#{state}\n\n"
      end
    elsif outcome == Outcome::Loop
      puts 'Player 1 can stay in a loop.'
    else
      puts 'I am broken.'
    end
  end
end


#!/usr/bin/env ruby
# magic_fingers.rb

# Ruby Quiz 120: Magic Fingers

require 'game'

Game.new.analyze # Normal, default game.
#Game.new([1,1], [0,4]).analyze # P1 should win on move 1.
#Game.new([4,4], [1,1]).analyze # P1 should win on move 2.
#Game.new([0,1], [3,3]).analyze # P2 should win on move 2.

-- 
Jesse Merriman
[e-mail]
http://www.jessemerriman.com/