[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Magic Fingers (#120

James Gray

4/13/2007 11:49:00 AM

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

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

Eric I.

4/14/2007 5:46:00 PM

0

On Apr 13, 7:48 am, Ruby Quiz <j...@grayproductions.net> 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://Lea...
for information about a well-reviewed class.

James Gray

4/14/2007 5:52:00 PM

0

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

> On Apr 13, 7:48 am, Ruby Quiz <j...@grayproductions.net> 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 Gray II

Eric I.

4/15/2007 1:59:00 PM

0

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://Lea...

====

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

Jesse Merriman

4/15/2007 7:20:00 PM

0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

However, for the regular game:

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

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

Here's the code:

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

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


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

require 'constants'

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

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


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

require 'constants'
require 'set'

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

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

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

self
end

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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


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

# Ruby Quiz 120: Magic Fingers

require 'game'

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

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemer...

James Gray

4/15/2007 7:50:00 PM

0

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 Gray II

Eric I.

4/15/2007 8:36:00 PM

0

On Apr 15, 3:49 pm, James Edward Gray II <j...@grayproductions.net>
wrote:
> 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 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.

4/15/2007 8:59:00 PM

0

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://Lea...

====

# 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 Gray

4/16/2007 11:48:00 AM

0

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

> On Apr 15, 3:49 pm, James Edward Gray II <j...@grayproductions.net>
> wrote:
>> 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 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

4/16/2007 3:17:00 PM

0

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

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 :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(5-@left.finger_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(5-@right.finger_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[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
matt.hulse@gmail.com
http://www.matt...






On Apr 13, 5:48 am, Ruby Quiz <j...@grayproductions.net> wrote:
> 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.rub...
>
> 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

4/18/2007 8:39:00 PM

0

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

On Friday 13 April 2007 07:48, Ruby Quiz 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.

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemer...