Le moins d'écritures de disque pour défragmenter plusieurs fichiers

18

introduction

Un disque est un conteneur linéaire avec des blocs indexés 0par size-1.

Un fichier est une liste nommée d'index de bloc utilisés par ce fichier.

Un exemple de système de fichiers est exprimé comme ceci:

15 ALPHA=3,5 BETA=11,10,7

"Le disque a 15 blocs, le premier bloc du fichier ALPHA est le bloc de disque à l'index 3 ..."

La carte du disque pourrait être dessinée comme ceci:

Block Index  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14
Contents    |   |   |   |A0 |   |A1 |   |B2 |   |   |B1 |B0 |   |   |   |

Un disque est considéré comme défragmenté lorsque tous les fichiers qu'il contient sont stockés de manière contiguë.

TON BUT:

Emettez une séquence de mouvements légaux la plus courte qui défragmentera un disque donné.

Mouvements légaux

Un déplacement contient trois informations: le nom d'un fichier, un index du bloc dans le fichier à déplacer et l'index du bloc de disque vers lequel il se déplace.

Par exemple

ALPHA:1>4

"Déplacer le bloc 1 du fichier ALPHA vers le bloc 4 du disque."

Après ce déplacement, l'exemple de système de fichiers est maintenant

15 ALPHA=3,4 BETA=11,10,7

Block Index  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14
Contents    |   |   |   |A0 |A1 |   |   |B2 |   |   |B1 |B0 |   |   |   |

Le bloc de disque précédemment habité est implicitement effacé. De manière équivalente, vous pouvez voir cela comme l'échange de deux blocs sur le disque, mais l' un des blocs dans l'échange doit être vide .

Les données ne peuvent pas être détruites. Les fichiers ne peuvent partager des blocs à aucun stade et les mouvements doivent être à portée du disque. Les mouvements suivants sont illégaux : ALPHA:0>10(appartenant à BETA), ALPHA:3>0(aucun bloc de ce type dans ALPHA), ALPHA:0>-1(aucun index de disque de ce type), ALPHA:0>15(index de disque trop volumineux)

Exemple 1

Résolution complète de l'exemple ci-dessus.

ALPHA:0>4
BETA:0>9
BETA:2>11

Les fichiers n'ont pas besoin d'être adjacents dans la solution, ils doivent être continus en eux-mêmes.

Exemple 2

Voici un cas plus contraint

Contribution:

10 A=1,2,3 B=6,7,8 C=4,5,0

Production:

B:2>9
B:1>8
B:0>7
C:2>6

La progression de ce système de fichiers est:

Block Index  00  01  02  03  04  05  06  07  08  09
Contents    |C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 |B2 |   |
            |C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 |   |B2 |
            |C2 |A0 |A1 |A2 |C0 |C1 |BO |   |B1 |B2 |
            |C2 |A0 |A1 |A2 |C0 |C1 |   |B0 |B1 |B2 |
            |   |A0 |A1 |A2 |C0 |C1 |C2 |B0 |B1 |B2 |

Une autre façon de défragmenter cela serait de C:2>9faire Adescendre une étape, puis de faire Cdescendre une étape, puis de le faire, C:2>5mais ce ne serait pas une solution légale car elle contient plus de mouvements que l'alternative .

Représentation

Vous pouvez utiliser n'importe quelle représentation pour l'entrée tant qu'elle est raisonnablement proche d'une chaîne de base. Selon votre langue, la saisie du premier exemple peut être notée comme

"15 ALPHA=3,5 BETA=11,10,7"
[15," ","ALPHA","=",3,",",5," ","BETA","=",11,",",10,",",7]
(15,(("ALPHA",(3,5)),("BETA",(11,10,7))))
etc

De même, la sortie peut être celle qui convient à votre langue sous forme de journal tel qu'il est imprimé, lisible par l'homme et représente une liste ordonnée de mouvements légaux, chaque mouvement étant décrit par 1) nom de fichier, 2) index de bloc de fichier , 3) index-nouveau-bloc-disque

"ALPHA:1>6 BETA:2>9"
(0=>(0=>"ALPHA",1=>"1",2=>"6"), 1=>(0=>"BETA",1=>"2",2=>"9"))
["ALPHA",1,6,"BETA",2,9]
etc

Exigences

Votre code doit accepter n'importe quelle taille de disque et n'importe quel nombre et taille de fichiers.

Les entrées qui ne décrivent pas les états initiaux légaux du système de fichiers peuvent conduire à un comportement indéfini.

Votre code doit produire une solution de mouvements les plus courts , pour toute entrée bien définie.

Tous les mouvements que vous produisez doivent être légaux; le système de fichiers doit être dans un état valide après avoir appliqué chaque étape que vous produisez.

Votre code doit se terminer pour toutes les entrées valides, c'est-à-dire qu'il ne doit jamais rester bloqué dans une boucle, le système de fichiers doit être dans un état distinctement nouveau après chaque déplacement est appliqué.

Lorsqu'il existe plusieurs solutions les plus courtes, toutes peuvent être sélectionnées comme valides.

Le code le plus court gagne. Veuillez publier au moins une nouvelle entrée d'exemple non trivial et sa sortie avec votre code.

code-golf combinatorics fewest-operations vaporiser
la source
Comment pourrions-nous déterminer la longueur de la "séquence la plus courte" pour un disque arbitraire? (Demander parce que si la réponse A dit que le plus court est 6 coups et que la réponse B dit que le plus court est 5, la réponse A devient-elle alors disqualifiée?)
ASCIIThenANSI
L'étendue de la recherche en premier peut fournir une solution de référence si nécessaire.
pulvérisation
2
Cela fonctionnerait probablement mieux en tant que défi [atomic-code-golf]. Vous obtiendrez ainsi plus de réponses. Au lieu du code le plus court, le gagnant serait la réponse avec le moins d'écritures sur disque.
mbomb007

Réponses:

1

Python 3 , 295 octets

S,F=eval(input());d=[0]*S;E=enumerate
for n,P in F:
 for j,p in E(P):d[int(p)]=n,j
Z=[(d,())]
while Z:d,p=Z.pop(0);any(e and(e[0],e[1]+1)in d and(S<j+2or(e[0],e[1]+1)!=d[j+1])for j,e in E(d))or print(p).q;{d[j]or exec("D=d[:];D[j]=e;D[k]=0;Z+=(D,p+(e,j)),")for j,_ in E(d)for k,e in E(d)if d[k]}

Essayez-le en ligne!

Un autre cas de test

Contribution:
   7 ALEF = 6,4,0 BET = 5,1 GIMEL = 3

État initial du disque:
   A2 B1 __ G0 A1 B0 A0

Solution:
   ALEF: 2> 2
   ALEF: 0> 0
   BET: 1> 6
   ALEF: 1> 1

Solution visualisée:
   A2 B1 __ G0 A1 B0 A0
   __ B1 A2 G0 A1 B0 A0
   A0 B1 A2 G0 A1 B0 __
   A0 __ A2 G0 A1 B0 B1
   A0 A1 A2 G0 __ B0 B1

Version non golfée .

Jonathan Frech
la source