Welcome, guest | Sign In | My Account | Store | Cart
```import random

class Table:

# a random table of n different cards
def __init__(self,n=12):
self.cards = random.sample(Card.allcards(),n)

###############################################
# four different algorithms that list all sets
# on the table, from slow to fast

def findsets_gnt(self):     # generate and test
found = []
for i,ci in enumerate(self.cards):
for j,cj in enumerate(self.cards[i+1:],i+1):
for k,ck in enumerate(self.cards[j+1:],j+1):
if ci.isset(cj,ck):
found.append((ci,cj,ck))
return found

def findsets_gnt_mod(self):   # generate and test (faster)
found = []
for i,ci in enumerate(self.cards):
for j,cj in enumerate(self.cards[i+1:],i+1):
for k,ck in enumerate(self.cards[j+1:],j+1):
if ci.isset_mod(cj,ck):
found.append((ci,cj,ck))
return found

def findsets_simple(self):  # using thirdcard_simple
found = []
have = {}
for pos,card in enumerate(self.cards):
have[card]=pos
for i,ci in enumerate(self.cards):
for j,cj in enumerate(self.cards[i+1:],i+1):
k = have.get(ci.thirdcard_simple(cj))
if k > j:  # False if k is None
found.append((ci,cj,self.cards[k]))
return found

def findsets_fast(self):  # using thirdcard_fast
found = []
have = [None for _ in range(256)]
for pos,card in enumerate(self.cards):
have[card.bits]=pos
for i,ci in enumerate(self.cards):
for j,cj in enumerate(self.cards[i+1:],i+1):
k = have[ci.thirdcard_fast(cj)]
if k > j:  # False if k is None
found.append((ci,cj,self.cards[k]))
return found

class Card:

def __init__(self,*attrs):
# a card is a simple 4-tuple of attributes
# each attr is supposed to be either 0, 1 or 2
self.attrs = attrs
# alternative representation of attrs, in 8 bits:
# 2 bits per attr, highest bits represent first attr
self.bits = sum(a<<(2*i) for i,a in enumerate(attrs[::-1]))

def __eq__(self,other):
return self.attrs == other.attrs

def __hash__(self):
return hash(self.attrs)

def __repr__(self):
return 'Card({})'.format(','.join(self.attrs))

# most readable way to express what a SET is
def isset(self,card1,card2):
def allsame(v0,v1,v2):
return v0==v1 and v1==v2
def alldifferent(v0,v1,v2):
return len(set((v0,v1,v2)))==3
return all(allsame(v0,v1,v2) or alldifferent(v0,v1,v2)
for (v0,v1,v2) in zip(self.attrs,card1.attrs,card2.attrs))

# a more mathy (and slightly faster) way
def isset_mod(self,card1,card2):
return all((v0+v1+v2)%3==0 for (v0,v1,v2) in zip(self.attrs,card1.attrs,card2.attrs))

# which third card is needed to complete the set
def thirdcard_simple(self,other):
def thirdval((v0,v1)):
return (-v0-v1)%3
return Card(*map(thirdval,zip(self.attrs,other.attrs)))

# same thing, but using the 8-bit representation
def thirdcard_fast(self,other):
# NB returns bits
x,y = self.bits,other.bits
xor = x^y
swap = ((xor & mask1) >> 1) | ((xor & mask0) << 1)
return (x&y) | (~(x|y) & swap)

# all 81 possible cards
@staticmethod
def allcards():
return [ Card(att0,att1,att2,att3)
for att0 in (0,1,2)
for att1 in (0,1,2)
for att2 in (0,1,2)
for att3 in (0,1,2)
]

# bit masks for low and high bits of the attributes
mask0 = sum(1<<(2*i) for i in range(4))    # 01010101
mask1 = sum(1<<(2*i+1) for i in range(4))  # 10101010
```

#### Diff to Previous Revision

```--- revision 1 2013-04-04 22:15:32
+++ revision 2 2013-04-05 12:49:36
@@ -2,17 +2,9 @@

class Table:

-    # all 81 possible cards
-    allcards = [ Card(att0,att1,att2,att3)
-                   for att0 in (0,1,2)
-                   for att1 in (0,1,2)
-                   for att2 in (0,1,2)
-                   for att3 in (0,1,2)
-               ]
-
# a random table of n different cards
def __init__(self,n=12):
-        self.cards = random.sample(Table.allcards,n)
+        self.cards = random.sample(Card.allcards(),n)

###############################################
# four different algorithms that list all sets
@@ -106,6 +98,16 @@
swap = ((xor & mask1) >> 1) | ((xor & mask0) << 1)
return (x&y) | (~(x|y) & swap)

+    # all 81 possible cards
+    @staticmethod
+    def allcards():
+        return [ Card(att0,att1,att2,att3)
+                   for att0 in (0,1,2)
+                   for att1 in (0,1,2)
+                   for att2 in (0,1,2)
+                   for att3 in (0,1,2)
+               ]
+
# bit masks for low and high bits of the attributes
mask0 = sum(1<<(2*i) for i in range(4))    # 01010101
mask1 = sum(1<<(2*i+1) for i in range(4))  # 10101010
```