Festplattenfragmente

Advent of Code 2024 Tag 9

Teil 1

Ein dreiphasiger Handschuh. Spannend!??

Die Phasen, wie ich sie sehe, im Einzelnen:

1. Den Speicher als Liste darstellen
2. Werte vom Ende zum Anfang verschieben
3. Gehen Sie die Linie entlang, um die Prüfsumme zu berechnen

Nichts davon fühlt sich besonders schwierig an.

Und einiges davon scheint tatsächlich eine weitere lustige algorithmische Herausforderung zu sein!

Erstellen der Liste

Ich möchte das ändern:

12345

Dazu:

0..111....22222

Ich muss Folgendes berücksichtigen:

• Verwenden einer Schleife
• Prüfung auf gerade und ungerade Indizes
• Erhöhen eines Werts um 1, beginnend bei 0

Hier ist mein Festplatten-Generierungsalgorithmus:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

Funktioniert wie ein Zauber!

Werte vom Ende zum Anfang verschieben

Was dies einfacher machen würde, wäre eine Liste aller leeren Stellen auf der Festplatte.

Ich muss meinen Algorithmus an zwei Stellen aktualisieren:

1. Eine neue Variable: let empty = []
2. Eine neue Aktion nach dem Einfügen eines .: empty.push(disk.length - 1)

Ein Test am Beispiel zeigt die erwarteten Indexzahlen von jedem .!

Dies ist die Liste, die ich durchlaufen werde, während ich Werte vom Ende der Liste zum Anfang und weiter verschiebe.

Aber warte.

Das könnte schwieriger sein, als ich dachte.

Woher weiß ich, wann ich aufhören muss, Werte zu verschieben?

• Muss ich die Liste der leeren Indizes durchlaufen? Wann sollte ich aufhören?
• Muss ich rückwärts durch die Festplatten iterieren? Wann sollte ich aufhören?

Eine Offenbarung: die magische Zahl 10

Dies ist der letzte Zustand des kurzen Beispiels:

022111222......

Und zum ersten Beispiel:

0099811188827773336446555566..............

Das bedeutet, dass es einen Punkt gibt, an dem sich alle Ausweise auf der linken und alle Leerzeichen auf der rechten Seite befinden.

Wie würde ich diesen Status überprüfen?

Geben Sie ein: die Zahl 10.

Die Anzahl der zusammenhängenden Leerräume wird niemals höher als 9 sein.

Wenn ich also auf einen leeren Bereich stoße, schaue ich 9 Bereiche nach vorne (oder bis zum Ende der Festplattenliste) und sehe alle leeren Bereiche, dann weiß ich, dass ich mit der Fragmentierung fertig bin.

Ich glaube, ich weiß, wie man den Rest dieses Algorithmus schreibt!

Ich schreibe meinen Fragmentierungsalgorithmus

Hier ist der Arbeitsalgorithmus:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

Wie es funktioniert:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

Zum Glück sehe ich die gleiche Ausgabe wie in beiden Beispielen!

Berechnung der Prüfsumme

Das scheint ziemlich einfach und unkompliziert zu sein:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

Im Pseudocode:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

Erfolg! Es generiert die richtige Antwort für die Beispieleingabe!

Wird das auch für meine Rätseleingabe gelten?

...

JA!!!

Woohoo!!!

Was wird die Wendung für Teil Zwei sein? Eine leichte Regelanpassung oder eine Größenherausforderung?

Teil 2

Eine interessante Wendung

Waren Teile. Jetzt ganz.

Dies erfordert definitiv eine Anpassung meines Algorithmus.

Wahrscheinlich robustere Verfolgung der Größe von Lücken und Blöcken.

Ich arbeite an meiner ersten Strategie

Ich hat nachverfolgt, wo sich jede Leerstelle befand.

Ich denke, ich muss nachverfolgen, wo und wie groß jeder Leerraum ist.

Wie würde das aussehen?

Kratz das. Vielleicht neue Strategie.

Am ersten Beispiel:

12345

Die Dateiblockgrößen sind ungerade Zahlen:

0..111....22222

Die leeren Zellengrößen sind die geraden Zahlen:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

Beginnend am Ende der ungeraden Zahlen und am Anfang der geraden Zahlen suche ich nach einer geraden Zahl, die größer oder gleich der ungeraden Zahl ist:

