[QUIZ] Magic Fingers (#120)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

We have a foreign exchange student from Korea staying with us. The best part of
that is the intended exchange of cultures. For example, to kill time on a
recent plane trip, the student taught us a common finger game children play in
Korea.

The rules are very easy:

1. Both players start by holding up one finger on each hand.
2. On each turn a player must do one of the following:
a. Touch one of their hands to an opponent's hand, adding the finger
count on their hand to the touched hand. The player keeps the same
number of fingers, but the opponent must add the player's finger
count in addition to the fingers already on that hand.
b. Clap their hands together to "transfer" one or more fingers from
one hand to the other. You cannot transfer all the fingers off of
a hand.
3. A hand with five or more fingers is eliminated, which is shown by
making a fist. An opponent can not add fingers to an eliminated
hand and an it cannot be used in touches, but players may transfer
fingers to it, "reviving" it. The first player with two eliminated
hands loses the game.

For example, here is how a quick game might play out:

1: ----| |---- Starting fingers.
2: ----| |----

1: ----| |---- Player 1's left hand touches player 2's right hand.
2: ----| ||---

1: ----| |||-- 2's right touches 1's right hand.
2: ----| ||---

1: ----| |||-- 1's right touches 2's right hand.
2: ----| -----

1: ----| ||||- 2's left touches 1's right hand.
2: ----| -----

1: ----| |||-- 1's right touches 2's left hand.
2: ----- -----

Of course, as a programmer, I immediately tried to solve this game. I suck the
fun right out of everything, but at least it gave us another quiz topic.

This week's Ruby Quiz is to programmatically solve Magic Fingers. Is it a win
for the first or second player with perfect play, or can you always force a draw
with repeating counts? Have your program print some output that would convince
anyone beyond the shadow of a doubt what the game's outcome will be.

 

[Eric I.]

b. Clap their hands together to "transfer" one or more fingers from
one hand to the other. You cannot transfer all the fingers off of
a hand.

Can one clap to transfer fingers from one hand to another such that
the receiving hand would get five or more fingers and therefore be
reduced to zero fingers?

Thanks,

Eric

 

[James Edward Gray II]

Can one clap to transfer fingers from one hand to another such that
the receiving hand would get five or more fingers and therefore be
reduced to zero fingers?

I don't think so. Let's say no.

James Edward Gray II

 

[Eric I.]

Part of the problem is to generate output that prints "some output
that would convince anyone beyond the shadow of a doubt what the
game's outcome will be." Even though I've convinced myself, I'm not
sure I've generated output that satisfies that requirement. My
program displays a table telling a player how to move given any state
of the hands. If there's a way to guarantee a win no matter what else
the opponent does, it tells them how to get there. If the opponent
has a guaranteed win if s/he plays perfectly, it makes a choice that
will delay the win as long as possible to hopefully allow the opponent
to make a mistake. Otherwise, it chooses a move that maintains the
draw.

Here's the generated output:

========

INSTRUCTIONS

If it's your turn, select the row that describes your two hands. Then
select the column that describes your opponent's two hands. The cell
at the intersection will tell you how to move and what to expect.

A leading "+" indicates there is a guaranteed way to win. A leading
"-" tells you that if the opponent plays perfectly, you will lose. If
neither of those symbols is present, then if you and your opponent
play well, neither of you will ever win.

The rest of the cell tells you what type of move to make. A "T"
represents a touching move, telling you which finger of yours first to
user first, and which finger of the opponent to touch. A "C"
represents a clapping move, and it tells you the finger counts should
end up with after the clap.

01 02 03 04 11 12 13 14 22 23 24 33
34 44
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
----
01: 1T1 1T2 -1T3 +1T4 1T1 1T1 1T1 1T4 1T2 1T2 1T4 -1T3 1T4
-1T4
02: C11 C11 +2T3 +2T4 C11 C11 C11 C11 C11 C11 C11 C11 C11 -
C11
03: C21 +3T2 +3T3 +3T4 C21 +3T2 +3T3 +3T4 C21 C21 C21 -C21 C21 -
C21
04: +4T1 +4T2 +4T3 +4T4 C31 C31 C31 C31 C31 C31 C31 C22 C31 -
C22
11: 1T1 1T2 1T3 +1T4 1T1 1T1 1T1 1T1 1T2 1T2 1T2 1T3 1T4
1T4
12: 1T1 C12 +2T3 +2T4 1T1 1T1 1T1 1T1 1T2 C12 1T2 1T3 C12
1T4
13: 1T1 +3T2 +3T3 +3T4 1T1 1T1 1T1 1T1 1T2 C22 1T2 1T3 C22
1T4
14: +4T1 +4T2 +4T3 +4T4 1T1 1T1 1T1 1T1 1T2 C32 1T2 1T3 C32
1T4
22: 2T1 2T2 +2T3 +2T4 2T1 2T1 2T1 2T1 2T2 2T2 C13 2T3 2T3
2T4
23: 2T1 +3T2 +3T3 +3T4 2T1 2T1 C23 2T1 2T2 2T2 C23 2T3 2T3
2T4
24: +4T1 +4T2 +2T3 +4T4 2T1 2T1 2T1 2T1 2T2 2T2 C33 2T3 2T3
2T4
33: 3T1 +3T2 +3T3 +3T4 3T1 +3T2 +3T3 +3T4 3T2 +3T2 3T2 +3T3 +3T4
3T4
34: +4T1 +4T2 +4T3 +4T4 3T1 3T1 3T1 C34 3T2 3T2 3T2 3T3 3T3
3T4
44: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4

========

Note that the initial state, where all hands have one finger, does not
have a guaranteed win by either player. So if both players play
perfectly, the game will never end.

Eric
----
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

====

HandNames = ["left hand", "right hand"]

AllowClapsToZero = false

Levels = 25


# Memo is used to store best moves for a given state to avoid
# re-calculation. The key is a GameState, and the value is an array
# containing the number of levels used to calculate the best move, the
# best move, and the score of the best move.
Memo = Hash.new


# Instances of this class represent the game state.
class GameState
attr_reader :hands

def initialize(hands = [[1, 1], [1, 1]])
@hands = hands
end

def do_turn(move)
new_hands, description1, description2 =
*move.call(@hands[0].dup, @hands[1].dup)
[GameState.new([new_hands[1], new_hands[0]]),
description1,
description2]
end

def to_s
result = ""
@hands.each_index do |i|
result << "#{i+1}: "
result << '-' * (5 - @hands[0])
result << '|' * @hands[0]
result << ' '
result << '|' * @hands[1]
result << '-' * (5 - @hands[1])
result << "\n"
end
result
end

def game_over?
@hands[0][0] == 0 && @hands[0][1] == 0 ||
@hands[1][0] == 0 && @hands[1][1] == 0
end

def score
if @hands[0][0] == 0 && @hands[0][1] == 0 : -1
elsif @hands[1][0] == 0 && @hands[1][1] == 0 : 1
else 0
end
end

def eql?(other)
@hands == other.hands
end

def hash
@hands[0][0] + 5 * @hands[0][1] + 25 * @hands[1][0] +
125 * @hands[1][1]
end
end


# Generates an array of Procs, each able to perform a touching move.
# Each Proc, when passed in the arrays representing the mover's hands
# and the opponent's hands returns an array containing the new states
# of the hands, a long description of the move, and an abbreviated
# description of the move. If the move cannot legally be applied to
# the hands, an exception is raised.
def generate_touches
result = []
(0..1).each do |from_hand|
(0..1).each do |to_hand|
result << Proc.new do |player_hands, opponent_hands|
raise "cannot touch from empty hand" if
player_hands[from_hand] == 0
raise "cannot touch to empty hand" if opponent_hands[to_hand]
== 0
description1 =
"touches #{HandNames[from_hand]} to opponent's
#{HandNames[to_hand]}"
description2 =
"#{player_hands[from_hand]}T#{opponent_hands[to_hand]}"
opponent_hands[to_hand] += player_hands[from_hand]
opponent_hands[to_hand] = 0 if opponent_hands[to_hand] >= 5
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end


# Generates an array of Procs, each able to perform a clapping move.
# See the comment for generate_touches for the remaining details since
# this method works analogously.
def generate_claps
result = []
(0..1).each do |from_hand|
to_hand = 1 - from_hand
(1..4).each do |fingers|
result << Proc.new do |player_hands, opponent_hands|
raise "do not have enough fingers on #{HandNames[from_hand]}"
unless
player_hands[from_hand] > fingers
raise "#{HandNames[to_hand]} would end up with five or more
fingers" if
!AllowClapsToZero && player_hands[to_hand] + fingers >= 5
description1 = "claps to transfer #{fingers} fingers from " +
"#{HandNames[from_hand]} to #{HandNames[to_hand]}"
player_hands[from_hand] -= fingers
player_hands[to_hand] += fingers
player_hands[to_hand] = 0 if player_hands[to_hand] >= 5
description2 =
"C#{player_hands[from_hand]}#{player_hands[to_hand]}"
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end


# All possible moves for any turn, some of which might not be legal
# given the state of the hands.
Moves = generate_claps + generate_touches


# Picks the best possible move that can be determined using no more
# than levels levels of recursion. To speed this up, if the current
# state is stored in the Memo with the same or fewer levels, then
# that's used rather than recalculation. This returns an array
# containing the score of the best move, the move, a long description
# of the move, and an abbreviated description of the move. If a move
# guaranteeing a win can be done, then that will be chosen. If there
# are multiple such moves, then the one that leads to a win most
# quickly is chosen. If a win can't be chosen but a draw can be, then
# it is. If a guaranteed lost must be chosen (assuming the opponent
# plays a perfect game), then the lose taking the most moves is chosen
# to increase the opportunities the opponent will make a mistake, and
# either a draw or win can be achieved.
def pick_move(state, levels = Levels)
return [state.score, nil, nil, nil] if levels <= 0 ||
state.game_over?

memoed_move = Memo[state]
if memoed_move && memoed_move[0] >= levels
# use memoed values if levels used meets or exceeds my levels
best_move = memoed_move[1]
best_score = memoed_move[2]
else
# otherwise, calculate values recursively
best_score = nil
best_move = nil

# try each of the possible moves on this state and generate an
# array of the results of those choices
move_choices = Moves.map do |move|
begin
# determine the new state if the chosen move is applied
new_state, description1, description2 = *state.do_turn(move)

# recursively determine the score for this move (i.e., this
# state); negate the score returned since it's in terms of
# opponent (i.e., a win for them is a loss for us)
score = -pick_move(new_state, levels - 1)[0]

# increment score (by shifting away from zero) in order to be
# able to treat is as a count of the number of moves to a win
# or a loss
score += score / score.abs unless score.zero?

[score, move, description1, description2]
rescue Exception => e
nil # the move was ilegal
end
end

# remove nils that were generated by illegal moves
move_choices = move_choices.select { |option| option }

# select and sort only those with positive (i.e., winning scores)
winning_choices = move_choices.
select { |option| option[0] > 0 }.
sort_by { |option| option[0] }

unless winning_choices.empty?
# if there's a winning option, choose the one that leads to a
# with the least number of moves
selected = winning_choices.first
else
# otherwise, choose a move that leads to a tie (preferable) or a
# loss but in the greatest number of moves (to increase
# opponent's opportunities to make a mistake)
move_choices = move_choices.sort_by { |option| option[0] }
if move_choices.last[0] == 0
selected = move_choices.last
else
selected = move_choices.first
end
end

best_score = selected[0]
best_move = selected[1..3]

# store the best move determined for future use
Memo[state] = [levels, best_move, best_score]
end

[best_score] + best_move
end


# Returns a string indicating win or loss depending on score.
def score_symbol(score)
if score > 0 : '+'
elsif score < 0 : '-'
else ' '
end
end


# Calculate the best move given every finger combination, and store in
# the results hash.
results = Hash.new
1.upto(4) do |left1|
0.upto(left1) do |right1|
key1 = "#{right1}#{left1}"
results[key1] = Hash.new
1.upto(4) do |left2|
0.upto(left2) do |right2|
state = GameState.new([[left1, right1], [left2, right2]])
score, move, description1, description2 = *pick_move(state,
40)
key2 = "#{right2}#{left2}"
results[key1][key2] = score_symbol(score) + description2
end
end
end
end


# display instructions
puts <<EOS
INSTRUCTIONS

If it's your turn, select the row that describes your two hands. Then
select the column that describes your opponent's two hands. The cell
at the intersection will tell you how to move and what to expect.

A leading "+" indicates there is a guaranteed way to win. A leading
"-" tells you that if the opponent plays perfectly, you will lose. If
neither of those symbols is present, then if you and your opponent
play well, neither of you will ever win.

The rest of the cell tells you what type of move to make. A "T"
represents a touching move, telling you which finger of yours first to
user first, and which finger of the opponent to touch. A "C"
represents a clapping move, and it tells you the finger counts should
end up with after the clap.

EOS


# display move strategy table
line1 = " " + results.keys.sort.map { |key1| " #{key1}" }.join
puts line1
puts line1.gsub(/\ \ \d\d/, '----')
results.keys.sort.each do |key1|
print "#{key1}: ",
results[key1].keys.sort.map { |key2| " #{results[key1]
[key2]}" }.join,
"\n"
end

 

[Jesse Merriman]

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:1Win = 0
Outcome::Loop = 1
Outcome:2Win = 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 layers, :turn, arent, :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

) +
'|' * player

