{"id":34590,"date":"2018-12-01T09:58:00","date_gmt":"2018-12-01T08:58:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=34590"},"modified":"2024-12-02T12:02:00","modified_gmt":"2024-12-02T11:02:00","slug":"advent-of-code-2015","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/advent-of-code-2015\/","title":{"rendered":"Advent of Code 2015 \u2013 Objektorientierte L\u00f6sungen in Java"},"content":{"rendered":"\n

In diesem Artikel findest du kurze Erkl\u00e4rungen zu meinen L\u00f6sungen f\u00fcr Advent of Code 2015<\/a>.<\/p>\n\n\n\n

Meine L\u00f6sungen findest du in diesem GitHub-Projekt: Advent of Code 2015 \u2013 Object-oriented Solutions in Java<\/a>.<\/p>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 1 L\u00f6sung<\/h2>\n\n\n\n

Tag 1<\/a> ist schnell gel\u00f6st: Ein Counter wird f\u00fcr jede '(' hoch- und f\u00fcr jede ')' wieder runtergez\u00e4hlt \u2013 entweder bis zum Ende (Teil eins) oder bis der Z\u00e4hler den Wert -1 erreicht (Teil zwei).<\/p>\n\n\n\n

GitHub: Advent of Code 2015 Tag 1 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 2 L\u00f6sung<\/h2>\n\n\n\n

Tag 2<\/a> ist auch recht einfach \u2013 man muss nur jede Zeile in L\u00e4nge, Breite und H\u00f6he parsen und ein paar Grundrechenarten anwenden, um Fl\u00e4chen, Umfang und Volumen zu berechnen.<\/p>\n\n\n\n

GitHub: Advent of Code 2015 Tag 2 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 3 L\u00f6sung<\/h2>\n\n\n\n

Die L\u00f6sung von Tag 3<\/a> habe ich mit einem Set<\/code> implementiert, das alle Orte speichert, die Santa besucht hat. Die L\u00f6sung von Teil eins entspricht der Gr\u00f6\u00dfe des Sets.<\/p>\n\n\n\n

F\u00fcr Teil zwei habe ich je ein Set<\/code> f\u00fcr Santa und eines f\u00fcr Robo-Santa verwendet. Am Ende werden beide Set<\/code>s zu einem zusammengef\u00fchrt und dessen Gr\u00f6\u00dfe zur\u00fcckgegeben.<\/p>\n\n\n\n

GitHub: Advent of Code 2015 Tag 3 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 4 L\u00f6sung<\/h2>\n\n\n\n

Um Tag 4<\/a> zu l\u00f6sen, m\u00fcssen wir \u00fcber alle positiven Zahlen iterieren, bis wir einen Hash mit der geforderten Anzahl von f\u00fchrenden Nullen finden. Es geht etwa doppelt so schnell, wenn wir direkt im Byte-Array nach den f\u00fchrenden Nullen suchen und dieses nicht erst in einen Hex-String umwandeln.<\/p>\n\n\n\n

GitHub: Advent of Code 2015 Tag 4 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 5 L\u00f6sung<\/h2>\n\n\n\n

F\u00fcr Tag 5<\/a> habe ich zwei \"Nice String\"-Detektoren geschrieben, die das Interface Predicate<String><\/code> implementieren. Auf diese Weise k\u00f6nnen wir den Detektor f\u00fcr Teil zwei leicht austauschen.<\/p>\n\n\n\n

GitHub: Advent of Code 2015 Tag 5 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n

\n

Advent of Code 2015 \u2013 Tag 6 L\u00f6sung<\/h2>\n\n\n\n

Tag 6<\/a> habe ich mit einem zweidimensionalen Array von ints gel\u00f6st. Ich habe die beiden Regels\u00e4tze f\u00fcr Teil eins und zwei jeweils mit einer Map<\/code> vom Kommando (\"turn on\", \"toggle\", \"turn off\") auf einen IntUnaryOperator<\/code> implementiert, der die neue Helligkeit auf der Grundlage der vorherigen berechnet.<\/p>\n\n\n\n

Dies ist der interessante Teil des Codes:<\/p>\n\n\n

EnumMap<Command, IntUnaryOperator> commandToOperatorPart1 = new<\/span> EnumMap<>(Command.class<\/span>)<\/span>;\ncommandToOperatorPart1.put(TURN_ON, brightness -> 1<\/span>);\ncommandToOperatorPart1.put(TOGGLE, brightness -> 1<\/span> - brightness);\ncommandToOperatorPart1.put(TURN_OFF, brightness -> 0<\/span>);\n\nEnumMap<Command, IntUnaryOperator> commandToOperatorPart2 = new<\/span> EnumMap<>(Command.class<\/span>)<\/span>;\ncommandToOperatorPart2.put(TURN_ON, brightness -> brightness + 1<\/span>);\ncommandToOperatorPart2.put(TOGGLE, brightness -> brightness + 2<\/span>);\ncommandToOperatorPart2.put(TURN_OFF, brightness -> Math.max(brightness - 1<\/span>, 0<\/span>));<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Und so wird eine solche Operation auf ein Feld im Array angewendet:<\/p>\n\n\n
IntUnaryOperator operator = commandToOperator.get(command);\nbrightness[y][x] = operator.applyAsInt(brightness[y][x]);<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
\n
Advent of Code 2015 \u2013 Tag 7 L\u00f6sung<\/h2>\n\n\n\n
Das Dom\u00e4nenmodell f\u00fcr Tag 7<\/a> war ein bisschen schwierig zu gestalten. So sah es am Ende aus:<\/p>\n\n\n\n
\"Advent<\/figure>\n\n\n\n
Wenn dieses Modell fertig verdrahtet ist, muss man nur noch die Instruction<\/code> mit der destinationWireId<\/code> finden und die Methode getSignal()<\/code> f\u00fcr die WireSource<\/code> dieser Instruction<\/code> aufrufen.<\/p>\n\n\n\n
GitHub: Advent of Code 2015 Tag 7 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
\n
Advent of Code 2015 \u2013 Tag 8 L\u00f6sung<\/h2>\n\n\n\n
An Tag 8<\/a> k\u00f6nnen wir uns ein wenig zur\u00fccklehnen. Die Escape- und Unescape-Methoden sind schnell implementiert.<\/p>\n\n\n\n
GitHub: Advent of Code 2015 Tag 8 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
\n
Advent of Code 2015 \u2013 Tag 9 L\u00f6sung<\/h2>\n\n\n\n
An Tag 9<\/a> m\u00fcssen wir das klassische \"Problem des Handlungsreisenden<\/a>\" (Travelling salesman problem) l\u00f6sen. Da wir nur ein paar St\u00e4dte haben, k\u00f6nnen wir eine einfache Tiefensuche durchf\u00fchren, um alle m\u00f6glichen Routen zu finden, und ihre minimale und maximale L\u00e4nge festhalten.<\/p>\n\n\n\n
GitHub: Advent of Code 2015 Tag 9 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
\n
Advent of Code 2015 \u2013 Tag 10 L\u00f6sung<\/h2>\n\n\n\n
Ein Blick in den von Tag 10<\/a> verlinkten Wikipedia-Artikel l\u00e4sst mich vermuten, dass die die L\u00e4nge der Sequenz nach 40 Runden in der Gr\u00f6\u00dfenordnung von einer Million liegt. Das sollte jeder moderne Computer in wenigen Millisekunden simulieren k\u00f6nnen.<\/p>\n\n\n\n
Der Algorithmus ist schnell implementiert und l\u00f6st Teil eins in 5 Millisekunden. Mein Ergebnis ist 492.982 \u2013 liegt also in der angepeilten Gr\u00f6\u00dfenordnung.<\/p>\n\n\n\n
Auch f\u00fcr Teil zwei \u2013 50 Runden \u2013 braucht der Algorithmus nur 70 ms.<\/p>\n\n\n\n
GitHub: Advent of Code 2015 Tag 10 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
\n
Advent of Code 2015 \u2013 Tag 11 L\u00f6sung<\/h2>\n\n\n\n
Der Algorithmus f\u00fcr Tag 11<\/a> schafft die Aufgabe auch ohne Optimierungen in unter 100 ms. Mit einigen Optimierungen l\u00e4sst sich diese Zeit stark reduzieren:<\/p>\n\n\n\n
    \n
  • Der String wird zu Beginn in ein Character-Array umgewandelt; alle Operationen erfolgen auf diesem; die R\u00fcckumwandung in einen String erfolgt erst am Ende.<\/li>\n\n\n\n
  • Zu Beginn wird gepr\u00fcft, ob das Passwort einen der Buchstaben i, l, o enth\u00e4lt. Wenn ja, dann wird die entsprechende Stelle sofort erh\u00f6ht und alle Folgestellen auf 'a' gesetzt.<\/li>\n\n\n\n
  • Beim Hochz\u00e4hlen werden die Buchstaben i, l, o \u00fcbersprungen.<\/li>\n<\/ul>\n\n\n\n
    Mit diesen Optimierungen findet der Algorithmus das n\u00e4chste Passwort in 0,016 ms!<\/p>\n\n\n\n
    GitHub: Advent of Code 2015 Tag 11 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
    \n
    Advent of Code 2015 \u2013 Tag 12 L\u00f6sung<\/h2>\n\n\n\n
    Teil eins von Tag 12<\/a> l\u00e4sst sich mit einem simplen regul\u00e4ren Ausdruck l\u00f6sen: \"-?\\d+\" (die Anf\u00fchrungszeichen geh\u00f6ren nicht dazu). Wir m\u00fcssen nur noch alle Treffer aufsummieren.<\/p>\n\n\n\n
    Teil zwei l\u00e4sst sich mit einem JSON-Parser (z. B. Gson<\/a>) und Rekursion gut l\u00f6sen.<\/p>\n\n\n\n
    GitHub: Advent of Code 2015 Tag 12 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
    \n
    Advent of Code 2015 \u2013 Tag 13 L\u00f6sung<\/h2>\n\n\n\n
    Tag 13<\/a> l\u00e4sst sich mit einer Tiefensuche \u00fcber alle m\u00f6glichen Sitzordnungen schnell l\u00f6sen.<\/p>\n\n\n\n
    GitHub: Advent of Code 2015 Tag 13 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
    \n
    Advent of Code 2015 \u2013 Tag 14 L\u00f6sung<\/h2>\n\n\n\n
    Teil eins von Tag 14<\/a>, also die Entfernung, die ein Rentier nach einer bestimmten Zeit zur\u00fcckgelegt hat, l\u00e4sst sich leicht berechnen. <\/p>\n\n\n\n
    Die gleiche Formel k\u00f6nnen wir f\u00fcr Teil zwei anwenden, mit ihr l\u00e4sst sich die Aufgabe in weniger als einer Millisekunde l\u00f6sen. Die Zeitkomplexit\u00e4t<\/a> ist allerdings O(n\u00b2 \u00b7 m)<\/em>, wobei n<\/em> die simulierte Zeit ist und m<\/em> die Anzahl der Rentiere. Die ben\u00f6tigte Zeit w\u00e4chst also im Quadrat mit der simulierten Zeit.<\/p>\n\n\n\n
    Schneller geht es, wenn wir den Fortschritt der Rentiere Sekunde f\u00fcr Sekunde simulieren (so habe ich Teil zwei letztlich implementiert). So erreichen wir die deutlich bessere Zeitkomplexit\u00e4t O(n \u00b7 m)<\/em>.<\/p>\n\n\n\n
    GitHub: Advent of Code 2015 Tag 14 L\u00f6sung<\/a><\/p>\n\n\n
GitHub: Advent of Code 2015 Tag 6 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n