022111222......

Ich finde sofort eine Übereinstimmung.

Als Ergebnis:

• Die ungerade Zahl bewegt sich
• Die gerade Zahl nimmt ab
• Aber jetzt haben die beiden ungeraden Zahlen keine Lücke mehr
• Und ich habe den zweiten 2s-Ausweis verloren

0099811188827773336446555566..............

Diese Strategie wird definitiv nicht funktionieren.

Ich arbeite an meiner zweiten Strategie

Mir gefallen die Auswirkungen auf die Leistung nicht.

Aber ich vertraue darauf, dass es funktionieren wird ... solange es nicht mehr läuft.

Für jede Nummer in der Festplatteneingabe werde ich als Listenelement Folgendes aufzeichnen:

1. Dateiblock oder leere Zelle
2. Länge
3. ID

Als Beispiel:

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

Wird:

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

Ew, lass uns das aufräumen:

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

Ich werde Lücken von Dateiblöcken anhand des Datentyps unterscheiden.

Das Verschieben von Dateiblöcken sieht in einer geänderten Beispieleingabe so aus:

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

Dies umfasst jeweils 100.000 Iterationen:

• Suche nach Artikeln in einer großen Auswahl
• Ein Array direkt mutieren

Beides sind sehr kostspielige Aufgaben.

Aber es ist die einzige Möglichkeit, die mir einfällt, um dieses Rätsel zu lösen.

Das soll also mein Ansatz sein.

Kodifizierung meiner Strategie

Hier ist das JavaScript, das mir die obige Datenarchitektur ermöglicht:

2333133121414131402

Wie beginne und beende ich meine Hauptschleife?

Versuchen Sie, jede Datei genau einmal in der Reihenfolge absteigender Datei-ID-Nummer zu verschieben, beginnend mit der Datei mit der höchsten Datei-ID-Nummer

Scheint so, als würde die Bewegung von hinten nach vorne das tun, was ich brauche.

Dieses for-Schleifengerüst sollte funktionieren:

[2,4,1,4,2,5,5,3,5,2]

Suchen, verschieben und ersetzen

[3,3,3,1,1,1,1,1,0]

Diese zweite Klausel im if war mein letzter Debug. Die niedrigsten IDs wurden zu früh eingestellt.

Codierung eines Festplattendruckers

Mir wurde klar, dass ich die Fragmentierung meiner Festplatte nahezu in Echtzeit miterleben musste. Zumindest ein Protokoll davon, wie in der Beispiel-Komplettlösung.

Zum Glück war das Codieren nicht schwierig. Nur der Teil, in dem ich zwei Indizes verwechselt habe und eine wirklich seltsame Ausgabe gesehen habe:

12345

• Ich baue eine Schnur auf
• Basierend auf der Art des Elements auf der Festplatte
• So oder so erstelle ich ein Array und fülle es entweder mit .s oder der Block-ID

Es funktioniert großartig! Ich konnte sehen, wohin Dateien verschoben wurden, und Fehler in meinem Code viel einfacher beheben!

Mir gefällt, was ich sehe

0..111....22222

Es sieht so aus, als ob mein Algorithmus zum Verschieben von Dateien funktioniert!

Der letzte Schritt besteht darin, die neue Prüfsumme zu berechnen.

Zum Schluss noch mehr Mathematik

Durch eine doppelte Reduzierung:

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• Die erste Reduzierung bringt mir ein verteiltes Array von IDs und .s
• Die zweite Reduzierung führt die entsprechende Berechnung durch, wenn es sich bei dem Element um eine ID handelt, und keine Berechnung, wenn es sich um eine handelt.

Funktioniert es?

Auf der Beispiel-Puzzle-Eingabe? JA!

Zu meinem Rätsel-Input?

...

YEEESSSSSS!

Wow. Ich bin überrascht. Die Zahl, die ich für Teil 2 eingereicht habe, ist fast identisch mit Teil 1. Ich dachte, sie wäre höher.

Ich bin nicht daran interessiert, weitere Nachforschungen anzustellen.

Ich nehme lieber meine zwei hart verdienten goldenen Sterne und gehe zu Tag 10.

Byeeeee Tag 9!

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