Advent of Code

[nezzcarth]

Spielt noch jemand?

Ich bin an Tag 7 in die Rekursionsfalle getappt, obwohl ich es hätte besser wissen müssen. Danach war dann allerdings auch meine Motivation weitgehend weg und ich habe nur noch vereinzelte Aufgaben gelöst.

[grubenfox]

Theoretisch ja... bin aber noch nicht dazu gekommen das Modul für Tag 7 fertigzustellen.

[__blackjack__]

@Manul: Mathe-Aufgaben. Bäh. Ich vermute für Teil zwei müsste man eine Repräsentation für die Zahlen finden die nicht so ”gross” wird und bei der man die Operationen und Tests effizient durchführen kann. Dann müsste man an einer Lösung für Teil 1 nicht viel ändern. Ich hätte eine Idee, wenn da nicht die Addition als Operation wäre. (Es ist wahrscheinlich jedem aufgefallen, dass die Teilbarkeit immer eine Primzahl betrifft.)

[Manul]

@Manul: Mathe-Aufgaben. Bäh. Ich vermute für Teil zwei müsste man eine Repräsentation für die Zahlen finden die nicht so ”gross” wird und bei der man die Operationen und Tests effizient durchführen kann.

Soweit d'accord.

Dann müsste man an einer Lösung für Teil 1 nicht viel ändern.

Sicher? Ich habe so eine Repräsentation gefunden (auch wenn ich nicht sicher bin, ob sie die effizienteste ist), aber die kommt mit dem "Abkühlen" nicht zurecht.

[narpfel]

Es gibt auch eine einfache Lösung, die nicht darauf basiert, dass der Test immer auf Teilbarkeit durch eine Primzahl testet. Und man kann auch ganz normale `int` zur Repräsentation nehmen. Im Prinzip ist das Diff von Teil 1 zu Teil 2 bei mir drei Zeilen lang.

[Manul]

Es gibt auch eine einfache Lösung, die nicht darauf basiert, dass der Test immer auf Teilbarkeit durch eine Primzahl testet. Und man kann auch ganz normale `int` zur Repräsentation nehmen. Im Prinzip ist das Diff von Teil 1 zu Teil 2 bei mir drei Zeilen lang.

Jetzt bin ich neugierig: Wie sieht die denn aus? Ich habe in Teil 2 für alle items zu allen vorkommenden Divisoren jeweils den "worry"-Wert modulo des Divisors gespeichert. Das funktioniert prima für Addition und Multiplikation, aber nicht mehr für Integerdivision mit Abrunden.

[narpfel]

@Manul: Wofür brauchst du denn die Division mit Abrunden?

[Manul]

@narpfel: Fürs "Abkühlen" des worry level:

After each monkey inspects an item but before it tests your worry level, your relief that the monkey's inspection didn't damage the item causes your worry level to be divided by three and rounded down to the nearest integer.

(Hervorhebung von mir)

[narpfel]

@Manul: Für Teil 2?

[Manul]

@narpfel: Nein, für Teil 1. Deswegen funktioniert ja meine Lösung für Teil 2 nur dort und nicht für Teil 1.

[sparrow]

@Manul: Das betrifft aber nur die Aufgabe Nummer 1 von heute.

[Manul]

@sparrow Sag ich doch: Ich habe beide Teile gelöst, aber keine Lösung gefunden, die für beide Teile passt. In Teil 1 habe ich die items ganz naiv als Integer modelliert. Da funktioniert das "Abkühlen", aber für Teil 2 explodiert mir die Rechenzeit. Für Teil 2 habe ich die oben beschriebene Modellierung benutzt. Das geht schnell, aber das Abkühlen funktioniert nicht mehr.

[narpfel]

@Manul: Wenn du das so meinst, dann habe ich auch keine Lösung, die für beide Teile funktioniert:

Code: Alles auswählen

def part_1(monkeys):
    return solve(
        monkeys,
        round_count=20,
        worry_level_update=lambda worry_level: worry_level // 3,
    )


def part_2(monkeys):
    return solve(
        monkeys,
        round_count=10_000,
        worry_level_update=lambda worry_level: <<magic>>,
    )

[Manul]

