Day 9 has us pretending to be an operating system’s file system manager. I created a class DiskHandler. There’s not really a lot of discussion to be had about the process of the differences between part 1 and 2. Pretty much you have to read the problem, and re-read it, until it makes sense, and then just implement the described processes. The one thing that did slow me down doing part 1 was that I needed an extra “cleanup pass” at the end because the moved file portions left a hole behind.
final class DiskHandler
{
final String diskDescription;
public DiskHandler(final String inputDiskDescription)
{
diskDescription = inputDiskDescription + "0";
}
record FileDescription(int fileStartBlock, int fileSize, int fileNumber) {}
record FreeBlock(int startBlock, int size) {}
public long getCompactedChecksum() // part 1
{
final List<FileDescription> fileDescriptions = new ArrayList<>();
final List<FreeBlock> freeBlocks = new ArrayList<>();
// Parse the input into pairs. Track the files and the free spaces in
// separate lists
int fileBlock = 0;
int fileNumber = 0;
for (int pos=0; pos < diskDescription.length(); pos += 2)
{
final int fileSize = diskDescription.charAt(pos)-'0';
final int freeSpaceAfterFile = diskDescription.charAt(pos+1)-'0';
final FileDescription fd = new FileDescription(fileBlock, fileSize, fileNumber++);
fileDescriptions.add(fd);
fileBlock += fileSize;
freeBlocks.add(new FreeBlock(fileBlock, freeSpaceAfterFile));
fileBlock += freeSpaceAfterFile;
}
// Make an array to track all the blocks, and initialize it to minus one
// because 0 is a valid file number
final int blocks[] = new int[fileBlock];
for (int i=0; i<fileBlock; i++) blocks[i] = -1;
// Copy the file numbers into the array, we'll need that info to
// calculate the checksum later
for (final FileDescription fd : fileDescriptions)
{
for (int i=0; i < fd.fileSize; i++)
{
blocks[fd.fileStartBlock + i] = fd.fileNumber;
}
}
// Move files from the end into the tracked empty spaces
int endPos = fileBlock-1;
for (final FreeBlock fb : freeBlocks)
{
final int numBlocksToMove = fb.size;
endPos = moveBlocksFromEnd(blocks, numBlocksToMove, endPos, fb.startBlock);
}
// "Cleanup phase" to get straggler blocks at the end
int curEmptyBlock = findNextEmptyBlock(blocks, 0);
endPos = fileBlock-1;
while (endPos > curEmptyBlock)
{
if (blocks[endPos] != -1)
{
blocks[curEmptyBlock] = blocks[endPos];
blocks[endPos] = -1;
curEmptyBlock = findNextEmptyBlock(blocks, curEmptyBlock+1);
}
endPos--;
}
// Calculate the checksum... sum of block number times
// the file number occupying the block
long checksum = 0;
for (int i=0; i<fileBlock; i++)
{
if (blocks[i] != -1)
{
checksum += i*blocks[i];
}
}
return checksum;
}
private int findNextEmptyBlock(final int[] blocks, final int startSearchPoint)
{
int pos = startSearchPoint;
while (blocks[pos] != -1) pos++;
return pos;
}
private int moveBlocksFromEnd(final int[] blocks, final int numBlocksToMove, final int endPos, final int startBlock)
{
int blocksLeft = numBlocksToMove;
int searchPos = endPos;
int destBlock = startBlock;
while (blocksLeft > 0)
{
while (blocks[searchPos]==-1) searchPos--;
blocks[destBlock++] = blocks[searchPos];
blocks[searchPos--] = -1;
blocksLeft--;
}
return searchPos;
}
public long getCompactedChecksum2() // part 2
{
final List<FileDescription> fileDescriptions = new ArrayList<>();
final List<FreeBlock> freeBlocks = new ArrayList<>();
// Same parsing as in part one
int fileBlock = 0;
int fileNumber = 0;
for (int pos=0; pos < diskDescription.length(); pos += 2)
{
final int fileSize = diskDescription.charAt(pos)-'0';
final int freeSpaceAfterFile = diskDescription.charAt(pos+1)-'0';
final FileDescription fd = new FileDescription(fileBlock, fileSize, fileNumber++);
fileDescriptions.add(fd);
fileBlock += fileSize;
freeBlocks.add(new FreeBlock(fileBlock, freeSpaceAfterFile));
fileBlock += freeSpaceAfterFile;
}
// Same array as in part one
final int blocks[] = new int[fileBlock];
for (int i=0; i<fileBlock; i++) blocks[i] = -1;
for (final FileDescription fd : fileDescriptions)
{
for (int i=0; i < fd.fileSize; i++)
{
blocks[fd.fileStartBlock + i] = fd.fileNumber;
}
}
// The instructions say to make one attempt to move each file
// from the highest file number to the lowest
for (int fileNum = fileDescriptions.size()-1; fileNum > 0; fileNum--)
{
final FileDescription fd = fileDescriptions.get(fileNum);
for (int j=0; j < freeBlocks.size(); j++)
{
final FreeBlock fb = freeBlocks.get(j);
if (fb.startBlock >= fd.fileStartBlock) break;
if (fb.size >= fd.fileSize)
{
moveFile(blocks, fd.fileStartBlock, fd.fileSize, fb.startBlock);
// Since a block is rarely the same size as the [smaller] file that
// will fit there, we need to track the remainder as a free block
if (fd.fileSize != fb.size)
{
freeBlocks.add(j+1, new FreeBlock(fb.startBlock + fd.fileSize, fb.size - fd.fileSize));
}
freeBlocks.remove(j);
break;
}
}
}
// Same checksum algorithm as in part one
long checksum = 0;
for (int i=0; i<fileBlock; i++)
{
if (blocks[i] != -1)
{
checksum += i*blocks[i];
}
}
return checksum;
}
private void moveFile(final int[] blocks, final int fromStartBlock, final int numberOfBlocksToMove, final int destStartBlock)
{
for (int i=0; i<numberOfBlocksToMove; i++)
{
blocks[destStartBlock+i] = blocks[fromStartBlock+i];
blocks[fromStartBlock+i] = -1;
}
}
}