+
' ' +
'|' * player

+
'-' * (FingersPerHand-player

)
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, 1_win_node, 2_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:1Win is returned, @p1_win_node will hold one way for player 1
# to win. Likewise for Outcome:2Win.
#
# 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:1Win
else
@p2_win_node = reached
reachable_outcomes << Outcome:2Win
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:1Win
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:2Win
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.​

 

[James Edward Gray II]

Note that the initial state, where all hands have one finger, does not
have a guaranteed win by either player. So if both players play
perfectly, the game will never end.

Wikipedia disagrees with this, which likely just means that I botched
my explanation of the rules somehow. I'm see if I can figure out
what I changed...

James Edward Gray II

 

[Eric I.]

Wikipedia disagrees with this, which likely just means that I botched
my explanation of the rules somehow. I'm see if I can figure out
what I changed...

James Edward Gray II

I just read the Wikipedia description as a result of reading your
comment. And as I read through the rules there, one difference did
jump out at me. The rules disallow a clap where you start out with 3
on left and 1 on right and end up with 1 on left and three on right.
My code does not disallow that.

So that's one possibility. The other is that I made some other
mistake (which shouldn't be rules out!). But I'll try adding that
aspect to the rules and re-run.

Eric

 

[Eric I.]

OK, I made two changes to my code. First, I don't allow a clap that
ends up with the same finger counts. Second, I made it possible to
clap all the fingers off of one hand to the other, leaving one hand
with zero. And now it is the case where the first player is
guaranteed a loss.

Here's my new move table:

01 02 03 04 11 12 13 14 22 23 24 33
34 44
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
----
01: -1T1 -1T2 -1T3 +1T4 -1T1 -1T2 -1T1 +1T4 -1T2 -1T2 -1T4 -1T3 -1T4
-1T4
02: +C11 -C11 +2T3 +2T4 +C11 -C11 +2T3 +2T4 -C11 +2T3 +2T4 -C11 -C11 -
C11
03: +C21 +3T2 +3T3 +3T4 -C21 +3T2 +3T3 +3T4 -C21 -C21 -C21 -C21 -C21 -
C21
04: +4T1 +4T2 +4T3 +4T4 +C31 +C22 C22 +C22 C22 +C22 C22 -C22 -C22 -
C22
11: +C02 +1T2 -1T3 +1T4 -1T1 +C02 -1T3 +1T4 C02 -1T2 -1T4 -1T3 +1T4
-1T4
12: +C03 -2T2 +2T3 +2T4 +C03 +2T2 +2T3 +2T4 -1T2 +2T3 +2T4 -1T3 -2T3
-1T4
13: +C22 +3T2 +3T3 +3T4 +3T1 +C22 +3T3 +1T4 C22 +C22 C22 -C22 3T3
1T4
14: +4T1 +4T2 +4T3 +4T4 +C32 -C32 -C32 +C32 -C32 -4T3 -4T2 -1T3 -4T3
-1T4
22: +C13 2T2 +2T3 +2T4 +C13 +2T2 +2T3 +2T4 2T2 +2T3 +2T4 +2T3 +2T4
2T4
23: +2T1 +3T2 +3T3 +3T4 +3T1 +3T2 +3T3 +3T4 -3T2 +3T2 -3T2 +3T3 +3T4
-2T4
24: +4T1 +4T2 +2T3 +2T4 +4T1 +4T2 +2T3 +2T4 2T2 +4T2 4T2 +4T3 +4T4
2T4
33: +C24 +3T2 +3T3 +3T4 +3T1 +3T2 +3T3 +3T4 +3T2 +3T2 +3T4 +3T3 +3T4
+3T4
34: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4
44: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4

Interestingly if you follow through starting at 11/11, then the first
player can apparently hold off on losing for 26 turns, 13 by each
player.

And my replacement generate_claps method is appended below.

Eric
----
Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://LearnRuby.com

====

# Generates an array of Procs, each able to perform a clapping
move.
# See the comment for generate_touches for the remaining details
since
# this method works
analogously.
def generate_claps
result = []
(0..1).each do |from_hand|
to_hand = 1 - from_hand
(1..4).each do |fingers|
result << Proc.new do |player_hands, opponent_hands|
raise "do not have enough fingers on #{HandNames[from_hand]}"
unless
player_hands[from_hand] >= fingers
raise "#{HandNames[to_hand]} would end up with five or more
fingers" if
!AllowClapsToZero && player_hands[to_hand] + fingers >= 5
raise "cannot end up with same number combination after clap"
if
player_hands[from_hand] - fingers == player_hands[to_hand]
description1 = "claps to transfer #{fingers} fingers from " +
"#{HandNames[from_hand]} to #{HandNames[to_hand]}"
player_hands[from_hand] -= fingers
player_hands[to_hand] += fingers
player_hands[to_hand] = 0 if player_hands[to_hand] >= 5
description2 =
"C#{player_hands[from_hand]}#{player_hands[to_hand]}"
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end

 

[James Edward Gray II]

I just read the Wikipedia description as a result of reading your
comment. And as I read through the rules there, one difference did
jump out at me. The rules disallow a clap where you start out with 3
on left and 1 on right and end up with 1 on left and three on right.
My code does not disallow that.

Sorry, yesterday was a busy day for me and I just got around to
looking into this. Thanks for looking into this for me.

Yes, this is the rule I didn't express in the quiz description. I
knew about it and just failed to state it correctly. For the record,
the missing rule is:

A clap must result in a change in finger counts. Just switching the
counts of the left and right hands is not allowed.

James Edward Gray II

 

[Matt Hulse]

I took the OO approach and implemented a strategy pattern.
To see the game play out, pass in the -v flag, and -d will show the
actual command given for each move.

The output of the test file contains a frequency distribution to show
how each matchup plays out.

Here is some sample output for the second matchup in the test over 200
games:
_____________________________________
Game 2: Aggressive vs Random
3: ---------------------------------33
4:
--------------------------------------------------------------------68
5: -------------------------------------------43
6: ------------------------24
7: ---------------15
8: -----5
9: -------7
10: ----4
11: -1
Player 1: 166 wins
Player 2: 34 wins
______________________________________

In an Aggressive vs Aggressive game, the first player wins in 3 rounds
every time. Obviously there are better
strategies that I didn't take the time to explore.

Again, I'm happy to receive any comments. I feel like my solutions
are so clunky compared to what you guys submit.
I am here to learn!

Here's my code:

#file: game.rb
#author: Matt Hulse - www.matt-hulse.com

require 'player'

class Game
attr_reader 1, 2, :winner, :rounds

def initialize(p1_strategy = "random", p2_strategy = "random")
@p1 = Player.new(1,p1_strategy, self)
@p2 = Player.new(2,p2_strategy, self)
@rounds = 0
end

def get_opponent(player)
return @p1 if @p2 == player
return @p2 if @p1 == player
end

def loop
#keep going until one person has no hands left
#after 100 rounds we're calling a draw!

puts self if $VERBOSE
until(game_over) do
@rounds += 1
p1.move
puts self if $VERBOSE

unless game_over then
p2.move
puts self if $VERBOSE
end
break if @rounds >= 100
end

if(lost?(p1)) then
@Winner = p2
elsif(lost?(p2))
@Winner = p1
else
puts "Draw"
end
end

def game_over
lost?(p1) || lost?(p2)
end

def lost?(player)
player.left.finger_count <= 0 and player.right.finger_count <= 0
end

def to_s
"#{p1}\n#{p2}\n"
end
end



#file: hand.rb
#author: Matt Hulse - www.matt-hulse.com

class Hand
attr_reader :right_or_left, :finger_count

def initialize(right_or_left, count = 1)
@right_or_left = right_or_left
@finger_count = count
end

def touch(hand)
hand.add_fingers(self.finger_count)
end

def add_fingers(num)
@finger_count += num
if @finger_count >= 5 then
@finger_count = 0
end
end

def clap(hand,num)
hand.add_fingers(num) #num must be <= self.finger_count
@finger_count -= num
end

def to_s
result = ""
#print left to right
i = 0
(1..5).each{
i += 1
if(i <= @finger_count) then
result += "|"
else
result += "-"
end
}
return result if @right_or_left == :right
return result.reverse
end

end



#file: player.rb
#author: Matt Hulse - www.matt-hulse.com

require 'hand'

class Player
attr_reader layer_num, :right, :left, :strategy, :game
def initialize(player_num, strategy, game)
@player_num = player_num
@strategy = strategy
@game = game
@right = Hand.newright,1)
@left = Hand.newleft,1)
end

