# Magic Fingers (#120)

**URL:** <https://www.ruby-forum.com/t/magic-fingers-120/91921>\
**Category:** Ruby\
**Created:** [April 13, 2007, 1:49pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921 "2007-04-13T13:49:00Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 13, 2007, 1:49pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/1 "2007-04-13T13:49:00Z")

</div>

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps  
everyone  
on Ruby T. 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 Q. 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.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 14, 2007, 7:50pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/2 "2007-04-14T19:50:45Z")

</div>

On Apr 13, 7:48 am, Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> ```
> 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

* * *

Interested in hands-on, on-site Ruby training? See [http://LearnRuby.com](http://LearnRuby.com)  
for information about a well-reviewed class.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 14, 2007, 7:53pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/3 "2007-04-14T19:53:46Z")

</div>

On Apr 14, 2007, at 12:50 PM, Eric I. wrote:

> On Apr 13, 7:48 am, Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > ```
> > 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?

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

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 15, 2007, 9:50pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/4 "2007-04-15T21:50:55Z")

</div>

On Apr 15, 2007, at 9:00 AM, Eric I. wrote:

> 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 G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 15, 2007, 4:02pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/5 "2007-04-15T16:02:45Z")

</div>

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](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[i][0])  
result \<\< ‘|’ \* @hands[i][0]  
result \<\< ’ ’  
result \<\< ‘|’ \* @hands[i][1]  
result \<\< ‘-’ \* (5 - @hands[i][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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 15, 2007, 10:41pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/6 "2007-04-15T22:41:06Z")

</div>

On Apr 15, 3:49 pm, James Edward G. II [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> James Edward G. 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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 15, 2007, 9:19pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/7 "2007-04-15T21:19:52Z")

</div>

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](http://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 Q. 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.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 15, 2007, 11:01pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/8 "2007-04-15T23:01:07Z")

</div>

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](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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 16, 2007, 1:49pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/9 "2007-04-16T13:49:28Z")

</div>

On Apr 15, 2007, at 3:40 PM, Eric I. wrote:

> > my explanation of the rules somehow. I’m see if I can figure out  
> > what I changed…
> > 
> > James Edward G. 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 G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 18, 2007, 10:40pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/10 "2007-04-18T22:40:03Z")

</div>

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

On Friday 13 April 2007 07:48, Ruby Q. wrote:

> 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.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 18, 2007, 10:47pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/11 "2007-04-18T22:47:04Z")

</div>

On Apr 18, 2007, at 3:38 PM, Jesse M. wrote:

> Regarding clapping, is something like 1,3 -\> 0,4 allowed?
> 
> On Friday 13 April 2007 07:48, Ruby Q. wrote:
> 
> > 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.

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 G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 18, 2007, 11:06pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/12 "2007-04-18T23:06:06Z")

</div>

On Apr 18, 4:45 pm, James Edward G. II [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> On Apr 18, 2007, at 3:38 PM, Jesse M. wrote:
> 
> > Regarding clapping, is something like 1,3 → 0,4 allowed?

> 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

On-site, hands-on Ruby training is available from [http://LearnRuby.com](http://LearnRuby.com)  
!

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 16, 2007, 5:22pm UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/13 "2007-04-16T17:22:01Z")

</div>

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](http://www.matt-hulse.com)

require ‘player’

class Game  
attr\_reader :p1, :p2, :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](http://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](http://www.matt-hulse.com)

require ‘hand’

class Player  
attr\_reader :player\_num, :right, :left, :strategy, :game  
def initialize(player\_num, strategy, game)  
@player\_num = player\_num  
@strategy = strategy  
@game = game  
@right = Hand.new(:right,1)  
@left = Hand.new(:left,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(removed\_email\_address@domain.invalid\_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(removed\_email\_address@domain.invalid\_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](http://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[i]}#{num\_rounds[i]}”  
}

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[i]}#{num\_rounds[i]}”  
}

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[i]}#{num\_rounds[i]}”  
}

wins.each\_pair{|key,value|  
puts “Player #{key}: #{value} wins”  
}

Thanks,

* * *

Matt Hulse  
removed\_email\_address@domain.invalid  
[http://www.matt-hulse.com](http://www.matt-hulse.com)

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 19, 2007, 4:25am UTC](https://www.ruby-forum.com/t/magic-fingers-120/91921/14 "2007-04-19T04:25:26Z")

</div>

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](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 Q. 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 Q. 120: Magic Fingers

require ‘constants’

module Outcome

# Order important: from best-for-player-1 to best-for-player-2

Outcome::P1Win = 0  
Outcome::Unknown = 1  
Outcome::P2Win = 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 Q. 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 = 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::P1Win : 

```

Outcome::P2Win)  
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[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] += 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 Q. 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::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 = 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 Q. 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::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 Q. 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 Q. 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::P1Win.

P1WinParentNodeOpts =  
‘[width=1.5,shape=oval,style=filled,fillcolor=green]’

# Node with best\_outcome == Outcome::P2Win.

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::P1Win =\> P1WinParentNodeOpts,  
Outcome::P2Win =\> 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

# -------------------------------------------------------------------