1 files changed, 48 insertions, 15 deletions

diff --git a/2024/9.c b/2024/9.c
index fc7c48a..63b20a9 100644
--- a/2024/9.c
+++ b/2024/9.c
@@ -24,6 +24,16 @@ static int* expand(size_t *lenp, const char *mp, size_t maplen) {
   return disk;
 }
 
+__attribute__((unused))
+static void print_disk(int *disk, size_t len) {
+  for (size_t i = 0; i < len; i++) {
+    if (i != 0) putchar(' ');
+    if (disk[i] == -1) putchar('.');
+    else printf("%d", disk[i]);
+  }
+  putchar('\n');
+}
+
 static size_t compact(int *disk, size_t len) {
   size_t j = len;  // one past the last non-empty block
   while (j > 0 && disk[j-1] == -1) j--;
@@ -35,25 +45,48 @@ static size_t compact(int *disk, size_t len) {
   return j;
 }
 
-static size_t defragment(int *disk, size_t len) {
-  // TODO
-}
+static void defragment(int *disk, const size_t len) {
+  printf("len = %zu\n", len);
+  int *blockoff = malloc(len * sizeof(int));
+  int *blocks = malloc(len * sizeof(int));  // negative is empty
+  int nblocks = 0;
+  for (int i = 0; i < (int)len; ) { 
+    blockoff[nblocks] = i;
+    int blocklen = 1;
+    for (; i + blocklen < (int)len && disk[i + blocklen] == disk[i]; blocklen++) {}
+    blocks[nblocks++] = disk[i] == -1 ? -blocklen : blocklen;
+    i += blocklen;
+  }
 
-static size_t checksum(int *disk, size_t len) {
-  size_t sum = 0;
-  for (size_t i = 0; i < len && disk[i] != -1; i++) {
-    sum += i * disk[i];
+  // printf("blockoff:"); for (int k = 0; k < nblocks; k++) printf(" %d", blockoff[k]); printf("\n\n");
+
+  for (int j = nblocks - 1; j > 0; j--) {
+    if (blocks[j] < 0) continue;
+
+    // print_disk(disk, len);
+    // printf("blocks:"); for (int k = 0; k < nblocks; k++) printf(" %s%d%s", k==j?"[":"", blocks[k], k==j?"]":""); printf("\n\n");
+
+    int i = 0;
+    while (i < j && (blocks[i] >= 0 || disk[blockoff[i]] >= 0 || -blocks[i] < blocks[j])) i++;
+    if (i >= j) continue;
+    memcpy(&disk[blockoff[i]], &disk[blockoff[j]], blocks[j] * sizeof(int));
+    memset(&disk[blockoff[j]], -1, blocks[j] * sizeof(int));
+    if (-blocks[i] - blocks[j] > 0) {
+      blocks[i] += blocks[j];
+      blockoff[i] += blocks[j];
+    }
   }
-  return sum;
+
+  // print_disk(disk, len);
+  // printf("blocks:"); for (int k = 0; k < nblocks; k++) printf(" %d", blocks[k]); printf("\n");
 }
 
-static void print_disk(int *disk, size_t len) {
+static size_t checksum(int *disk, size_t len) {
+  size_t sum = 0;
   for (size_t i = 0; i < len; i++) {
-    if (i != 0) putchar(' ');
-    if (disk[i] == -1) putchar('.');
-    else printf("%d", disk[i]);
+    if (disk[i] != -1) sum += i * disk[i];
   }
-  putchar('\n');
+  return sum;
 }
 
 int main(void) {
@@ -71,6 +104,6 @@ int main(void) {
   size_t disklen1 = compact(disk, disklen);
   printf("%zu\n", checksum(disk, disklen1));
 
-  size_t disklen2 = defragment(disk2, disklen);
-  printf("%zu\n", checksum(disk2, disklen2));
+  defragment(disk2, disklen);
+  printf("%zu\n", checksum(disk2, disklen));
 }