def move
begin
eval(@strategy)
rescue NameError => e
random #default to random
end
end

def get_opponent
@game.get_opponent(self)
end

def get_larger_hand
return @right if @right.finger_count > @left.finger_count
return @left
end

def min(a,b)
return a if a <= b
return b
end

def random
#all possible moves, choose randomly among them
opponent = get_opponent

valid_moves = Array.new

opp_rt_count = opponent.right.finger_count
opp_lt_count = opponent.left.finger_count

if(@right.finger_count > 0) then
valid_moves << "@right.touch(opponent.right)" if opp_rt_count >
0
valid_moves << "@right.touch(opponent.left)" if opp_lt_count > 0
#total on hand transferred to cannot be more than 5
#random number is between 1 and the minimum of what left can
receive and right can give
rand_max = min([email protected]_count,@right.finger_count-1)
valid_moves << "@right.clap(@left, #{rand(rand_max) + 1})" if
rand_max > 0
end

if(@left.finger_count > 0) then
valid_moves << "@left.touch(opponent.right)" if opp_rt_count > 0
valid_moves << "@left.touch(opponent.left)" if opp_lt_count > 0
#total on hand transferred to cannot be more than 5
#random number is between 1 and the minimum of what right can
receive and left can give
rand_max = min([email protected]_count,@left.finger_count-1)
valid_moves << "@left.clap(@right, #{rand(rand_max) + 1})" if
rand_max > 0
end

