Full kode finner du her.
Main metode
For alle oppgavene i 2024 bruker jeg Java, og dette vil være metoden jeg bruker for å hente input for de ulike oppgavene. Input blir lagret i en txt fil og hentes via denne metoden.
Oppgave 1
Oppgave 1 for luke 9 tar for seg komprimering av diskplass. Ganske enkelt å greit gis det en streng med tall (1-9) hvor annenhvert tall indikerer enten
størrelse på filen eller megde ledig plass. Det er også ID knyttet til hver fil, hvor fil 1 har ID 0, fil 2 har ID 1 osv. Eksempel: 2343. ID 0 tar plass 2, 3 ledige plasser før neste, ID 1 tar plass 4 og 3 ledige plasser før neste.
Visuelt vil det 2343 se slik ut: 00...1111.... Vi skal da komprimere fra høyre til venstre, og flytte deler av hver fil inn i de ledige plassene. Ta utgangspunkt i strengt 23432 som visuelt
ser slik ut: 00...1111...22. Vi kan da først flytte fra ID 2, slik at vi får 0022.1111...... Deretter flytte fra ID 1, slik at vi får 00221111.......
Til slutt skal vi ha en checksum for å den nye filplasseringen. Checksum kalkuleres ved å ta ID * Index. Så for siste strengen vår vil det bli 0 * 0 + 0 * 1 + 2 * 2…, totalt får vi da 36 (4 + 6 + 5 + 6 + 7 + 8).
Vi har da 3 metoder, en metode for å opprette strengen visuelt, en for checksum, og en for komprimmering.
private static List<Integer> parseDisk(String line) {
List<Integer> disk = new ArrayList<>();
int fileId = 0;
for (int i = 0; i < line.length(); i++) {
int length = Character.digit(line.charAt(i), 10);
if (i % 2 == 0) {
for (int j = 0; j < length; j++) disk.add(fileId);
fileId++;
} else {
for (int j = 0; j < length; j++) disk.add(-1);
}
}
return disk;
}
private static long checksum(List<Integer> disk) {
long sum = 0;
for (int i = 0; i < disk.size(); i++) {
int id = disk.get(i);
if (id != -1) sum += (long) id * i;
}
return sum;
}
private static long performBlockByBlockCompaction(String line) {
List<Integer> disk = parseDisk(line);
for (int i = disk.size() - 1; i >= 0; i--) {
if (disk.get(i) != -1) {
for (int j = 0; j < i; j++) {
if (disk.get(j) == -1) {
disk.set(j, disk.get(i));
disk.set(i, -1);
break;
}
}
}
}
return checksum(disk);
}
Oppgave 2
For oppgave 2 skal vi istedenfor å komprimere deler av filer kun komprimere en hel fil dersom det er plass. Det vil si at dersom vi har 3 ledige plasser og en fil på størrelse 4, vil denne ikke flyttes, men heller sjekke neste ledige plass. Metoden må derfor endres for komprimering, mens de to andre (tall til streng, og checksum) forblir. Det blir totalt 3 metoder, hvorav den ene er lik oppgave 1 med små endringer, og de to nye er for endrede krav.
private static long performWholeFileCompaction(String line) {
List<Integer> disk = parseDisk(line);
int maxFileId = 0;
for (int i = 0; i < line.length(); i += 2) {
maxFileId++;
}
maxFileId--;
compactByFiles(disk, maxFileId);
return checksum(disk);
}
private static void compactByFiles(List<Integer> disk, int maxFileId) {
for (int fileId = maxFileId; fileId >= 0; fileId--) moveFileIfPossible(disk, fileId);
}
private static void moveFileIfPossible(List<Integer> disk, int fileId) {
int start = -1, end = -1;
for (int i = 0; i < disk.size(); i++) {
if (disk.get(i) == fileId) {
if (start == -1) start = i;
end = i;
}
}
if (start == -1) return;
int fileLength = end - start + 1;
int freeSegmentStart = -1;
int freeCount = 0;
int bestStart = -1;
for (int i = 0; i < start; i++) {
if (disk.get(i) == -1) {
if (freeSegmentStart == -1) freeSegmentStart = i;
freeCount++;
if (freeCount == fileLength) {
bestStart = freeSegmentStart;
break;
}
} else {
freeSegmentStart = -1;
freeCount = 0;
}
}
if (bestStart == -1) return;
for (int i = 0; i < fileLength; i++) disk.set(bestStart + i, fileId);
for (int i = start; i <= end; i++) disk.set(i, -1);
}