1
2 """More arithmetic support for "zero-agnostic" numbers.
3
4 This class optimizes the common search computation: given this subset of
5 cords, can I make a sum which is present in the full set of cords, and
6 if so, which cords could be sums?
7
8 Examples
9 ========
10
11 Create the set of "possible answers"::
12
13 >>> cords = Possibilities.create([9,18,90,180,181,222,635])
14 >>> str(cords)
15 '[9, 18, 90, 180, 181, 222, 635]'
16
17 Find the sums which can be made (note that zeroes are elided in the sums)::
18
19 >>> sums = tsum([116,118,2436,4440], cords)
20 >>> list(sorted(sums))
21 [90, 180]
22 >>> list(tsum([30,30,30], cords))
23 [90]
24
25 You can also pass the sum in as a list of (frequency, number) tuples,
26 for example::
27
28 >>> sums = tsum([(1,116),(1,118),(1,2436),(1,4440)], cords)
29 >>> list(sorted(sums))
30 [90, 180]
31 >>> list(tsum([(3,30)], cords))
32 [90]
33
34 Note that the `Possibilities` data structure can be reused across multiple
35 *sequential* calls to `tsum`, but it is not thread-safe.
36 """
37
39 """A set of possible "answers" to a summation."""
40 __slots__ = [ 'value', 'leaves', 'accept' ]
41 - def __init__ (self, value, accept=False):
42 """Create an `Possibilities` node with the given value."""
43 self.value = value
44 """The number associated with this node. This is the number
45 which would be accepted by this node, if it were an accepting
46 state, or -1 for the root node."""
47 self.leaves = [None] * 10
48 """`Possibilities` nodes corresponding to the 10 possible
49 significant digits which could be accepted by this node."""
50 self.accept = accept
51 """Whether this node is an "accepting state". For example,
52 the `Possibilities` object corresponding to the set [51,61]
53 has an internal node with the value '1' which is not an accepting
54 state, since the number 1 is not in the set."""
55 self.na = 1 if accept else 0
56 """The number of accepting states in this node and child nodes."""
57
59 """Return the `Possibilities` tree with `idx` as least-significant
60 digit, or None if there is no such tree."""
61 return self.leaves[idx]
63 """Return `True` if the least-significant digit 'v' can lead to
64 an accepting state."""
65 return self.leaves[v] is not None
67 """Return a human-readable representation of the numbers accepted
68 by this `Possibilities` object."""
69 def recurse(p):
70 if p.accept: yield 0
71 for i in range(10):
72 if p[i] is not None:
73 for v in recurse(p[i]):
74 yield v*10 + i
75 return str(sorted(recurse(self)))
77
78 assert self.value == -1
79 return "Possibilities.create("+str(self)+")"
85 """Return `True` iff the objects are reference-equal. This is a
86 very strict notion of equality! For example::
87
88 >>> a = Possibilities.create([1,2,3])
89 >>> b = Possibilities.create([1,2,3])
90 >>> a == a
91 True
92 >>> a == b
93 False
94
95 """
96 return self is other
97
98 - def add(self, num, mul=1):
99 """Return a new `Possibilities` object which can accept the
100 given number. Returns 1 if the number was not previously accepted,
101 else 0. For example::
102
103 >>> p = Possibilities.create([42])
104 >>> p.add(534)
105 1
106 >>> p.na
107 2
108 >>> p.add(534)
109 0
110 >>> p.na
111 2
112
113 """
114 rem,digit = divmod(num, 10)
115 if self[digit] is None:
116 self.leaves[digit] = Possibilities(self._value() + digit*mul)
117 if rem != 0:
118 v = self[digit].add(rem, mul=mul*10)
119 else:
120 v = 0 if self[digit].accept else 1
121 self[digit].accept = True
122 self[digit].na += v
123 self.na += v
124 return v
125
127 """Special accessor to handle special case value of root node."""
128 return self.value if self.value>= 0 else 0
129
131 """Count the number of accepting states and reset the 'na' field."""
132 self.na = 1 if self.accept else 0
133 self.na += sum(p.reset() for p in self.leaves if p is not None)
134 return self.na
135
137 p = Possibilities(-1)
138 for n in nums: p.add(n)
139 assert not p.accept
140 return p
141 create = staticmethod(create)
142
143 -def tsum(arg, possibilities):
144 """Return an iterator over the possible zero-agnostic sums
145 (from those included in the given `possibilities` object) which it is
146 possible to obtain by summing the given arguments. The `arg` may either
147 be a straight list/iterable of zero-agnostic integers, or it may be
148 a list/iterable of pairs (in which case the first component gives the
149 multiplier for the zero-agnostic number in the second component).
150 See the `TTally` module docs for examples.
151 """
152
153 try:
154 arg = [[0,freq,num] for freq,num in arg if freq > 0]
155 except TypeError:
156 t = {}
157 for n in arg:
158 t[n] = t.get(n, 0) + 1
159 arg = [[0, freq, num] for num,freq in t.iteritems()]
160
161
162
163 def inc(whichToSum):
164
165 for i in range(len(whichToSum)):
166 cnt,freq,num = whichToSum[i]
167 if cnt+1 <= freq:
168 whichToSum[i][0] = cnt+1
169 return True
170 else:
171 whichToSum[i][0] = 0
172 return False
173
174
175 def _tsum(whichToSum, p, carry=0):
176 first = True
177 if carry==0:
178 first = False
179 if not whichToSum:
180 if p.accept: yield p.value
181 return
182
183 while first or inc(whichToSum):
184 first = False
185 thisSum = carry + \
186 sum(cnt*(num%10) for cnt,freq,num in whichToSum if cnt>0)
187 ncarry,digit = divmod(thisSum, 10)
188 if digit==0 or digit in p:
189 nnums = {}
190 for cnt, freq, num in whichToSum:
191 if cnt < freq:
192 nnums[num] = nnums.get(num,0) + (freq-cnt)
193 if cnt > 0 and (num/10)!=0:
194 nnums[num/10] = nnums.get(num/10, 0) + cnt
195 nextp = p[digit] if digit in p else p
196 for r in _tsum([[0,freq,num] for num,freq in nnums.iteritems()],
197 nextp, ncarry):
198 yield r
199
200
201
202 return frozenset(r for r in _tsum(arg, possibilities))
203
204
205 if __name__ == '__main__':
206 import doctest
207 doctest.testmod()
208