move = valid_moves[rand(valid_moves.size)]
eval(move)
puts "Player #{player_num}: #{move}" if $DEBUG
end

def aggressive
opponent = get_opponent

#every move is to touch the opponents largest hand with the local
largest hand
move = "get_larger_hand.touch(opponent.get_larger_hand)"

eval(move)
puts "Player #{player_num}: #{move}" if $DEBUG
end

def to_s
"#{player_num}: #{@left} #{@right}"
end
end



#file: test.rb
#author: Matt Hulse - www.matt-hulse.com

require 'game'

puts "Game 1: Random vs Random"

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1..200).each{
game = Game.new("random","random")
game.loop
if(game.winner) then
puts "Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy." if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts "#{i}: #{'-'*num_rounds}#{num_rounds}"
}

wins.each_pair{|key,value|
puts "Player #{key}: #{value} wins"
}



puts
puts "Game 2: Aggressive vs Random"

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1..200).each{
game = Game.new("aggressive", "random")
game.loop
if(game.winner) then
puts "Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy." if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts "#{i}: #{'-'*num_rounds}#{num_rounds}"
}

wins.each_pair{|key,value|
puts "Player #{key}: #{value} wins"
}


puts
puts "Game 3: Aggressive vs Aggressive"

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1..200).each{
game = Game.new("aggressive","aggressive")
game.loop
if(game.winner) then
puts "Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy." if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts "#{i}: #{'-'*num_rounds}#{num_rounds}"
}

