--Boundary-00
LtJGEH0xbm6z8m
Content-Type: Multipart/Mixed;
  boundaryoundary-00
LtJGEH0xbm6z8m"

--Boundary-00
LtJGEH0xbm6z8m
Content-Type: text/plain;
  charsettf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

My original solution to this quiz had a lot of problems, but I think I fixed
them now. I re-worked my StateTree class into the new StateGraph class (which
is what it originally should have been named anyway). Basically, now I build
a graph of states, with a node for each state and an edge for each touch/clap
state change (StateGraph#build & StateGraph#build_recurse). This graph is then
repeatedly traversed, so that definite outcomes propagate through it (each
state has a best_outcome attached to it) (StateGraph#propagate_outcomes). Once
no more changes are made, the propagation is complete. Then each node's
best_outcome contains the best outcome for the player whose turn it is at the
node.

So if the root is, say, Outcome::P2Win, then player 2 is guaranteed a
winning strategy. (Another change from my first submission: Outcome::Loop has
been replaced with Outcome::Unknown, which all states default to at first. If
they are still unknown after executing StateGraph#propagate_outcomes, looping
is the best they can do.

The code is longer than I'd like, and there's some definite redundancy and
ugliness in there, but I've spent far too long debugging this to feel like
cleaning it up now. Speaking of debugging, it became quite a chore to verify
that my program was working right, so I wrote a little script to turn a
StateGraph into input for the graph-drawing program GraphViz. This did add
to the bloat, but I think it was worth it, since being able to look at the
graphs made things much easier. By setting FingersPerHand to 2, I generated
the attached f2.png image. That's not very impressive, but you can see the
next step up here (somewhat large):

http://www.jessemerriman.com/images/ruby_quiz/120_magic_fingers/f3.png

For higher values its impractical, both for the size of the generated image,
and the running time of the image generator. In the images, yellow nodes are
loop states, green are states that lead to player 1 winning, dark green are
actual player 1 win nodes, red are states that lead to player 2 winning, and
magenta are actual player 2 win nodes. The asterisks show whose turn it is.
Touch edges are solid and black, while clap edges are dashed and gray.

Using grep & wc -l on my dot files, I came up with the following stats:

FingersPerHand   #Nodes   #Edges
--------------   ------   -------
       2            4         3
       3           46        64
       4          156       316
       5          382      1000
       6          784      2444

(any higher than 6 and I get stack overflows).

One thing I could have done differently was not count whose turn it is in the
state, and just reverse the outcome or not depending on whose it is. But then
I'd have to store an array of reachable outcomes in each state, instead of just
the single best one for its player.

The diff between my original submission and my new code would be pretty long,
so I'm just going to paste it all in here:

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# constants.rb
# Ruby Quiz 120: Magic Fingers

Left,    Right    , 1 # hand array indices
Player1, Player2  , 1 # player array indices
FingersPerHand        # on my machine, > 6 causes a stack overflow

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# outcome.rb
# Ruby Quiz 120: Magic Fingers

require 'constants'

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

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

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# state.rb
# Ruby Quiz 120: Magic Fingers

require 'constants'
require 'outcome'
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  il)
    @players  player_1, player_2]
    @turn  urn
    @parent  arent
    @touch_reachable  clap_reachable  il

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

    if end_state?
      @best_outcome  self.winner Player1 ? Outcome::P1Win : Outcome::P2Win)
    else
      @best_outcome  utcome::Unknown
    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 > ingesPerHand
  # fingers up, and sort the hands.
  def State.normalize(player)
    for hand_num in [Left, Right] do
      player[hand_num]   if player[hand_num] > ingersPerHand
    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

  # Return a compact string representation.
  def to_compact_s
    if @turn Player1
      "[#{@players[Player1].join(',')}]* [#{@players[Player2].join(',')}]"
    else
      "[#{@players[Player1].join(',')}] [#{@players[Player2].join(',')}]*"
    end
  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).
  def State.touch(toucher, toucher_hand, touchee, touchee_hand)
    touchee[touchee_hand] + oucher[toucher_hand]
  end

  # Yield each state reachable from this state by a touch move.
  def each_touch_reachable_state
    if @touch_reachable.nil?
      # Set to avoid duplicates.
      @touch_reachable  et[]

      player  players[@turn]
      opponent_num  @turn + 1) % 2
      opponent  players[opponent_num]

      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  pponent.clone # because touch modifies it
            State.touch(player, player_hand, op, opponent_hand)
            if @turn Player1
              @touch_reachable << State.new(player, op, opponent_num, self)
            else
              @touch_reachable << State.new(op, player, opponent_num, self)
            end
          end
        end
      end
    end

    @touch_reachable.each { |r| yield r }
  end

  # Yield each state reachable from this state by a clap move.
  def each_clap_reachable_state
    if @clap_reachable.nil?
    # Set to avoid duplicates.
      @clap_reachable  et[]
      player  players[@turn]
      opponent_num  @turn + 1) % 2
      opponent  players[opponent_num]

      # 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],
                      (FingersPerHand - player[target_hand] - 1)].min
        (1..max_transfer).each do |i|
          # skip transfers that just flip the hands
          next if (player[source_hand] - i) player[target_hand]

          p  layer.clone
          p[source_hand] - 
          p[target_hand] + 
          if @turn Player1
            @clap_reachable << State.new(p, opponent.clone, opponent_num, self)
          else
            @clap_reachable << State.new(opponent.clone, p, opponent_num, self)
          end
        end
      end
    end

    @clap_reachable.each { |r| yield r }
  end

  # Yield once for each state reachable from this one.
  def each_reachable_state
    each_touch_reachable_state { |r| yield r }
    each_clap_reachable_state  { |r| yield r }
  end
