Fragments de disque

Avènement du Code 2024 Jour 9

Partie 1

Un gant en trois phases. Passionnant!??

Les phases telles que je les vois énoncées :

1. Représenter la mémoire sous forme de liste
2. Déplacer les valeurs de la fin au début
3. Parcourir la ligne pour calculer la somme de contrôle

Rien de tout cela ne semble particulièrement difficile.

Et certains d'entre eux semblent être encore un autre défi algorithmique amusant !

Faire la liste

Je veux transformer ceci :

12345

Dans ceci :

0..111....22222

Je dois considérer :

• Utiliser une boucle
• Vérification des indices pairs et impairs
• Incrémenter une valeur de 1, en partant de 0

Voici mon algorithme de génération de disque :

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++
    }
}

Fonctionne à merveille !

Déplacer les valeurs de la fin au début

Ce qui rendrait cela plus facile, c'est d'avoir une liste de tous les emplacements vides sur le disque.

Je dois mettre à jour mon algorithme à deux endroits :

1. Une nouvelle variable : laisser vide = []
2. Une nouvelle action après l'insertion d'un .: empty.push(disk.length - 1)

Le tester sur l'exemple montre les numéros d'index attendus de chacun.!

C'est la liste que je vais parcourir en déplaçant les valeurs de la fin de la liste au début et au-delà.

Mais attendez.

Cela pourrait être plus difficile que je ne le pensais.

Comment saurai-je quand arrêter d'essayer de déplacer des valeurs ?

• Est-ce que je parcourt la liste des index vides ? Quand dois-je arrêter ?
• Est-ce que je parcourt les disques en arrière ? Quand dois-je arrêter ?

Une révélation : le chiffre magique 10

Voici le dernier état du court exemple :

022111222......

Et du premier exemple :

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

Ce qui signifie qu'il arrive un moment où tous les identifiants sont à gauche et tous les espaces vides sont à droite.

Comment puis-je vérifier cet état ?

Entrez : le chiffre 10.

Le nombre d'espaces vides contigus ne sera jamais supérieur à 9.

Donc, si je tombe sur un espace vide, que j'attends 9 espaces (ou la fin de la liste des disques) et que je vois tous les espaces vides, je sais que j'aurai fini de fragmenter.

Je pense savoir comment écrire le reste de cet algorithme !

Écrire mon algorithme de fragmentation

Voici l'algorithme de travail :

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;
    }
}

Comment ça marche :

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

Heureusement, je vois le même résultat que dans les deux exemples !

Calcul de la somme de contrôle

Cela semble assez simple et direct :

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

En 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

Succès ! Il génère la réponse correcte pour l'exemple d'entrée !

Est-ce que cela fera la même chose pour ma saisie de puzzle ?

...

OUI !!!

Woohoo!!!

Quelle sera la tournure de la deuxième partie ? Un léger ajustement des règles ou un défi d’échelle ?

Partie 2

Une tournure intéressante

Il y avait des pièces. Maintenant entier.

Cela nécessitera certainement quelques ajustements de mon algorithme.

Suivi probablement plus robuste de la taille des espaces et des blocs.

Travailler sur ma première stratégie

Je suivi où se trouvait chaque vide.

Je pense que je dois savoir où - et quelle est la taille - de chaque vide.

À quoi cela ressemblerait-il ?

Grattez ça. Peut-être une nouvelle stratégie.

En utilisant le premier exemple :

12345

Les tailles des blocs de fichiers sont les nombres impairs :

0..111....22222

Les tailles de cellules vides sont les nombres pairs :

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++
    }
}

En partant de la fin des nombres impairs et du début des nombres pairs, je recherche un nombre pair supérieur ou égal au nombre impair :

022111222......

Je trouve immédiatement une correspondance.

En conséquence :

• Le nombre impair bouge
• Le nombre pair diminue
• Mais maintenant les deux nombres impairs n'ont plus d'écart
• Et j'ai perdu la deuxième pièce d'identité 2s

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

Cette stratégie ne fonctionnera certainement pas.

Travailler sur ma deuxième stratégie

Je n'aime pas les implications de celui-ci en termes de performances.

Mais j'espère que cela fonctionnera... tant qu'il aura fini de fonctionner.

Pour chaque numéro dans l'entrée disque, j'enregistrerai comme élément de liste :

1. Bloc de fichiers ou cellule vide
2. Longueur
3. Pièce d'identité

À titre d'exemple :

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;
    }
}

Deviendra :

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, nettoyons ça :

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

Je distinguerai les lacunes des blocs de fichiers en fonction du type de données.

Le déplacement de blocs de fichiers ressemblera à ceci dans un exemple d'entrée modifié :

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

Cela impliquera dans chaque 100 000 itérations :

• Recherche d'éléments dans un large éventail
• Muter un tableau sur place

Les deux sont des tâches très coûteuses.

Mais c'est la seule façon à laquelle je peux penser pour résoudre cette énigme.

Donc, ce sera mon approche.

Codifier ma stratégie

Voici le JavaScript qui me permet d'obtenir l'architecture de données ci-dessus :

2333133121414131402

Comment vais-je commencer et terminer ma boucle principale ?

Essayez de déplacer chaque fichier exactement une fois par ordre décroissant de numéro d'identification de fichier en commençant par le fichier avec le numéro d'identification de fichier le plus élevé

On dirait que passer de l'arrière vers l'avant fera ce dont j'ai besoin.

Ce squelette de boucle for devrait fonctionner :

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

Rechercher, déplacer et remplacer

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

Cette deuxième clause du if était mon dernier débogage. Cela mettait les identifiants les plus bas trop tôt.

Codage d'une imprimante à disque

J'ai réalisé que je devais voir mon disque se fragmenter en temps quasi réel. Au moins un journal, comme dans l'exemple de procédure pas à pas.

Heureusement, le coder n’a pas été difficile. Juste la partie où j'ai mélangé deux indices et vu un résultat vraiment bizarre :

12345

• Je construis une chaîne
• Basé sur le type d'élément sur le disque
• Quoi qu'il en soit, je crée un tableau et le remplis avec .s ou l'ID du bloc

Ça marche très bien ! Je pouvais voir où les fichiers étaient déplacés et dépanner mon code beaucoup plus facilement !

J'aime ce que je vois

0..111....22222

On dirait que mon algorithme de déplacement de fichiers fonctionne !

La dernière étape consiste à calculer la nouvelle somme de contrôle.

Enfin, plus de maths

En guise de double réduction :

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++
    }
}

• La première réduction me donne un tableau étendu d'identifiants et de .s
• La deuxième réduction effectue les calculs appropriés lorsque l'élément est un identifiant et aucun calcul lorsqu'il s'agit d'un .

Est-ce que ça marche ?

Sur l'exemple de saisie de puzzle ? OUI !

Sur ma contribution au puzzle ?

...

OUIESSSSSS !

Wow. Je suis surpris. Le nombre que j'ai soumis pour la partie 2 est presque identique à celui de la partie 1. Je pensais qu'il serait plus élevé.

Je ne suis pas intéressé à enquêter davantage.

Je préfère prendre mes deux étoiles d'or durement gagnées et marcher jusqu'au jour 10.

Au revoir, jour 9 !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!