#include "aoc.h"

namespace aoc2016 {

struct elf {
  int i;
  elf* next;
};

void add_elf(elf* e1, elf* ex, elf** last) {
  ex->next = e1;
  (*last)->next = ex;
  *last = ex;
}

elf* del_elf(elf* e1) {
  elf* e = e1;
  while (e->next != e) {
    elf* n = e->next->next;
    e->next = n;
    e = n;
  }
  return e;
}

elf* cross(elf* e, int n) {
  n = n / 2 - 1;
  while (n > 0) {
    e = e->next;
    n--;
  }
  return e;
}

elf* del_elf(elf* e1, size_t n) {
  elf* e = e1;
  while (e->next != e) {
    elf* ex = cross(e, n);
    elf* en = ex->next->next;
    ex->next = en;
    e = e->next;
    n -= 1;
  }
  return e;
}

elf* make_elf(int n) {
  elf* e1 = new elf;
  e1->i = 1;
  e1->next = e1;
  elf* last = e1;
  for (int i = 2; i <= n; i++) {
    elf* e = new elf;
    e->i = i;
    add_elf(e1, e, &last);
  }
  return e1;
}

size_t last_elf(size_t n) {
  size_t x{0};
  size_t i{1};
  while (x < n) {
    x += i;
    i <<= 1;
  }
  x -= (i >> 1);
  x += 1;
  size_t a{1};
  while (x != n) {
    a += 2;
    x += 1;
  }
  return a;
}

size_t final_elf(size_t n) {
  if (n == 1) return 1;
  size_t x{0};
  size_t i{1};
  while (x + 1 < n) {
    x += i + i;
    i *= 3;
  }

  x -= (i / 3) * 2;
  x += 1;
  size_t m = x + i / 3;
  size_t a{1};
  while (x != n) {
    a += x < m ? 1 : 2;
    x += 1;
  }
  return a - 1;
}

std::pair<int64_t, int64_t> day19(line_view) {
  // for (int i = 1; i < 100; i++) {
  //   elf* e = make_elf(i);
  //   elf* x = del_elf(e, i);
  //   printf("%d: %d %zu\n", i, x->i, final_elf(i));
  // }
  return {last_elf(3005290), final_elf(3005290)};
}

} // namespace aoc2016