#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "../../lib/aoc.h"

#define EMPTY -1

typedef struct File {
  int id;
  int *location;
  int size;
  bool free;
} File;

int main() {
  char *input = aoc_read_input();
  int input_size = strlen(input);

  int disk[200000];
  int *write_head = disk;
  int file_number = 0;
  int total_file_size = 0;

  File files[10000];
  int files_count = 0;
  File empties[10000];
  int empties_count = 0;

  int i = 0;
  while (i < input_size) {
    int file_size = input[i++] - '0';
    total_file_size += file_size;

    files[files_count].id = file_number;
    files[files_count].location = write_head;
    files[files_count].size = file_size;
    files_count++;
      
    for (int j = 0; j < file_size; j++) {
      *write_head = file_number;
      write_head++;
    }
    file_number++;

    int empty_size = input[i++] - '0';
    if (empty_size > 0) {
      empties[empties_count].id = EMPTY;
      empties[empties_count].location = write_head;
      empties[empties_count].size = empty_size;
      empties_count++;
    }

    for (int j = 0; j < empty_size; j++) {
      *write_head = EMPTY;
      write_head++;
    }
  }

  int *read_head = write_head - 1;
  write_head = disk;

  while (read_head > write_head) {
    if (*read_head == EMPTY) read_head--;
    else if (*write_head != EMPTY) write_head++;
    else {
      *write_head = *read_head;
      *read_head = EMPTY;
    }
  }

  long checksum = 0l;
  for (int i = 0; i < total_file_size; i++) checksum += i * disk[i];

  for (int i = files_count - 1; i >= 0; i--) {
    for (int j = 0; j < empties_count; j++) {
      if (empties[j].size >= files[i].size) {
	files[i].location = empties[j].location;
	empties[j].size -= files[i].size;
	empties[j].location += files[i].size;
	break;
      }
      if (empties[j].location > files[i].location) break;
    }
  }

  long second_checksum = 0l;
  for (int i = 0; i < files_count; i++) {
    for (int j = 0; j < files[i].size; j++) {
      second_checksum += (files[i].id * (files[i].location - disk + j));
    }
  }


  printf("Part 1: %ld\n", checksum);
  printf("Part 2: %ld\n", second_checksum);
  
  aoc_free();
  return 0;
}