Menos gravações de disco para desfragmentar vários arquivos

18

Introdução

Um disco é um recipiente linear com blocos indexados 0através size-1.

Um arquivo é uma lista nomeada de índices de bloco usados ​​por esse arquivo.

Um exemplo de sistema de arquivos é expresso assim:

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

"O disco possui 15 blocos, o primeiro bloco do arquivo ALPHA é o bloco de disco no índice 3 ..."

O mapa do disco pode ser desenhado assim:

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

Um disco é considerado desfragmentado quando todos os arquivos contidos nele são armazenados contiguamente.

SEU OBJETIVO:

Emita uma sequência mais curta de movimentos legais que desfragmentam um determinado disco.

Movimentos legais

Uma movimentação contém três informações: o nome de um arquivo, um índice do bloco no arquivo a ser movido e o índice do bloco de disco para o qual ele se move.

Por exemplo

ALPHA:1>4

"Mova o bloco 1 do arquivo ALPHA para o bloco 4 do disco."

Após essa mudança, o sistema de arquivos de exemplo agora é este

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

O bloco de disco previamente habitado é limpo implicitamente. Equivalentemente, você pode ver isso trocando dois blocos no disco, mas um dos blocos na troca deve estar vazio .

Os dados não podem ser destruídos. Os arquivos não podem compartilhar blocos em nenhum estágio e os movimentos devem estar dentro do alcance do disco. Os movimentos a seguir são ilegais : ALPHA:0>10(de propriedade de BETA), ALPHA:3>0(nenhum bloco no ALPHA), ALPHA:0>-1(nenhum índice de disco), ALPHA:0>15(índice de disco muito grande)

Exemplo 1

Resolvendo o exemplo acima na íntegra.

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

Os arquivos não precisam ser adjacentes à solução, apenas contínuos entre si.

Exemplo 2

Aqui está um caso mais restrito

Entrada:

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

Resultado:

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

A progressão deste sistema de arquivos é:

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 |

Uma forma alternativa para desfragmentar isso seria por que C:2>9, em seguida, trazer Apara baixo um passo, em seguida, trazer Cpara baixo um passo, em seguida, fazer C:2>5, mas isso não seria uma solução legal, pois contém mais movimentos do que a alternativa .

Representação

Você pode usar qualquer representação para a entrada, desde que ela esteja razoavelmente próxima de uma sequência básica. Dependendo do seu idioma, a entrada para o primeiro exemplo pode ser anotada como

"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

Da mesma forma, a saída pode ser conveniente para o seu idioma como log, pois é impresso, legível por humanos e representa uma lista ordenada de movimentos legais, cada movimento sendo descrito por 1) nome do arquivo, 2) índice de bloco de arquivo , 3) novo índice de bloco de disco

"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

Exigências

Seu código deve aceitar qualquer tamanho de disco e qualquer número e tamanho de arquivos.

Entradas que não descrevem estados legais legais do sistema de arquivos podem levar a um comportamento indefinido.

Seu código deve produzir uma solução de movimentos mais curtos , para qualquer entrada bem definida.

Todos os movimentos que você produz devem ser legais; o sistema de arquivos deve estar em um estado válido após a aplicação de cada etapa que você produz.

Seu código deve terminar para todas as entradas válidas, ou seja, nunca deve ficar preso em um loop, o sistema de arquivos deve estar em um estado distintamente novo após cada movimento ser aplicado.

Onde existe mais de uma solução mais curta, qualquer uma pode ser selecionada como válida.

O menor código vence. Poste pelo menos um novo exemplo de exemplo não trivial e sua saída com seu código.

code-golf combinatorics fewest-operations spraff
fonte
Como descobriríamos quanto tempo a "menor seqüência" dura para um disco arbitrário? (Perguntando porque se a resposta Uma diz que o menor é de 6 movimentos e resposta B diz que o mais curto é 5, faz resposta A, em seguida, ficar reprovado?)
ASCIIThenANSI
A primeira pesquisa de largura pode fornecer uma solução de referência, se necessário.
spraff
2
Provavelmente isso funcionaria melhor como um desafio [de código atômico-golfe]. Você obterá mais respostas dessa maneira. Em vez do código mais curto, o vencedor seria a resposta com o menor número de gravações em disco.
mbomb007

Respostas:

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

Experimente online!

Outro caso de teste

Entrada:
   7 ALEF = 6,4,0 APOSTE = 5,1 GIMEL = 3

Estado inicial do disco:
   A2 B1 __ G0 A1 B0 A0

Solução:
   ALEF: 2> 2
   ALEF: 0> 0
   APOSTA: 1> 6
   ALEF: 1> 1

Solução visualizada:
   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

Versão não destruída .

Jonathan Frech
fonte