AoC 2019 Day 3

aoc_2019_3.js

// this is a var because I hack directly into chrome devtools for these and you can't redeclare consts and lets haha.
var day32019 = () => {
  const start = performance.now();
  const src = `R1005,U563,R417,U509,L237,U555,R397,U414,L490,U336,L697,D682,L180,U951,L189,D547,R697,U583,L172,D859,L370,D114,L519,U829,R389,U608,R66,D634,L320,D49,L931,U137,L349,D689,L351,D829,R819,D138,L118,D849,R230,U858,L509,D311,R815,U217,R359,U840,R77,U230,R361,U322,R300,D646,R348,U815,R793,D752,R967,U128,R948,D499,R359,U572,L566,U815,R630,D290,L829,D736,R358,U778,R891,U941,R544,U889,L920,U913,L447,D604,R538,U818,L215,D437,R447,U576,R452,D794,R864,U269,L325,D35,L268,D639,L101,U777,L776,U958,R105,U517,R667,D423,R603,U469,L125,D919,R879,U994,R665,D377,R456,D570,L685,U291,R261,U846,R840,U418,L974,D270,L312,D426,R621,D334,L855,D378,R694,U845,R481,U895,L362,D840,L712,U57,R276,D643,R566,U348,R361,D144,L287,D864,L556,U610,L927,U322,R271,D90,L741,U446,R181,D527,R56,U805,L907,D406,L286,U873,L79,D280,L153,D377,R253,D61,R475,D804,R788,U393,L660,U314,R489,D491,L234,D712,L253,U651,L777,D726,R146,U47,R630,U517,R226,U624,L834,D153,L513,U799,R287,D868,R982,U390,L296,D373,R9,U994,R105,D673,L657,D868,R738,D277,R374,U828,R860,U247,R484,U986,L723,D847,L578,U487,L51,D865,L328,D199,R812,D726,R355,D463,R761,U69,R508,D753,L81,D50,L345,D66,L764,D466,L975,U619,R59,D788,L737,D360,R14,D253,L512,D417,R828,D188,L394,U212,R658,U369,R920,U927,L339,U552,R856,D458,R407,U41,L930,D460,R809,U467,L410,D800,L135,D596,R678,D4,L771,D637,L876,U192,L406,D136,R666,U730,R711,D291,L586,U845,R606,U2,L228,D759,R244,U946,R948,U160,R397,U134,R188,U850,R623,D315,L219,D450,R489,U374,R299,D474,L767,D679,L160,D403,L708
L1003,D878,R937,D979,R921,U572,R4,D959,L884,U394,R221,U206,R806,U912,R345,D290,R65,D996,L411,D157,R590,D557,L32,D360,L691,D861,L156,D603,R733,U444,L433,U144,L238,U213,R827,U949,R384,D409,L727,U923,L98,U781,L201,D200,R749,U288,L486,U158,L494,D522,R636,D330,L507,U691,R918,D706,R163,U609,R559,U674,R784,D87,R670,U401,L85,U981,R848,D579,L882,U777,R671,D385,R913,D899,R92,D780,L795,U821,R956,U446,L109,D955,L570,D874,R499,U845,R769,U88,L529,U657,R553,D357,L83,D324,L273,U689,L715,U933,R161,U561,L603,U349,L445,U781,R299,U26,L212,U429,R763,U116,R961,D258,L518,D668,L767,U587,L654,D24,R318,U35,L9,D199,L161,U419,R6,D707,R944,U499,R207,D349,L727,D637,R735,D137,R18,D214,L531,D327,L916,U440,R859,U483,R952,D631,L96,D320,L192,D985,R330,D196,L345,D575,L535,D868,R376,D126,R903,D619,L126,D624,L990,D67,L927,U685,L200,D759,L157,D816,L585,U910,R587,D598,L398,U706,R847,U682,L919,D291,L932,D54,L314,U430,L60,U206,L997,D487,L874,U957,L753,U999,R156,U102,L826,U923,L204,U293,L244,U787,L273,D687,R134,D167,L287,D459,R875,D32,R635,D400,L179,D19,L576,U60,L182,D409,R114,U329,R207,U525,L295,U305,L861,U280,R531,D49,L890,U521,L283,U37,R344,D867,L474,U893,R140,U289,L67,U490,R121,D34,L696,U902,R288,U249,R107,D750,R389,U125,L406,U950,R932,U795,R205,U583,L665,U214,R806,D409,R832,D39,R207,D977,L873,U645,L762,U847,L725,U397,R414,D558,L669,D736,R897,U464,R207,U359,R257,U304,L932,U240,L582,U409,L493,D481,R48,D537,R893,U48,R707,U630,L70,D289,L769,U98,L679,U504,L337,U117,L343,D574,R595,U168,R498`
    .split(/\n/g)
    .map(m => m.split(/,/g));

  const directions = {
      'L': { x: -1, y: 0},
      'R': { x: 1, y: 0},
      'U': { x: 0, y: 1},
      'D': { x: 0, y: -1}
  }

  const lines = 
    // process weird data format into vectors
    src.map(w => w.map(v => {
      let dist = parseInt(v.substr(1), 10);
      const normal = directions[v.substr(0, 1)];
      return [dist * normal.x, dist * normal.y];
    }))
    // process the vectors into line objects
    .map(m => m.reduce((p, [x, y]) => {
      let c = p[p.length -1];
      if (!c) c = {t: {x: 0, y: 0}, d: 0}
      // make an object that contains a from vector, to vector and 
      // a distance accumulator. Also a precomputed normal. 
      p.push(
        {
            f: {x: c.t.x, y:c.t.y },
            t: {x: c.t.x + x, y: c.t.y + y},
            n: {
              x: x ? (c.t.x / Math.abs(c.t.x)) : 0,
              y: y ? (c.t.y / Math.abs(c.t.y)) : 0,
            },
            d: c.d + Math.max(Math.abs(x), Math.abs(y))
        }
      )
      return p;
    }, []));

  // checks if two lines intersect, ignoring
  // parallel lines.
  const doesIntersect = (opa, opb) => {
    let a, b;
    // parallel test...
    if (Math.abs(opa.n.x) === Math.abs(opb.n.x)) return false;
    // try to make sure operand a is vertical
    // to save a bunch of cut and pasting...
    if (Math.abs(opa.n.x) === 1) {
      a = opb;
      b = opa;
    } else {
      a = opa;
      b = opb;
    }
    if (a.f.x > Math.min(b.f.x, b.t.x) && a.f.x < Math.max(b.t.x, b.f.x)) {
        if (b.f.y > Math.min(a.f.y, a.t.y) && b.f.y < Math.max(a.t.y, a.f.y)) {
            return [a.f.x, b.f.y];
            
        }
    }
    return false;
  }

  // star 1: Just get the list of collisions by comparing 
  // every line against every other line.
  let collisions = [];
  for (let i = 0; i < lines[0].length; i++) {
    for (let j = 0; j < lines[1].length; j++) {
       let result = doesIntersect(lines[0][i], lines[1][j])
        if (result) {
            collisions.push(result);
        }
    }
  }

  
  // star 1: sort collisions by manhatten distance and return the result
  const star1result = collisions
    .map(([x, y]) => Math.abs(x) + Math.abs(y))
    .sort((a, b) => a - b)[0];
  //console.log(star1result);
  //return `Done in ${performance.now() - start}`
  


  // star 2:
  // checks if a line intersects with a point and then 
  // returns the total distance from the beginning of the 
  // path to reach that point.
  const findFirstIntersectionWithPoint = ({f, t, n, d}, [x, y]) => {
    if (n.x === 0) {
        if (t.x === x) {
            if (y > Math.min(t.y, f.y) && y < Math.max(t.y, f.y)) {
                let lineLength = Math.abs(t.y - f.y);
                let distSoFar = d - lineLength;

                let distToPoint = Math.abs(y - f.y)
                return distSoFar + distToPoint;
            }
        }
        return false;
    } else {
        if (t.y === y) {
            if (x > Math.min(t.x, f.x) && x < Math.max(t.x, f.x)) {
                let lineLength = Math.abs(t.x - f.x);
                let distSoFar = d - lineLength;
                let distToPoint = Math.abs(x - f.x)
                return distSoFar + distToPoint;
            }

        }
        return false;
    }
  }

  // using the collisions, find the first time 
  // that a line visits a co-ordinate by checking for 
  // an intersection with a point
  const firstVisit = collisions.map(([ax, ay]) => {
    let d1, d2;

    // line 1
    for (let i = 0; i < lines[0].length; i++) {
        let td1 = findFirstIntersectionWithPoint(lines[0][i], [ax, ay]);
        if (td1) {
          d1 = td1;
          break;  
        } 
    }
    // line 2
    for (let i = 0; i < lines[1].length; i++) {
        let td2 = findFirstIntersectionWithPoint(lines[1][i], [ax, ay]);
        if (td2) {
          d2 = td2;
          break;  
        } 
    }
    // star 2 demands a sum of these numbers...
    return d1 + d2;
  });

  // sort...
  firstVisit.sort((a, b) => a - b);
  console.log(firstVisit[0]);
  return `Done in ${performance.now() - start}`
}