Tally

1 #!/usr/bin/python2.5 2 """Arithmetic support for "zero-agnostic" numbers. 3 4 Example use:: 5 6 # simple addition test 7 a = Tally(["19"]) 8 b = Tally(["1"]) 9 c = a + b 10 print c.possibilities() # set([110,20]) 11 12 # simple multiplication test 13 a = Tally(10) 14 c = a * 3 15 print c.possibilities() # set([120, 210, 30, 1110]) 16 17 """ 18 import types 19 from Functional import LList, NULL 20

21 -def _addFast(a, b, limit=None, cache=None):

22 """Add two zero-agnostic values, specially treating the least-significant 23 digit (whose position is fixed). This is 'fast' addition: carries are 24 reduced immediately, which means addition is not commutative as the 25 results may (conservatively) include extra values. For example, 26 18+(51+52) will (incorrectly) include '31' as a possibility, since 27 51+52=103=13.""" 28 29 if cache is None: 30 cache = {} # create a new tail cache if none is given. 31 def addTailCache (t1, t2, carry, limit): 32 key = (t1, t2, carry, limit) 33 if not key in cache: 34 cache[key] = frozenset(addTail(t1, t2, carry, limit)) 35 for r in cache[key]: 36 yield r

37 def addTail (t1, t2, carry, limit): 38 """Add two zero-agnostic integers to yield a generator of 39 zero-agnostic integers. This function is only valid on the 40 tails of zero-agnostic integers, since the least-significant 41 digits of these are actually fixed in position.""" 42 assert isinstance(t1, int) and isinstance(t2, int) 43 assert isinstance(carry, int) and carry < 10 44 def skpsum(num, carry): 45 """If the least-significant digit of the supplied carry is 46 non-zero, shift on that least-significant digit; otherwise 47 return num unchanged.""" 48 digit = carry % 10 49 return num if digit == 0 else (num*10)+digit 50 def head (num): 51 """Return the least-significant digit of the number.""" 52 assert (num % 10) != 0 # zeros should have been elided 53 return num % 10 54 def tail (num): 55 """Strip the least-significant digit from the number.""" 56 return num // 10 57 def nlimit (num): 58 return limit if limit is None or (num%10)==0 else limit-1 59 # early exit if result is too long. 60 if limit is not None and limit < 0: 61 return 62 # 1st option: insert 0 on both cords, so this # is just the carry. 63 if carry != 0: 64 assert carry < 10 65 for r in addTailCache(t1, t2, 0, nlimit(carry)): 66 yield skpsum(r, carry) 67 # 2nd option: add knot value from t1 68 if t1 > 0: 69 digit = carry + head(t1) 70 for r in addTailCache(tail(t1), t2, tail(digit), nlimit(digit)): 71 yield skpsum(r, digit) 72 # 3rd option: add knot value from t2 73 if t2 > 0: 74 digit = carry + head(t2) 75 for r in addTailCache(t1, tail(t2), tail(digit), nlimit(digit)): 76 yield skpsum(r, digit) 77 # 4th option: add knot value from t1 and t2 (both knots same place) 78 if t1 > 0 and t2 > 0: 79 digit = carry + head(t1) + head(t2) 80 for r in addTailCache(tail(t1), tail(t2), tail(digit), nlimit(digit)): 81 yield skpsum(r, digit) 82 # check for terminal condition 83 if t1 == 0 and t2 == 0 and carry == 0: 84 yield 0 85 # okay, let's do the addition! 86 # first digit is special 87 digit = (a%10) + (b%10) 88 for r in addTail(a//10, b//10, digit//10, 89 limit-1 if limit is not None else None): 90 yield (r*10) + (digit%10) 91

92 -class TallyNum:

93 """A single "zero agnostic" number, as represented 94 in khipu. 95 96 `TallyNum` is only used during 'slow' tally processing. To avoid 97 breaking commutivity, each 'digit' can exceed 10; a separate step 98 is required to 'reduce' the carries in order to perform comparisons 99 with other `TallyNum` objects. 100 """

101 - def __init__ (self, arg):

102 """The lstval field is a little-endian list of 'digits', although 103 carries are not performed so digits can be any positive integer. 104 The least-significant 'digit' is lstval[0].""" 105 if isinstance (arg, TallyNum): 106 self.lstval = arg.lstval 107 elif isinstance (arg, LList): 108 self.lstval = arg 109 elif isinstance (arg, list): 110 self.lstval = LList.fromList(arg) 111 else: 112 if isinstance (arg, str): 113 arg = int(arg) # sanity-check. 114 assert isinstance(arg, int) or isinstance(arg, long) 115 # split integer into reverse-ordered digits 116 self.lstval = LList.fromList(map(int, reversed(str(arg))))

117 - def __repr__ (self):

118 return "TallyNum("+self.lstval.toList().__repr__()+")"

119 - def __str__ (self):

120 return '-'.join(reversed(map(str, self.lstval)))

121 - def __eq__ (self, other):

122 return self.lstval == other.lstval

123 - def __ne__ (self, other):

