DEV Community

Discussion on: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

Collapse
 
maxart2501 profile image
Massimo Artizzu • Edited

Finally a nice and short one.

My solutions aren't particularly efficient as they involve recursive functions, but still run pretty fast so whatever. ¯\_(ツ)_/¯

Part 1

const starMap = input.split('\n').reduce((map, line) => {
  map[line.split(')')[1]] = line.split(')')[0];
  return map;
}, {});

const getAncestorCount = body => body in starMap ? 1 + getAncestorCount(starMap[body]) : 0;

console.log(Object.keys(starMap).reduce((sum, body) => sum + getAncestorCount(body), 0));

Part 2

// starMap defined as above...
const getAncestors = body => body in starMap ? [ ...getAncestors(starMap[body]), starMap[body] ] : [];

const youAncestors = getAncestors('YOU');
const santaAncestors = getAncestors('SAN');

const transfers = youAncestors
  .filter(body => santaAncestors.includes(body))
  .map(body => [
    // .reverse is actually not necessary...
    ...youAncestors.slice(youAncestors.indexOf(body)).reverse(),
    // + 1 because we'd include the common planet twice
    ...santaAncestors.slice(santaAncestors.indexOf(body) + 1)
  ]);

// - 1 because we're counting the movements, not the positions
console.log(Math.min(...transfers.map(xfer => xfer.length - 1)));

You can find my solutions on GitHub.

Collapse
 
jbristow profile image
Jon Bristow

Maybe a future node version will add tail call optimization, and Javascript could have efficient recursion again.

Tail recursive functions are so much clearer to me than a while loop... something about walking down to a trivial solution just makes sense. 🤷‍♀️

Collapse
 
maxart2501 profile image
Massimo Artizzu

I long the day they will tackle the problem once and for all. It's the last thing missing from ES2015! (Only Safari supports it.)