Mercurial > hg > problem6

annotate optim.py @ 4:14c8b6dad88a draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
final_capital: new function This is the objective function that we must maximise with a buying plan
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 10 Mar 2015 21:21:03 -0400
parents c683f80bc858
children cd24a8027d5f
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)
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
23 # 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
24 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
25 - machine.buy + machine.sell)
c683f80bc858 parseinput: also save the maximum possible profit for each machine
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 2
diff changeset
26 machine = machine._replace(maxprofit = maxprofit)
2
3632502b8af1 parseinput: replace lists with namedtuplese
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 1
diff changeset
27 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
28
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 cases.append(case)
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30
4
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
31 class InvalidPlan(Exception):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
32 pass
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
33
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
34 def final_capital(case, machines, plan):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
35 """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
36 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
37 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
38 any step.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
39
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
40 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
41 plans.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
42
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
43 """
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
44 capital = case.capital
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
45
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
46 # 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
47 # there.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
48 slot = None
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
49
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
50 for (action, machine) in sorted(zip(plan, machines),
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
51 key = lambda x: x[1].day):
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
52 if action:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
53 # We attempt to buy a new machine
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
54 if capital < machine.buy:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
55 raise InvalidPlan("Not enough capital at day %d: "
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
56 "machine cost is %d, and capital is %d"
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
57 % (machine.day, machine.buy, capital))
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
58
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
59 capital -= machine.buy
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
60 if slot:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
61 # 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
62 # be used the day it's sold.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
63 days_used = machine.day - slot.day - 1
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
64 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
65 capital += slot.sell
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 slot = machine
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
68
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
69 # 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
70 if slot:
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
71 # 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
72 # subtracting 1 here.
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
73 days_used = case.days - slot.day
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
74 capital += days_used*slot.profit
14c8b6dad88a final_capital: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 3
diff changeset
75 capital += slot.sell
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 return capital
1
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
78 def main():
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
79 cases = parseinput("input.txt")
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
80 for case in cases:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
81 print "Next case:", case["header"]
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
82 for machine in case["machines"]:
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
83 print machine
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
84
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
85 if __name__ == "__main__":
15944d95f399 parseinput: new function
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
86 main()