#include "aoc.h"
#include <memory.h>
#include <vector>

namespace aoc2022 {

struct Co {
  int x;
  int y;
};

struct Move {
  char direction;
  int steps = 0;

  Move(char d, int s): direction(d), steps(s) {}
  Move(line_view lv) {
    const char *p = lv.line;
    direction = p[0];
    p += 2;
    while(*p != '\n') {
      steps = steps * 10 + *p - '0';
      p++;
    }
  }
};

// U D L R
Co next(Co c, Move m, int d4[]) {
  Co n = c;
  switch(m.direction) {
    case 'U' : {
       n.y = c.y - m.steps;
       d4[0] = d4[0] > n.y ? n.y : d4[0];
       break;
    }
    case 'D' : {
       n.y = c.y + m.steps; 
       d4[1] = d4[1] < n.y ? n.y : d4[1];
       break;
    }
    case 'L' : {
       n.x = c.x - m.steps; 
       d4[2] = d4[2] > n.x ? n.x : d4[2];
       break;
    }
    case 'R' : {
       n.x = c.x + m.steps; 
       d4[3] = d4[3] < n.x ? n.x : d4[3];
       break;
    }
    default: break;
  }
  return n;
}

bool too_far(Co c1, Co c2) {
  int y = std::abs(c2.y - c1.y);
  int x = std::abs(c2.x - c1.x);
  return y > 1 || x > 1;
}

struct arena {
  int len;
  char *n;
  Co head;
  Co tail;

  Co tails[10];

  arena(int m) {
    len = m * 2 + 1;
    n = (char *) malloc(len * len);
    memset(n, 0, len * len);
    
    head.x = len / 2;
    head.y = len / 2;
    tail = head;

    for (int i = 0; i < 10; i++) {
      tails[i] = head;
    }
  }

  char& get(Co c) {
    return *(n + c.y * len + c.x);
  }

  void reset() {
    memset(n, 0, len * len);
  }

  int moves() {
    int m{0};
    for (int i = 0; i < len*len; i++) {
      m += (int) *(n+i) > 0;
    }
    return m;
  }

  void follow(Co& t, Co& h) {
    int dy = h.y - t.y;
    int dx = h.x - t.x;
    // printf("(%d,%d) -> (%d,%d) %d %d\n", t.x, t.y, h.x, h.y, dx, dy);
    if (std::abs(dy) == 2 && std::abs(dx) == 2) {
      t.x += dx / 2;
      t.y += dy / 2;
      return;
    }

    if (dy == 2) {
      t.y += 1;
      t.x += dx;
    }

    if (dy == -2) {
      t.y -= 1;
      t.x += dx;
    }

    if (dx == 2) {
      t.x += 1;
      t.y += dy;
    }

    if (dx == -2) {
      t.x -= 1;
      t.y += dy;
    }
  }

  void travel(std::vector<Move>& ms) {
    int d4[4] = {0};
    for(auto& m: ms) {
      for (int i = 0; i < m.steps; i++) {
        Move mx{m.direction, 1};
        head = next(head, mx, d4);
        if (too_far(tail, head)) {
          follow(tail, head);
          get(tail) += 1;
        }
      } 
    }
  }

  void travel_tails(std::vector<Move>& ms) {
    int d4[4] = {0};
    for(auto& m: ms) {
      for (int i = 0; i < m.steps; i++) {
        Move mx{m.direction, 1};
        tails[0] = next(tails[0], mx, d4);
        for (int j = 1; j <= 9; j++) {
          if (too_far(tails[j], tails[j-1])) {
            follow(tails[j], tails[j - 1]);
            if (j == 9) {
              get(tails[j]) += 1;
            }
          }
        }
      } 
    }
  }
};

std::pair<int,int> day9(line_view file) {
  Co p{0, 0};
  int d4[] = {0, 0, 0, 0};

  std::vector<Move> ms;
  per_line(file, [&p, &d4, &ms](line_view lv){
    Move m{lv};
    ms.push_back(m);
    p = next(p, m, d4);
    return true;
  });

  int max{0};
  for (auto d: d4) {
    if (max < std::abs(d)) {
      max = d;
    }
  }

  // printf("%d %d %d %d -> %d\n", d4[0], d4[1], d4[2], d4[3], max);
  arena an(max);
  an.travel(ms);
  int m1 = an.moves();

  an.reset();
  an.travel_tails(ms);
  int m2 = an.moves();
  return {m1, m2 + 1};
}

}