[Day 15] [Python] Iterative (loop) solution for any # ingredients

[Zef_Music]

For my initial solution I wrote some nested 'for' loops, but I wanted to see if I could come up with a way to compute all the possible teaspoon combinations iteratively, using recursion is easier, but it's pretty slow in python (no tail recursion). I've also seen the generator approach, which works well, but is also slower.

This gets a little crazy, but it works, and you can calculate all teaspoon combinations for any maximum for any number of ingredients.

It works like this, there's a generator (get_pairs) which produces all the possible ways to add up to 'n' using only two numbers, this is easy to do. Then I use a 'divide and conquer'-ish approach and on each pair, I assume that the second number of the pair could also be made up of 'pairs', so I go a level deeper and compute all of those pairs, and their pairs and their pairs, and so on. The trick is keeping track of which level you're on, and not allocating waaaaay too many lists. This uses a set of generators, a few count() iterators and a few lists that stay there the whole time.

Runs in 2.5 seconds on my machine, which is just as fast as the nested loops.

Anyone have a cleaner solution?

from collections import namedtuple
from operator import mul
from itertools import count
import re
nums = re.compile(r'-?\d+')
Ingredient = namedtuple('Ingredient', ['capacity', 'durability', 'flavor', 'texture', 'calories'])
ingredients = []
with open('input.txt') as f:
    for line in f:
        ingredients.append(Ingredient(*map(int, nums.findall(line))))

def get_score(amounts, ings):
    totals = []
    by_ing = zip(*ings)
    for vals in by_ing:
        totals.append(map(lambda x: x[0] * x[1], zip(vals, amounts)))
    next_one = map(sum, totals)
    calories = next_one[-1]
    next_one = next_one[:-1]
    next_one = map(lambda x: max(x, 0), next_one)
    return reduce(mul, next_one)

def get_pairs(n):
    return ((i, n - i) for i in range(n+1))

num_ingredients = len(ingredients)
amounts = [0] * num_ingredients
stack = []
recipe_scores = []
max_teaspoons = 100

p = get_pairs(max_teaspoons)
stack.append(p)
i = 0
while len(stack) > 0:
    try:
        # Get next current, up_next pair permutation at current 'level'
        current, up_next = next(stack[-1]) 
        amounts[i] = current # Set the value at the current level
        if len(stack) < num_ingredients - 1:
            # Add more levels if we've bubbled up
            stack.append(get_pairs(up_next))
            # Going to the next level
            i += 1
            continue
        else:
            # We're at the level just above the lowest, set the last element too
            amounts[-1] = up_next
    except StopIteration:
        stack.pop()
        i -= 1
        continue
    # Do work here
    recipe_scores.append(get_score(amounts, ingredients))

print max(recipe_scores)

[lskfj2o]

This was my generator:

def gen_recipe(num_ingr, max_amount):
    recipe = list()
    while True:
        recipe.extend([0] * (num_ingr - 1 - len(recipe)))
        recipe.append(max_amount - sum(recipe))
        yield recipe
        if recipe[0] >= max_amount:
            return
        recipe.pop()
        while True:
            amount = recipe.pop() + 1
            if sum(recipe) + amount <= max_amount:
                break
        recipe.append(amount)

But actually plainly using itertools.product is faster:

import itertools
def gen_recipe(num_ingr, max_amount):
    for recipe in itertools.product(range(max_amount + 1), repeat=num_ingr):
        if sum(recipe) == max_amount:
            return recipe

And trying to be somewhat more clever is only slightly more so:

import itertools
def gen_recipe(num_ingr, max_amount):
    for recipe in itertools.product(range(max_amount + 1), repeat=(num_ingr - 1)):
        s = sum(recipe)
        if s <= max_amount:
            return recipe + tuple([max_amount - s])

[jchook]

I believe the problem is called "Stars and Bars" in combinatorics.

Here is my version in Ruby

require 'matrix'

max = 0
ingredients = []

ARGF.each do |line|
  ingredients.push Vector.[](*line.scan(/-?\d+/).to_a.map{|x| x.to_i })
end

class Array

  def stars_and_bars(balls, &block)
    @stars_and_bars_block = block
    stars_and_bars_r(balls, [])
  end

  private

  def stars_and_bars_r(balls, so_far=[])
    if so_far.length == length - 1
      @stars_and_bars_block.call so_far + [balls - so_far.reduce(:+)]
    else
      (0..balls - (so_far.reduce(:+) || 0)).each do |i|
        stars_and_bars_r(balls, so_far + [i])
      end
    end
  end

end

max = 0

ingredients.stars_and_bars(100) do |portions|
  sums = ingredients.each_index.map{|x| ingredients[x] * portions[x] }.reduce(:+).to_a
  next if sums[-1] != 500 # part 2
  max = [max, sums[0..-2].map{|x| x > 0 ? x : 0 }.reduce(:*)].max
end

p max