view @ 6:d4be13772b01 draft

final_capital: consider as invalid plans that buy more than one machine per day
author Jordi Gutiérrez Hermoso <>
date Tue, 10 Mar 2015 22:20:59 -0400
parents cd24a8027d5f
children af2598b58791
line wrap: on
line source

#!/usr/bin/env python

from collections import namedtuple

Machine = namedtuple("Machine", ["day", "buy", "sell", "profit", "maxprofit"])
Case = namedtuple("Case", ["machines", "days", "capital"])

def parseinput(fname):
    Parse the input file, forget about input validation
    cases = []
    with open(fname) as f:
        while True:
            header = [int(x) for x in f.readline().split()]
            if header == [0, 0, 0]:
                return cases
            N = header[0]
            case = Case([], header[1], header[2])
            for i in range(0, N):
                machine = Machine(*[int(x) for x in f.readline().split()],
                                  maxprofit = None)

                # Maximum profit possible from each machine
                maxprofit = ((case.days -*machine.profit
                             - + machine.sell)

                # Skip machines that can only give a loss. This
                # includes machines that can only be bought after
                # case.days.
                if maxprofit < 0:

                machine = machine._replace(maxprofit = maxprofit)


class InvalidPlan(Exception):

def final_capital(case, machines, plan):
    """Given a case, some machines, and an action plan about whether to
    buy a machine or not, compute the final capital given by this
    plan. Raises InvalidPlan if it's impossible to buy a machine at
    any step.

    This is our objective function to maximise over all possible

    capital =

    # The "slot" that holds a machine. Initially, there's nothing
    # there.
    slot = None

    for (action, machine) in sorted(zip(plan, machines),
                                    key = lambda x: x[1].day):
        if action:
            # We attempt to buy a new machine
            if capital <
                raise InvalidPlan("Not enough capital at day %d: "
                                  "machine cost is %d, and capital is %d"
                                  % (,, capital))

            capital -=
            if slot:
                if ==
                    raise InvalidPlan("Cannot buy two machines on the same day: %d"
                                      % (

                # Subtract 1, because the machine in the slot cannot
                # be used the day it's sold.
                days_used = - - 1
                capital += days_used*slot.profit
                capital += slot.sell

            slot = machine

    # We account for the final machine, if we have it.
    if slot:
        # We can sell the day after the restructuring period, so no
        # subtracting 1 here.
        days_used = case.days -
        capital += days_used*slot.profit
        capital += slot.sell

    return capital
def main():
    cases = parseinput("input.txt")
    for case in cases:
        print "Next case:", case["header"]
        for machine in case["machines"]:
            print machine

if __name__ == "__main__":