Mercurial > hg > problem6

annotate optim.py @ 20:7413c98553c3 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
main: call solver with new optional debug arguments Also add debug arguments to greedy and brute_force.
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 17 Mar 2015 09:48:55 -0400
parents 6015c8cfe502
children 523f1eb145be
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
1 #!/usr/bin/env python
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
2
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
3 from collections import namedtuple
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
4
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
5 Machine = namedtuple("Machine", ["day", "buy", "sell", "profit", "maxprofit"])
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
6 Case = namedtuple("Case", ["machines", "days", "capital"])
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
7
12
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
8 from argparse import ArgumentParser
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
9
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
10 def process_options():
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
11 parser = ArgumentParser(
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
12 description=("Solve problem F."))
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
13 parser.add_argument("file", help = "input file to read")
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
14 parser.add_argument("--debug", dest = "debug", action = "store_true",
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
15 help = "enable debug output")
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
16
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
17 algorithm = parser.add_mutually_exclusive_group(required = False)
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
18
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
19 algorithm.add_argument("-b", "--brute-force", dest = "brute_force",
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
20 action = "store_true",
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
21 help = "Use brute force, O(2**N) time")
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
22 algorithm.add_argument("-g", "--greedy", dest = "greedy",
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
23 action = "store_true", default = True,
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
24 help = ("Use greedy algorithm, fails for some cases, "
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
25 "roughly O(N) time"))
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
26
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
27 args = parser.parse_args()
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
28 return args
9f485ecdc2a9 process_options: new function to handle CLI args
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 9
diff changeset
29
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30 def parseinput(fname):
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31 """
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 Parse the input file, forget about input validation
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33 """
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 cases = []
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35 with open(fname) as f:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36 while True:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 header = [int(x) for x in f.readline().split()]
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38 if header == [0, 0, 0]:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
39 return cases
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40 N = header[0]
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
41 case = Case([], header[1], header[2])
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
42 for i in range(0, N):
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
43 machine = Machine(*[int(x) for x in f.readline().split()],
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
44 maxprofit = None)
5
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
45
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
46 # Maximum profit possible from each machine
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
47 maxprofit = ((case.days - machine.day)*machine.profit
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
48 - machine.buy + machine.sell)
5
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
49
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
50 # Skip machines that can only give a loss. This
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
51 # includes machines that can only be bought after
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
52 # case.days.
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
53 if maxprofit < 0:
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
54 continue
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
55
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
56 machine = machine._replace(maxprofit = maxprofit)
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
57 case.machines.append(machine)
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
58
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
59 cases.append(case)
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
60
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
61 class InvalidPlan(Exception):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
62 pass
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
63
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
64 def final_capital(case, machines, plan):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
65 """Given a case, some machines, and an action plan about whether to
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
66 buy a machine or not, compute the final capital given by this
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
67 plan. Raises InvalidPlan if it's impossible to buy a machine at
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
68 any step.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
69
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
70 This is our objective function to maximise over all possible
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
71 plans.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
72
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
73 """
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
74 capital = case.capital
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
75
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
76 # The "slot" that holds a machine. Initially, there's nothing
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
77 # there.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
78 slot = None
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
79
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
80 for (action, machine) in sorted(zip(plan, machines),
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
81 key = lambda x: x[1].day):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
82 if action:
8
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
83 # We first sell the old machine, if any
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
84 if slot:
6
d4be13772b01 final_capital: consider as invalid plans that buy more than one machine per day
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 5
diff changeset
85 if machine.day == slot.day:
9
69e65d1d94af maint: keep line lengths to 80 chars
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 8
diff changeset
86 raise InvalidPlan(
69e65d1d94af maint: keep line lengths to 80 chars
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 8
diff changeset
87 "Cannot buy two machines on the same day: %d"
69e65d1d94af maint: keep line lengths to 80 chars
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 8
diff changeset
88 % (machine.day))
6
d4be13772b01 final_capital: consider as invalid plans that buy more than one machine per day
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 5
diff changeset
89
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
90 # Subtract 1, because the machine in the slot cannot
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
91 # be used the day it's sold.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
92 days_used = machine.day - slot.day - 1
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
93 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
94 capital += slot.sell
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
95
8
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
96 # Then we try to buy the new one
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
97 if capital < machine.buy:
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
98 raise InvalidPlan("Not enough capital at day %d: "
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
99 "machine cost is %d, and capital is %d"
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
100 % (machine.day, machine.buy, capital))
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
101
b5cbd6bdb611 final_capital: first sell the machine before checking balance to buy (bug)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 7
diff changeset
102 capital -= machine.buy
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
103 slot = machine
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
104
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
105 # We account for the final machine, if we have it.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
106 if slot:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
107 # We can sell the day after the restructuring period, so no
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
108 # subtracting 1 here.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
109 days_used = case.days - slot.day
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
110 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
111 capital += slot.sell
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
112
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
113 return capital
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
114
19
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
115
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
116 def showplan(plan, machines):
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
117 print
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
118 empty = True
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
119 for (action, machine) in sorted(zip(plan, machines),
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
120 key = lambda x: x[1].day):
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
121 if action:
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
122 empty = False
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
123 print "\t", machine
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
124 if empty:
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
125 print "\t(do nothing)"
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
126
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
127 print
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
128
6015c8cfe502 showplan: new debug function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 16
diff changeset
129
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
130 def brute_force(case, debug=False):
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
131 """Form all possible plans, and just try them all."""
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
132 machines = case.machines
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
133
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
134 # Just count in binary to enumerate all plans
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
135 N = len(machines)
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
136 if N > 0:
9
69e65d1d94af maint: keep line lengths to 80 chars
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 8
diff changeset
137 plans = [[y == "1" for y in format(x, "0%db" % N)]
69e65d1d94af maint: keep line lengths to 80 chars
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 8
diff changeset
138 for x in range(0, 2**N)]
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
139 else:
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
140 plans = []
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
141
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
142 maxcapital = case.capital
16
4c23cfdeaa5f main: enable some debug output
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 15
diff changeset
143 maxplan = []
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
144 for plan in plans:
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
145 try:
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
146 plancapital = final_capital(case, machines, plan)
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
147 if debug:
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
148 showplan(plan, machines)
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
149 print "final capital: ", plancapital
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
150 if plancapital > maxcapital:
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
151 maxcapital = plancapital
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
152 maxplan = plan
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
153 except InvalidPlan as e:
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
154 if debug:
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
155 showplan(plan, machines)
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
156 print "\t", e
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
157 pass
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
158
15
d9aa5e25859c main: use CLI args to select the algorithm to use
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 14
diff changeset
159 return maxcapital, maxplan
13
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
160
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
161 def greedy(case, debug=False):
13
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
162 """Greedy algorithm, considering each machine only once, in decreasing
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
163 order of maxprofit.
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
164
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
165 """
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
166 machines = sorted(case.machines, key = lambda m: -m.maxprofit)
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
167 N = len(machines)
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
168 maxcapital = case.capital
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
169
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
170 # Base plan, pick no machine
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
171 plan = [False]*len(machines)
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
172 maxplan = plan
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
173
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
174 for idx in range(0, N):
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
175 plan[idx] = True
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
176 try:
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
177 plancapital = final_capital(case, machines, plan)
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
178 if plancapital > maxcapital:
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
179 maxcapital = plancapital
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
180 maxplan = plan
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
181 else:
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
182 plan[idx] = False
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
183 except InvalidPlan:
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
184 plan[idx] = False
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
185
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
186 return maxcapital, maxplan
ad39a394a011 greedy: new greedy algorithm, works reasonably well
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 12
diff changeset
187
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
188 def main():
14
a72cf3c7c976 main: use args to get input filename instead of hardwiring it
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 13
diff changeset
189 args = process_options()
a72cf3c7c976 main: use args to get input filename instead of hardwiring it
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 13
diff changeset
190 cases = parseinput(args.file)
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
191 for (number, case) in enumerate(cases):
15
d9aa5e25859c main: use CLI args to select the algorithm to use
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 14
diff changeset
192 if args.greedy:
d9aa5e25859c main: use CLI args to select the algorithm to use
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 14
diff changeset
193 solver = greedy
d9aa5e25859c main: use CLI args to select the algorithm to use
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 14
diff changeset
194 if args.brute_force:
d9aa5e25859c main: use CLI args to select the algorithm to use
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 14
diff changeset
195 solver = brute_force
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
196 maxcapital, plan = solver(case, debug=args.debug)
7
af2598b58791 brute_force: new function, O(2^N) solution (exponential time)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 6
diff changeset
197 print "Case %d: %d" % (number + 1, maxcapital)
16
4c23cfdeaa5f main: enable some debug output
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 15
diff changeset
198 if args.debug:
4c23cfdeaa5f main: enable some debug output
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 15
diff changeset
199 print
20
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
200 print " Winning plan:"
7413c98553c3 main: call solver with new optional debug arguments
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 19
diff changeset
201 showplan(plan, case.machines)
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
202
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
203 if __name__ == "__main__":
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
204 main()