DEV Community

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

View post
Collapse
 
savagepixie profile image
SavagePixie •

There's got to be some better way to go about it, as even with memoisation it takes about half a minute to sort through part one, but hey, memoisation is cool.

JavaScript

const findElement = (input, tag) => input.filter(x => x.split(')')[1] == tag)

const getOrbits = (input, element, orbits=1) => {
    if (!getOrbits.checkedOrbits) getOrbits.checkedOrbits = {}

    const [ centre, object ] = element.split(')')
    if (centre == 'COM') {
        getOrbits.checkedOrbits[object] = 1
        return orbits
    }
    if (getOrbits.checkedOrbits.hasOwnProperty(centre)) {
        getOrbits.checkedOrbits[object] = getOrbits.checkedOrbits[centre] + 1
        return orbits + getOrbits.checkedOrbits[centre]
    }
    const [ nextObject ] = findElement(input, centre)
    return getOrbits(input, nextObject, orbits + 1)
}

const getOrbitChain = (input, element, chain=[]) => {
    const [ centre, object ] = element.split(')')
    const newChain = chain.concat(centre)
    if (centre == 'COM') return newChain
    const [ nextObject ] = findElement(input, centre)
    return getOrbitChain(input, nextObject, newChain)
}

const calculateTransfers = (input, origin, destination) => {
    const fromYou = getOrbitChain(input, origin)
    const fromDest = getOrbitChain(input, destination)
    const commonObject = fromYou.filter(x => fromDest.includes(x))[0]
    return fromYou.indexOf(commonObject) + fromDest.indexOf(commonObject) - 2
}

module.exports = input => {
    const data = input.split('\n')
    const partOne = data.reduce((a, b) => a + getOrbits(data, b), 0)
    const partTwo = calculateTransfers(data, 'YOU', 'SAN')
    return({ partOne, partTwo })
}
Collapse
 
jbristow profile image
Jon Bristow • • Edited

Unsolicited hints from a fellow 2+ minute initial runtime maker:

  • Make sure your culling is working properly,
  • only keep the minimum info you need for each loop pass
  • meditate on the implications of “every object orbits around one other object.”
Collapse
 
savagepixie profile image
SavagePixie • • Edited

You're absolutely right. I've changed the approach and with this I managed to reduce the processing time from 43.3 seconds to 2.6:

const calculateOrbits = (input, centre, orbits=0) => {
    const objects = input.filter(x => x.split(')')[0] == centre)
    return objects. length == 0
        ? orbits
        : objects.reduce((a, b) => a + calculateOrbits(input, b.split(')')[1], orbits + 1), orbits)
}

const calculateTransfers = (input, origin, destination) => {
    const fromYou = getOrbitChain(input, origin)
    const fromDest = getOrbitChain(input, destination)
    const commonObject = fromYou.filter(x => fromDest.includes(x))[0]
    return fromYou.indexOf(commonObject) + fromDest.indexOf(commonObject) - 2
}

const findElement = (input, tag) => input.filter(x => x.split(')')[1] == tag)

const getOrbitChain = (input, element, chain=[]) => {
    const [ centre, object ] = element.split(')')
    const newChain = chain.concat(centre)
    if (centre == 'COM') return newChain
    const [ nextObject ] = findElement(input, centre)
    return getOrbitChain(input, nextObject, newChain)
}

module.exports = input => {
    const data = input.split('\n')
    const partOne = calculateOrbits(data, 'COM')
    const partTwo = calculateTransfers(data, 'YOU', 'SAN')
    return({ partOne, partTwo })
}