Menu
▾
▴
[Pybridge-commits] SF.net SVN: pybridge: [485] trunk/pybridge
|
From: <umg...@us...> - 2007-07-20 14:32:17
|
Revision: 485
http://svn.sourceforge.net/pybridge/?rev=485&view=rev
Author: umgangee
Date: 2007-07-20 07:32:16 -0700 (Fri, 20 Jul 2007)
Log Message:
-----------
New Deal class replaces Deck. Deck-specific methods become Deal classmethods. Use 1..D range instead of 0..D-1 for consistency with IBB. (although the IBB algorithm itself deals in ranges 0..D-1)
Modified Paths:
--------------
trunk/pybridge/pybridge/games/bridge/board.py
Added Paths:
-----------
trunk/pybridge/pybridge/games/bridge/deal.py
trunk/pybridge/tests/bridge/test_deal.py
Removed Paths:
-------------
trunk/pybridge/pybridge/games/bridge/deck.py
trunk/pybridge/tests/bridge/test_deck.py
Modified: trunk/pybridge/pybridge/games/bridge/board.py
===================================================================
--- trunk/pybridge/pybridge/games/bridge/board.py 2007-07-19 15:30:30 UTC (rev 484)
+++ trunk/pybridge/pybridge/games/bridge/board.py 2007-07-20 14:32:16 UTC (rev 485)
@@ -18,7 +18,7 @@
import random
import time
-from deck import Deck
+from deal import Deal
from symbols import Direction, Vulnerable
@@ -53,8 +53,7 @@
@param result:
@type result:
"""
- deck = Deck()
- self['deal'] = deck.randomDeal()
+ self['deal'] = Deal.fromRandom()
self['num'] = self.get('num', 0) + 1
self['time'] = tuple(time.localtime())
Copied: trunk/pybridge/pybridge/games/bridge/deal.py (from rev 480, trunk/pybridge/pybridge/games/bridge/deck.py)
===================================================================
--- trunk/pybridge/pybridge/games/bridge/deal.py (rev 0)
+++ trunk/pybridge/pybridge/games/bridge/deal.py 2007-07-20 14:32:16 UTC (rev 485)
@@ -0,0 +1,184 @@
+# PyBridge -- online contract bridge made easy.
+# Copyright (C) 2004-2007 PyBridge Project.
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+
+from copy import copy
+from operator import mul
+import random
+
+from card import Card
+from symbols import Direction, Rank, Suit
+
+
+# See http://mail.python.org/pipermail/edu-sig/2001-May/001288.html for details.
+comb = lambda n, k: reduce(mul, range(n, n-k, -1)) / reduce(mul, range(1, k+1))
+
+
+class Deal(dict):
+ """Represents a deal of hands as a dict containing lists of cards.
+
+ Operations to encode/decode deals into a variety of formats are provided,
+ including "impossible bridge book" index values and PBN strings.
+
+ Definitions:
+ - A hand is a collection of 13 cards from the deck.
+ - A deal is a distribution of all 52 cards to four hands.
+
+ There are exactly 52! / (13!)**4 (comb(52,13) * comb(39,13) * comb(26,13))
+ distinct deals of 13 cards to 4 positions from a standard 52-card deck.
+ """
+
+ # Required order: Ace of Spades, King of Spades, ..., Two of Clubs.
+ __cards = [Card(r, s) for s in reversed(Suit) for r in reversed(Rank)]
+
+ __Nmax = comb(52, 13)
+ __Emax = comb(39, 13)
+ __Smax = comb(26, 13)
+ __D = __Nmax * __Emax * __Smax
+
+
+ def __init__(self, mapping):
+ super(Deal, self).__init__(mapping)
+ for hand in self.values():
+ hand.sort()
+
+
+ @classmethod
+ def fromRandom(cls):
+ """Generates a random deal of hands from a 'shuffled' deck.
+
+ @return: an instance of Deal.
+ """
+ # This is more efficient than calling fromIndex() with a random number.
+ deck = copy(cls.__cards)
+ random.shuffle(deck)
+ hands = dict((pos, sorted(deck[13*i : 13*(i+1)]))
+ for i, pos in enumerate(Direction))
+ return cls(hands)
+
+
+ @classmethod
+ def fromIndex(cls, num):
+ """Generates the deal which corresponds to the specified "page number".
+
+ This implements the "impossible bridge book" decoding algorithm by
+ Thomas Andrews, see http://bridge.thomasoandrews.com/impossible/.
+
+ @param num: integer in range 1..D.
+ @return: a Deal object containing the corresponding deal.
+ """
+ assert isinstance(num, (int, long)), "index must be an integer"
+ assert 1 <= num <= cls.__D, "index not in range %s..%s" % (1, cls.__D)
+
+ cardSeq = copy(cls.__cards) # Make a copy for modification.
+ hands = dict((pos, []) for pos in Direction)
+ num -= 1 # Decrement page number to fit within range 0..D-1.
+
+ # Split index into hand indexes.
+ indexes = {Direction.North : (num / cls.__Smax) / cls.__Emax,
+ Direction.East : (num / cls.__Smax) % cls.__Emax,
+ Direction.South : (num % cls.__Smax) }
+
+ for position in (Direction.North, Direction.East, Direction.South):
+ for k in range(13, 0, -1):
+
+ # Find the largest n such that comb(n, k) <= indexes[position].
+ n = k-1 # n < k implies comb(n, k) = 0
+ # comb(n+1, k) =
+ # n-k == -1 => comb(n, k) * (n+1)
+ # otherwise => (comb(n, k) * (n+1)) / (n+1 - k)
+ while comb(n+1, k) <= indexes[position]:
+ n += 1
+
+ # Remove card index from indices, add card to hand.
+ indexes[position] -= comb(n, k)
+ card = cardSeq[n]
+ hands[position].append(card)
+ cardSeq.remove(card)
+
+ hands[Direction.West] = cardSeq # West has the remaining cards.
+
+ return cls(hands)
+
+
+ def toIndex(self):
+ """Computes the "page number" which corresponds to this deal.
+
+ This implements the "impossible bridge book" encoding algorithm by
+ Thomas Andrews, see http://bridge.thomasoandrews.com/impossible/.
+
+ @return: integer in range 1..D
+ """
+ cardSeq = copy(self.__cards) # Make a copy for modification.
+ indexes = {}
+
+ # For each hand, compute indexes of cards in cardSeq.
+ for position in (Direction.North, Direction.East, Direction.South):
+ indexes[position] = 0
+ self[position].sort(reverse=False)
+ # It is desirable to remove cards from cardSeq when adding their
+ # indexes, instead of doing so in an extra step.
+ # Removing cards backwards preserves the indexes of later cards.
+ for i, card in enumerate(self[position]):
+ indexes[position] += comb(cardSeq.index(card), 13-i)
+ cardSeq.remove(card)
+
+ # Deal index = (Nindex * Emax * Smax) + (Eindex * Smax) + Sindex
+ indexes[Direction.North] *= self.__Emax * self.__Smax
+ indexes[Direction.East] *= self.__Smax
+
+ num = sum(indexes.values()) + 1 # Increment to fit within range 1..D.
+ return long(num)
+
+
+ __pbnDirection = dict(zip('NESW', Direction))
+ __pbnRank = dict(zip('23456789TJQKA', Rank))
+
+
+ @classmethod
+ def fromString(cls, dealstr):
+ """Generates the deal which corresponds to the given PBN deal string.
+
+ As per the PBN specification, the given deal string should conform to
+ the format "<first>:<1st_hand> <2nd_hand> <3rd_hand> <4th_hand>".
+
+ @param dealstr: a PBN deal string.
+ @return: a Deal object containing the corresponding deal.
+ """
+ # Reconstruct deal.
+ first, hands = dealstr.split(":")
+ firstindex = cls.__pbnDirection[first.strip()].index
+ order = Direction[firstindex:] + Direction[:firstindex]
+
+ deal = dict((pos, []) for pos in Direction)
+
+ for position, hand in zip(order, hands.strip().split(' ')):
+ for suit, suitcards in zip(reversed(Suit), hand.split('.')):
+ for rank in suitcards:
+ card = Card(cls.__pbnRank[rank], suit)
+ deal[position].append(card)
+
+ return cls(deal)
+
+
+ def toString(self):
+ """Computes the PBN deal string which corresponds to this deal.
+
+ @return: a PBN deal string.
+ """
+ raise NotImplementedError
+
Deleted: trunk/pybridge/pybridge/games/bridge/deck.py
===================================================================
--- trunk/pybridge/pybridge/games/bridge/deck.py 2007-07-19 15:30:30 UTC (rev 484)
+++ trunk/pybridge/pybridge/games/bridge/deck.py 2007-07-20 14:32:16 UTC (rev 485)
@@ -1,157 +0,0 @@
-# PyBridge -- online contract bridge made easy.
-# Copyright (C) 2004-2007 PyBridge Project.
-#
-# This program is free software; you can redistribute it and/or
-# modify it under the terms of the GNU General Public License
-# as published by the Free Software Foundation; either version 2
-# of the License, or (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
-
-
-from copy import copy
-from operator import mul
-from random import shuffle
-
-from card import Card
-from symbols import Direction, Rank, Suit
-
-
-# See http://mail.python.org/pipermail/edu-sig/2001-May/001288.html for details.
-comb = lambda n, k: reduce(mul, range(n, n-k, -1)) / reduce(mul, range(1, k+1))
-
-
-# TODO: consider making Hand a subclass of List, with additional constraints.
-
-class Deck(object):
- """A Deck object provides operations for dealing Card objects.
-
- A hand is a collection of 13 cards from the deck.
- A deal is a distribution of all 52 cards to four hands.
-
- A deal is represented as a dictionary, mapping Direction labels to
- lists (hands) of Card objects.
-
- There are exactly 52! / (13!)**4 (comb(52,13) * comb(39,13) * comb(26,13))
- distinct deals of 13 cards to 4 positions from a standard 52-card deck.
- """
-
- cards = [Card(r, s) for r in Rank for s in Suit]
- cardSeq = copy(cards)
- cardSeq.sort(reverse=True) # Required order: Ace of Spades -> Two of Clubs.
-
- Nmax = comb(52, 13)
- Emax = comb(39, 13)
- Smax = comb(26, 13)
- D = Nmax * Emax * Smax
-
-
- def isValidDeal(self, deal):
- """Checks that structure of deal conforms to requirements:
-
- * 4-element dict, mapping Direction objects to hand lists.
- * Hand lists contain exactly 13 Card objects.
- * No card may be repeated in the same hand, or between hands.
- * The cards in hands may be in any order.
-
- @param deal: a deal dict.
- @return: True if deal is valid, False otherwise.
- """
- return True # TODO - if invalid, perhaps give reason
-
-
- def randomDeal(self):
- """Shuffles the deck and generates a random deal of hands.
-
- @return: a deal dictionary.
- """
- shuffle(self.cards)
- hands = {}
- for position in Direction:
- hands[position] = []
- for index, card in enumerate(self.cards):
- hands[Direction[index % len(Direction)]].append(card)
- for hand in hands.values():
- hand.sort()
- return hands
-
-
- def dealToIndex(self, deal):
- """Computes the index which corresponds to the specified deal.
-
- This implements the "impossible bridge book" encoding algorithm by
- Thomas Andrews, see http://bridge.thomasoandrews.com/impossible/.
-
- @param deal: dict representing a valid deal.
- @return: integer in range 0..D-1
- """
- assert self.isValidDeal(deal)
-
- cardSeq = copy(self.cardSeq) # Make a copy for modification.
- indexes = {}
-
- # For each hand, compute indexes of cards in cardSeq.
- for position in (Direction.North, Direction.East, Direction.South):
- indexes[position] = 0
- deal[position].sort(reverse=False)
- # It is desirable to remove cards from cardSeq when adding their
- # indexes, instead of doing so in an extra step.
- # Removing cards backwards preserves the indexes of later cards.
- for i, card in enumerate(deal[position]):
- indexes[position] += comb(cardSeq.index(card), 13-i)
- cardSeq.remove(card)
-
- # Deal index = (Nindex * Emax * Smax) + (Eindex * Smax) + Sindex
- indexes[Direction.North] *= self.Emax * self.Smax
- indexes[Direction.East] *= self.Smax
- return long(sum(indexes.values()))
-
-
- def indexToDeal(self, num):
- """Generates the deal which corresponds to the specified index.
-
- This implements the "impossible bridge book" decoding algorithm by
- Thomas Andrews, see http://bridge.thomasoandrews.com/impossible/.
-
- @param num: integer in range 0..D-1.
- @return: dict representing a valid deal.
- """
- assert type(num) in (int, long), "index must be an integer"
- assert 0 <= num < self.D, "index not in required range"
-
- cardSeq = copy(self.cardSeq) # Make a copy for modification.
- deal = {}
-
- # Split index into hand indexes.
- indexes = {Direction.North : (num / self.Smax) / self.Emax,
- Direction.East : (num / self.Smax) % self.Emax,
- Direction.South : (num % self.Smax) }
-
- for position in (Direction.North, Direction.East, Direction.South):
- deal[position] = []
- for k in range(13, 0, -1):
- # Find the largest n such that comb(n, k) <= indexes[position].
- n = k-1 # n < k implies comb(n, k) = 0
-
- # comb(n+1, k) =
- # n-k = -1 => comb(n, k) * (n+1)
- # otherwise => (comb(n, k) * (n+1)) / (n+1 - k)
- while comb(n+1, k) <= indexes[position]:
- n += 1
-
- # Remove card index from indices, add card to hand.
- indexes[position] -= comb(n, k)
- card = cardSeq[n]
- deal[position].append(card)
- cardSeq.remove(card)
-
- deal[Direction.West] = cardSeq # West has the remaining cards.
- return deal
-
Copied: trunk/pybridge/tests/bridge/test_deal.py (from rev 480, trunk/pybridge/tests/bridge/test_deck.py)
===================================================================
--- trunk/pybridge/tests/bridge/test_deal.py (rev 0)
+++ trunk/pybridge/tests/bridge/test_deal.py 2007-07-20 14:32:16 UTC (rev 485)
@@ -0,0 +1,83 @@
+import unittest
+
+from pybridge.games.bridge.card import Card
+from pybridge.games.bridge.deal import Deal
+from pybridge.games.bridge.symbols import Direction, Rank, Suit
+
+
+class TestDeck(unittest.TestCase):
+
+ cards = sorted(Card(r, s) for r in Rank for s in Suit)
+
+ samples = {}
+
+ samples[1] = Deal({Direction.North: [Card(r, Suit.Spade) for r in Rank],
+ Direction.East: [Card(r, Suit.Heart) for r in Rank],
+ Direction.South: [Card(r, Suit.Diamond) for r in Rank],
+ Direction.West: [Card(r, Suit.Club) for r in Rank]})
+
+ # http://bridgehands.com/D/Duke_of_Cumberland_Hand.htm
+ samples[25216995119420903953708290155] = Deal.fromString(
+ "N:..Q8765432.AQT84 65432.T9872.JT9. T987.6543..76532 AKQJ.AKQJ.AK.KJ9")
+
+ # http://bridgehands.com/B/John_Bennett_Murder.htm
+ samples[49115408832893597588305377049] = Deal.fromString(
+ "S:KJ985.K762.85.KT Q72.AJ3.AQT92.J6 AT63.T85.4.A9842 4.Q94.KJ763.Q753")
+
+ # From the PBN v2.0 specification document.
+ samples[51845212465382378289082480212] = Deal.fromString(
+ "N:.63.AKQ987.A9732 A8654.KQ5.T.QJT6 J973.J98742.3.K4 KQT2.AT.J6542.85")
+
+ # http://bridgehands.com/M/Mississippi_Heart_Hand.htm
+ samples[53520933857671775260919265981] = Deal.fromString(
+ "S:AKQ.AKQJT9..AKQJ .8765432.AKQJT9. T5432..5432.5432 J9876..876.T9876")
+
+
+ def validateDeal(self, deal):
+ """Checks that structure of deal conforms to requirements:
+
+ - Each position in Direction maps to a hand, represented as a list.
+ - Hand lists contain exactly 13 Card objects.
+ - No card may be repeated in the same hand, or between hands.
+
+ @param deal: a Deal instance.
+ """
+ assert isinstance(deal, Deal), "deal not a Deal instance"
+ assert set(deal.keys()) == set(Direction), "invalid set of keys"
+
+ extractcards = []
+ for pos, hand in deal.items():
+ assert len(hand) == 13, "%s hand does not contain 13 cards" % pos
+ extractcards.extend(hand)
+ assert self.cards == sorted(extractcards), "not a pure set of cards"
+
+
+ def test_generateRandom(self):
+ """Testing generation of random deals"""
+ deal = Deal.fromRandom()
+ try:
+ self.validateDeal(deal)
+ except Exception, e:
+ self.fail(e, deal)
+
+
+ def test_toIndex(self):
+ """Testing toIndex method over a set of known deals"""
+ for index, deal in self.samples.items():
+ self.assertEqual(deal.toIndex(), index)
+
+
+ def test_fromIndex(self):
+ """Testing Deal.fromIndex over a set of known indexes"""
+ for index, deal in self.samples.items():
+ self.assertEqual(Deal.fromIndex(index), deal)
+
+
+def main():
+ suite = unittest.makeSuite(TestDeck)
+ unittest.TextTestRunner(verbosity=2).run(suite)
+
+
+if __name__ == '__main__':
+ main()
+
Deleted: trunk/pybridge/tests/bridge/test_deck.py
===================================================================
--- trunk/pybridge/tests/bridge/test_deck.py 2007-07-19 15:30:30 UTC (rev 484)
+++ trunk/pybridge/tests/bridge/test_deck.py 2007-07-20 14:32:16 UTC (rev 485)
@@ -1,52 +0,0 @@
-import unittest
-
-from pybridge.games.bridge.deck import Deck
-
-
-class TestDeck(unittest.TestCase):
-
-
- def setUp(self):
- self.deck = Deck()
-
-
- def tearDown(self):
- self.deck = None
-
-
- def testRandomDeal(self):
- """Testing randomDeal"""
- for i in range(100):
- deal = self.deck.randomDeal()
- self.assert_(self.deck.isValidDeal(deal))
-
-
- def testDealToIndex(self):
- """Testing dealToIndex (assuming indexToDeal correct)"""
- n = 1
- while n < self.deck.D:
- deal = self.deck.indexToDeal(n)
- pn = self.deck.dealToIndex(deal)
- self.assertEqual(n, pn)
- n = n*2 + 1
-
-
- def testIndexToDeal(self):
- """Testing indexToDeal (assuming dealToIndex and isValidDeal correct)"""
- n = 1
- while n < self.deck.D:
- deal = self.deck.indexToDeal(n)
- self.assert_(self.deck.isValidDeal(deal))
- pn = self.deck.dealToIndex(deal)
- self.assertEqual(n, pn)
- n = n*2 + 1
-
-
-def main():
- suite = unittest.makeSuite(TestDeck)
- unittest.TextTestRunner(verbosity=2).run(suite)
-
-
-if __name__ == '__main__':
- main()
-
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
