Wache Gallivant

Advent of Code 2024 Tag 6

Teil 1

Eine sehr bekannte Art von Rätsel

• 2D-Raster
• Überall Hindernisse
• Verfolgen Sie einen Pfad
• Zählen Sie die einzelnen besuchten Kacheln

Lasst uns loslegen!

Schritt für Schritt

Raster analysieren:

let grid = input.split('\n').map(el => el.split(''))

Identifizieren Sie den Startort der Wache und ersetzen Sie ihn durch eine leere Kachel:

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Erstellen eines Objekts zur Verfolgung der aktuellen Rotation des Wächters:

let facing = [
  [-1,0],
  [0,1],
  [1,0],
  [0,-1]
]

• Die Wache ist zunächst nach Norden gerichtet, sodass nachfolgende Bewegungen den Besuch von Reihen mit geringeren Indizes erfordern
• Bei jedem Hindernis muss der Wachmann nach rechts abbiegen
• Das würde dazu führen, dass sie nach Osten zeigt, sodass nachfolgende Bewegungen den Besuch von Spalten mit größeren Indizes erfordern
• Jedes Mal, wenn die nächste Zelle ein Hindernis darstellt, zieht mein Algorithmus das erste Element aus der Liste und verschiebt es nach hinten

Verfolgung besuchter Zellen:

let visited = new Set()

Bei jedem Zug werde ich versuchen, die stringifizierten Koordinaten zu diesem Set() hinzuzufügen.

Die Wache bewegen:

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let oldDirection = facing.shift();
      facing.push(oldDirection);
    }
  } else {
    break;
  }
}

Eine Erklärung:

Keep going until manually broken out of
  Add the current coordinate to the tracked list
  Record the next location to visit
  If it is within the grid
    If it is empty cell
      Move the guard
    Else If it is an obstacle
      Rotate the guard
  Else
    Break out of the loop

Dieser Algorithmus generiert erfolgreich eine Liste besuchter Zellen mit 41 für die Beispieleingabe!

Wird es die richtige Antwort für meine Rätseleingabe generieren?

Ja!!!

Super.

Weiter zu Teil 2!

Teil 2

Ich habe das irgendwie kommen sehen und hatte Angst davor

Der alte, prüfen Sie jede mögliche Option für ein gültiges Rätsel.

Meine große Frage beim Lesen ist:

• Wie erkenne ich, wenn der Wachmann in eine Schleife gerät?

Aber ich glaube ich weiß:

• Ich verfolge sowohl die Blickrichtung als auch die Koordinaten
• Wenn die Liste eine Kopie der nächsten hinzugefügten Datei enthält, beginnt gleich eine Schleife

Zeit, die Dinge viel komplizierter zu machen!

Durchlaufen Sie jede Zelle, um alle Schleifen zu finden

Zuerst möchte ich eine Liste aller Zellen mit einem . erstellen, mit Ausnahme der Startzelle des Wächters:

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Dann verwenden Sie eine Reduzierung, um jedes zu durchlaufen. im Raster, Kopieren des Rasters und der ursprünglichen Schutzposition, Verschieben großer Teile des ursprünglichen Codes innerhalb der Reduzierung, Erweitern der while-Schleife, um eine Bedingung für die verfolgte Koordinaten- und Rotationsliste mit einer Instanz des aktuellen Status einzuschließen:

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

Es ist eine Menge.

Aber es funktioniert! Zumindest bei der Beispieleingabe.

Wird es bei mir funktionieren???

Nun... es hat 30 Sekunden gedauert, bis es lief.

Aber...es hat eine Antwort generiert!

Und es ist das...

RICHTIGE ANTWORT!!!

Woohoo!!!

Teil 1 war ein Kinderspiel. Und Teil 2 war ein harter, aber willkommener Maßstabsschub.

Zwei weitere goldene Sterne im Beutel!

Weiter zu Tag 7.

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