wins.each_pair{|key,value|
puts "Player #{key}: #{value} wins"
}



Thanks,

__________
Matt Hulse
(e-mail address removed)
http://www.matt-hulse.com

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

We have a foreign exchange student from Korea staying with us. The best part of
that is the intended exchange of cultures. For example, to kill time on a
recent plane trip, the student taught us a common finger game children play in
Korea.

The rules are very easy:

1. Both players start by holding up one finger on each hand.
2. On each turn a player must do one of the following:
a. Touch one of their hands to an opponent's hand, adding the finger
count on their hand to the touched hand. The player keeps the same
number of fingers, but the opponent must add the player's finger
count in addition to the fingers already on that hand.
b. Clap their hands together to "transfer" one or more fingers from
one hand to the other. You cannot transfer all the fingers off of
a hand.
3. A hand with five or more fingers is eliminated, which is shown by
making a fist. An opponent can not add fingers to an eliminated
hand and an it cannot be used in touches, but players may transfer
fingers to it, "reviving" it. The first player with two eliminated
hands loses the game.

For example, here is how a quick game might play out:

1: ----| |---- Starting fingers.
2: ----| |----

1: ----| |---- Player 1's left hand touches player 2's right hand.
2: ----| ||---

1: ----| |||-- 2's right touches 1's right hand.
2: ----| ||---

