changeset 23:c555afaeede4 draft

optim.hs: new Haskell implementation
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Mon, 23 Mar 2015 17:45:52 -0400
parents 1c49ab3f44b0
children 1bebd7b76bac
files optim.hs optim.py snapshot_input.txt
diffstat 3 files changed, 73 insertions(+), 69 deletions(-) [+]
line wrap: on
line diff
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
--- 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
--- 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