Menu
▾
▴
[Pybridge-commits] SF.net SVN: pybridge: [352] trunk/pybridge/pybridge/bridge/deck.py
|
From: <umg...@us...> - 2007-02-18 21:51:42
|
Revision: 352
http://svn.sourceforge.net/pybridge/?rev=352&view=rev
Author: umgangee
Date: 2007-02-18 13:51:28 -0800 (Sun, 18 Feb 2007)
Log Message:
-----------
Implemented two-way conversion between deals and deal indexes, based on the "Impossible Bridge Book" algorithm (see http://bridge.thomasoandrews.com/impossible/).
Modified Paths:
--------------
trunk/pybridge/pybridge/bridge/deck.py
Modified: trunk/pybridge/pybridge/bridge/deck.py
===================================================================
--- trunk/pybridge/pybridge/bridge/deck.py 2006-12-01 15:21:18 UTC (rev 351)
+++ trunk/pybridge/pybridge/bridge/deck.py 2007-02-18 21:51:28 UTC (rev 352)
@@ -1,5 +1,5 @@
# PyBridge -- online contract bridge made easy.
-# Copyright (C) 2004-2006 PyBridge Project.
+# 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
@@ -10,13 +10,15 @@
# 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.
-import random # To shuffle a deck.
+from copy import copy
+from operator import mul
+from random import shuffle
from card import Card, Rank, Suit
@@ -25,21 +27,55 @@
Seat = Enum('North', 'East', 'South', 'West') # Clockwise.
+# 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:
- """A Deck consists of 52 Card objects."""
+ """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 Seat 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 players from a standard 52-card deck.
+ """
- def __init__(self):
- self.cards = [Card(r, s) for r in Rank for s in Suit]
+ 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 dealOrdered(self, combination):
- """Returns a deal, ordered by combination."""
- pass # Not implemented yet.
+ def isValidDeal(self, deal):
+ """Checks that structure of deal conforms to requirements:
- def dealRandom(self):
- """Returns a deal, from a shuffled deck."""
- random.shuffle(self.cards)
+ * 4-element dict, mapping Seat 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
+
+
+ def dealRandom(self): # randomDeal
+ """Shuffles the deck and generates a random deal of hands.
+
+ @return: a deal dictionary.
+ """
+ shuffle(self.cards)
hands = {}
for seat in Seat:
hands[seat] = []
@@ -49,3 +85,71 @@
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 seat in (Seat.North, Seat.East, Seat.South):
+ indexes[seat] = 0
+ deal[seat].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[seat]):
+ indexes[seat] += comb(cardSeq.index(card), 13-i)
+ cardSeq.remove(card)
+
+ # Deal index = (Nindex * Emax * Smax) + (Eindex * Smax) + Sindex
+ indexes[Seat.North] *= self.Emax * self.Smax
+ indexes[Seat.East] *= self.Smax
+ return 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 = {Seat.North : (num / self.Smax) / self.Emax,
+ Seat.East : (num / self.Smax) % self.Emax,
+ Seat.South : (num % self.Smax) }
+
+ for seat in (Seat.North, Seat.East, Seat.South):
+ deal[seat] = []
+ for k in range(13, 0, -1):
+ # Find the largest n such that comb(n, k) <= indexes[seat].
+ n = 0
+ while comb(n+1, k) <= indexes[seat]:
+ n += 1
+ # Remove card index from indices, add card to hand.
+ indexes[seat] -= comb(n, k)
+ card = cardSeq[n]
+ deal[seat].append(card)
+ cardSeq.remove(card)
+
+ deal[Seat.West] = cardSeq # South has the remaining cards.
+ return deal
+
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
