1 files changed, 76 insertions, 0 deletions
diff --git a/2024/9.c b/2024/9.c
new file mode 100644
index 0000000..fc7c48a
--- /dev/null
+++ b/2024/9.c
@@ -0,0 +1,76 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
+
+#define INPUTLEN 20000
+
+static int* expand(size_t *lenp, const char *mp, size_t maplen) {
+  size_t len = 0;
+  for (size_t i = 0; i < maplen; i++) len += mp[i] - '0';
+
+  int *disk = malloc(len * sizeof(int));
+  size_t cursor = 0;
+  for (size_t i = 0; i + 1 < maplen; i += 2) {
+    for (int j = 0; j < mp[i] - '0'; j++) disk[cursor++] = i / 2;
+    for (int j = 0; j < mp[i+1] - '0'; j++) disk[cursor++] = -1;
+  }
+  if (maplen % 2 == 1) {
+    size_t i = maplen - 1;
+    for (int j = 0; j < mp[i] - '0'; j++) disk[cursor++] = i / 2;
+  }
+  *lenp = len;
+  return disk;
+}
+
+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--;
+  for (size_t i = 0; i < j - 1; i++) {
+    if (disk[i] != -1) continue;
+    disk[i] = disk[--j];
+    while (j > 0 && disk[j-1] == -1) j--;
+  }
+  return j;
+}
+
+static size_t defragment(int *disk, size_t len) {
+  // TODO
+}
+
+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];
+  }
+  return sum;
+}
+
+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');
+}
+
+int main(void) {
+  char *diskmap = malloc(INPUTLEN + 1);
+  size_t nr = fread(diskmap, 1, INPUTLEN, stdin);
+  assert(nr <= INPUTLEN);
+  while (nr > 0 && isspace(diskmap[nr-1])) nr--;
+  diskmap[nr] = 0;
+
+  size_t disklen;
+  int *disk = expand(&disklen, diskmap, nr);
+  int *disk2 = malloc(disklen * sizeof(int));
+  memcpy(disk2, disk, disklen * sizeof(int));
+
+  size_t disklen1 = compact(disk, disklen);
+  printf("%zu\n", checksum(disk, disklen1));
+
+  size_t disklen2 = defragment(disk2, disklen);
+  printf("%zu\n", checksum(disk2, disklen2));
+}