124 return self.lstval != other.lstval

125 - def __cmp__ (self, other):

126 return self.lstval.__cmp__(other.lstval)

127 - def __hash__ (self):

128 return self.lstval.__hash__()

129 - def reduceCarry (self, limit=None):

130 """Generator of ints representing carry-reduced values of this 131 TallyNum. If none of the 'digits' in this TallyNum are greater 132 than nine, than this function generates a single int, which is 133 the result of concatenating the reversed digits together. Otherwise, 134 we iterate over the carry possibilities; for example: 1-10 generates 135 both '110' and '20'.""" 136 def redTail (lst, carry, limit): 137 def skpsum(num, carry): 138 """If the least-significant digit of the supplied carry is 139 non-zero, shift on that least-significant digit; otherwise 140 return num unchanged.""" 141 digit = carry % 10 142 return num if digit == 0 else (num*10)+digit

143 def nlimit (num): 144 return limit if limit is None or (num%10)==0 else limit-1

145 # early exit if number is too long. 146 if limit is not None and limit < 0: 147 return 148 # 1st option: next digit is just the carry 149 if carry != 0: 150 for r in redTail (lst, carry//10, nlimit(carry)): 151 yield skpsum (r, carry) 152 # 2nd option: add in next value 153 if lst: 154 digit = carry + lst[0] 155 for r in redTail (lst[1:], digit//10, nlimit(digit)): 156 yield skpsum (r, digit) 157 # check for terminal condition 158 if (not lst) and carry == 0: 159 yield 0 160 # okay, let's do the reduction. first digit is special 161 digit = self.lstval[0] 162 for r in redTail (self.lstval[1:], digit//10, 163 limit-1 if limit is not None else None): 164 yield (r*10) + (digit%10) 165

166 -def _addSlow(a, b, limit=None, cache=None):

167 """Add two `TallyNum` objects, specially treating the least-significant 168 digit (whose position is fixed). This is 'slow' addition: carries are 169 preserved and digits are not reduced, which guarantees commutativity 170 but requires special care during comparison.""" 171 172 if cache is None: 173 cache = {} # create a new tail cache if none is given. 174 def addTailCache (t1, t2, limit): 175 key = (t1, t2, limit) 176 if not key in cache: 177 cache[key] = frozenset(addTail(t1, t2, limit)) 178 for r in cache[key]: 179 yield r

180 def addTail (t1, t2, limit): 181 """Add two TallyNums to yield a generator of TallyNums.""" 182 assert isinstance(t1, LList) and isinstance(t2, LList) 183 # early exit if result is too long. 184 if limit is not None and limit < 0: 185 return 186 nlimit = None if limit is None else limit - 1 187 # 1st option: add knot value from t1 188 if t1: 189 for r in addTailCache(t1[1:], t2, nlimit): 190 yield LList(t1[0], r) 191 # 2nd option: add knot value from t2 192 if t2: 193 for r in addTailCache(t1, t2[1:], nlimit): 194 yield LList(t2[0], r) 195 # 3rd option: add knot value from t1 and t2 (both knots same place) 196 if t1 and t2: 197 for r in addTailCache(t1[1:], t2[1:], nlimit): 198 yield LList(t1[0] + t2[0], r) 199 # check for terminal condition 200 if not (t1 or t2): 201 yield NULL 202 203 assert isinstance(a, TallyNum) and isinstance(b, TallyNum) 204 a = a.lstval 205 b = b.lstval 206 # first digit is special 207 for r in addTail(a[1:], b[1:], limit): 208 yield TallyNum(LList(a[0] + b[0], r)) 209

210 -class Tally:

211 """A set of "zero-agnostic" numbers which could represent the sum 212 of several cords in a khipu. 213 214 "Zero-agnostic" means that all zeros in the number except for the 215 one in the units place (if any) have been elided. The `limit` 216 argument to the constructor constrains the length of the numbers 217 contained in a `Tally` resulting from arithmetic operations, in 218 order to more efficiently model likely khipu sums (where the 219 maximum # of knots on a cord, and thus decimal places, can be 220 estimated). 221 222 If the `fast` argument is true, `Tally` will represent the 223 zero-agnostic numbers as unadorned integers, which is likely to be 224 faster. As a trade off, it can't carefully track the carry digit 225 in intermediate results, with the result that addition on `Tally` 226 objects will not be commutative, and the `Tally` objects may 227 contain some arithmetic possibilities that can't actually occur. 228 For example, (18+51)+52 will differ from 18+(51+52): the latter 229 incorrectly contains the zero-agnostic sum "31" as a possibility (since 230 51+52=103=13). However, I *believe* that fast Tallys will contain a 231 superset of the actual possibilities; in any case pass `False` as the fast 232 argument for more precise results (and slower operation). 233 """

234 - def __init__ (self, arg, fast=True, limit=None):

235 self.limit = limit 236 """The maximum number of digits allowed in a `Tally` component.""" 237 self.fast = fast 238 """If `True`, trade accuracy for speed.""" 239 if isinstance (arg, set) or isinstance (arg, list) or isinstance (arg, types.GeneratorType): 240 self._possibilities = frozenset(self._tn(tn) for tn in arg) 241 else: 242 self._possibilities = frozenset([self._tn(arg)])

