Nur wenige Schreibvorgänge können mehrere Dateien defragmentieren

18

Einführung

Eine Festplatte ist ein linearer Behälter mit Blöcken indexierten 0durch size-1.

Eine Datei ist eine benannte Liste von Blockindizes, die von dieser Datei verwendet werden.

Ein Beispiel für ein Dateisystem sieht folgendermaßen aus:

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

"Die Platte hat 15 Blöcke, der erste Block der Datei ALPHA ist der Plattenblock bei Index 3 ..."

Die Disk Map könnte folgendermaßen gezeichnet werden:

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

Eine Festplatte gilt als defragmentiert, wenn alle darin enthaltenen Dateien zusammenhängend gespeichert sind.

DEIN ZIEL:

Senden Sie eine kürzeste Sequenz legaler Aktionen aus, die eine bestimmte Festplatte defragmentieren.

Legale Schritte

Eine Verschiebung enthält drei Informationen: den Namen einer Datei, einen Index des Blocks in der zu verschiebenden Datei und den Index des Plattenblocks, zu dem sie verschoben wird .

Beispielsweise

ALPHA:1>4

"Verschieben Sie Block 1 der Datei ALPHA in Block 4 der Festplatte."

Nach dieser Verschiebung lautet das Beispieldateisystem nun "this"

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

Der zuvor belegte Plattenblock wird implizit gelöscht. Sie können dies auch so anzeigen, dass zwei Blöcke auf der Festplatte vertauscht werden, aber einer der Blöcke im Swap muss leer sein .

Daten dürfen nicht vernichtet werden. Dateien können zu keinem Zeitpunkt Blöcke gemeinsam nutzen, und Bewegungen müssen innerhalb der Reichweite der Festplatte liegen. Die folgenden Bewegungen sind illegal : ALPHA:0>10(im Besitz von BETA), ALPHA:3>0(kein solcher Block in ALPHA), ALPHA:0>-1(kein solcher Festplattenindex), ALPHA:0>15(Festplattenindex zu groß)

Beispiel 1

Lösen Sie das obige Beispiel vollständig.

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

Dateien müssen in der Lösung nicht nebeneinander liegen, sondern müssen nur in sich fortlaufend sein.

Beispiel 2

Hier ist ein eingeschränkter Fall

Eingang:

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

Ausgabe:

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

Der Fortschritt dieses Dateisystems ist:

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 |

Eine alternative Möglichkeit , dies würde zu defragmentieren von bis C:2>9dann brachte Aeinen Schritt nach unten, dann brachte Ceinen Schritt nach unten, dann tun , C:2>5aber dies wäre eine rechtliche Lösung nicht sein , weil es mehr bewegt als die Alternative enthält .

Darstellung

Sie können eine beliebige Darstellung für die Eingabe verwenden, sofern diese einer Basiszeichenfolge einigermaßen nahe kommt. Abhängig von Ihrer Sprache wird die Eingabe für das erste Beispiel möglicherweise als notiert

"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

In ähnlicher Weise kann die Ausgabe das sein, was für Ihre Sprache praktisch ist, da das Protokoll gedruckt und für den Menschen lesbar ist und eine geordnete Liste zulässiger Schritte darstellt, wobei jeder Schritt durch 1) Dateiname, 2) Dateiblockindex beschrieben wird , 3) New-Disk-Block-Index

"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

Bedarf

Ihr Code muss Datenträger beliebiger Größe sowie eine beliebige Anzahl und Größe von Dateien akzeptieren.

Eingaben, die keine gültigen Dateisystem-Ausgangszustände beschreiben, können zu undefiniertem Verhalten führen.

Ihr Code muss für jede genau definierte Eingabe eine Lösung für kürzeste Bewegungen liefern .

Alle Spielzüge, die Sie produzieren, müssen legal sein. Das Dateisystem muss sich nach jedem Schritt, den Sie ausführen, in einem gültigen Zustand befinden.

Ihr Code muss für alle gültigen Eingaben enden, dh er sollte niemals in einer Schleife hängen bleiben, das Dateisystem sollte sich nach jedem Zug in einem deutlich neuen Zustand befinden.

Wenn es mehr als eine kürzeste Lösung gibt, kann jede als gültig ausgewählt werden.

Kürzester Code gewinnt. Bitte posten Sie mindestens eine neue nichttriviale Beispieleingabe und deren Ausgabe mit Ihrem Code.

code-golf combinatorics fewest-operations spraff
quelle
Wie würden wir herausfinden, wie lange die "kürzeste Sequenz" für eine beliebige Platte ist? (Fragen, denn wenn Antwort A sagt, dass der kürzeste
Zug
Bei Bedarf bietet die Breitensuche eine Referenzlösung.
Spraff
2
Dies würde wahrscheinlich besser als [Atomic-Code-Golf] -Herausforderung funktionieren. Auf diese Weise erhalten Sie mehr Antworten. Anstelle des kürzesten Codes wäre der Gewinner die Antwort mit den wenigsten Schreibvorgängen.
mbomb007

Antworten:

1

Python 3 , 295 Bytes

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

Probieren Sie es online!

Ein weiterer Testfall

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

Anfangszustand der Festplatte:
   A2 B1 __ G0 A1 B0 A0

Lösung:
   ALEF: 2> 2
   ALEF: 0> 0
   BET: 1> 6
   ALEF: 1> 1

Visualisierte Lösung:
   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

Ungolfed-Version .

Jonathan Frech
quelle