From: <umgangee@us...>  20070720 14:32:17

Revision: 485 http://svn.sourceforge.net/pybridge/?rev=485&view=rev Author: umgangee Date: 20070720 07:32:16 0700 (Fri, 20 Jul 2007) Log Message:  New Deal class replaces Deck. Deckspecific methods become Deal classmethods. Use 1..D range instead of 0..D1 for consistency with IBB. (although the IBB algorithm itself deals in ranges 0..D1) 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 20070719 15:30:30 UTC (rev 484) +++ trunk/pybridge/pybridge/games/bridge/board.py 20070720 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 20070720 14:32:16 UTC (rev 485) @@ 0,0 +1,184 @@ +# PyBridge  online contract bridge made easy. +# Copyright (C) 20042007 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 021101301, 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/edusig/2001May/001288.html for details. +comb = lambda n, k: reduce(mul, range(n, nk, 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 52card 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..D1. + + # 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 = k1 # n < k implies comb(n, k) = 0 + # comb(n+1, k) = + # nk == 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), 13i) + 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 20070719 15:30:30 UTC (rev 484) +++ trunk/pybridge/pybridge/games/bridge/deck.py 20070720 14:32:16 UTC (rev 485) @@ 1,157 +0,0 @@ # PyBridge  online contract bridge made easy. # Copyright (C) 20042007 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 021101301, 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/edusig/2001May/001288.html for details. comb = lambda n, k: reduce(mul, range(n, nk, 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 52card 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:   * 4element 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..D1  """  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), 13i)  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..D1.  @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 = k1 # n < k implies comb(n, k) = 0   # comb(n+1, k) =  # nk = 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 20070720 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 20070719 15:30:30 UTC (rev 484) +++ trunk/pybridge/tests/bridge/test_deck.py 20070720 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. 