#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include "../../lib/aoc.h"

typedef struct Range {
  uint64_t begin;
  uint64_t end;
} Range;

int sort_range(const void *a, const void *b) {
  return (*(Range*) a).begin > (*(Range*) b).begin ? 1 :
    (*(Range*) a).begin < (*(Range*) b).begin ? -1 : 0;
}

bool id_in_range(uint64_t id, Range *ranges, int range_count) {
  for (int i = 0; i < range_count; i++) {
    if (id >= ranges[i].begin && id <= ranges[i].end) return true;
  }

  return false;
}

bool combine_ranges(Range *r1, Range *r2) {
  if (r2->begin > r1->end || r1->begin > r2->end) return false;
  
  r1->begin = r1->begin > r2->begin ? r2->begin : r1->begin;
  r1->end = r1->end < r2->end ? r2->end : r1->end;
  r2->begin = 0;
  r2->end = 0;
  return true;
}

int main() {
  char *line;

  Range ranges[200];
  uint64_t ids[1000];

  int index = 0;
  int range_count;
  int id_count;
  bool reading_ids = false;
  while ((line = aoc_read_line()) != NULL) {
    if (reading_ids) {
      sscanf(line, "%lu", &(ids[index]));
      index++;
    } else {
      if (strlen(line) == 0) {
	reading_ids = true;
	range_count = index;
	index = 0;
      } else {
	sscanf(line, "%lu-%lu", &(ranges[index].begin), &(ranges[index].end));
	index++;
      }
    }
  }

  id_count = index;
  int valid_id_count = 0;

  for (int i = 0; i < id_count; i++) {
    if (id_in_range(ids[i], ranges, range_count)) valid_id_count++;
  }

  printf("Part 1: %d\n", valid_id_count);

  qsort(ranges, range_count, sizeof(Range), sort_range);
  
  for (int i = 0; i < range_count - 1;) {
    bool combined = combine_ranges(&ranges[i], &ranges[i + 1]);
    if (combined) {
      memcpy(&(ranges[i+1]), &(ranges[i+2]), sizeof(Range) * (range_count - (i + 1)));
      range_count--;
    } else {
      i++;
    }
  }

  uint64_t covered_id_count = 0;

  for (int i = 0; i < range_count; i++) {
    covered_id_count += (ranges[i].end - ranges[i].begin + 1);
  }

  printf("Part 2: %lu\n", covered_id_count);

  aoc_free();

  return 0;
}