git @ Cat's Eye Technologies
master

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71``` ```#!/usr/bin/env python # A 2-player game based on the description here: # http://blog.computationalcomplexity.org/2012/11/a-simple-pspace-complete-problem.html # # SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain. # For more information, please refer to # SPDX-License-Identifier: Unlicense import random class SetGame(object): def __init__(self, num_sets=10, num_elems=10, density=0.4): self.num_sets = num_sets self.num_elems = num_elems self.density = density random.seed() self.sets = [] for i in xrange(0, num_sets): self.sets.append(self.random_set()) def random_set(self): s = set() for i in xrange(0, int(self.num_elems * self.density)): s.add(random.randint(0, self.num_elems - 1)) return s def game_over(self): for s in self.sets: if len(s) > 0: return False return True def perform_move(self, n): t = self.sets[n].copy() for s in self.sets: s -= t def show(self): i = 0 for s in self.sets: print "Set #%d: %s" % (i, sorted(list(s))) i += 1 def move(self, player): valid = False while not valid: s = raw_input("Player %d, select a set to remove: " % player) try: s = int(s) if len(self.sets[s]) == 0: print "That set is empty. Try a different one." else: self.perform_move(int(s)) valid = True except (ValueError, IndexError): print "Bad input!" self.show() def play(self): player = 2 self.show() while not self.game_over(): player = 3 - player self.move(player) print "Player %d won!" % player if __name__ == '__main__': s = SetGame() s.play() ```