2019-12-18

# Day 18: Many-Worlds Interpretation

Description:
--- Day 18: Many-Worlds Interpretation ---

As you approach Neptune, a planetary security system detects you and activates a giant tractor beam on Triton! You have no choice but to land.

A scan of the local area reveals only one interesting feature: a massive underground vault. You generate a map of the tunnels (your puzzle input). The tunnels are too narrow to move diagonally.

Only one entrance (marked @) is present among the open passages (marked .) and stone walls (#), but you also detect an assortment of keys (shown as lowercase letters) and doors (shown as uppercase letters). Keys of a given letter open the door of the same letter: a opens A, b opens B, and so on. You aren't sure which key you need to disable the tractor beam, so you'll need to collect all of them.

For example, suppose you have the following map:

#########
#b.A.@.a#
#########

Starting from the entrance (@), you can only access a large door (A) and a key (a). Moving toward the door doesn't help you, but you can move 2 steps to collect the key, unlocking A in the process:

#########
#b.....@#
#########

Then, you can move 6 steps to collect the only other key, b:

#########
#@......#
#########

So, collecting every key took a total of 8 steps.

Here is a larger example:

########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################

The only reasonable move is to take key a and unlock door A:

########################
#f.D.E.e.C.b.....@.B.c.#
######################.#
#d.....................#
########################

Then, do the same with key b:

########################
#f.D.E.e.C.@.........c.#
######################.#
#d.....................#
########################

...and the same with key c:

########################
#f.D.E.e.............@.#
######################.#
#d.....................#
########################

Now, you have a choice between keys d and e. While key e is closer, collecting it now would be slower in the long run than collecting key d first, so that's the best choice:

########################
#f...E.e...............#
######################.#
#@.....................#
########################

Finally, collect key e to unlock door E, then collect key f, taking a grand total of 86 steps.

Here are a few more examples:

########################
#...............b.C.D.f#
#.######################
#.....@.a.B.c.d.A.e.F.g#
########################

Shortest path is 132 steps: b, a, c, d, f, e, g

#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

Shortest paths are 136 steps;
one is: a, f, b, j, g, n, h, d, l, o, e, p, c, i, k, m

########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################

Shortest paths are 81 steps; one is: a, c, f, i, d, g, b, e, h

How many steps is the shortest path that collects all of the keys?

--- Part Two ---

You arrive at the vault only to discover that there is not one vault, but four - each with its own entrance.

On your map, find the area in the middle that looks like this:

...
.@.
...

@#@
###
@#@

This change will split your map into four separate sections, each with its own entrance:

####### #######
#a.#Cd# #a.#Cd#
##...## ##@#@##
##.@.## --> #######
##...## ##@#@##
#cB#Ab# #cB#Ab#
####### #######

Because some of the keys are for doors in other vaults, it would take much too long to collect all of the keys by yourself. Instead, you deploy four remote-controlled robots. Each starts at one of the entrances (@).

Your goal is still to collect all of the keys in the fewest steps, but now, each robot has its own position and can move independently. You can only remotely control a single robot at a time. Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key or door is found.

For example, in the map above, the top-left robot first collects key a, unlocking door A in the bottom-right vault:

#######
#@.#Cd#
##.#@##
#######
##@#@##
#cB#.b#
#######

Then, the bottom-right robot collects key b, unlocking door B in the bottom-left vault:

#######
#@.#Cd#
##.#@##
#######
##@#.##
#c.#.@#
#######

Then, the bottom-left robot collects key c:

#######
#@.#.d#
##.#@##
#######
##.#.##
#@.#.@#
#######

Finally, the top-right robot collects key d:

#######
#@.#.@#
##.#.##
#######
##.#.##
#@.#.@#
#######

In this example, it only took 8 steps to collect all of the keys.

Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple keys to be collected:

###############
#d.ABC.#.....a#
######@#@######
###############
######@#@######
#b.....#.....c#
###############

First, the top-right, bottom-left, and bottom-right robots take turns collecting keys a, b, and c, a total of 6 + 6 + 6 = 18 steps. Then, the top-left robot can access key d, spending another 6 steps; collecting all of the keys here takes a minimum of 24 steps.

Here's a more complex example:

#############
#DcBa.#.GhKl#
#.###@#@#I###
#e#d#####j#k#
###C#@#@###J#
#fEbA.#.FgHi#
#############

Top-left robot collects key a.
Bottom-left robot collects key b.
Top-left robot collects key c.
Bottom-left robot collects key d.
Top-left robot collects key e.
Bottom-left robot collects key f.
Bottom-right robot collects key g.
Top-right robot collects key h.
Bottom-right robot collects key i.
Top-right robot collects key j.
Bottom-right robot collects key k.
Top-right robot collects key l.

In the above example, the fewest steps to collect all of the keys is 32.

Here's an example with more choices:

#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba@#@BcIJ#
#############
#nK.L@#@G...#
#M###N#H###.#
#o#m..#i#jk.#
#############

One solution with the fewest steps is:

Top-left robot collects key e.
Top-right robot collects key h.
Bottom-right robot collects key i.
Top-left robot collects key a.
Top-left robot collects key b.
Top-right robot collects key c.
Top-left robot collects key d.
Top-left robot collects key f.
Top-left robot collects key g.
Bottom-right robot collects key k.
Bottom-right robot collects key j.
Top-right robot collects key l.
Bottom-left robot collects key n.
Bottom-left robot collects key m.
Bottom-left robot collects key o.

This example requires at least 72 steps to collect all keys.

After updating your map and using the remote-controlled robots, what is the fewest steps necessary to collect all of the keys?

Input:
#################################################################################
#........h#..........t..#...#.#e........#.............#.....#....g..#...........#
#.#######.#.#####.#####.#.#.#.#.#.#####.#.###########.#.#.###.#####.#.#.#.#####.#
#.#.....#.#.#.#...#.#...#.#.#...#.#.#...#...#.....#...#.#.....#..l#...#.#.#...#.#
#.#.###.#.#.#.#.###.#.###.#.#####.#.#.###.#.#.###.###.#####.###.#.#####.###.#.#.#
#.#.#.#.#.....#.#.........#.......#...#.#.#.#.#.#...#.....#...#.#.....#.....#.#.#
#.#.#.#.#######.###################.###.#.#.#.#.###.#####.###.#.#####.#######.#.#
#.#.#.#...#...#.........#.....#...#.#...#.#.......#.#.....#...#.#...#...#.....#.#
###I#.###.#.#.#########.#.###.#.#.#.#.#.#########.#.#####.#.###.#.#.###.#.#####.#
#...#...#.#.#.........#.#.#.#...#...#.#.#.....#...#.....#.#.#...#.#...#...#...#.#
#.###.#.#.#.#########.#.#.#.#########.#.#Q###.#.#######.#.###.#######.#######.#.#
#...#.#.....#...#.......#.#...........#.#.#...#.....#...#.....#.....#.........#.#
###.#########.#.#########.#####.###.###.#.#.#########.#######.#.###.###.###.###.#
#...#...#...#.#.........#.....#.#...#...#.#.........#.#...#...#.#.#...#.#.#.#...#
#.###.#.#.#.#.#########.#####.#.#.#####.#.#########.#.#.#.#.###.#.###.#.#.#.#.###
#.....#...#.#...#.....#...#.#.#.#.#...#.#...#.....#...#.#.#.#...#.....#...#...#.#
#.#########.###.#.#######.#.#.#.#.#.#.#.#.#.#.#########.###.#.#.#####.###.#####.#
#.#.....#.#.#.....#.......#...#.#...#.#.#.#.#.........#.....#.#.#...#.#.......#.#
#Z#.#.#.#.#.#.#####.#######.###C#####.#.###.#.#######.#.#####.###.#.#.#######.#.#
#.#.#.#...#.....#.D.#.....#.#.......#.#.#...#.#...#.#...#...#...#.#.#.....#...#.#
#.###.###.#######.###S###.#.#########.###.###.#.#.#.#####.#####.#.#.#####.###.#.#
#.#..u#...#j#...#...#.#...#.........#...#.#.#...#...#.......#.#...#.....#...#.#.#
#.#.###.###.#.#.#.#.###.###########.###.#.#.#######.#######.#.#.#######.###.#.#.#
#...#.......#r#.#.#...#...#.......#.....#.#...#...#.........#.#.......#.#.#.#...#
#.#####.#####.#.#.#.#.###.#.###.#.#####.#.###.#.#.###.#######.#########.#.#.###.#
#.#...#.#...#.#.#.#.#...#.#...#.#.#.....#...#...#.....#.....#...........#...#...#
###.#.###.#.#.#.###.#####.###.#.###.#####.#.#####.#####.###.#############.#####.#
#...#.....#...#...W.#...#s..#.#.....#...#.#.....#.#.....#..y..#.....#.....#...#.#
#F#################.#.#.###.#.#######.#.#.#####.###.#####.###.#.###.#.#####.#.#.#
#.........#.........#.#.B...#...#...#.#.#.....#.....#.#...#...#.#.#.#.......#.#.#
#####.###.###########.#########.#.#.#.#.#####.#######.#.#######.#.#.#########.###
#...#..v#...#.........#.......#...#.#.#.#.....#a......#...........#.#.....#.#...#
#.#.#######.#.#########.#####.#####.#.#.#.###########.#############.#.#.#.#.###.#
#.#.........#.#...#...#.....#.#...#.#.#.#.......#.....#..m......#...#.#.#...#...#
#.###########.#.#.###.#####.#.#.#.#.#.#########.#.###.#.#######.#.#.#.#.#####.###
#p....#n......#.#.........#.#...#...#...#.....#...#...#.#.......#.#.#.#x#.....#.#
#.###.#.#######.#########.#.#########.#.#.#.#.#####.#####.#####.#.###.#.#.#####.#
#.#.#.#.#.....#.....O...#.#.#.......#.#.#.#.#...#...#...#...#.#.#.#...#...#.....#
#.#.#.#.#.#####.#######.###.#####.#.###.#.#.#####.###.#.###.#.#.#.#.#########.#.#
#...#...#.............#...........#.......#..o........#.....#...#.............#.#
#######################################.@.#######################################
#q......M.............#.....#.....#.#.........#...#..w..........#.#.....#.......#
#######.#####.#######.#.#.#.#.###.#.#.#.#.###.###.#.###########.#.#.#.#.#####.#.#
#.....#...#...#.....#.#.#.#.#.#.#.#...#.#...#.....#...#...#...#.#...#.#...J...#.#
#.###.#####.###.#####.#.#.#.#.#.#.#####.###.#####.###.#.#.#.#.#.#####.#########.#
#.#.#.#.....#.......#.#.#.#...#.#.......#...#.#...#.#...#...#.#.......#.....#.#.#
#.#.#.#.###########.#.###.#####.#######.#.###.#.###.#########.#######.#.###V#.#.#
#.#...#.#...........#.....#.......#.....#.#...#.#.....#.#.R...#...#.#.#.#...#.#.#
#.#.###.#.###.#####.#######.###.#.#.#####.#.###.#.###.#.#.###.#.#.#.#.#.#.###U#.#
#.#.....#...#...#.#.#.......#.#.#.#.#...#.#...#...#.#.#.#...#.#.#.#..d#.#...#...#
#.#########.###.#.#.#.#######.#.#.#.###.#.#.#.#####.#.#.###.###.#.#####.###.#.###
#.#...#.......#.#...#...#.....#.#.#.#...#.#.#.#...........#....f#.......#.P.#...#
#.#.#.#########.#.#####.#.#####.#.#.#.###.#.#.#.#######.###########.#####.#####.#
#.Y.#.......#...#.....#.#...#...#.#.#...#.#.#...#.#...#.#.....#...#...#...#...#.#
#.#########.#.#####.###.###.#.###.#.###.#.#.#####.#.#.###.###.#.#.#####.###.###.#
#.#...#.....#.#.....#...#...#...#.#...#.#.#.#.....#.#.....#...#.#.......#...#...#
#.#.#.#.#####.#.#####.###.#.###.#####.#.#.#.#.###.#.#######.###N#########.###.###
#...#.#.#...#.#.....#...#.#...#.....#.#.#.#...#...#...#.....#...#.#.........#...#
#####.#.#.#.#.#########.#.###.#####.#.#.#.#####.#####.#.###.#.###.#.#######.###.#
#...#.#...#.#.............#.....#...#...#.#...#...#...#...#.#.#...#...#...#..z#.#
#K###.#####.#.###################.#####.#.#.#.###.#.#####.#.#.#.#.###.#.#.#.#.#.#
#.....#...#.#.#.....#.....#.....#.....#.#.#.#...#.#...#...#.#b#.#...#...#.#.#.#.#
#####.#.###.#.#####.#####.#.###.#####.#.#.#.###.###.###.###.#######.#####.#.###.#
#...#.#.#...#...#.......#...#.#.....#.#.#...#.#.#...#...#.........#...#...#.....#
#.#.#.#.#.#####.#.#####.#####.#####.#.#.#.###.#.#.###.###########.#.#.#.#########
#.#.#...#.#...#...#...#...#.#...#...#...#.#.A.#.....#.....#..k..#.#.#.#.#.......#
#.#.#####.###.#####.#####.#.#.#.#.###.###.###.#######.###.#####.#.#.###.#.#######
#.#.......#.......#.....#.#...#.#...#...#.......#...#.#.#.....#...#.#...#.......#
#X#########.#####.#.###.#.#####.###.#####.#######.#.#.#.#####.#.###.#.###.#####.#
#.....#.......#...#.#.#.#...#.....#.....#.#.......#.#...#.....#...#.#...#.....#.#
#####.#.#####.#.###.#.#.###.#.#########.###.#######.###.#.#######.#.###.#.#####.#
#.....#...#...#...#.#.#.....#.#...#.....#...#.....#.#...#.#.#.....#...#.#.#...#.#
#.#######.#.#######.#.#######.#.#.#.#####.#####.###.#####.#.#.#####.#.#.###.#.#.#
#.......#.#.............#.....#.#...#...#.....#.......#...#...#.....#.#.....#.#.#
#.#####.###############.#.###.#.#####.#.#.###.#######.#.###.#######.#.#######.#.#
#.#.....#...T.....#...#.#.#...#.....#.#.#...#.......#...#......c....#.......#...#
###.###.#.#######.#H#.#.#.#.#######.#.#####.#######.#####.#####.###############.#
#...#...#.#.#.....#.#.#...#...#.....#...#...#.E...#...#...#...#.#.......#.......#
#.#######.#.#.#####.#.#########.#######.#.###.###.###.#####.#.###.#####.#.#######
#.....L.....#.......#.............G..i..#.....#.....#.......#.........#.........#
#################################################################################

Part 1:
``````namespace AdventOfCode2019_18_1
{
const DAY     = 18;
const PROBLEM = 1;

export async function run()
{
if (input == null) return;

let grid = input
.trim()
.split(new RegExp('\r?\n'))
.filter(p => p.trim().length > 0)
.map(p => p.trim().split('').map(q => q.charCodeAt(0)) );

let str = "";
for(let line of grid)
{
str += line.map(p =>
{
if (p == 46) return " ";
if (p == 35) return "\u2591";
return String.fromCharCode(p);
}).reduce((a,b)=>a+b)+"\n";
}

let map = new AOCMap(grid);

await map.dump();

await createReachabilityMap(map, "@", map.start, 0);
for(let i=0;i<26;i++) await createReachabilityMap(map, String.fromCharCode(i+97), map.keys[i], 1);

await map.dump();

let best_path = (await findPaths(map))!;

await map.dump();

AdventOfCode.outputConsole(best_path[0] + " (" + map.getPathLength(best_path[1]) + ") --> " + best_path[1]);

}

async function createReachabilityMap(map: AOCMap, letter:string, pos: [number, number], dumpmode: number)
{
let quadrant: {[_:string]: [number, number]} = {};
for(let i=0;i<26;i++)
{
quadrant[String.fromCharCode(i+97)] = [ Math.sign(map.keys[i][0] - map.start[0]), Math.sign(map.keys[i][1] - map.start[1]) ];
}

const no_doors = new Array<boolean>(26).fill(false);
map.reachability.set("@>@", [0, no_doors]);
for(let i=0;i<26;i++) map.reachability.set(String.fromCharCode(i+97)+">"+String.fromCharCode(i+97), [0, no_doors]);

let visited_map: { [_:number]: number } = {};

let next: [number, number, boolean[], string[] ][] = []; // x, y, currently_passed_doors, currently_found_keys
next.push([pos[0], pos[1], no_doors, ['@']]);

let counter = 0;

if (dumpmode===0 || dumpmode===1) await map.dumpWithFillAndNext(visited_map, next);

for(;;)
{
let ls = next.slice();
next = [];

for(let pos of ls)
{
const x = pos[0];
const y = pos[1];

let currently_passed_doors: boolean[] = pos[2];
let currently_found_keys: string[]    = pos[3];

const i = (y*10000000 + x);
if (i in visited_map) { if (visited_map[i] < counter && visited_map[i]>4) throw "loop in map :("; continue; }

visited_map[i] = counter;

if (map.iskey([x,y]))
{
const key1 = letter;
const key2 = String.fromCharCode(map.get([x, y]));

{
let dist = counter;
const keys = currently_passed_doors;

//if (key1 !== "@" && key2 !== "@")
//{
//
//	if (q1[0]*q2[0]*q1[1]*q2[1] === -1) dist -= 2; // big middle area
//}

map.reachability.set(key1+">"+key2, [ dist, keys ]);
map.reachability.set(key2+">"+key1, [ dist, keys ]);

AdventOfCode.outputConsole("Add reachability ("+key1+" <-> " + key2 + ") == " + dist);

if (dumpmode===1) await map.dumpWithFillAndNext(visited_map, next);
}

currently_found_keys = currently_found_keys.slice();
currently_found_keys.push(key2);
}
else if (map.isdoor([x,y]))
{
const v = map.get([x, y]);
currently_passed_doors = currently_passed_doors.slice();
currently_passed_doors[v-65] = true;
}

if (map.iswalkable([x-1, y]) && !(((y  )*10000000 + (x-1)) in visited_map)) next.push([x-1, y, currently_passed_doors, currently_found_keys]);
if (map.iswalkable([x+1, y]) && !(((y  )*10000000 + (x+1)) in visited_map)) next.push([x+1, y, currently_passed_doors, currently_found_keys]);
if (map.iswalkable([x, y-1]) && !(((y-1)*10000000 + (x  )) in visited_map)) next.push([x, y-1, currently_passed_doors, currently_found_keys]);
if (map.iswalkable([x, y+1]) && !(((y+1)*10000000 + (x  )) in visited_map)) next.push([x, y+1, currently_passed_doors, currently_found_keys]);
}

if (dumpmode===0) await map.dumpWithFillAndNext(visited_map, next);

counter++;
}

await map.dumpWithFill(visited_map);

return;
}

async function findPaths(map: AOCMap): Promise<[number, string]|null>
{
let queue: [string, boolean[], number, number, string][] = []; // < pos, keys, key_count, path_len, path >

queue.push(["@", new Array<boolean>(26).fill(false), 0, 0, ""]);

let best_result: [number, string]|null = null;

let seen = new Set<string>();

for(let ctr=1;;ctr++)
{

let [ pos, keys, key_count, path_len, path ] = queue.shift()!;

let hskey = pos+keys.map(p=>p?1:0).join()+""+path_len;
if (seen.has(hskey)) continue;

if (ctr %  100 === 0) AdventOfCode.outputConsole("[INTERMED] ["+path_len+"] " + path);
if (ctr %  500 === 0) await AdventOfCode.sleep(0);

if (key_count === 26)
{
if (best_result === null || best_result[0]>path_len)
{
best_result = [path_len, path];
AdventOfCode.outputConsole("[RESULT] ["+path_len+"] ==== " + path);
//return [path_len, path];
}
}

if (best_result !== null && best_result[0] < path_len) return best_result;

let reachable = "abcdefghijklmnopqrstuvwxyz"
.split('')
.filter(p => !keys[p.charCodeAt(0)-97])
.filter(p => map.isreachable(pos, p, keys))
.map(p => [p, map.reachability.get(pos+">"+p)![0]] as [string, number] )
.sort((a,b) => a[1] - b[1])
;

for(const [nextkey, steplen] of reachable)
{
let keys_copy = keys.slice();
keys_copy[nextkey.charCodeAt(0)-97]=true;

if (best_result!==null && best_result[0] < path_len+steplen) continue;

array_insert(queue, [nextkey, keys_copy, key_count+1, path_len+steplen, path+nextkey]);
//queue.push([nextkey, keys_copy, key_count+1, path_len+steplen, path+nextkey]);
//queue.sort((a, b) => b[3] - a[3] );
}

if (queue.length===0) break;
}

return best_result;

}

function array_insert(array: [string, boolean[], number, number, string][], element: [string, boolean[], number, number, string])
{
function sortedIndex(array: [string, boolean[], number, number, string][], value: [string, boolean[], number, number, string])
{
var low = 0, high = array.length;

while (low < high) {
var mid = (low + high) >>> 1;
if (array[mid][3] < value[3]) low = mid + 1;
else high = mid;
}
return low;
}

array.splice(sortedIndex(array, element) + 1, 0, element);
return array;
}

function key_except(base: boolean[], exc: boolean[])
{
let r = base;
let cp = false;
for(let i=0; i<26; i++)
{
if (exc[i] && base[i])
{
if (!cp) {r = base.slice(); cp=true; }
r[i]=false;
}
}
return r;
}

function key_combine(a: boolean[], b: boolean[])
{
let r = a;
let cp = false;
for(let i=0; i<26; i++)
{
if (b[i] && !r[i])
{
if (!cp) {r = a.slice(); cp=true; }
r[i]=true;
}
}
return r;
}

class AOCMap
{
grid:   number[][];
width:  number;
height: number;
start:  [number, number];
doors:  [number, number][];
keys:   [number, number][];

reachability: Map<string, [number, boolean[]]> = new Map<string, [number, boolean[]]>(); // [x;y] => [length;keys]

constructor(g: number[][])
{
this.grid   = g;
this.width  = g[0].length;
this.height = g.length;
this.doors  = new Array(26);
this.keys   = new Array(26);
this.start  = [-1, -1];

for(let y=0; y<this.height;y++)
for(let x=0; x<this.width;x++)
{
const v = String.fromCharCode(this.get([x,y]));
if (v === "#") continue;
if (v === ".") continue;
if (v === "@") { this.start = [x, y]; continue; }

if (v.charCodeAt(0) >= "A".charCodeAt(0) && v.charCodeAt(0) <= "Z".charCodeAt(0))
{
this.doors[v.charCodeAt(0) - "A".charCodeAt(0)] = [x,y];
continue;
}

if (v.charCodeAt(0) >= "a".charCodeAt(0) && v.charCodeAt(0) <= "z".charCodeAt(0))
{
this.keys[v.charCodeAt(0) - "a".charCodeAt(0)] = [x,y];
continue;
}

throw "input:"+v+":";
}
}

getPathLength(path: string): number
{
path = "@" + path;

let sum = 0;
for (let i=1; i<path.length; i++)
{
sum += this.reachability.get(path.charAt(i-1)+">"+path.charAt(i))![0];
}
return sum;
}

isreachable(p0: string, p1: string, keys: boolean[]): boolean
{
const k_needed = this.reachability.get(p0+">"+p1)![1];
for(let i=0; i<26; i++)
{
if (k_needed[i] && !keys[i]) return false;
}
return true;
}

get(pos: [number, number]): number {
return this.grid[pos[1]][pos[0]];
}

iswalkable(pos: [number, number]): boolean {
const v = this.get(pos);
return (v !== 35 && v !== 64); // # && @
}

iskey(pos: [number, number]): boolean {
const v = this.get(pos);
return (v >= 97 && v <= 122); // a-z
}

isdoor(pos: [number, number]): boolean {
const v = this.get(pos);
return (v >= 65 && v <= 90); // A-Z
}

async dump()
{
let str = "";
for(let y=0; y<this.height;y++)
{
for(let x=0; x<this.width;x++)
{
let v = this.get([x, y]);
if (v == 46) str += " ";
else if (v == 35) str += "\u2591";
else str += String.fromCharCode(v);
}
str += "\n";
}
}

async dumpWithFill(visited_map: { [_: number]: any; })
{
let str = "";
for(let y=0; y<this.height;y++)
{
for(let x=0; x<this.width;x++)
{
const i = (y*10000000 + x);

if (i in visited_map) str += "\u25cf"
else
{
let v = this.get([x, y]);
if (v == 46) str += " ";
else if (v == 35) str += "\u2591";
else str += String.fromCharCode(v);
}
}
str += "\n";
}
}

async dumpWithFillAndNext(visited_map: { [_: number]: any; }, next: [number, number, any, any][])
{
let str = "";
for(let y=0; y<this.height;y++)
{
for(let x=0; x<this.width;x++)
{
const i = (y*10000000 + x);

if (next.findIndex(p => p[0]==x && p[1]==y)>=0) str += "\u25cb"
else if (i in visited_map) str += "\u25cf"
else
{
let v = this.get([x, y]);
if (v == 46) str += " ";
else if (v == 35) str += "\u2591";
else str += String.fromCharCode(v);
}
}
str += "\n";
}
}
}
}
``````
Result: 7430

Part 2:
``````namespace AdventOfCode2019_18_2
{
const DAY     = 18;
const PROBLEM = 2;

type P = [number, number];
type PSet = [P, P, P, P];

export async function run()
{
if (input == null) return;

let grid = input
.trim()
.split(new RegExp('\r?\n'))
.filter(p => p.trim().length > 0)
.map(p => p.trim().split('').map(q => q.charCodeAt(0)) );

grid[40][40] = "#".charCodeAt(0);

grid[39][40] = "#".charCodeAt(0);
grid[41][40] = "#".charCodeAt(0);
grid[40][39] = "#".charCodeAt(0);
grid[40][41] = "#".charCodeAt(0);

let keys = grid.flatMap(p => p.filter(q => q>=97 && q<=122));

await AdventOfCode.outputIntermed(  grid.map(p => p.map(q=>String.fromCharCode(q)).join("") ).join("\n")  );

let dictionary: {[_:number]: ReachableKey[] } = {};

dictionary[id([39,39])] = ReachableKeys(grid, [39,39], "");
dictionary[id([41,39])] = ReachableKeys(grid, [41,39], "");
dictionary[id([39,41])] = ReachableKeys(grid, [39,41], "");
dictionary[id([41,41])] = ReachableKeys(grid, [41,41], "");

for (let k of keys)
{
const pos = FindPositionOf(grid, k);
dictionary[id(pos)] = ReachableKeys(grid, pos, "");
}

let positions: {[_:number]: P} = {};
for (let k of keys) { positions[k] = FindPositionOf(grid, k); }

let minimumSteps = CollectKeys(grid, dictionary, positions, [[39,39], [41,39], [39,41], [41,41]])

}

function CollectKeys(grid: number[][], keyPaths: {[_:number]: ReachableKey[]}, positions: {[_:number]: P}, pos: P[])
{
let currentMinimum = Number.MAX_SAFE_INTEGER;

let startingSet: PSet = [ pos[0], pos[1], pos[2], pos[3] ];

let q: State[] = [];
q.unshift(new State(startingSet, 0, 0));

let visited = new Map<string, number>();
let finishValue = 0;
for (var i = 0; i < Object.entries(positions).length; ++i)
{
finishValue = finishValue | Math.floor(Math.pow(2, i));
}

while (q.length>0)
{
let state = q.pop()!;

let valueTupleKey = state.strPositionsOwnedKeys();
if (valueTupleKey in visited)
{
let steps = visited.get(valueTupleKey)!;

if (steps <= state.Steps) continue;

visited.set(valueTupleKey, state.Steps);
}
else
{
visited.set(valueTupleKey, state.Steps);
}

if (state.OwnedKeys === finishValue)
{
currentMinimum = Math.min(currentMinimum, state.Steps);
continue;
}

for (let i=0; i < 4; i++)
{
for (let k of keyPaths[id(state.Positions[i])])
{
let ki = Math.floor(Math.pow(2, k.Key.charCodeAt(0) - "a".charCodeAt(0)));
if ((state.OwnedKeys & ki) === ki || (k.Obstacles & state.OwnedKeys) != k.Obstacles) continue;

let newOwned = state.OwnedKeys | ki;

var newPos = state.Positions.slice() as PSet;
newPos[i] = positions[k.Key.charCodeAt(0)];

q.unshift(new State(newPos, newOwned, state.Steps + k.Distance));
}
}
}

return currentMinimum;
}

function id (p: P) { return p[1]*10000+p[0]; }

function FindPositionOf(grid: number[][], needle: number): P
{
for(let y=0; y<grid.length; y++)
for(let x=0; x<grid[y].length; x++)
{
if (grid[y][x] === needle) return [x, y];
}
throw "";
}

class State
{
Positions: PSet;
OwnedKeys: number;
Steps: number = 0;

constructor(s: PSet, ok: number, ss: number) { this.Positions=s; this.OwnedKeys=ok; this.Steps = ss; }

strPositionsOwnedKeys()
{
return "" +
this.Positions[0][0]+";" +
this.Positions[0][1]+";" +
this.Positions[1][0]+";" +
this.Positions[1][1]+";" +
this.Positions[2][0]+";" +
this.Positions[2][1]+";" +
this.Positions[3][0]+";" +
this.Positions[0][1]+";" +
this.OwnedKeys+";";
}
}

function ReachableKeys(map: number[][], start: P, currentKeys: string): ReachableKey[]
{
let list: ReachableKey[] = [];
let visited: Set<number> = new Set<number>();

var q: P[] = [];
var s: number[] = [];
var o: number[] = [];
q.unshift(start);
s.unshift(0);
o.unshift(0);

while (q.length>0)
{
const pos  = q.pop()!;
const dist = s.pop()!;
let   obst = o.pop()!;

if (visited.has(id(pos))) continue;

var c = map[pos[1]][pos[0]];

if (c>=97 && c<=122) // lower
{
let rk = new ReachableKey();
rk.Distance = dist; rk.Key = String.fromCharCode(c); rk.Obstacles = obst;
list.push(rk);
pos_around(pos).forEach(p =>
{
q.unshift(p);
s.unshift(dist+1);
o.unshift(obst);
});
}
else if (c>=65 && c<=90) // upper
{
pos_around(pos).forEach(p =>
{
q.unshift(p);
s.unshift(dist+1);
obst = obst | Math.floor(Math.pow(2, c-65))
o.unshift(obst);
});
}
else if (c === 46) // .
{
pos_around(pos).forEach(p =>
{
q.unshift(p);
s.unshift(dist+1);
o.unshift(obst);
});
}
else if (c === 35) {}// #
else throw "["+c+"]";
}

return list;
}

function pos_around(pos: P): P[]
{
return [
[pos[0], pos[1]-1],
[pos[0]-1, pos[1]],
[pos[0]+1, pos[1]],
[pos[0], pos[1]+1],
];
}

class ReachableKey
{
Key: string = "";
Distance: number = 0;
Obstacles: number = 0;
}
}
``````
Result: 1864

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript