Advent of Code 2019 Day 14

day_14.py

import math
from collections import Counter

from funcy import post_processing
from parse import parse
from scipy.optimize import minimize_scalar


@post_processing(dict)
def parse_input(input_str):
    quantity_pattern = '{num:d} {unit:w}'
    for line in input_str.strip().splitlines():
        left_str, right = line.split(' => ')
        lefts = [parse(quantity_pattern, input) for input in left_str.split(', ')]
        lefts = {input['unit']: input['num'] for input in lefts}
        right = parse(quantity_pattern, right)
        yield right['unit'], {'right_num': right['num'], 'lefts': lefts}


def calc_ore(eqs, fuel):
    chemicals = Counter()
    chemicals['FUEL'] = fuel

    last_chemicals = None

    while last_chemicals != chemicals:
        last_chemicals = chemicals.copy()

        for right, eq_data in eqs.items():
            for got_unit, got_num in list(chemicals.items()):

                if got_unit == right and got_num > 0:
                    mult = math.ceil(got_num / eq_data['right_num'])
                    chemicals[got_unit] -= mult * eq_data['right_num']

                    for left_unit, left_num in eq_data['lefts'].items():
                        chemicals[left_unit] += mult * left_num

    return chemicals['ORE']


def part_one(input_str):
    eqs = parse_input(input_str)
    return calc_ore(eqs, fuel=1)


def part_two(input_str):
    eqs = parse_input(input_str)
    max_ore = 1e12

    def fuel_error(fuel_quota):
        ore = calc_ore(eqs, int(fuel_quota))
        print(fuel_quota, ore)

        ore_left = max_ore - ore
        if ore_left < 0:
            # Penalise using more than the quota
            return abs(ore_left) * 100
        return ore_left

    ore_per_fuel = calc_ore(eqs, fuel=1)
    fuel_estimate = max_ore / ore_per_fuel

    fuel = minimize_scalar(
        fuel_error,
        bracket=(fuel_estimate, 2 * fuel_estimate)
    ).x
    return int(fuel)

Worked perfectly. I cannot thank you enough for engaging. I know a (very) little bit about the theory of optimization approaches, but have never put them into practice or really delved into them. You have jump started a whole area I needed to learn about!

My solution was brute force and not efficient and took 2 hours! Yours was instantaneous.

That's great to hear David. I'm treating the optimiser as a black box, and trying the different "methods" listed in the docs until it works. Also tweaking the penalty for being on the wrong side of the quota.

The alternative to brute force would be to implement a binary search, where you start with the "bracket" values I've defined, and keep checking the mid point, until you narrow it down to a single int. But I quite like the magical approach of telling scipy to "optimise" and get the answer for "free"!

Yes, once you have a complex enough problem, being able to black box it like this is a huge plus.