DEV Community

Jon Bristow

Posted on

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

Day 18 - The Problem

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

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

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.

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.

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...

Joana Borges Late

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

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()

}

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

function processInput() {

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()

``````