Ceres-Suche

Advent of Code 2024 Tag 4

Teil 1

X markiert die (Hunderte?) Punkte

Ich bin überrascht, dass es bisher noch kein wörtliches Wortsuchrätsel wie dieses gab.

Es scheint entmutigend, aber meine Strategie wird sein:

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

Wenn ich diese Strategie anhand des Beispiels betrachte, glaube ich, dass es sich um einen erfolgreichen Ansatz handelt.

Jetzt kommt der spannende Teil: das Ganze von Grund auf programmieren!

Finden Sie den Index jedes X in einem Raster ... schließlich

Zuerst muss ich die Eingabe in ein 2D-Array von Zeichen analysieren:

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

Ein Hindernis, auf das ich bei Rasterrätseln oft stoße, ist die Berücksichtigung von Out-of-Bounds-Indizes.

Wenn ich von einer Grenzzelle – oder einer Zelle nahe der Grenze – beginne und so weit in Richtung Rand gehe, werde ich irgendwann auf eine Zeile oder Spalte stoßen, die außerhalb der Grenzen liegt.

Ich habe zwei Strategien, um damit umzugehen:

1. Fügen Sie Prüfungen zu meinen Bedingungen für nicht vorhandene Zeilen oder Spalten hinzu
2. Füllen Sie das Raster mit genügend Zeilen und Spalten auf, damit keine Gefahr besteht, dass Sie außerhalb der Grenzen geraten

Für diese Herausforderung entscheide ich mich für #2.

Das Auffüllen meines Rasters mit einem 3 Zellen dicken Rand sieht so aus:

grid = grid.map(line => ['.','.','.',...line,'.','.','.'])
grid = [
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  ...grid,
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.'),
  new Array(grid[0].length).fill('.')
]

Das Beispielraster sieht jetzt so aus:

................
................
................
...MMMSXXMASM...
...MSAMXMSMSA...
...AMXSXMAAMM...
...MSAMASMSMX...
...XMASAMXAMM...
...XXAMMXXAMA...
...SMSMSASXSS...
...SAXAMASAAA...
...MAMMMXMMMM...
...MXMXAXMASX...
................
................
................

Jetzt bin ich bereit, die Koordinaten jedes X im gepolsterten Raster zu katalogisieren:

let Xs = []
for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[0].length; col++) {
    if (grid[row][col] == "X") {
      Xs.push([row, col])
    }
  }
}

Erfolg: Es wurden alle 19 X im Beispielraster gefunden!

Von jedem X aus drei Schritte in acht Richtungen gehen

Alle acht relativen Koordinaten werden als 8-Elemente-Array codiert:

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

Jetzt zum Hauptalgorithmus:

For each X
  For each direction
    Create an array that starts with X
    Do 3 times
      Move one cell in this direction
      Add the value of that cell to the array
    Check whether the concatenation of all four values is "XMAS"
      If it is, increment a tally

Und in JavaScript:

Xs.reduce((total, coord) => {
  dirs.forEach((dir) => {
    let [row, col] = coord;
    let [y, x] = dir;
    let word = ["X"];
    for (let i = 0; i < 3; i++) {
      row += y;
      col += x;
      word.push(grid[row][col]);
    }
    if (word.join("") == "XMAS") {
      total++;
    }
  });
  return total;
}, 0);

Es generiert die richtige Antwort für die Beispieleingabe!

Was passiert, wenn ich es auf meiner Puzzle-Eingabe ausführe??!!

Ich bekomme eine Zahl: ein paar tausend „WEIHNACHTEN“

Ist es die richtige Antwort?

ES IST!!!

Woohooo!!!

Ich kann es kaum erwarten zu sehen, was Teil 2 zu bieten hat...

Teil 2

Ohhh mein Gott. Das wurde etwas komplizierter. Aber machbar!

In Teil 1 habe ich nach Xs gesucht.

Jetzt suche ich Frau

In Teil 1 habe ich Buchstaben in einer geraden Linie aufgezeichnet, um ein Wort zu bilden.

Jetzt suche ich nach vier Konfigurationen einer 5-Zellen-Phrase:

M S   M M   S M   S S
 A     A     A     A
M S   S S   S M   M M

Ein einzelnes M könnte Teil mehrerer X-MASs sein.

Wenn ich jedes M überprüfe, werde ich wahrscheinlich auf mehrere Male stoßen.

Ich muss für jede Übereinstimmung ein Set() mit stringifizierten Koordinaten erstellen. Auf diese Weise berücksichtige ich eine X-MAS-Instanz nur einmal.

Plötzlich – genial! - Idee

Ich werde nicht jedes M. überprüfen

Ich überprüfe jedes A.

Und ich überprüfe die vier diagonal benachbarten Zellen im Uhrzeigersinn.

X-MAS-Matches passen zu einem dieser vier Muster:

Find the index of each X in the grid
For each X
  Check the next three letters in a straight path in each of the eight directions
  If the path ends up spelling XMAS
    Add one to a running total

`

Puh! Das wird viel weniger mühsam sein als meine ursprüngliche Idee.

Und ich sollte in der Lage sein, den größten Teil meines Teil-1-Codes wiederzuverwenden!

Kopieren-Einfügen-Optimieren

Alle As im Raster finden:
js
sei As = [];
for (let row = 0; row < grid.length; row ) {
for (let col = 0; col < grid[0].length; col ) {
if (grid[row][col] == "A") {
As.push([row, col]);
}
}
}

Festlegen der Reihenfolge der zu überprüfenden relativen Koordinaten:
js
let Adirs = [
[-1, -1],
[-1, 1],
[1, 1],
[1, -1],
];

Summierung der Übereinstimmungen:
js
let part2 = As.reduce((total, coord) => {
let im Uhrzeigersinn = Adirs.map((dir) => {
let [row, col] = coord;
sei [y, x] = dir;
return grid[row y][col x];
});
if (["MSSM", "MMSS", "SMMS", "SSMM"].includes(im Uhrzeigersinn.join(""))) {
insgesamt ;
}
Gesamtsumme zurückgeben;
}, 0);

Es generiert die richtige Antwort für die Beispieleingabe!

Nun, um meine Rätseleingabe zu überprüfen...

In der Tat!!! Die richtige Antwort!!!

Ich bin so froh, dass mir der Gedanke gekommen ist, das As anstelle des Ms. zu verwenden.

Ich bin mir sicher, dass es mir stundenlange Kopfschmerzen bei der Fehlerbehebung erspart hat.

Das war ein weiteres lustiges und leicht zugängliches Rätsel!

Ich frage mich, was Tag 5 bereithält.

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