aoc2019/d1-10/day3.c

//
// Created by red on 03/12/19.
//

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

struct Point {
  int x;
  int y;
};

#ifndef ORIGIN
#define ORIGIN (struct Point){.x=0,.y=0,}
#endif

//given a point, a direction and a distance, return the point that's that distance in the given direction
struct Point get_pt(char dir, int delta, struct Point loc) {
  struct Point dloc;
  switch(dir) {
  case 'R': dloc = (struct Point){
        .x = loc.x + delta,
        .y = loc.y,
    }; break;
  case 'L': dloc = (struct Point){
        .x = loc.x - delta,
        .y = loc.y,
    }; break;
  case 'U': dloc = (struct Point){
        .x = loc.x,
        .y = loc.y + delta,
    }; break;
  case 'D': dloc = (struct Point){
        .x = loc.x,
        .y = loc.y - delta,
    }; break;
  default: dloc = loc;
  }
  return dloc;
}

//takes four points, checks if the line a1 - a2 intersects b1 - b2, returns intersection point if yes, origin otherwise
struct Point intersects(struct Point a1, struct Point a2, struct Point b1, struct Point b2) {
  bool a_isvert = (a1.x == a2.x);
  bool b_isvert = (b1.x == b2.x);
  if (a_isvert == b_isvert) { //no collision if lines are both vertical or both horizontal
    return ORIGIN;
  }
  // if b is vertical, call the function again with the operands reversed. we want to assume a is vertical
  if (b_isvert) {
    return intersects(b1, b2, a1, a2);
  }
  // determine the smaller and bigger x-coord of b1 & b2. same for y-coord of a1 & a2
  int b_lx = (b1.x < b2.x) ? b1.x : b2.x;
  int b_gx = (b1.x < b2.x) ? b2.x : b1.x;
  int a_ly = (a1.y < a2.y) ? a1.y : a2.y;
  int a_gy = (a1.y < a2.y) ? a2.y : a1.y;
  // if the x-coord of a1 is somewhere between b1 and b2, and the y-coord of b1 is somewhere between a1 and a2
  // then the lines must intersect.
  if (a1.x > b_lx && a1.x < b_gx && b1.y > a_ly && b1.y < a_gy) {
    //return the manhattan distance of the intersection
    return (struct Point){
      .x = a1.x,
      .y = b1.y,
    };
  }
  //if the end of the function is reached, the lines don't intersect.
  return ORIGIN;
}

//returns the manhattan distance between two points
int manhattan(struct Point a, struct Point b) {
  return (abs(a.x - b.x) + abs(a.y - b.y));
}

//scan an input string, saving all the points to out. return the no. of points read
size_t scan_points(char* in, struct Point* out){
  //sequence is assumed to start at the origin.
  out[0] = ORIGIN;
  size_t i = 1;
  while (*in != 0) { //read until null
    char dir;
    int delta;
    int num_read;
    sscanf(in, "%c%d%n", &dir, &delta, &num_read);
    out[i] = get_pt(dir, delta, out[i]);
    i++;
    in += num_read + 1; // skip the number we just read, and the separator
  }
  return i;
}

int main() {
  //allocate an input string, and two arrays for input points
  //we don't know the exact length of the arrays but we know it's smaller than 400
  char* input_raw = calloc(1500,sizeof(char));
  scanf("%s", input_raw);
  struct Point a[400];
  struct Point b[400];
  char* ptr = input_raw;
  size_t a_size = scan_points(ptr, a);
  //clear the input buffer
  memset((void*) input_raw, 0, sizeof(char)*1500);
  //scan the second input sequence, reset var ptr to the beginning of the string, reset location to the origin
  scanf("%s", input_raw);
  ptr = input_raw;
  size_t b_size = scan_points(ptr, b);
  free((void*) input_raw);
  /*
   * we want to find collisions between a and
   */
  int min = INT_MAX;
  int min_delay = INT_MAX;
  int a_delay = 0;
  for (size_t i = 1; i < a_size; i++) {
    int b_delay = 0;
    for (size_t j = 1; j < b_size; j++) {
      struct Point pt = intersects(a[i-1], a[i], b[j-1], b[j]);
      int dist = manhattan(ORIGIN, pt);
      if (dist > 0) {
        if (dist < min) min = dist;
        int delay = a_delay + b_delay + manhattan(pt, a[i-1]) + manhattan(pt, b[j-1]);
        if (delay < min_delay) min_delay = delay;
      }
      b_delay += manhattan(b[j-1], b[j]);
    }
    a_delay += manhattan(a[i-1], a[i]);
  }
  printf("Min. intersection distance from origin: %d\n"
         "Min. intersection distance on lines: %d\n", min, min_delay);
  return EXIT_SUCCESS;
}