end

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# state_graph.rb
# Ruby Quiz 120: Magic Fingers

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

class Set
  # Get an object in the Set which equals (by  obj.
  def get(obj)
    find { |x| x obj }
  end
end

# Represents a tree of States in parent-child relationships.
class StateGraph
  attr_reader :root, :edges

  def initialize(root  tate.new([1,1], [1,1], Player1))
    @root  oot
    @node_clap_children  } # Maps States to Arrays of their clapped children.
    @node_touch_children  } # Maps States to Arrays of their touched children.
    build
    self
  end

  # Traverse the graph from the root, filling in @node_*_children.
  def build
    @seen_nodes  et[]
    build_recurse(@root)
    remove_instance_variable :@seen_nodes
  end

  # Traverse the graph from the given node, filling in @node_*_children.
  def build_recurse(node)
    @seen_nodes << node
    @node_clap_children[node]   ] if not @node_clap_children.has_key? node
    @node_touch_children[node]  ] if not @node_touch_children.has_key? node

    # Here we have to be careful to not re-create nodes that are equal to
    # previously created nodes. This is why I added Set#get above.
    node.each_clap_reachable_state do |reached|
      if @seen_nodes.include? reached
        @node_clap_children[node] << @seen_nodes.get(reached)
      else
        @node_clap_children[node] << reached
        build_recurse(reached)
      end
    end
    node.each_touch_reachable_state do |reached|
      if @seen_nodes.include? reached
        @node_touch_children[node] << @seen_nodes.get(reached)
      else
        @node_touch_children[node] << reached
        build_recurse(reached)
      end
    end
  end

  # Call a Proc for every state encountered in the tree.
  # All procs should accept two arguments: the found state, and
  # the state from which it was found (nil for the root, may be different from
  # what the state reports as its parent, if there is more than one parent).
  def walk(new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc)
    @seen_nodes  et[]
    new_touch_proc[@root, nil]
    walk_recurse(@root, new_clap_proc, new_touch_proc,
                        old_clap_proc, old_touch_proc)
    remove_instance_variable :@seen_nodes
  end

  def walk_recurse(node, new_clap_proc, new_touch_proc,
                         old_clap_proc, old_touch_proc)
    @seen_nodes << node

    @node_clap_children[node].each do |reached|
      if @seen_nodes.include?(reached)
        old_clap_proc[reached, node]
      else
        new_clap_proc[reached, node]
        walk_recurse(reached, new_clap_proc, new_touch_proc,
                              old_clap_proc, old_touch_proc)
      end
    end

    @node_touch_children[node].each do |reached|
      if @seen_nodes.include?(reached)
        old_touch_proc[reached, node]
      else
        new_touch_proc[reached, node]
        walk_recurse(reached, new_clap_proc, new_touch_proc,
                              old_clap_proc, old_touch_proc)
      end
    end
  end

  # Yield for each node in the graph.
  def each_node
    # Can use either @node_clap_children or @node_touch_children here.
    @node_clap_children.each_key { |node| yield node }
  end

  # Yield for every child of the given node.
  def each_child(node)
    @node_clap_children[node].each  { |child| yield child }
    @node_touch_children[node].each { |child| yield child }
  end

  # Starting from the root, pull up all outcomes that are absolutely determined
  # given perfect play. Eg, say we have a state, S. S can move to a win state
  # for player 1. If its player 1's turn in S, then S's best_outcome will be
  # set to Outcome::P1Win. The graph will be scanned from the root repeatedly
  # until no more changes can be made to let these outcomes propagate. If
  # complete is set to true, outcome propagation will be completely determined
  # for all states in the graph. If its false, only those that affect the root
  # will be determined. This is faster if you only care about knowing root's
  # outcome.
  def pull_up_outcomes(complete  rue)
    begin
      @seen_nodes  et[]
      @changed  alse
      if complete
        each_node { |node| pull_up_recurse(node) }
      else
        pull_up_recurse(@root)
      end
    end while @changed
    remove_instance_variable :@seen_nodes
    remove_instance_variable :@changed
  end

  def pull_up_recurse(node)
    @seen_nodes << node

    if node.best_outcome Outcome::Unknown
      reachable_outcomes  et[]

      each_child(node) do |reached|
        if @seen_nodes.include? reached
          reachable_outcomes << reached.best_outcome
        else
          reachable_outcomes << pull_up_recurse(reached)
        end
      end

      best  utcome.best(node.turn, reachable_outcomes)
      if best ! ode.best_outcome
        node.best_outcome  est
        @changed  rue
      end
    end

    node.best_outcome
  end
