reddit-challenge/reddit.py

# Lily Carpenter
# lily-redditchallenge@azrazalea.net
# 2049 South Florence Apt. 8
# Springfield, MO
# 417-379-3326
#
# Copyright (c) 2013, Lily Carpenter
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without modification,
# are permitted provided that the following conditions are met:
#
#   Redistributions of source code must retain the above copyright notice, this
#   list of conditions and the following disclaimer.
#
#   Redistributions in binary form must reproduce the above copyright notice, this
#   list of conditions and the following disclaimer in the documentation and/or
#   other materials provided with the distribution.
#
#   Neither the name of Lily Carpenter nor the names of its
#   contributors may be used to endorse or promote products derived from
#   this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# Premise:
# While I'm sure there is a fancy algorithm to do this very efficiently, I have not gotten far enough into
# math/computer science theory in order to be able to come up with it effectively.
#
# Therefore, here is how my script works:
# 1. Sorts all panels in descending order based on value
# 2. Starting with the person with the highest yield (me) and going from there
#    it adds the highest value panels to the set panel list until we reach or surpass goal
# 3. If we managed to hit goal exactly, we are done. Otherwise, start second process
# 4. In the second process we resort data in ascending order and try until we reach or surpass goal
#
# This should theoretically result in using the lower yield people the least, as well as getting as close as possible
# to the goal without going over.

import argparse
import sys
import locale

# Setup command line arguments
# I did goal and days partly just because I wanted to play with the values
parser = argparse.ArgumentParser(description='Determine panel distribution')
parser.add_argument('file_name', metavar='<File Name>', type=str, help='file containing panel data')
parser.add_argument('-g', '--goal', metavar='<Goal>', type=int, help='Goal we are trying to reach (default 250000)', default=250000)
parser.add_argument('-d', '--days', metavar='<Days>', type=int, help='Number of days to reach goal (default 7)', default=7)


# A list of dictionaries containing the necessary data on each person
# Also stores the set of panels to be assigned to each person
# This is pulled from the problem description, of course
people = [
        {'name': 'M', 'yield': 1, 'pan_a_day': 1, 'panels': [] },
        {'name': 'GM', 'yield': .95, 'pan_a_day': 2, 'panels': [] },
        {'name': '?', 'yield': .85, 'pan_a_day': 3, 'panels': [] },
        {'name': 'GB', 'yield': .6, 'pan_a_day': 4, 'panels': [] },
    ]

# Simple function, simply loads data from file_name and converts it to int, puts in list data, and returns data
# The data list contains tuples of (index, value) to preserve original index later when sorting
# If it gets something that isn't a number it'll tell you about it, make that entry 0, then continue like nothing happened
def get_data(file_name):
    data = []
    with open(file_name, 'r') as _file:
        for line_num, line in enumerate(_file, 1):
            try:
                line = int(line)
            except ValueError:
                sys.stderr.write('Skipping invalid data at line: ' + str(line_num) + '\n')
                # This is so that we don't miss a panel index
                data.append(0)
            else:
                data.append((line_num - 1, int(line)))
    return data

# Grab the data and arguments
args = parser.parse_args()
data = get_data(args.file_name)
days = args.days
goal = args.goal

# Grab replacement cost of panels
replace_cost = data.pop(0)[1]

# Sort by the 'value' column, descending, to get list ready for processing
data.sort(key=lambda datem: datem[1], reverse=True)

current_money = 0
panel = 0
# This loop goes through each person, people is already setup to be descending by yield
for person in people:
    for x in range(0, person['pan_a_day'] * days):
        # This is how much the current panel is worth, taking into account yield and
        # replacement cost
        additional_amt = data[panel][1] * person['yield'] - replace_cost

        # If the next panel in list does not meet or go past the goal, add to person's panel set
        # and increment current_money by additional_amt
        if current_money + additional_amt <= goal:
            current_money += additional_amt
            person['panels'].append((data[panel][0], data[panel][1]))
            panel += 1
        # Otherwise, we need to switch gears and look for the smallest possible panel to finish
        else:
            data.sort(key=lambda datem: datem[1])

            # Have to have this up here in case there was a perfect match
            if current_money >= goal:
                break;

            for y in range(0, len(data) - panel):
                additional_amt = data[y][1] * person['yield'] - replace_cost
                if current_money + additional_amt >= goal:
                    current_money += additional_amt
                    person['panels'].append((data[y][0], data[y][1]))
                    break;

    if current_money >= goal:
        break;

# Print the output, all pretty like
for person in people:
    print ' '.join([person['name'], '=', repr(person['panels'])])

# Add up how much money is left
money_left = 0
for x in range(panel, len(data)):
    money_left += data[x][1]

# Print out how much money is left
locale.setlocale(locale.LC_ALL, '')
print 'Total cash left in bannana stand: $' + format(money_left, "n")