Najmniej zapisu na dysku w celu defragmentacji wielu plików

18

Wprowadzenie

Dysk jest liniową pojemnik z bloków indeksowanych 0przez size-1.

Plik to nazwana lista indeksów bloków używanych przez ten plik.

Przykładowy system plików jest wyrażony w następujący sposób:

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

„Dysk ma 15 bloków, pierwszym blokiem pliku ALPHA jest blok dysku o indeksie 3 ...”

Mapę dysku można narysować w następujący sposób:

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

Dysk uważa się za zdefragmentowany, gdy wszystkie znajdujące się na nim pliki są przechowywane w sposób ciągły.

TWÓJ CEL:

Emituj najkrótszą sekwencję legalnych ruchów, która zdefragmentuje dany dysk.

Legalne ruchy

Ruch zawiera trzy informacje: nazwę pliku, indeks bloku w pliku, który ma zostać przeniesiony, oraz indeks bloku dysku, do którego się przenosi.

Na przykład

ALPHA:1>4

„Przenieś blok 1 pliku ALPHA do bloku 4 dysku.”

Po tym przeniesieniu przykładowy system plików jest teraz taki

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

Poprzednio zamieszkały blok dysku jest domyślnie usuwany. Odpowiednio można to postrzegać jako zamianę dwóch bloków na dysku, ale jeden z bloków w zamianie musi być pusty .

Dane nie mogą zostać zniszczone. Pliki nie mogą współużytkować bloków na żadnym etapie, a ruchy muszą znajdować się w zasięgu dysku. Następujące ruchy są nielegalne : ALPHA:0>10(własność BETA), ALPHA:3>0(brak takiego bloku w ALPHA), ALPHA:0>-1(brak takiego indeksu dysku), ALPHA:0>15(indeks dysku zbyt duży)

Przykład 1

Rozwiązanie powyższego przykładu w całości.

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

Pliki nie muszą przylegać do rozwiązania, tylko ciągłe w sobie.

Przykład 2

Oto bardziej ograniczony przypadek

Wejście:

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

Wynik:

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

Postęp tego systemu plików jest następujący:

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 |

Alternatywnym sposobem na to by przez oszukiwać, aby C:2>9następnie doprowadzić Adół krok, a następnie przynieść Cdół krok, potem zrobić C:2>5, ale to nie byłoby to rozwiązanie prawne, ponieważ zawiera więcej ruchów niż alternatywa .

Reprezentacja

Możesz użyć dowolnej reprezentacji danych wejściowych, o ile jest ona dość zbliżona do podstawowego ciągu. W zależności od języka dane wejściowe do pierwszego przykładu można zapisać jako

"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

Podobnie, wyjście może być tym, co jest wygodne dla twojego języka, ponieważ dziennik jest drukowany, czytelny dla człowieka i reprezentuje uporządkowaną listę legalnych ruchów, przy czym każdy ruch jest opisany przez 1) nazwa-pliku, 2) indeks-bloku-pliku , 3) indeks nowego bloku dysku

"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

Wymagania

Twój kod musi akceptować dysk o dowolnym rozmiarze oraz dowolną liczbę i rozmiar plików.

Dane wejściowe, które nie opisują początkowych stanów systemu plików, mogą prowadzić do nieokreślonego zachowania.

Twój kod musi generować najkrótsze ruchy , dla każdego dobrze zdefiniowanego wejścia.

Wszystkie wykonywane ruchy muszą być legalne; system plików musi znajdować się w poprawnym stanie po zastosowaniu każdego wykonanego kroku.

Twój kod musi kończyć się dla wszystkich poprawnych danych wejściowych, tj. Nigdy nie powinien utknąć w pętli, system plików powinien być w wyraźnie nowym stanie po zastosowaniu każdego ruchu.

Jeśli istnieje więcej niż jedno najkrótsze rozwiązanie, każde można wybrać jako prawidłowe.

Najkrótszy kod wygrywa. Proszę zamieścić co najmniej jedno nowe nietypowe przykładowe wejście i jego wynik wraz z kodem.

code-golf combinatorics fewest-operations spraff
źródło
Jak ustalilibyśmy, jak długo trwa „najkrótsza sekwencja” dla dowolnego dysku? (Pytanie, ponieważ jeśli odpowiedź A mówi, że najkrótszy to 6 ruchów, a odpowiedź B mówi, że najkrótszy to 5, to czy odpowiedź A następnie zostaje zdyskwalifikowana?)
ASCIIThenANSI
W razie potrzeby szerokie wyszukiwanie może dostarczyć rozwiązanie referencyjne.
spraff
2
Prawdopodobnie działałoby to lepiej jako wyzwanie [golf atomowy]. W ten sposób uzyskasz więcej odpowiedzi. Zamiast najkrótszego kodu zwycięzcą byłaby odpowiedź przy najmniejszej liczbie zapisów na dysku.
mbomb007,

Odpowiedzi:

1

Python 3 , 295 bajtów

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

Wypróbuj online!

Kolejny przypadek testowy

Wejście:
   7 ALEF = 6,4,0 BET = 5,1 GIMEL = 3

Początkowy stan dysku:
   A2 B1 __ G0 A1 B0 A0

Rozwiązanie:
   ALEF: 2> 2
   ALEF: 0> 0
   ZAKŁAD: 1> 6
   ALEF: 1> 1

Wizualizowane rozwiązanie:
   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

Wersja bez golfa .

Jonathan Frech
źródło