1: ----| |||-- 1's right touches 2's right hand.
2: ----| -----

1: ----| ||||- 2's left touches 1's right hand.
2: ----| -----

1: ----| |||-- 1's right touches 2's left hand.
2: ----- -----

Of course, as a programmer, I immediately tried to solve this game. I suck the
fun right out of everything, but at least it gave us another quiz topic.

This week's Ruby Quiz is to programmatically solve Magic Fingers. Is it a win
for the first or second player with perfect play, or can you always force a draw
with repeating counts? Have your program print some output that would convince
anyone beyond the shadow of a doubt what the game's outcome will be.

 

[Jesse Merriman]

Regarding clapping, is something like 1,3 -> 0,4 allowed?

You cannot transfer all the fingers off of a hand.

Whilst Wikipedia says (under "Alternate Explanation"):

They are free to remove all fingers from a hand

Which is it? WP's Gameplay section doesn't say one way or the other.

 

[James Edward Gray II]

Regarding clapping, is something like 1,3 -> 0,4 allowed?



Whilst Wikipedia says (under "Alternate Explanation"):

Which is it? WP's Gameplay section doesn't say one way or the other.

Interesting. It seems I may have had that rule wrong. I now
understand why Eric's code had a constant to toggle that behavior on
and off. Eric's code still gets the right answer with it off, so I
doubt it matters.

