DEV Community

Cover image for Advent of Code 2019 Solution Megathread - Day 18: Many-Worlds Interpretation
Jon Bristow
Jon Bristow

Posted on

Advent of Code 2019 Solution Megathread - Day 18: Many-Worlds Interpretation

Welp, it's time for the A Stars to get to work.

Day 18 - The Problem

Our run-in with the space police earlier was a dread foreshadowing!

Passing Triton, we've been pulled into some sort of base or prison and need to escape. Lets pick up the keys (which are helpfully all color coded).

Part 1 is to find the most efficient way to get all the keys and report their order.

Part 2 has to wait, since Tuesday is my nerd night out.

Ongoing Meta

Dev.to List of Leaderboards

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Top comments (3)

Collapse
 
neilgall profile image
Neil Gall

While I'm sure there's a fast solution to day 16 part 2, I find fiddly numeric algorithms quite frustrating and my laptop at home is still running a brute-force solution 36 hours on. Day 17 part 1 was straightforward (mainly because it doesn't matter which way you follow a loop in the path so an effective strategy is to go straight ahead at every intersection) but part 2 seems to involve a depth-first search for the possible routes with another depth-first search to find a data compression candidate. Day 18 part 1 is another complex search.

I want to solve these problems and I want to do them well, not just find any old solution that gets me the stars. Hopefully that's evident in some of my earlier solutions which have tests and what I believe to be well-structured code, rather than a dense set of nested for loops iterating over a tuple-of-maps-of-lists-of data structure. The first two weeks of AoC 2019 were fun and mostly small enough to do in an hour or two, then optimise or improve if you have more time. The problems since day 16 are too hard to solve well in a single day. If you have other commitments (a job, kids, Christmas parties!) it's impossible. This, a bit of burn-out and Ben Lovy's post the other day have made me reconsider racing through AoC.

I hope to finish AoC 2019 but I feel I've already let the quality slip and that gives me no joy. I'll post solutions as I get them, even if that means I'm still thinking about how to help the elves when I'm sitting in the garden in the summer sun.

Collapse
 
jbristow profile image
Jon Bristow • Edited

No need to apologize for doing what’s right for your health (mentally, spiritually, physically)! There are NO PRIZES or deadlines, so I encourage everyone to solve these at your leisure.

I’ll be watching these threads and the category tag, so I’m looking forward to see more people’s solutions.

My only hint: any solution that requires more than a minute or two to run is probably not the intended solution.

Also also: yesterday’s problem was most likely meant to be solved by hand for the middle portion. There was only 20-30 instruction pairs in my set...

Collapse
 
joanablate profile image
Joana Borges Late

I got the solutions for parts 1 and 2 (260ms each) in vanilla JavaScript:

github.com/JoanaBLate/advent-of-co...

Below goes part 1:

"use strict"

// solving the puzzle takes (my computer) 0.260s

const map = [ ]

var WIDTH = 0
var HEIGHT = 0

var homeRow = 0
var homeCol = 0

var numberOfKeys = 0

const NODES = new Array(128) // 'z' is 122 // has blanks!

const GROUPS = { } // for performance

var bestDistance = 999999


function main() {

    processInput()

    fillNodes() // also gets home and numberOfKeys and fills GROUPS

    findBestDistance()

    console.log("the answer is", bestDistance)
}

///////////////////////////////////////////////////////////

function processInput() {

    const input = Deno.readTextFileSync("input.txt").trim()

    const lines = input.split("\n")

    for (const line of lines) { map.push(line.trim()) }

    WIDTH = map[0].length
    HEIGHT = map.length
}

///////////////////////////////////////////////////////////

function fillNodes() { // also gets home and numberOfKeys

    for (let row = 0; row < HEIGHT; row++) {

        for (let col = 0; col < WIDTH; col++) {

            const item = map[row][col]

            if (item == ".") { continue }
            if (item == "#") { continue }

            if (item == "@") { homeRow = row; homeCol = col; continue } // '@' is not a node, just the starting position

            if (item >= "a"  &&  item <= "z") { numberOfKeys += 1; GROUPS[item] = [ ] }

            NODES[item.charCodeAt(0)] = explore(row, col)
        }
    }
}

///////////////////////////////////////////////////////////

function explore(row, col) {

    const myTrips = [ ]

    let futurePoints = [ createPoint(row, col) ]

    const walkTable = new Uint8Array(WIDTH * HEIGHT)    

    const index = row * WIDTH + col

    walkTable[index] = 1

    let distance = 0

    while (true) {

        const currentPoints = futurePoints

        futurePoints = [ ]

        for (const point of currentPoints) {

            const row = point.row
            const col = point.col

            grabNeighbor(row-1, col)
            grabNeighbor(row+1, col)
            grabNeighbor(row, col-1)
            grabNeighbor(row, col+1)            
        }

        if (futurePoints.length == 0) { return myTrips }

        distance += 1
    }

    function grabNeighbor(row, col) {

        if (row < 0) { return }
        if (col < 0) { return }

        if (row >= HEIGHT) { return }
        if (col >= WIDTH)  { return }

        const index = row * WIDTH + col

        if (walkTable[index] == 1) { return }

        walkTable[index] = 1 // touched

        const symbol = map[row][col] 

        if (symbol == "#") { return }

        const point = createPoint(row, col)

        if (symbol == ".") { futurePoints.push(point); return }

        if (symbol == "@") { futurePoints.push(point); return }

        myTrips.push(createNode(symbol, distance + 1))

        if (symbol >= "A"  &&  symbol <= "Z") { return }

        futurePoints.push(point)        
    }
}

///////////////////////////////////////////////////////////

function findBestDistance() {

    const allKeys = Object.keys(GROUPS)

    const startingTrips = explore(homeRow, homeCol)

    let futurePaths = [ ]

    for (const trip  of startingTrips) {

        if (trip.destiny < "a"  ||  trip.destiny > "z") { continue }

        const n = trip.destiny.charCodeAt(0) - "a".charCodeAt(0)

        const trekCode = Math.pow(2, n)

        const path = createPath(trip.destiny, trip.distance, trekCode)

        futurePaths.push(path)    
    }
    //

    while (futurePaths.length > 0) {

        const currentPaths = futurePaths

        for (const key of allKeys) { GROUPS[key] = [ ] }

        for (const path of currentPaths) {

            if (path.trek.length == numberOfKeys) {

                if (path.distance < bestDistance) { bestDistance = path.distance }

                continue
            }

            const trips = walkNodes(path.trek)

            for (const trip of trips) {

                const trek = path.trek + trip.destiny

                const distance = path.distance + trip.distance

                const n = trip.destiny.charCodeAt(0) - "a".charCodeAt(0)

                const trekCode = path.trekCode + Math.pow(2, n)

                includeInGroupOrNot(trek, distance, trekCode, GROUPS[trip.destiny])
            }
        }

        futurePaths = [ ]

        for (const key of allKeys) {

            const group = GROUPS[key]

            for (const node of group) { futurePaths.push(node) }
        }        
    }
}

///////////////////////////////////////////////////////////

function includeInGroupOrNot(trek, distance, trekCode, group) {

    // checking through small groups is far more efficient than
    // checking each candidate path against all future paths!

    for (const path of group) {

        if (path.trekCode != trekCode) { continue }

        if (path.distance <= distance) { return } // the candidate is not better

        // replacing old data with candidate's data
        path.trek = trek
        path.distance = distance
        return
    }

    group.push(createPath(trek, distance, trekCode))           
}  

///////////////////////////////////////////////////////////

function createPoint(row, col) {

    return { "row": row, "col": col }
}

function createNode(destiny, distance) {

    return { "destiny": destiny, "distance": distance }
}

function createPath(trek, distance, trekCode) {

    return { "trek": trek, "distance": distance, "trekCode": trekCode }
}

///////////////////////////////////////////////////////////

function walkNodes(trek) { 

    const NOT_VISITED = 999999

    const home = trek.at(-1)

    const distances = new Uint32Array(128) // z is 122

    for (let n = 0; n < 128; n++) { distances[n] = NOT_VISITED } 

    distances[home.charCodeAt(0)] = 0 

    let newKeys = ""

    let futureNodes = [ createNode(home, 0) ]

    while (true) {

        const currentNodes = futureNodes

        futureNodes = [ ]

        if (currentNodes.length == 0) {

            const result = [ ]

            for (const key of newKeys) { 

                const distance = distances[key.charCodeAt(0)]

                result.push(createNode(key, distance))
            }
            return result
        }

        for (const node of currentNodes) {

            const trips = NODES[node.destiny.charCodeAt(0)]

            for (const trip of trips) {

                const destiny = trip.destiny

                const index = destiny.charCodeAt(0)

                const distance = node.distance + trip.distance

                if (distances[index] == NOT_VISITED) { 

                    distances[index] = distance 
                }
                else if (distance < distances[index]) {

                     distances[index] = distance
                }
                else {

                     continue
                }

                if (destiny >= "a"  &&  destiny <= "z") {

                    if (trek.includes(destiny)) { continue }

                    if (newKeys.includes(destiny)) { continue }

                    newKeys += destiny; continue // not going forward
                }

                // it is a door

                const neededKey = destiny.toLowerCase()

                if (! trek.includes(neededKey)) { continue } // locked door

                futureNodes.push(createNode(destiny, distance))
            }
        }
    }       
}

main()

Enter fullscreen mode Exit fullscreen mode