# 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='', type=str, help='file containing panel data') parser.add_argument('-g', '--goal', metavar='', type=int, help='Goal we are trying to reach (default 250000)', default=250000) parser.add_argument('-d', '--days', metavar='', 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")