Fewest disk writes to defrag multiple files

Question

Introduction

A disk is a linear container with blocks indexed 0 through size-1.

A file is a named list of block indexes used by that file.

An example filesystem is expressed like this:

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

"The disk has 15 blocks, the first block of file ALPHA is the disk block at index 3..."

The disk map could be drawn like this:

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

A disk is considered defragged when all of the files within it are stored contiguously.

YOUR GOAL:

Emit a shortest sequence of legal moves which will defrag a given disk.

Legal Moves

A move contains three pieces of information: the name of a file, an index of the block in the file to be moved, and the index of the disk block it moves to.

For example

ALPHA:1>4

"Move block 1 of the file ALPHA to block 4 of the disk."

After this move, the example file system is now 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 |   |   |   |

The previously-inhabited disk block is implicitly cleared. Equivalently, you can view this as swapping two blocks on the disk but one of the blocks in the swap must be empty.

Data may not be destroyed. Files cannot share blocks at any stage and movements must be within range of the disk. The following moves are illegal: ALPHA:0>10 (owned by BETA), ALPHA:3>0 (no such block in ALPHA), ALPHA:0>-1 (no such disk index), ALPHA:0>15 (disk index too big)

Example 1

Solving the above example in full.

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

Files do not have to be adjacent in the solution, just continuous within themselves.

Example 2

Here is a more constrained case

Input:

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

Output:

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

The progression of this filesystem is:

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 |

An alternative way to defrag this would by to C:2>9 then bring A down a step, then bring C down a step, then do C:2>5 but this would not be a legal solution because it contains more moves than the alternative.

Representation

You can use any representation for the input as long as it is reasonably close to a basic string. Depending on your language, the input to the first example might be notated as

"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

Similarly, the output can be whatever is convenient for your language as log as it is printed, human-readable, and represents an ordered list of legal moves, each move being described by 1)file-name, 2)file-block-index, 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

Requirements

Your code must accept any size disk, and any number and size of files.

Inputs which do not describe legal initial filesystem states can lead to undefined behaviour.

Your code must produce a shortest moves solution, for any well-defined input.

All moves you produce must be legal; the filesystem must be in a valid state after applying each step you produce.

Your code must terminate for all valid inputs, i.e. it should never get stuck in a loop, the filesystem should be in a distinctly new state after each move is applied.

Where there exists more than one shortest solution, any can be selected as valid.

Shortest code wins. Please post at least one new nontrivial example input and its output with your code.

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

Try it online!

---

Another test case

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

Initial disk state:
   A2 B1 __ G0 A1 B0 A0

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

Visualized solution:
   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.