243 - def _tn (self, arg):

244 return int(arg) if self.fast else TallyNum(arg)

245 - def __str__ (self):

246 return str(self._possibilities if self.fast else map(str, self._possibilities))

247 - def __eq__ (self, other):

248 return self._possibilities == other._possibilities

249 - def __ne__ (self, other):

250 return self._possibilities != other._possibilities

251 - def __hash__ (self):

252 return self._possibilities.__hash__()

253 - def __add__ (self, num):

254 """Add a Tally to a Tally. Since Tallys are sets of zero-agnostic 255 integers, we return the cartesian product of adding all the possible 256 numbers in each Tally.""" 257 if not isinstance (num, Tally): 258 num = Tally([num], limit=self.limit, fast=self.fast) 259 assert isinstance(num, Tally) 260 assert self.fast == num.fast 261 assert self.limit == num.limit 262 result = set() 263 cache = {} # cache partial results for reuse 264 add = _addFast if self.fast else _addSlow 265 for gen in (add(a, b, limit=self.limit, cache=cache) 266 for a in self._possibilities 267 for b in num._possibilities): 268 result = result.union(gen) # gen is a generator of z-a ints here. 269 return Tally(result, limit=self.limit, fast=self.fast)

270 - def __mul__ (self, num):

271 """Multiply a Tally by a nonnegative integer (via addition). Note 272 that the 'num' multiplicand argument here is *not* a zero-agnostic 273 integer: it is a plain ol' normal everyday actual integer.""" 274 assert isinstance(num, int) and num >= 0 275 # this is the usual logarithmic multiplication-by-addition algorithm 276 if num == 0: 277 return Tally([0], limit=self.limit, fast=self.fast) 278 if num == 1: 279 return self 280 if (num % 2) == 1: 281 return self + (self * (num-1)) 282 half = self * (num/2) 283 return half + half

284 - def possibilities (self):

285 if self.fast: 286 return self._possibilities 287 result = set() 288 for tn in self._possibilities: 289 result = result.union(tn.reduceCarry (limit=self.limit)) 290 return result

291

292 -def main ():

293 # simple addition test 294 a = Tally(["19"]) 295 b = Tally(["1"]) 296 c = a + b 297 print c.possibilities() 298 assert c.possibilities() == set([110,20]) 299 300 # simple multiplication test 301 a = Tally(10) 302 c = a * 3 303 print c.possibilities() 304 assert c.possibilities() == set([120, 210, 30, 1110]) 305 306 # test that the length limit works correctly: the results may not be 307 # exactly those elements of the complete result set where the length 308 # is less than the limit given, due to suppression of zeros which may 309 # occur in intermediate results, but they are those elements of the 310 # complete result set where no intermediate sum exceeds the given length. 311 a.limit = 3 312 c = a * 6 313 print c.possibilities() 314 assert c.possibilities() == set([420, 330, 240, 150, 60, 510]) 315 a.limit = 4 316 c = a * 6 317 print c.possibilities() 318 assert c.possibilities() == set([240, 1410, 420, 2310, 1320, 3210, 2220, 1230, 3120, 2130, 1140, 4110, 150, 60, 330, 510]) 319 320 # test the suppression of intermediate zeros. 321 a = Tally(999) 322 b = Tally(11) 323 c = a + b 324 print c.possibilities() 325 assert c.possibilities() == set([9920, 91910, 19910, 110, 99110, 20, 1910, 9110, 920]) 326 327 # addition is commutative with slow Tallys, not with fast Tallys 328 a = Tally(18) 329 b = Tally(51) 330 c = Tally(52) 331 d = (a + b) + c 332 print d.possibilities() 333 d = a + (b + c) 334 print d.possibilities() 335 336 print "------------------------------------------------------------" 337 limit=6 338 a = Tally(116, limit=limit) 339 l = list(a._possibilities) 340 #l.sort() 341 #print str(l) 342 #print a.possibilities() 343 a += Tally(118, limit=limit) 344 l = list(a._possibilities) 345 #l.sort() 346 #print str(l) 347 #print a.possibilities() 348 a += Tally(2436, limit=limit) 349 l = list(a._possibilities) 350 #l.sort() 351 #print str(l) 352 #print a.possibilities() 353 a += Tally(4440, limit=limit) 354 l = list(a._possibilities) 355 l.sort() 356 print str(l) 357 print a.possibilities()

358

359 -def profile():

360 print "Profiling." 361 import hotshot 362 prof = hotshot.Profile("hotshot_tally_stats") 363 try: 364 prof.runcall(main) 365 except: 366 pass 367 prof.close()

368

369 -def psyco():

370 # Import Psyco if available 371 try: 372 import psyco 373 psyco.full() 374 except ImportError: 375 pass

376 377 if __name__ == '__main__': 378 #psyco() 379 if True: 380 main() 381 else: 382 profile() 383

Source Code for Module Tally