Mercurial > hg > config

annotate python/example/possibilities.py @ 777:ef6731a4ad86

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
close enough
author Jeff Hammel <k0scist@gmail.com>
date Sun, 03 Jul 2016 18:48:38 -0700
parents 67fa26b40dc6
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
1 #!/usr/bin/env python
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
2
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
3 """
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
4 """
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
5
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
6 # imports
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
7 import argparse
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
8 import sys
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
9 import time
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
10 from pprint import pprint
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
11
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
12 costs = {1:1,
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
13 7:3,
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
14 30:25}
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
15
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
16 A = [1, 2, 4, 5, 7, 29, 30]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
17
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
18 def possibilities(A):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
19 possibilities = [[(1, date) for date in A]]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
20 for_consideration = [0]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
21 while True:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
22 if not for_consideration:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
23 break
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
24 _for_consideration = []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
25 for item in for_consideration:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
26 basis = possibilities[item][:]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
27 tickets = [i[0] for i in basis]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
28 if set(tickets) == set([7]):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
29 continue
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
30 index = 0
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
31 potential = []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
32 while True:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
33 try:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
34 pos = tickets.find(1, index)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
35 except ValueError:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
36 break
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
37 potential = basis[:]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
38 potential[pos] = (7, basis[pos][-1])
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
39
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
40 try:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
41 while A[index] < date+6:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
42 index += 1
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
43 except IndexError:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
44 pass
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
45
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
46 return possibilities
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
47
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
48
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
49 def fill_space(A, spans):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
50 """
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
51 A -- the space to be filled
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
52 spans -- the discrete length of each space
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
53 """
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
54 if not A:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
55 return []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
56
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
57 A = sorted(A)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
58
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
59 possibilities = []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
60
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
61 # [(ticket_value, index_into_A)]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
62 working_set = [[(value, 0)] for value in spans]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
63 # print "working set"
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
64 # pprint(working_set)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
65 while working_set:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
66 item = working_set.pop()
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
67 last_span, index = item[-1]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
68 last_date = A[index]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
69 e = None
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
70 index += 1
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
71 try:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
72 while last_date + last_span > A[index]:
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
73 # print ('index: {}'.format(index))
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
74 index += 1
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
75 except IndexError as e:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
76 possibilities.append(item)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
77 continue
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
78
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
79 # print "item:"
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
80 # pprint(item)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
81 extension = [item[:] + [(span, index)]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
82 for span in spans]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
83
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
84 working_set.extend(extension)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
85
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
86 # fill possibility indices with dates
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
87 retval = [[(A[index], span) for span, index in possibility]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
88 for possibility in possibilities]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
89 return retval
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
90
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
91
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
92 def sorted_costs(A, costs=tuple(costs.items())):
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
93
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
94 costs = dict(costs)
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
95
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
96 # determine possibility spaces
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
97 spaces = fill_space(A, spans=costs.keys())
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
98
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
99 # determine costs
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
100 retval = []
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
101 for space in spaces:
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
102 cost = sum([costs[value] for date, value in space])
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
103 retval.append((cost, space))
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
104
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
105 # sort by cost
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
106 retval.sort(key=lambda x: x[0])
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
107
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
108 return retval
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
109
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
110 if __name__ == '__main__':
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
111
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
112 parser = argparse.ArgumentParser(description=__doc__)
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
113 options = parser.parse_args()
776
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
114
777
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
115 dates = sorted(A)
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
116
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
117 print "Dates: {}".format(', '.join([str(i) for i in dates]))
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
118 for cost, value in sorted_costs(A, costs):
ef6731a4ad86 close enough
Jeff Hammel <k0scist@gmail.com>
parents: 776
diff changeset
119 print ("{} : {}".format(cost, value))