Advent of Code day 15

[nezzcarth]

Hallo

Weihnachten ist zwar schon vorbei, aber ich habe immer noch Spaß mit den Advent of Code Aufgaben. Für Tag 15 habe ich folgendes gebastelt:

(Python 3)

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import re
import fileinput
from itertools import tee, product
from functools import reduce
from operator import mul


ATTRIBUTES = ('capacity', 'durability', 'flavor', 'texture', 'calories')
EXCLUDED = ('calories')
SEPARATOR = re.compile(r'^(\w+)[^\d-]+(-?[\d]+)[^\d-]+(-?[\d]+)[^\d-]+(-?[\d]+)[^\d-]+(-?[\d]+)[^\d-]+(-?[\d]+)$')
SPOONS = 100
CALORIES = 500

class Cookie:
    def __init__(self, amounts, stats, spoons=SPOONS):
        self.amounts = amounts
        self.stats = stats
        if not sum(self.amounts.values()) == spoons:
            raise ValueError
    
    def __getattr__(self, name):
        attribute = name
        result = sum(
            self.stats[ingredient][attribute]*amount
            for ingredient, amount in self.amounts.items()
        )
        return result if result > 0 else 0

    @property 
    def score(self):
        return reduce(
            mul,
            [getattr(self, attribute) for attribute in ATTRIBUTES if not attribute in EXCLUDED]
        )


def parse_file():
    result = dict()
    lines = [line.strip() for line in fileinput.input()]
    for line in lines:
        name, *stats = re.search(SEPARATOR, line).groups()
        stats = map(int, stats)
        result[name] = dict(zip(ATTRIBUTES, stats))
    return result


def main():
    stats = parse_file()
    ingredients = stats.keys()
    ingredients_n = len(ingredients)
    upper_boundary = SPOONS - ingredients_n + 1
    print("Part A")
    result = max(
        Cookie(dict(zip(ingredients, item)), stats).score
        for item in filter(
            lambda x:sum(x)==SPOONS,
            product(*tee(range(1, upper_boundary), ingredients_n))
        )
    )
   
    print(result)
    print("Part B")
    result = 0
    for item in filter(
        lambda x:sum(x)==SPOONS,
        product(*tee(range(1, upper_boundary), ingredients_n))):

        cookie = Cookie(dict(zip(ingredients, item)), stats)
        if cookie.calories == CALORIES:
            result = cookie.score if cookie.score > result else result
    print(result)
    
if __name__ == '__main__':
    main()

Ich versuche zwar keine Minimallösungen zu schreiben, wie vieles, was man so findet. Allerdings kommt mir das wieder an einigen Stellen trotzdem zu kompliziert vor. Insb. hatte ich Probleme, eine geschickte Repräsentationen für die vorgegebenen Daten zu finden. Ist die Cookie-Klasse so sinnvoll, oder ist das zu meta? (Objekt-orientiertes Programmieren ist ja leider nicht so meine Stärke ) Unschön finde ich beispielsweise die Behandlung der Kalorien oder das Erstellen der Dictionaries für die Mengenangaben. Ungünstig ist auch, dass die Attribute jedes Mal neu berechnet werden, obwohl sie sich selten ändern werden; da einen Caching/Update-Mechanismus einzubauen ist aber vielleicht etwas übertrieben?

Bzgl. der eigentlichen Lösung war ich unkreativ; das Verfahren ist ineffizient, aber liefert das Ergebnis in vertretbarer Zeit. Gibt es eigentlich auch einen effizienteren Algorithmus, um das zu bewältigen? Ich hatte zwischenzeitlich mal zufällige Kekse erstellt und mir den jeweils besten gemerkt; das gesuchte Optimum kommt spannenderweise meist in wenigen Sekunden und deutlich schneller, als per Brute-Force

An Kommentaren und Alternativvorschlägen wäre ich wie immer sehr interessiert.

[BlackJack]

@nezzcarth: Ich habe die Zutaten im Grunde 1:1 in einer Klasse für eine Zutat abgebildet die man mit Konstanten multiplizieren kann und die man aufaddieren kann. Und es gibt ein `score`-Property. Man kann also die einzelnen Zutaten erst mit der jeweiligen Anzahl von Löffeln multiplizieren, dann alle zusammenaddieren, und davon dann die Bewertung abfragen. Auf `getattr()` und ähnliches habe ich verzichtet — die vier Attribute kann man auch hinschreiben ohne das es zu viel wird und ich find's leichter lesbar.

Einzige Optimierung gegenüber Deinem Ansatz die ich gemacht habe ist eine Funktion die nur gültige Löffel-Kombinationen erstellt, statt alle zu erstellen und dann die ungültigen zu filtern:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
import sys
from itertools import imap
from operator import mul


def product(iterable):
    return reduce(mul, iterable, 1)


class Ingredient(object):
    
    def __init__(self, name, capacity, durability, flavor, texture, calories):
        self.name = name
        self.capacity = capacity
        self.durability = durability
        self.flavor = flavor
        self.texture = texture
        self.calories = calories

    def __str__(self):
        return self.name

    def __mul__(self, amount):
        return Ingredient(
            '{0}x{1}'.format(amount, self.name),
            self.capacity * amount,
            self.durability * amount,
            self.flavor * amount,
            self.texture * amount,
            self.calories * amount,
        )

    def __add__(self, other):
        return Ingredient(
            '{0}, {1}'.format(self.name, other.name),
            self.capacity + other.capacity,
            self.durability + other.durability,
            self.flavor + other.flavor,
            self.texture + other.texture,
            self.calories + other.calories,
        )

    @property
    def score(self):
        properties = [self.capacity, self.durability, self.flavor, self.texture]
        return product(max(0, p) for p in properties)


ZERO = Ingredient('Nothing', 0, 0, 0, 0, 0)


def parse_property(string):
    name, value = string.split()
    return (name, int(value))


def parse_line(line):
    name, colon, properties_string = line.partition(':')
    if colon != ':':
        raise ValueError('colon expected')
    properties = dict(imap(parse_property, properties_string.split(',')))
    return Ingredient(
        name,
        properties['capacity'],
        properties['durability'],
        properties['flavor'],
        properties['texture'],
        properties['calories'],
    )


def iter_combinations(spoon_count, ingredient_count):

    result = list()

    def recurse(spoon_count):
        if len(result) == ingredient_count - 1:
            yield result + [spoon_count]
        else:
            for i in xrange(spoon_count + 1):
                result.append(i)
                for sub_result in recurse(spoon_count - i):
                    yield sub_result
                result.pop()

    return recurse(spoon_count)


def make_cookie(ingredients, spoon_counts):
    return sum((i * n for i, n in zip(ingredients, spoon_counts)), ZERO)


def main():
    ingredients = map(parse_line, sys.stdin)
    cookies = [
        make_cookie(ingredients, spoon_counts)
        for spoon_counts in iter_combinations(100, len(ingredients))
    ]
    print(max(c.score for c in cookies))
    print(max(c.score for c in cookies if c.calories == 500))


if __name__ == '__main__':
    main()