Discussion on: Advent of Code 2019 Solution Megathread - Day 10: Monitoring Station

View post

Things are getting complicated now! I like it!

In the first part I tried an arithmetic approach, trying to find - for each asteroid - if there was another one in line with the target location. JavaScript as usual:

const PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; // Enough primes...
const spaceMap = input.trim().split('\n');

const asteroids = new Set();
spaceMap.flatMap((line, row) => {
  line.split('').forEach((char, column) => {
    if (char === '#') {
      asteroids.add(column + ',' + row);
    }
  });
});

function simplifyFraction(numerator, denominator) {
  for (const prime of PRIMES) {
    while (numerator % prime === 0 && denominator % prime === 0) {
      numerator /= prime;
      denominator /= prime;
    }
  }
  return [numerator, denominator];
}

function countVisibile(coords, _, astArray) {
  const [ row, column ] = coords.split(',').map(Number);
  const visible = astArray.filter(astCoords => {
    if (astCoords !== coords) {
      const [ astRow, astColumn ] = astCoords.split(',').map(Number);
      const diffRow = astRow - row;
      const diffColumn = astColumn - column;
      const [ baseColumn, baseRow ] = simplifyFraction(diffColumn, diffRow);
      let checkRow = row + baseRow;
      let checkColum = column + baseColumn;
      while (checkRow !== astRow || checkColum !== astColumn) {
        if (asteroids.has(checkColum + ',' + checkRow)) {
          break;
        }
        checkRow += baseRow;
        checkColum += baseColumn;
      }
      return checkRow === astRow && checkColum === astColumn;
    }
  });
  return visible.length;
}

const asteroidCounts = [ ...asteroids ].map(countVisibile);

console.log(Math.max(...asteroidCounts));

The second part showed that it would have been too complex. So I just converted all the coordinates in polar, sorted them out and counted to the 200th asteroid. Finally, converted back to orthogonal coordinates:

// `asteroids` defined as above...
const stationRow = 29;
const stationColumn = 23;

const polarCoords = new Map();
asteroids.forEach(([ column, row ]) => {
  if (column === stationColumn && row === stationRow) {
    return;
  }
  const diffColumn = stationColumn - column;
  const diffRow = stationRow - row;
  const theta = (Math.atan2(diffColumn, -diffRow) + Math.PI) % (Math.PI * 2);
  const rho = Math.sqrt(diffColumn ** 2 + diffRow ** 2);
  if (polarCoords.has(theta)) {
    polarCoords.get(theta).add(rho);
  } else {
    polarCoords.set(theta, new Set([ rho ]));
  }
});

function* getTargets() {
  const sortedAngles = new Set([ ...polarCoords.keys() ].sort((a, b) => a - b));
  while (sortedAngles.size) {
    for (const theta of sortedAngles) {
      const rhos = polarCoords.get(theta);
      if (rhos.size === 1) {
        sortedAngles.delete(theta);
        yield [theta, ...rhos];
      } else {
        const nearest = Math.min(...rhos);
        rhos.delete(nearest);
        yield [theta, nearest];
      }
    }
  }
}

function toOrtho(theta, rho) {
  return [
    stationColumn + Math.round(Math.sin(theta) * rho),
    stationRow - Math.round(Math.cos(theta) * rho)
  ]
}

const targets = getTargets();
let value;
for (let i = 0; i < 200; i++) {
  ({ value } = targets.next());
}
const [ resColumn, resRow ] = toOrtho(...value);
console.log(resColumn * 100 + resRow);