James Edward Gray II

 

[Eric I.]

Interesting. It seems I may have had that rule wrong. I now
understand why Eric's code had a constant to toggle that behavior on
and off. Eric's code still gets the right answer with it off, so I
doubt it matters.

Well, there are two related issues, and my constant does not cover the
situation described.

The first issue is whether 1,3 -> 0,4 is allowed. I only got the
"right answer" (i.e., second player can force a win) *after* I made
that legal, so it seems to be important.

The second issue is whether 3,4 -> 1,0 (via 1,6) is allowed. That's
what my constant controls (and therefore it's somewhat misnamed). I
don't think the Wikipedia article is clear on this issue, as it
describes it as a "transfer" of fingers. If it had used the work
"redistribution" of fingers, then I think we could say it's clearly
disallowed. I think it makes sense to view the clap as a
redistribution, so my personal preference is to disallow it.

So that's my $0.02, FWIW.

Eric

 

[Jesse Merriman]

--Boundary-00=_ALtJGEH0xbm6z8m
Content-Type: Multipart/Mixed;
boundary="Boundary-00=_ALtJGEH0xbm6z8m"

--Boundary-00=_ALtJGEH0xbm6z8m
Content-Type: text/plain;
charset="utf-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:2Win, 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 = 0, 1 # hand array indices
Player1, Player2 = 0, 1 # player array indices
FingersPerHand = 5 # 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:1Win = 0
Outcome::Unknown = 1
Outcome:2Win = 2

# 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 layers, :turn, arent, :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
@touch_reachable = @clap_reachable = nil

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

if end_state?
@best_outcome = (self.winner == Player1 ? Outcome:1Win : Outcome:2Win)
else
@best_outcome = Outcome::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 >= 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

) +
'|' * player

