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

Ungeduldig? Dann geht es hier ohne Umwege zu meinen L\u00f6sungen f\u00fcr Advent of Code 2022<\/a> :-)<\/p>\n\n\n\n

Was ist Advent of Code?<\/h2>\n\n\n\n

Advent of Code<\/a> ist eine j\u00e4hrliche, vorweihnachtliche Serie von Programmieraufgaben, die als Adventskalender verpackt sind. Hinter dessen T\u00fcren verbergen sich t\u00e4glich neue \u2013 von Tag zu Tag schwierigere \u2013 Herausforderungen.<\/p>\n\n\n\n

Die Aufgaben k\u00f6nnen in einer beliebigen Programmiersprache gel\u00f6st werden und bestehen jeweils aus zwei Teilaufgaben.<\/p>\n\n\n\n

Wie schwer ist Advent of Code?<\/h2>\n\n\n\n

Die erste Teilaufgabe ist meist relativ schnell gel\u00f6st.<\/p>\n\n\n\n

Bei der zweiten Aufgabe wird die Gr\u00f6\u00dfenordnung des Problems drastisch angehoben. Das f\u00fchrt in der Regel dazu, dass die L\u00f6sung noch einmal \u00fcberarbeitet werden muss, da der intuitiv implementierte Algorithmus oft eine zu hohe Komplexit\u00e4tsklasse<\/a> aufweist und Stunden, Tage oder gar Monate f\u00fcr die L\u00f6sung der Aufgabe brauchen w\u00fcrde.<\/p>\n\n\n\n

Kurz nach der Ver\u00f6ffentlichung eines neuen Advent-of-Code-R\u00e4tsels findet man bereits die ersten L\u00f6sungen im entsprechenden Reddit<\/a>. Diese bestehen meist aus prozeduralem Spaghetti-Code, der nicht besonders gut lesbar, geschweige denn wartbar, ist.<\/p>\n\n\n\n

Meine Advent of Code Antworten 2022<\/h2>\n\n\n\n

Ich habe mir daher die M\u00fche gemacht, jede Aufgabe wirklich objektorientiert und testgetrieben in Java zu implementieren, so dass eine L\u00f6sung aus kleinen, verst\u00e4ndlichen, miteinander interagierenden Objekten entsteht.<\/p>\n\n\n\n

Dieser Ansatz f\u00fchrt in der Regel auch dazu, dass sich die Optimierungen, die f\u00fcr Teilaufgabe zwei notwendig sind, auf einen kleinen Ausschnitt des Codes beschr\u00e4nken \u2013 oft auf eine einzige Klasse.<\/p>\n\n\n\n

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

\n

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

Die Aufgaben von Tag 1<\/a> lassen sich elegant mit Java Streams l\u00f6sen. Die folgende Methode liefert einen Stream der Kaloriensummen f\u00fcr jeden Block:<\/p>\n\n\n

static<\/span> IntStream getCaloriesSums<\/span>(String input)<\/span> <\/span>{\n  String[] blocks = input.split(\"\\\\n\\\\n\"<\/span>);\n  return<\/span> Arrays.stream(blocks)\n      .mapToInt(block -> block.lines().mapToInt(Integer::parseInt).sum());\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Den gr\u00f6\u00dften Block ermitteln wir mittels max()<\/code>:<\/p>\n\n\n
static<\/span> int<\/span> calculateMaxCalories<\/span>(String input)<\/span> <\/span>{\n  IntStream caloriesSums = getCaloriesSums(input);\n  return<\/span> caloriesSums.max().orElse(0<\/span>);\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
F\u00fcr die Summe der drei gr\u00f6\u00dften Blocks m\u00fcssen wir den Stream absteigend sortieren. Dazu ist leider ein Boxing und ein Unboxing erforderlich, da sich ein IntStream<\/code> nur aufsteigend sortieren l\u00e4sst:<\/p>\n\n\n
static<\/span> int<\/span> calculateSumOfTopThreeCalories<\/span>(String input)<\/span> <\/span>{\n  IntStream caloriesSums = getCaloriesSums(input);\n  return<\/span> caloriesSums\n      .boxed()\n      .sorted(Comparator.reverseOrder())\n      .mapToInt(Integer::valueOf)\n      .limit(3<\/span>)\n      .sum();\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
\n
Advent of Code 2022 \u2013 Tag 2 L\u00f6sung<\/h2>\n\n\n\n
An Tag 2<\/a> m\u00fcssen wir einen Simulator f\u00fcr Schere-Stein-Papier<\/a> schreiben. Teilaufgabe zwei, bei der wir vom Spielergebnis auf den Zug r\u00fcckschlie\u00dfen m\u00fcssen, habe ich durch ausprobieren gel\u00f6st \u2013 es gibt ja nur drei m\u00f6gliche Z\u00fcge. Eleganter w\u00e4re es nat\u00fcrlich, den eigenen Zug aus dem Zug dem Gegners und dem gew\u00fcnschten Ergebnis zu berechnen.<\/p>\n\n\n\n
GitHub: Advent of Code 2022 Tag 2 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n
\n
Advent of Code 2022 \u2013 Tag 3 L\u00f6sung<\/h2>\n\n\n\n
An Tag 3<\/a> m\u00fcssen wir einen Algorithmus implementieren, der aus mehreren Listen von Gegenst\u00e4nden (aus zwei F\u00e4chern eines Rucksacks bzw. aus drei Rucks\u00e4cken) diejenigen herausfiltert, die mehrfach vorkommen.<\/p>\n\n\n\n
Wenn wir dabei jedes Element einer Liste mit allen Elementen der zwei anderen Listen vergleichen, k\u00e4men wir auf eine Zeitkomplexit\u00e4t<\/a> von O(n\u00b2)<\/em>.<\/p>\n\n\n\n
Da die Menge der m\u00f6glichen Elemente (A-Z und a-z) sehr klein ist, k\u00f6nnen wir stattdessen ein Array mit Bitsets f\u00fcr jedes m\u00f6gliche Element anlegen, dann \u00fcber jede Liste iterieren und f\u00fcr jedes enthaltene Element ein Bit f\u00fcr die entsprechende Liste setzen und zuletzt pr\u00fcfen, f\u00fcr welche Elemente alle Bits gesetzt sind. Dieser Algorithmus hat die deutlich bessere Zeitkomplexit\u00e4t O(n)<\/em>.<\/p>\n\n\n\n
GitHub: Advent of Code 2022 Tag 3 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n
GitHub: Advent of Code 2022 Tag 1 L\u00f6sung<\/a><\/p>\n<\/div><\/div>\n\n\n\n