Ich liebe ja Adventskalender, mit jeder Tür bekommt man eine weihnachtliche schokoladige Figur zum Vernaschen, je nachdem welche Art von Kalender man sich kauft. Dieses Jahr gönne ich mir einen quasi kostenlosen Adventskalender, der jeden Tag etwas spannendes wenngleich schokoladiges für mich bereithält. Damit ist der diesjährige Advent of Code gemeint. Auf der Webseite wird jeden Tag ein Stück eines ASCII-Bildes freigegeben. Über das Jahr haben die Organisatoren 25 Rätsel vorbereitet, welche jeweils mit einem neuen Programm gelöst werden muss. Im Subreddit tauschen sich User darüber aus wie sie ihre Lösung in den verschiedensten Programmiersprachen realisiert haben.
Die Geschichte rund um die Coding Challenge ging schon einmal gut los: Die Liste der Braven und Bösen Kinder konnte nicht gedruckt werden. Jemand muss den TRON machen und die Sache von innen reparieren. Also werden wir als hhilfreicher Elf in den Drucker gebeamt und müssen dann erstmal in einer Quarantäne ausharen.
Tag 1 Inverse Captcha
In Tag 1 ging es darum ein Captcha zu lösen um zu beweisen das man kein Mensch ist.
Der Input für Tag 1 sieht so aus: 95148459654114155731698......(insgesamt sind es 2156 Zahlen in der Reihe) Der Algorithmus sollte die Summe aller Zahlen bilden, welche identisch mit der nächsten Zahl in der Liste ist. Hier die Erklärung. Dabei soll zudem in Teil 2 des Rätsels eine Rotation durchgeführt werden. Die Lösung des Problems sieht in Ruby so aus:
`951484596541141557316984781494999179679767747627132447513171626424561779662873157761442952212296685573452311263445163233493199211387838461594635666699422982947782623317333683978438123261326863959719777179228599319321138948466562743761584836184512984131635354116264899181952748224523953976485816295227945792555726121913344959454458829485471174415775278865324142733339789878929596275998341778873889585819916457474773252249179366599951454182657225576277834669222982366884688565754691273745959468648957498511326215934353963981471593984617554514519623785326888374742147318993423214834751785956958395133486656388454552769722562524415715913869946325551396638593398729938526424994348267935153555851552287223313383583669912941364344694725478258297498969517632881187394141593479818536194597976519254215932257653777455227477617957833273463216593642394215275314734914719726618923177918342664351954252667253233858814365351722938716621544226598956257753212248859258351363174782742336961425325381561575992352415514168782816173861148859478285339529151631429536819286498721812323861771638574344416879476255929929157912984151742613268754779685396125954595318134933366626594498249956388771723777242772654678448815844555372892574747735672368299826548254744359377667294764559334659523233146587568261116253155189394188696831691284711264872914348961888253386971994431352474717376878745948769171243242621219912378731755544387249443997382399714738351857752329367997665166956467544459817582915478514486541453932175598413554259672117364863112592515988922747164842668361925135551248923449968328385889877512156952725198691746951431443497496455761516486573476185321748523644283494181119399874324683922393547682851931435931276267766772798261563117954648576421741384823494187895272582575669685279986988357796138794326125852772995446355723211161523161886222562853546488411563473998633847953246787557146187696947831335722888918172961256498971868946237299523474841983527391489962357196433927251798764362493965894995592683296651874787384247326643886774966828657393717626591578321174832222434128817871765347278152799425565633521152643686221411129463425496425385516719682884157452772141585743166647191938727971366274357874252166721759'.freeze
def compute_sum(pairs)
matches = pairs
.find_all { |pair| pair[0] == pair[1] }
.map(&:first)
matches.reduce(&:+)
end
def generate_pairs(lhs, rhs, rotation)
lhs_digits = lhs.split('').map(&:to_i)
rhs_digits = rhs.split('').map(&:to_i)
rotation.times do
head = rhs_digits.shift
rhs_digits << head
end
lhs_digits.zip(rhs_digits)
end
first_pairs = generate_pairs INPUT, INPUT, 1
first_sum = compute_sum first_pairs
puts "First Sum: #{first_sum}"
second_pairs = generate_pairs INPUT, INPUT, INPUT.length / 2
second_sum = compute_sum second_pairs
puts "Second Sum: #{second_sum}"Meine Antworten waren damit korrekt und ich erhielt meine ersten zwei Golden Sterne :)
Tag 2 Corruption Checksum
Nachdem ich erfolgreich bewiesen hatte das ich kein Mensch war sollte ich eine Kalkulationstabelle reparieren. Nichts leichter als das! (oder etwa doch) Um dies zu bewerkstellen musste die "Checksum" jeder Tabelle berechnet werden. Die Regeln dafür waren einfach: Finde den höchsten und niedrigsten und davon die Differenz.
Perfekt! Teil 1 war schnell programmiert.
private int getChecksumPartOne() {
ArrayList<Integer> Differences = new ArrayList<>();
int checksum = 0;
for (int row = 0; row < inputvalues.length; row++) {
Differences.add(getMaximum(row) - getMinimum(row));
}
for (int index = 0; index < Differences.size(); index++) {
checksum += Differences.get(index);
}
return checksum;
}und Teil 2 war auch kein Problem. Dort musste bestimmt werden welche beiden Zahlen in einer Zeile gleichmäßig teilbare Werte voneinander sind und davon das Ergebnis ihrer Division.
private int getChecksumPartTwo() {
ArrayList<Integer> Results = new ArrayList<>();
Integer[] sortedArray = new Integer[inputvalues.length];
int checksum = 0;
for (int row = 0; row < inputvalues.length; row++) {
for (int i = 0; i < sortedArray.length; i++) {
sortedArray[i] = inputvalues[row][i];
}
Arrays.sort(sortedArray, Collections.reverseOrder());
Results.add(getDivisionResult(sortedArray));
}
for (int index = 0; index < Results.size(); index++) {
checksum += Results.get(index);
}
return checksum;
}Zwei weitere goldene Sterne für und hinzu zum bisher schwersten Rätsel für mich.
Tag 3 Spiral Memory
Nachdem die Tabelle repariert wurde, stolpert man in ein experimentellen zweidimensionalen Speicher. Im ersten Teil des Rätsel gilt es herauszufinden wie weit man laufen muss um von einem bestimmten vorgegebenen Punkt zur Mitte des Speichers zu gelangen.
Die Spirale sieht dabei so aus:
17 | 16 | 15 | 14 | 13 18 | 5 | 4 | 3 | 12 19 | 6 | 1 | 2 | 11 20 | 7 | 8 | 9 | 10 21 | 22 | 23---> ...
Meine Idee war die Erstellung der Spirale bis zum Punkt 347991 zu simulieren. Also einfach die Spirale solange zu laufen bis man angekommen ist und die Koordinaten dann addieren. Das hat zwar funktioniert, war aber eine absolute Katastrophe es zu programmieren. Den Quellcode erspare ich euch an dieser Stelle einfach mal. Mein Mitbewohner hat für dieses Rätsel ein weitaus besseren Weg gefunden. Er läuft auf der Diagonalen solange nach unten bis er einen Punkt erreicht an dem der Eckpunkt größer als die gesuchte Zahl ist. Von diesem Punkt aus läuft er dann soweit die Spirale hinunter bis er die gesuchte Zahl erreicht. Mein Programm dauert 407 Millisekunden, seins nur 9. Hieran sieht man anschaulich den Unterschied zwischen einem performanten und einem sehr stumpfen Weg.
17 | 16 | 15 | 14 | 13
18 | 5 | 4 | 3 | 12
19 | 6 | 1 | 2 | 11
20 | 7 | 8 | 9 | 10
21 | 22 | 23 | 24 | 25
45
|-->...
Tag 4 High-Entropy Passphrases
Am nächsten Tag drehte sich alles um Passwörter und Passphrasen. Denn es galt herauszufinden wie viele aus einer Liste von Passphrasen gültig waren. Im ersten Teil des Rätsel ging es nur darum die Passphrasen auszusortieren die eine doppeltes Wort enthielten wie zum Beispiel: aa bb cc dd aa (hier ist das aa doppelt) Ich speichere dazu sämtliche Zeilen in ein String[] und iteriere darüber. Gleichzeitig sumiere ich einen Zähler auf der die gültigen Passphrasen zählt.
private boolean isPhassphraseValid(String[] words) {
for (int i = 0; i < words.length - 1; i++) {
String word = words[i];
for (int j = i + 1; j < words.length; j++) {
if ((word.equals(words[j]))) {
return false;
}
}
}
return true;
}Im zweiten Teil des Rätsel ging es um Anagramme. Die neue Passwordrichtlinie war das keine Anagramme in den Passphrasen erlaubt waren. Zum Beispiel:
- abcde fghij is a valid passphrase.
- abcde xyz ecdab is not valid
Dazu wird die Methode isPassphraseValid ein wenig angepasst indem in der IF-Anweisung die boolsche Bedingung um einen weiteren Teil erweitert wird: || isAnagram(word, words[j]) Die Methode prüft dabei mit simplem Mitteln ob die beiden Wörter ein Anagram voneinander sind.
private boolean isAnagram(String leftWord, String rightWord) {
char[] left = leftWord.toCharArray();
char[] right = rightWord.toCharArray();
Arrays.sort(left);
Arrays.sort(right);
return Arrays.equals(left,right);
}Tag 5 A Maze of Twisty Trampolines, All Alike
Am fünften Tag wurde ich mit dem bisher einfachsten Rätsel konfrontiert welches ich um 5 Uhr morgens innerhalb von 10 Minuten lösen konnte. Ich konnte nicht mehr schlafen und wenn man dann schon wach ist, warum dann nicht das Tagesrätsel lösen.
Der Input war eine lange Reihe an Zahlen: 0 3 0 1 -3
Der Algorithmus sollte jedesmal an die Position des Wertes innerhalb eines Arrays oder wie bei mir einer Arrayliste springen. Dabei sollte nachdem Sprung der Wert um eins erhöht werden. Das Ziel des Rätsels war es die Anzahl der Sprünge zu zählen die benötigt werden um das Labyrinth zu verlassen.
Die Variable "steps" ist hierbei eine globale Variable welche bei jedem Sprung um 1 erhöht wird.
private void runTheMaze(){
int offset;
int index =0;
while(index < AllNumbers.size()){
offset = AllNumbers.get(index);
AllNumbers.set(index,AllNumbers.get(index)+1);
index +=offset;
steps++;
}
}Im zweiten Teil des Rätsels sollte beim Sprung noch darauf geachtet werden ob der Wert über oder gleich 3 ist. Bei einer 3 oder höher wird der Wert um 1 verringert ansonsten erhöht. Ich passte meine erste Methode daher etwas an und schon war ich fertig. Die Antwort für den Teil Zwei war 24315397 Sprünge. Das sind eine ganze Menge.
private void runTheMazePartTwo(){
int offset = 0;
int index =0;
while((index < AllNumbers.size())){
offset = AllNumbers.get(index);
AllNumbers.set(index, (offset>=3 ? AllNumbers.get(index)-1 : AllNumbers.get(index)+1));
index +=offset;
steps++;
}
}Tja und das waren die Tage 1 bis 5. Wir sehen uns am Tag 10 wieder. Bis dahin Viel Spaß beim Programmieren :)