Tingeln

Advent of Code 2024 Tag 10

Teil 1

Kurzer Schrecken, dann Aufregung

Normalerweise überfliege ich eine Seite, bevor ich alles genau lese.

Heute habe ich Folgendes gesehen:

• Ein Gitter
• und was wie Wege aussah

Und ich befürchtete, dass dies eine weitere Herausforderung auf dem kürzesten Weg sein würde.

Dann habe ich es gelesen.

Und atmete erleichtert auf...zumindest für Teil 1.

Ich muss alle gültigen Pfade finden.

Das...kann ich schaffen!

Beginnen Sie bei 0

Ich muss alle Nullen finden:

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0: gefunden!

Versuchen Sie, sich in Schritten von 1 zu bewegen

Ab jeder 0 besteht ein gültiger Pfad aus neun Schritten, wobei jede Zahl um eins größer als die letzte ist und bei 9 endet.

Das klingt nach einem Job für die Rekursion.

Ich brauche einen Basisfall:

1. Die aktuelle Zahl ist nicht genau um eins größer als die vorherige
2. Aktuelle Nummer ist 9

So sollte mein Algorithmus funktionieren:

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

Nachdem ich es jetzt geschrieben habe, fehlte mir der Teil, der das Verzeichnis der gültigen Endkoordinaten verfolgt.

Ich hatte einige Zeit damit zu kämpfen.

Ich bekam immer wieder eine Fehlermeldung, die mich fälschlicherweise glauben ließ, ich könne kein Set oder gar ein Array übergeben.

Aber zum Glück habe ich einfach vergessen, es in weitere Aufrufe der rekursiven Funktion zu übergeben.

Hier ist mein funktionierender rekursiver Algorithmus:

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

Da ich mit den Koordinaten 0 beginnen muss, verwende ich beim ersten Aufruf -1:

pathFinder(-1, zeroCoordinate, matches)

Um schließlich die richtige Punktzahl zu erhalten, iteriere ich durch jede Null, erzeuge den eindeutigen Satz von Ziel-Neunen, behalte die Größen der Sätze bei und fasse sie zusammen:

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

Schnelle Tests, schnelle Ergebnisse

Es wurde die richtige Antwort für die kleine Beispieleingabe generiert.

Und für die größere Beispieleingabe.

Und...

...für meinen Rätsel-Input!!!

Woohoo!!!

Womit wird mich Teil 2 herausfordern?

Teil 2

Ähm, das scheint zu einfach zu sein

Ist es möglich, dass die Art und Weise, wie ich meinen Algorithmus in Teil 1 geschrieben habe, bedeutet, dass nur ein paar kleine Änderungen erforderlich sind, um die richtige Antwort zu erhalten?

Zählen Sie sie alle!

Im Moment füge ich jede gültige 9 zu einem Satz hinzu.

Für Teil 2 muss ich wohl nur für jede gültige 9 einen Zähler erhöhen.

Einen Versuch wert!

Ändern Sie „Set“ in „Array“ und voilà!

Richtige Antwort für das Beispiel.

Richtige Antwort für meine Rätseleingabe.

Wow. Wow. Wow.

Weiter zum nächsten Tag...der wahrscheinlich viel schwieriger wird.

Das obige ist der detaillierte Inhalt vonTingeln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!