# HG changeset patch # User Jordi Gutiérrez Hermoso # Date 1427147152 14400 # Node ID c555afaeede4cbb5a191370de2d0f730d651e467 # Parent 1c49ab3f44b0e5b3ea3eedd76ca30a1b32d4e646 optim.hs: new Haskell implementation diff --git a/optim.hs b/optim.hs new file mode 100755 --- /dev/null +++ b/optim.hs @@ -0,0 +1,44 @@ +#!/usr/bin/runhaskell + +type Number = Int + +data Machine = Machine {day :: Number + ,buy :: Number + ,sell :: Number + ,profit :: Number + ,maxprofit :: Number} deriving Show + +data Case = Case {machines :: [Machine] + ,capital :: Number + ,days :: Number} deriving Show + +numSplit :: String -> [[Number]] +numSplit str = [[read num | num <- words line] | line <- lines str] + +makeMachine :: Number -> [Number] -> Machine +makeMachine days line = Machine mDay mBuy mSell mProfit mMaxprofit + where + mMaxprofit = (days - mDay)*mProfit - mBuy + mSell + [mDay, mBuy, mSell, mProfit] = line + +groupCases :: [[Number]] -> [Case] +groupCases [] = [] +groupCases (header:rest) = + Case machines capital days : groupCases nextCase + where + (machinelist, nextCase) = splitAt n rest + [n, capital, days] = header + machines = map (makeMachine capital) machinelist + +parseInput :: String -> [Case] +parseInput input = groupCases (numSplit input) + +solver :: Case -> Number +solver thecase = capital thecase + sum (map maxprofit (machines thecase)) + +processCases input = + unlines $ + map (\(n,m) -> "Case " ++ show n ++ ": " ++ show m) + (zip [1, 2..] (map solver (parseInput input))) + +main = interact processCases diff --git a/optim.py b/optim.py --- a/optim.py +++ b/optim.py @@ -10,19 +10,19 @@ def process_options(): parser = ArgumentParser( description=("Solve problem F.")) - parser.add_argument("file", help = "input file to read") - parser.add_argument("--debug", dest = "debug", action = "store_true", - help = "enable debug output") + parser.add_argument("file", help="input file to read") + parser.add_argument("--debug", dest="debug", action="store_true", + help="enable debug output") - algorithm = parser.add_mutually_exclusive_group(required = False) + algorithm = parser.add_mutually_exclusive_group(required=False) - algorithm.add_argument("-b", "--brute-force", dest = "brute_force", - action = "store_true", - help = "Use brute force, O(2**N) time") - algorithm.add_argument("-g", "--greedy", dest = "greedy", - action = "store_true", default = True, - help = ("Use greedy algorithm, fails for some cases, " - "roughly O(N) time")) + algorithm.add_argument("-b", "--brute-force", dest="brute_force", + action="store_true", + help="Use brute force, O(2**N) time") + algorithm.add_argument("-g", "--greedy", dest="greedy", + action="store_true", default=True, + help=("Use greedy algorithm, fails for some cases, " + "roughly O(N) time")) args = parser.parse_args() return args @@ -41,10 +41,10 @@ case = Case([], header[1], header[2]) for i in range(0, N): machine = Machine(*[int(x) for x in f.readline().split()], - maxprofit = None) + maxprofit=None) # Maximum profit possible from each machine - maxprofit = ((case.days - machine.day)*machine.profit + maxprofit = ((case.days - machine.day) * machine.profit - machine.buy + machine.sell) # Skip machines that can only give a loss. This @@ -53,7 +53,7 @@ if maxprofit < 0: continue - machine = machine._replace(maxprofit = maxprofit) + machine = machine._replace(maxprofit=maxprofit) case.machines.append(machine) cases.append(case) @@ -78,7 +78,7 @@ slot = None for (action, machine) in sorted(zip(plan, machines), - key = lambda x: x[1].day): + key=lambda x: x[1].day): if action: # We first sell the old machine, if any if slot: @@ -90,7 +90,7 @@ # Subtract 1, because the machine in the slot cannot # be used the day it's sold. days_used = machine.day - slot.day - 1 - capital += days_used*slot.profit + capital += days_used * slot.profit capital += slot.sell # Then we try to buy the new one @@ -107,7 +107,7 @@ # We can sell the day after the restructuring period, so no # subtracting 1 here. days_used = case.days - slot.day - capital += days_used*slot.profit + capital += days_used * slot.profit capital += slot.sell return capital @@ -117,7 +117,7 @@ print empty = True for (action, machine) in sorted(zip(plan, machines), - key = lambda x: x[1].day): + key=lambda x: x[1].day): if action: empty = False print "\t", machine @@ -135,7 +135,7 @@ N = len(machines) if N > 0: plans = [[y == "1" for y in format(x, "0%db" % N)] - for x in range(0, 2**N)] + for x in range(0, 2 ** N)] else: plans = [] @@ -163,24 +163,30 @@ order of maxprofit. """ - machines = sorted(case.machines, key = lambda m: -m.maxprofit) + machines = sorted(case.machines, key=lambda m: -m.maxprofit) N = len(machines) maxcapital = case.capital # Base plan, pick no machine - plan = [False]*len(machines) + plan = [False] * len(machines) maxplan = plan for idx in range(0, N): plan[idx] = True try: plancapital = final_capital(case, machines, plan) + if debug: + showplan(plan, machines) + print "final capital: ", plancapital if plancapital > maxcapital: maxcapital = plancapital maxplan = plan else: plan[idx] = False - except InvalidPlan: + except InvalidPlan as e: + if debug: + showplan(plan, machines) + print "\t", e plan[idx] = False return maxcapital, maxplan diff --git a/snapshot_input.txt b/snapshot_input.txt --- a/snapshot_input.txt +++ b/snapshot_input.txt @@ -1,50 +1,4 @@ -6 10 20 -6 12 1 3 -1 9 1 2 -3 2 1 2 -8 20 5 4 -4 11 7 4 -2 10 9 1 -4 979142410 1000000000 -719554784 535235252 43212142 2 -679922882 929213070 72282699 3 -947550084 114776168 96759913 1 -811283493 865444308 248312924 4 -10 936980155 1000000000 -762761567 683459202 109944378 6 -686089795 734650986 45620682 4 -678254540 925086416 24622261 5 -807652386 596279745 140024880 9 -791494729 585405092 50583956 8 -655401693 691328196 82491162 3 -799450676 654579438 65612488 10 -580278950 624801431 68664589 2 -834332323 692933073 524827737 7 -101802074 760182347 3637050 1 -1 10 100 -50 11 9 100 -1 10 100 -50 10 9 100 -1 10 100 -1 10 9 100 -1 10 100 -100 10 9 100 -1 10 100 -95 10 1 1 -1 10 100 -95 10 1 2 -1 1000000000 1000000000 -1 10 9 1000000000 -2 10 100 -80 67 60 7 -20 8 5 1 2 10 100 80 66 60 7 20 8 5 1 -2 10 100 -80 66 60 1 -20 8 5 7 -2 10 30 -20 8 5 8 -20 2 1 7 -0 0 0 \ No newline at end of file +0 0 0