@narpfel: Aber Du hast für beide Teile die gleiche Repräsentation des worry level - das habe ich nicht hinbekommen. Magst Du teilen, wie Du's gelöst hast?

[__blackjack__]

@Manul: Woher weisst Du das? Da steht ja nur ``<<magic>>``. Das kann ja auch bedeuten das man da sowohl `int`-Objekte als auch `WorryLevel`-Objekte rein füttern kann.

[bords0]

@Manul: Mathe-Aufgaben. Bäh. Ich vermute für Teil zwei müsste man eine Repräsentation für die Zahlen finden die nicht so ”gross” wird und bei der man die Operationen und Tests effizient durchführen kann. Dann müsste man an einer Lösung für Teil 1 nicht viel ändern. Ich hätte eine Idee, wenn da nicht die Addition als Operation wäre. (Es ist wahrscheinlich jedem aufgefallen, dass die Teilbarkeit immer eine Primzahl betrifft.)

Da bin ich gespannt. Ich habe keine Ahnung, wie eine Repräsentation aussieht, die wegen der Addition nicht klappt.
Die "offensichtliche" Repräsentation ist ja, dass man sich nur den Rest bei Division durch eine Zahl merkt. Diese Zahl kann z.B. ein Vielfaches der Divisoren der Tests sein, dann kann man die Würfe der Affen noch nachvollziehen (weil sich die Reste der Test-Divisonen offensichtlich nicht ändern).

Wie macht man es so, dass die Addition ein Problem ist?

[__blackjack__]

@bords0: Ich hatte an eine Primfaktorzerlegung gedacht. Das lässt sich leicht multiplizieren, aber Addition geht halt nicht. AFAIK. Kein Mathegenie hier.

[Manul]

@Manul: Woher weisst Du das?

Das hatte ich indirekt aus

Im Prinzip ist das Diff von Teil 1 zu Teil 2 bei mir drei Zeilen lang.

geschlossen. Je nach Interpretation sehen wir hier schon 1 bis 3 geänderte Zeilen, da bleibt an anderer Stelle nicht mehr viel Luft.

[ThomasL]

Teil 1 war ja relativ zügig machbar. Bei Teil 2 musste man entweder ein Mathegenie sein oder irgendwo nachschauen. Ich habe letzteres.

Code: Alles auswählen

from math import prod

class Monkey:
    def __init__(self, data):
        self.items = list(map(int, data[1][16:].split(', ')))
        self.op = data[2][21:].split()
        self.divisor = int(data[3].split()[-1])
        self.next = [int(data[4].split()[-1]), int(data[5].split()[-1])]
        self.inspected = 0

    def inspect(self, part1):
        while self.items:
            worry = self.items.pop(0)
            self.inspected += 1
            factor = worry if self.op[1] == 'old' else int(self.op[1])
            new = worry * factor if self.op[0] == '*' else worry + factor                
            new = int(new / 3) if part1 else new % common
            monkeys[self.next[bool(new % self.divisor)]].items.append(new)

data = [line.strip() for line in open('input.txt').readlines()]
monkeys = [Monkey(data[i*7:(i+1)*7]) for i in range((len(data) // 7)+1)]

common = prod([monkey.divisor for monkey in monkeys]) # Produkt aller Modulo Werte der Affen

def run(amount, part1):
    for round in range(amount):
        for monkey in monkeys:
            monkey.inspect(part1)

run(20, True)
print('Part 1:', prod(sorted([monkey.inspected for monkey in monkeys])[-2:]))

monkeys = [Monkey(data[i*7:(i+1)*7]) for i in range((len(data) // 7)+1)]
run(10000, False)
print('Part 2:', prod(sorted([monkey.inspected for monkey in monkeys])[-2:]))

[bords0]

@bords0: Ich hatte an eine Primfaktorzerlegung gedacht. Das lässt sich leicht multiplizieren, aber Addition geht halt nicht. AFAIK. Kein Mathegenie hier.

Ah, ja, das wäre eine gute Möglichkeit, auch große Zahlen darzustellen, wenn es nur Multiplikation gäbe.

"Divisionsrest" schreit aber eigentlich nach Modulo. Man muss natürlich wissen, dass den man den in Additionen und Multiplikationen "reinziehen" kann.