Source Code for Module IntraSums

  1  #!/usr/bin/python2.5 
  2  """Look for intra-khipu sums.""" 
  3  from __future__ import with_statement 
  4  import warnings, sys 
  5  import json # package python-json in debian. 
  6  import IO # sums IO package in this directory 
  7   
  8  # KhipuDB & Tally are in parent dir 
  9  sys.path.append('..') 
 10  #import KhipuDB 
 11  from Tally import Tally 
 12   
 13  # configuration 
 14  LENLIMIT=6 # ignore sums if intermediate results exceed 10^LENLIMIT 
 15  MINCORDS=3 # look for sums involving at least this many cords. 
 16  MAXCORDS=12 # look for sums involving at most this many cords. 
 17  MAXSUMS=10 # stop looking after you've found this many sums of a particular len 
 18   
 19  # read in the cached numerical values of the khipu cords. 
 20 -def setup (): 
 21      global khipu 
 22      khipu = json.read (open ('khipu-numbers.yaml', 'r').read () ) 
 23   
 24 -def process (k, nCords): 
 25      # compute set of numbers represented by these cords 
 26      # (ignore zeros for now) 
 27      nums = [int(n) for n in khipu.get(k) if n is not None and n != 0] 
 28      if len(nums) < (nCords+1): 
 29          return # finding an appropriate sum impossible 
 30      # also, sorted list. 
 31      numList = list(set(nums)) 
 32      numList.sort() 
 33      # and a count of how many times each of these numbers appears. 
 34      numCount = dict.fromkeys(numList, 0) 
 35      for n in nums: 
 36          numCount[n] += 1 
 37      numCount = [numCount[n] for n in numList] 
 38      # throw away duplicates in nums 
 39      nums = set(nums) 
 40      # finally, lets map numbers to where they appear in the sorted list. 
 41      numPos = {} 
 42      numPos.update(zip(numList,range(len(numList)))) 
 43      # okay, let's enumerate the possible sums 
 44      def incToMargin (curSum, margin=nCords, maxlen=len(numList)): 
 45          for i in range(maxlen): 
 46              if margin == 0: 
 47                  break 
 48              curSum[i] = min(margin, numCount[i]) 
 49              margin -= curSum[i] 
 50          assert margin == 0 
 51          return 
 52               
 53      def inc (curSum): 
 54          """Cycle through next possible sum. 
 55   
 56          Find the element with the smallest i which can be increased, and 
 57          then set the elements with smaller i's to their least possible 
 58          value.  Eg: with max (3,3,3) the progression goes: (lsb on left) 
 59          (3,0,0) (2,1,0) (1,2,0) (0,3,0) (2,0,1) (1,1,1) (0,2,1) (1,0,2) ... 
 60          """ 
 61          # find the 'leftmost' element which can be increased 
 62          margin = 0 
 63          for i in range(len(numList)): 
 64              if curSum[i] == numCount[i] or margin == 0: 
 65                  # can't be increased. 
 66                  margin += curSum[i] 
 67                  curSum[i] = 0 
 68                  continue 
 69              # found an element which can be increased! 
 70              curSum[i] += 1 
 71              margin -= 1 
 72              # elements with smaller i's are set to zero; increase from 
 73              # lsb up to account for margin. 
 74              incToMargin(curSum, margin, i) 
 75              return True 
 76          else: 
 77              return False # no more possible sums 
 78      cache = [ (None,None) ] * len(numList) 
 79      def tally (num): 
 80          return Tally(num, limit=LENLIMIT) # XXX: fast? 
 81      def cacheSum (lst): 
 82          if len(lst) == 0: 
 83              return tally(0) 
 84          key, value = cache[len(lst)-1] 
 85          if key == lst: 
 86              return value 
 87          cnt, num = lst[0] 
 88          result = cacheSum(lst[1:]) 
 89          if cnt != 0: # minor efficiency hack 
 90              result = result + (tally(num) * cnt) 
 91          cache[len(lst)-1] = (lst, result) 
 92          return result 
 93      def check (curSum): 
 94          """Check to see if the given sum yields a number in this khipu.""" 
 95          #print "Checking:", zip(curSum,numList), zip(numCount,numList) 
 96          t = cacheSum(zip(curSum,numList)) 
 97          #print "  Sum:", t 
 98          for p in t.possibilities(): 
 99              if p in nums and curSum[numPos[p]] < numCount[numPos[p]]: 
100                  return True 
101          else: 
102              return False 
103   
104      curSum = [0 for n in numList] 
105      incToMargin(curSum) 
106      results = [] 
107      while True: 
108          if check(curSum): 
109              yield [(cnt,num) for cnt,num in zip(curSum,numList) 
110                              if cnt>0] 
111          if not inc(curSum): 
112              break 
113   
114 -def main (): 
115      if len(sys.argv) > 1 and sys.argv[1] != 'all': 
116          k = sys.argv[1] 
117          for n in range(MINCORDS,MAXCORDS+1): 
118              print k + ": looking for a", n, "cord sum", 
119              sys.stdout.flush () 
120              for sumFound in process(k, n): 
121                  print sumFound, 
122                  print '.', 
123                  sys.stdout.flush () 
124              print 
125      else: 
126          output = {} 
127          try: 
128              output = IO.readSums(preserveInc=True) 
129          except IOError: 
130              pass # cache is dead, long live the cache. 
131          INC = '**INCOMPLETE**' 
132          output.setdefault(INC, []) 
133          try: 
134              khipus = list(khipu.keys()) 
135              khipus.sort(lambda x,y: cmp(len(khipu[x]), len(khipu[y]))) 
136              for n in range(MINCORDS,MAXCORDS+1): 
137                  for k in khipus: 
138                      output.setdefault(k, {}) 
139                      if not output[k].has_key(n): 
140                          output[INC].append([k,n]) # mark this as incomplete 
141                      if [k,str(n)] in output[INC]: # back-compatibility 
142                          output[INC].append([k,n]) 
143                          output[INC].remove([k,str(n)]) 
144                      if [k,n] in output[INC]: 
145                          output[k].setdefault(n, []) 
146                          print k + ": looking for a", n, "cord sum", 
147                          sys.stdout.flush () 
148                          for sumFound in process(k, n): 
149                              print sumFound, 
150                              print '.', 
151                              sys.stdout.flush () 
152                              if sum not in output[k][n]: 
153                                  output[k][n].append(sumFound) 
154                              if len(output[k][n]) >= MAXSUMS: 
155                                  break 
156                          output[INC].remove([k,n]) # k,n processing complete 
157                          print 
158          except KeyboardInterrupt: 
159              pass # that's all we'll do today. 
160          # write (partial) results. 
161          IO.writeSums(output, trim=False) 
162   
163 -def psyco(): 
164      # Import Psyco if available 
165      try: 
166          import psyco 
167          psyco.full() 
168      except ImportError: 
169          pass 
170   
171  if __name__ == '__main__': 
172      setup () 
173      psyco() 
174      main () 
175