+
' ' +
'|' * player

+
'-' * (FingersPerHand-player

)
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] += toucher[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 = Set[]

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 = opponent.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 = Set[]
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 = player.clone
p[source_hand] -= i
p[target_hand] += i
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 = State.new([1,1], [1,1], Player1))
@root = root
@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 = Set[]
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 = Set[]
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:1Win. 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 = true)
begin
@seen_nodes = Set[]
@changed = false
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 = Set[]

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 = Outcome.best(node.turn, reachable_outcomes)
if best != node.best_outcome
node.best_outcome = best
@changed = true
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 = StateGraph.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:1Win
puts 'Player 1, with perfect play, can win.'
elsif outcome == Outcome:2Win
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} {\nmargin=0.2"
GraphVizFooter = '}'

# Node with best_outcome == Outcome::Unknown.
DefaultNodeOpts = '[width=1.5,shape=oval,style=filled,fillcolor=lightyellow]'
# Node with best_outcome == Outcome:1Win.
P1WinParentNodeOpts = '[width=1.5,shape=oval,style=filled,fillcolor=green]'
# Node with best_outcome == Outcome:2Win.
P2WinParentNodeOpts = '[width=1.5,shape=box,style=filled,fillcolor=red]'
# End state node where player 1 wins.
P1WinnerNodeOpts = '[width=2.2,shape=box,style=filled,fillcolor=darkgreen]'
# End state node where player 2 wins.
P2WinnerNodeOpts = '[width=2.2,shape=box,style=filled,fillcolor=magenta]'
# Edge for state --clap--> state.
ClapEdgeOpts = '[style="dashed",color=gray]'
# Edge for state --touch-> state.
TouchEdgeOpts = '[style="solid",color=black]'

# Only for use with non-end-states.
OutcomesToOpts = {
Outcome:1Win => P1WinParentNodeOpts,
Outcome:2Win => P2WinParentNodeOpts,
Outcome::Unknown => DefaultNodeOpts
}

def node_opts(node)
if node.end_state?
node.winner == Player1 ? P1WinnerNodeOpts : P2WinnerNodeOpts
else
OutcomesToOpts[node.best_outcome]
end
end

def name(state)
state.end_state? ? 'End: ' + state.to_compact_s : state.to_compact_s
end

# Adds a newly clapped state to the graph.
new_clap = lambda do |state, parent|
name = name(state)

puts "\"#{name}\" #{node_opts(state)};"
if not parent.nil?
puts "\"#{name(parent)}\" -> \"#{name}\" #{ClapEdgeOpts};"
end
end

# Adds a newly touched state to the graph.
new_touch = lambda do |state, parent|
name = name(state)

puts "\"#{name}\" #{node_opts(state)};"
if not parent.nil?
puts "\"#{name(parent)}\" -> \"#{name}\" #{TouchEdgeOpts};"
end
end

# Adds a clap edge to an old state to the graph.
old_clap = lambda do |state, parent|
puts "\"#{name(parent)}\" -> \"#{name(state)}\" #{ClapEdgeOpts}"
end

# Adds a touch edge to an old state to the graph.
old_touch = lambda do |state, parent|
puts "\"#{name(parent)}\" -> \"#{name(state)}\" #{TouchEdgeOpts}"
end

puts GraphVizHeader
# Create the initial state tree, with only end states' outcomes known.
graph = StateGraph.new
# Pull up all outcomes.
graph.pull_up_outcomes
# Walk the tree and generate GraphViz input.
graph.walk(new_clap, new_touch, old_clap, old_touch)
puts GraphVizFooter
# -------------------------------------------------------------------

--
Jesse Merriman
(e-mail address removed)
http://www.jessemerriman.com/

--Boundary-00=_ALtJGEH0xbm6z8m
Content-Type: image/png;
name="f2.png"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="f2.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=_ALtJGEH0xbm6z8m--
--Boundary-00=_ALtJGEH0xbm6z8m--​