Mercurial > hg > config

annotate python/example/possibilities.py @ 776:67fa26b40dc6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add example program for time-spacing
author Jeff Hammel <k0scist@gmail.com>
date Sun, 03 Jul 2016 18:33:09 -0700
parents
children ef6731a4ad86
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
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
3 # imports
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
4 import argparse
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
5 import sys
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
6 import time
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
7 from pprint import pprint
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
8
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
9 costs = {1:1,
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
10 7:3,
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
11 30:25}
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
12
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
13 A = [1, 2, 4, 5, 7, 29, 30]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
14
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
15 #A = [3, 7, 10]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
16
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
17 #A=[1,2,3]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
18
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
19 def possibilities(A):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
20 possibilities = [[(1, date) for date in A]]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
21 for_consideration = [0]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
22 while True:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
23 if not for_consideration:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
24 break
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
25 _for_consideration = []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
26 for item in for_consideration:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
27 basis = possibilities[item][:]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
28 tickets = [i[0] for i in basis]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
29 if set(tickets) == set([7]):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
30 continue
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
31 index = 0
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
32 potential = []
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
33 while True:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
34 try:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
35 pos = tickets.find(1, index)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
36 except ValueError:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
37 break
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
38 potential = basis[:]
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
39 potential[pos] = (7, basis[pos][-1])
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
40
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
41 try:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
42 while A[index] < date+6:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
43 index += 1
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
44 except IndexError:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
45 pass
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
46
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
47 return possibilities
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
48
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]:
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
73 print ('index: {}'.format(index))
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
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
92 def cost(A, spans=(30,)):
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
93
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
94 # determine possibility spaces
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
95 spaces = fill_space(A, spans=spans)
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
96
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
97 # determine costs
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 if __name__ == '__main__':
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
100
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
101 parser = argparse
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
102 spans = costs.keys()
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
103
67fa26b40dc6 add example program for time-spacing
Jeff Hammel <k0scist@gmail.com>
parents:
diff changeset
104 pprint (fill_space(A, spans))