annotate optim.py @ 5:cd24a8027d5f draft

parseinput: skip impossible and unprofitable machines
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Wed, 11 Mar 2015 10:30:15 -0400 (2015-03-11)
parents 14c8b6dad88a
children d4be13772b01
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
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
8 def parseinput(fname):
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9 """
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10 Parse the input file, forget about input validation
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 """
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 cases = []
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 with open(fname) as f:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14 while True:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15 header = [int(x) for x in f.readline().split()]
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 if header == [0, 0, 0]:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 return cases
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18 N = header[0]
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
19 case = Case([], header[1], header[2])
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20 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
21 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
22 maxprofit = None)
5
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
23
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
24 # 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
25 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
26 - machine.buy + machine.sell)
5
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
27
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
28 # 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
29 # 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
30 # case.days.
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
31 if maxprofit < 0:
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
32 continue
cd24a8027d5f parseinput: skip impossible and unprofitable machines
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 4
diff changeset
33
3
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
34 machine = machine._replace(maxprofit = maxprofit)
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
35 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
36
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 cases.append(case)
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
39 class InvalidPlan(Exception):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
40 pass
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
41
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
42 def final_capital(case, machines, plan):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
43 """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
44 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
45 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
46 any step.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
47
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
48 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
49 plans.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
50
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
51 """
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
52 capital = case.capital
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
53
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
54 # 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
55 # there.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
56 slot = None
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
57
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
58 for (action, machine) in sorted(zip(plan, machines),
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
59 key = lambda x: x[1].day):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
60 if action:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
61 # We attempt to buy a new machine
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
62 if capital < machine.buy:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
63 raise InvalidPlan("Not enough capital at day %d: "
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
64 "machine cost is %d, and capital is %d"
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
65 % (machine.day, machine.buy, capital))
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
66
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
67 capital -= machine.buy
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
68 if slot:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
69 # 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
70 # be used the day it's sold.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
71 days_used = machine.day - slot.day - 1
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
72 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
73 capital += slot.sell
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
74
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
75 slot = machine
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
76
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
77 # 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
78 if slot:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
79 # 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
80 # subtracting 1 here.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
81 days_used = case.days - slot.day
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
82 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
83 capital += slot.sell
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
84
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
85 return capital
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
86 def main():
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
87 cases = parseinput("input.txt")
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
88 for case in cases:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
89 print "Next case:", case["header"]
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
90 for machine in case["machines"]:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
91 print machine
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
92
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
93 if __name__ == "__main__":
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
94 main()