end

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# game.rb
# Ruby Quiz 120: Magic Fingers

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

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])
    @graph  tateGraph.new(State.new(p1_start, p2_start, Player1))
    self
  end

  # Print out an analysis of the game.
  def analyze
    @graph.pull_up_outcomes
    outcome  graph.root.best_outcome

    if outcome Outcome::P1Win
      puts 'Player 1, with perfect play, can win.'
    elsif outcome Outcome::P2Win
      puts 'No matter how well Player 1 plays, Player 2 can win.'
    elsif outcome Outcome::Unknown
      puts 'Perfect play by both players leads to a loop.'
    else
      puts 'I am broken.'
    end
  end
end

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# magic_fingers.rb
# Ruby Quiz 120: Magic Fingers

require 'game'

# Note: These examples assume FingersPerHand 5.

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.

# -------------------------------------------------------------------
#!/usr/bin/env ruby
# state_graph_to_graphviz.rb
# Ruby Quiz 120: Magic Fingers

# This script outputs to stdout a dot file for use with GraphViz.
# ./state_graph_to_graphviz.rb | dot -Tpng -o output.png

require 'state_graph'

GraphVizHeader  digraph F#{FingersPerHand} {\nmargin2"
GraphVizFooter  }'

# Node with best_outcome Outcome::Unknown.
DefaultNodeOpts   [width5,shapeal,style韭led,fillcolorghtyellow]'
# Node with best_outcome Outcome::P1Win.
P1WinParentNodeOpts  [width5,shapeal,style韭led,fillcoloreen]'
# Node with best_outcome Outcome::P2Win.
P2WinParentNodeOpts  [width5,shape,styleled,fillcolorンァ
」 ナ     ア ョ
ミアラホマ  ロ イャャャ嗷ンァ
」 ナ     イ ョ
ミイラホマ  ロ イャーャャ
ンァ
」 ナ   ュュュュセ ョ
テナマ      ロ
「ャンァ
」 ナ   ュュュセ ョ 
ヤナマ     ロ「ャンァ

」 マ    ュュョ
マヤマ  
  マココミアラ   ミアラミホマャ
  マココミイラ   ミイラミホマャ
  マココユ トホマ


 ゜ィゥ
   ョ゜ソ
    ョ ミア ソ ミアラホマ コ ミイラホマ
  
    マヤマロョ゜ン
  


 ィゥ
  ョ゜ソ ソ ァナコ ァ ォ ョ゜゜ コ ョ゜゜


」 チ       ョ
゜    ャ 
    ィゥ

   「ワ「」ワ「 」゜ィゥサ「
    ョソ
     「ワ「」ィゥワ「 ュセ ワ「」ワ「 」テナマサ「
  


」 チ       ョ
゜    ャ 
    ィゥ

   「ワ「」ワ「 」゜ィゥサ「
    ョソ
     「ワ「」ィゥワ「 ュセ ワ「」ワ「 」ヤナマサ「
  


」 チ          ョ
゜    ャ 
   「ワ「」ィゥワ「 ュセ ワ「」ィゥワ「 」テナマ「


」 チ          ョ
゜    ャ 
   「ワ「」ィゥワ「 ュセ ワ「」ィゥワ「 」ヤナマ「


 ヌヨネ
」 テ    ャ    ァ  ョ
  ヌョ
」 ミ   ョ
ョ゜゜
」 ラ     ヌヨ ョ
ョィ゜ャ ゜ャ ゜ャ ゜ゥ
 ヌヨニ
」 ュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュュ

ュュ 
ハ ヘ
タョ
コッッョョッ

ュュツューー
フハヌナネーカク
テュヤコ ッサ
  2.png"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
	filename2.png"

iVBORw0KGgoAAAANSUhEUgAAAQMAAAGBBAMAAACQh8krAAAAElBMVEX+//8AZAAA/wDT09MAAAD/
//87CdYqAAAAAXRSTlMAQObYZgAABMBJREFUeJzt3WGOoyAYxvG5wiQ9gXEPUsN+3zT1/ldZAXmr
VkVF5G3z58NsW2flN4io6JP+tKXLv5/SAggQIECAAAECBAgQIFxGqHxp/D9/LiZUlZFSy6tjjgOE
R+Wrey/286bKTqjq+epDsYv3tcU+wqO2f2as2DbKROgA8fqDYjtiB2E7wCO2bo7NhEe9B+AQGxti
K2FfE+xqiI2E3U3QI7YYNhEeB5qgNzQnEQ4LOsPfUwirQ1Gs1FHDBsLBfiDtEOsPccIzTdAZkglJ
m8GW2KaIEpIbIdoMUUK6oKrWmyFGeJ4gqOokQnJPcITVZogQHs0ZhGp1jIwQTtkOkS0RIdSTVdmT
Nhmq7IvxWZR7J9vOVOEsr14bnnYSbH1SqXsxGjuNY4o3fJREmPRGW5+cOdTzBDm7NQPCWn880Aqj
DWF/1I3UKj/G787eEG+EwabJQJjsEfMEI31ykbBWx75x4WgrpIwLk/54sC8kjY6TLSEEtzeMQaNK
3d7wIqxWse9IaUcad01X+2GnmRma3CWvG6L8L1epR8qF84XI0Wt8rpd6vqDgrEnDuaOCM2gN1xEa
rqY0XFMquLJuNcwvaJhlaRXMNbUaZtxaBfOOrpSefXWl+By0L4Vn4gcOV/rOcfX9iGGJHwUgQIAA
AQIECBAgQIAAAQIECBAgRMrTzjGlIb6A0FpC2hq+gfBUQUjcJb6B0ELwhMQVpBOeEGwpeZgqez+C
fAT5iHj9QUE+okeQj+gR5CO8gXyEbwfyEbaQj/CFfIQjkI+w5Zp8xGp04pp8hF9k5hZdlY9wi5r+
3TQ6kT0f8Wp6eUZ78rh8/nzEMqHfatnzESuEPjqRPx8RbYXs+Qh5I91x0hcuykfITjkTnbgoHyFD
00x04up8xPsi8hHxRviMM2gN1xEarqY0XFMquLJuNcwvaJhlaRXMNbUaZtxaBfOOrpSefXWl+By0
L+QjpqX0wwMQIECAAAECBAgQIECAAAECBAhfQFAQTlBA0BBOUEAgH6GEoCOcoICQuIKvCCcoIJCP
IB9R6A5d8fuU5e/WFr9nXf7OffnnF4o/xaHgWZbyT/SUf66p/NNdCp5xK/+kH/mIlnyEK+QjbNH6
/RELIYgqfH9EE7zho9PzEUshiL4+E5oh3/dHLIYg+qZvRJXt+yMWH//PRJjJRyyGINYIa3Xsz0cc
aYWT8xFLIYhQn3THjN8fsRCCkPrc2JD1+yOWQhCuvjA0eQbfHzHwkI8gH+HagHwE+QjyEeQjyEeQ
jzheIECAAAECBAgQIECAAAECBAgQIGgIJyggaAgnKCCQj1BC0BFOUEBIXMFXhBMUEE4+TJnLyiLh
/ntRuUGAAAECBAgQIECAkIdw60545fXgN4zp3sgS434xvugY4T7/2jjePTjDRzOL7oNFpxNMWLV5
I7wW9W9TCebmmrN7LQrjFoW3U4Is6l8Yuw5Z//6+cP819+7/d3/P/dfM1bOJcHu1xKFW8H9ESiuM
unUSQUq5VhgSXn3ujTDTHRP6QiD4vjDcEH6HM9Lj33ZKY87ZKe02NH5r3obdMYw/vi4zNzSF2hOH
prlGWf1gw6LPO0ZAgAABAgQIEPqi4H5EkQIBAgQIECBAgAABAoRPI/wHez7KCkpmYhQAAAAASUVO
RK5CYII-Boundary-00
LtJGEH0xbm6z8m--
--Boundary-00
LtJGEH0xbm6z8m--