## vim:ts=4:et:nowrap ## ##---------------------------------------------------------------------------## ## ## PySol -- a Python Solitaire game ## ## Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer ## Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer ## Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer ## Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer ## Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer ## Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer ## All Rights Reserved. ## ## 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; see the file COPYING. ## If not, write to the Free Software Foundation, Inc., ## 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ## ## Markus F.X.J. Oberhumer ## ## http://www.oberhumer.com/pysol ## ##---------------------------------------------------------------------------## # imports import sys, os, re, string, time, types # PySol imports from mfxtools import * from mfxutil import SubclassResponsibility # /*********************************************************************** # // Abstract PySol Random number generator. # // # // We use a seed of type long in the range [0, MAX_SEED]. # ************************************************************************/ class PysolRandom: MAX_SEED = 0L ORIGIN_UNKNOWN = 0 ORIGIN_RANDOM = 1 ORIGIN_PREVIEW = 2 # random from preview ORIGIN_SELECTED = 3 # manually entered ORIGIN_NEXT_GAME = 4 # "Next game number" def __init__(self, seed=None): if seed is None: seed = self._getRandomSeed() self.initial_seed = self.setSeed(seed) self.origin = self.ORIGIN_UNKNOWN def __str__(self): return self.str(self.initial_seed) def reset(self): self.seed = self.initial_seed def getSeed(self): return self.seed def setSeed(self, seed): seed = self._convertSeed(seed) if type(seed) is not types.LongType: raise TypeError, "seeds must be longs" if not (0L <= seed <= self.MAX_SEED): raise ValueError, "seed out of range" self.seed = seed return seed def copy(self): random = PysolRandom(0L) random.__class__ = self.__class__ random.__dict__.update(self.__dict__) return random # # implementation # def choice(self, seq): return seq[int(self.random() * len(seq))] # Get a random integer in the range [a, b] including both end points. def randint(self, a, b): return a + int(self.random() * (b+1-a)) # # subclass responsibility # # Get the next random number in the range [0.0, 1.0). def random(self): raise SubclassResponsibility # # subclass overrideable # def _convertSeed(self, seed): return long(seed) def increaseSeed(self, seed): if seed < self.MAX_SEED: return seed + 1L return 0L def _getRandomSeed(self): t = long(time.time() * 256.0) t = (t ^ (t >> 24)) % (self.MAX_SEED + 1L) return t # # shuffle # see: Knuth, Vol. 2, Chapter 3.4.2, Algorithm P # see: FAQ of sci.crypt: "How do I shuffle cards ?" # def shuffle(self, seq): n = len(seq) - 1 while n > 0: j = self.randint(0, n) seq[n], seq[j] = seq[j], seq[n] n = n - 1 # /*********************************************************************** # // Linear Congruential random generator # // # // Knuth, Donald.E., "The Art of Computer Programming,", Vol 2, # // Seminumerical Algorithms, Third Edition, Addison-Wesley, 1998, # // p. 106 (line 26) & p. 108 # ************************************************************************/ class LCRandom64(PysolRandom): MAX_SEED = 0xffffffffffffffffL # 64 bits def str(self, seed): s = repr(long(seed)) if s[-1:] == "L": s = s[:-1] s = "0"*(20-len(s)) + s return s def random(self): self.seed = (self.seed*6364136223846793005L + 1L) & self.MAX_SEED return ((self.seed >> 21) & 0x7fffffffL) / 2147483648.0 # /*********************************************************************** # // Linear Congruential random generator # // In PySol this is only used for 0 <= seed <= 32000. # ************************************************************************/ class LCRandom31(PysolRandom): MAX_SEED = 0x7fffffffL # 31 bits def str(self, seed): return "%05d" % int(seed) def random(self): self.seed = (self.seed*214013L + 2531011L) & self.MAX_SEED return (self.seed >> 16) / 32768.0 def randint(self, a, b): self.seed = (self.seed*214013L + 2531011L) & self.MAX_SEED return a + (int(self.seed >> 16) % (b+1-a)) # /*********************************************************************** # // Old WHRandom code # ************************************************************************/ class WHRandom(PysolRandom): MAX_SEED = 30268L * 30306L * 30322L - 1 # ~44.66 bits (2.78e13) def str(self, seed): x, y, z = self._unpackSeed(seed) return "%04x-%04x-%04x" % (x, y, z) def random(self): x, y, z = self._unpackSeed(self.seed) x = (171 * x) % 30269 y = (172 * y) % 30307 z = (170 * z) % 30323 self.seed = self._packSeed(x, y, z) return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0 def _convertSeed(self, seed): if type(seed) is types.TupleType: return self._packSeed(seed[0], seed[1], seed[2]) return long(seed) # pack the tuple (x, y, z) into a long [0 .. MAX_SEED] def _packSeed(self, x, y, z): # precondition assert 0 < x < 30269 assert 0 < y < 30307 assert 0 < z < 30323 # convert seed = ((x - 1) * 30306L + (y - 1)) * 30322L + (z - 1) # postcondition assert 0L <= seed <= self.MAX_SEED return seed # unpack the long into a tuple (x, y, z) def _unpackSeed(self, seed): # precondition assert 0L <= seed <= self.MAX_SEED # convert seed, z = divmod(seed, 30322L) seed, y = divmod(seed, 30306L) x, y, z = int(seed + 1), int(y + 1), int(z + 1) # postcondition assert 0 < x < 30269 assert 0 < y < 30307 assert 0 < z < 30323 return x, y, z # /*********************************************************************** # // PySol support code # ************************************************************************/ # construct (gameid, Random) from seed string def constructRandom(s): s = re.sub(r"L$", "", str(s)) # cut off "L" from possible conversion to long s = re.sub(r"[\s\#\-\_\.\,]", "", string.lower(s)) if not s: return (None, None) gameid = None if 1 and len(s) in (12, 16): # check if this an old WHRandrom seed if re.search(r"[^0-9a-f]", s): raise ValueError, s ss = s if len(s) == 16: gameid = string.atoi(s[:4], 16) ss = s[4:] x = string.atoi(ss[ 0: 4], 16) y = string.atoi(ss[ 4: 8], 16) z = string.atoi(ss[ 8:12], 16) if 0 < x < 30269 and 0 < y < 30307 and 0 < z < 30323: return gameid, WHRandom((x, y, z)) if re.search(r"[^0-9]", s): raise ValueError, s seed = string.atol(s) if 0 <= seed <= 32000: return (gameid, LCRandom31(seed)) return (gameid, LCRandom64(seed)) # /*********************************************************************** # // # ************************************************************************/ def random_main(args): # check the WHRandom pack/unpack code x = ((1,1,1), (1,1,30322), (1,2,1), (30268,1,1), (30268,30306,30322)) print WHRandom.MAX_SEED for s in x: r = WHRandom(s) print s, r._unpackSeed(r.seed), r.seed assert s == r._unpackSeed(r.seed) rr = WHRandom() print rr.seed for i in range(100000): s = (rr.randint(1, 30268), rr.randint(1, 30306), rr.randint(1, 30322)) r = WHRandom(s) assert s == r._unpackSeed(r.seed) return 0 if __name__ == "__main__": sys.exit(random_main(sys.argv))