18b.md

Day 18: Many-Worlds Interpretation Part 2 - Code

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:

...
.@.
...

Update your map to instead use the correct data:

@#@
###
@#@

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?

Solution

The hardest part about this problem is wrapping your head around it. The maps are changed in a way so that no robot other than robot1 can reach a, and no robot other than robot2 can access b. No key can be accessed by two or more robots. The quadrants are blocked off in a way that robots can't go into other quadrants.

Lower-bound / Good Guess

The first thing we do is get a lower-bound on the number of steps needed. I.e., we assume each robot has all doors that have their key belonging to other quadrants unlocked. E.g., if robot1 has door A but key a belongs in robot2's quadrant, we assume A is unlocked because robot2 will get key a at some point eventually because it has to. My answer from this lower-bound problem was the correct answer to my input! As well as Greg's!

export const lowerBound = (keytoKeyMap: Map<string, IKeyToKeyInfo[]>, entrances: Map<string, IPoint>) => {
    type QueueState = {totalSteps: number; keysObtained: string; atKey: string};
    const queue = new PriorityQueue<QueueState>(p => -1 * p.totalSteps);
    const visited = new Map<string, number>();
    const getReachableKeys = makeGetReachableKeys(keytoKeyMap);
    const keyToQuadrantMap = getKeyToEntranceMap(keytoKeyMap, entrances); // The entrance a key belongs to
    // all the keys that will be obtained in a quadrant.
    const allKeysInQuadrant = new Map(Array.from(entrances.keys()).map(k => [
        k, // key of the Map
        keytoKeyMap.get(k)!.map(k1 => k1.toKey).join('')
    ]));
    const keysPerQuadrant = new Map(Array.from(entrances.keys()).map(k => [k, keytoKeyMap.get(k)!.length]));
    const minSteps = new Map(Array.from(entrances.keys()).map(k => [k, Infinity]));

    for (const e of entrances.keys())
        queue.enqueue({totalSteps: 0, keysObtained: '', atKey: e});

    while (!queue.isEmpty()) {
        const { totalSteps, keysObtained, atKey } = queue.dequeue()!;
        const quadrant = keyToQuadrantMap.get(atKey)!;

        if (keysObtained.length === keysPerQuadrant.get(quadrant)) {
            const currMinSteps = minSteps.get(quadrant)!;
            minSteps.set(quadrant, Math.min(currMinSteps, totalSteps));
        }

        const keysObtainedOtherQuadrants = getAllValuesExcludingKey(quadrant, allKeysInQuadrant);
        const keysObtainedSet = new GenericSet(k => k, [...keysObtained, ...keysObtainedOtherQuadrants]);
        const reachableKeys = getReachableKeys(atKey, keysObtainedSet);

        for (const key of reachableKeys) {
            const newKeysObtained = keysObtained + key.toKey;
            const newCacheKey = getCacheKey(key.toKey, newKeysObtained);
            const newTotalSteps = totalSteps + key.steps;
            if (!visited.has(newCacheKey) || visited.get(newCacheKey)! > newTotalSteps) {
                queue.enqueue({
                    totalSteps: totalSteps + key.steps,
                    atKey: key.toKey,
                    keysObtained: newKeysObtained
                });
                visited.set(newCacheKey, newTotalSteps);
            }
        }
    }
    return Array.from(minSteps.values()).reduce((a, c) => a + c, 0);
};

The lower-bound above isn't always correct. E.g., for the following maze:

[4, 36steps]
###########
#.DeE#aB..#
#.#######.#
#...@#@...#
###########
#cA.@#@...#
####.####.#
#b...#dC..#
###########

It returns 34 steps, because the bottom-left quadrant assumes it'll have door A unlocked sometime in the future, so it goes @ -> c -> b, when really, it needs to go @ -> b -> c because then will it be able to unlock door B for top-right quadant, and so on. The right answer is 36 steps.

Always Correct Solution

It helps to visualize the problem with just two robots first. So imagine if there were only two robots: @ and @1. The reachable key for @ are [] and reachable keys for @1 are [a, b] with steps [10, 3], respectively. Thus, we have the following two possible options:

• (@, a) - robot0 stays where it's at because its the only option it can take, and robot1 goes to key a, unlocking door A when it gets popped from queue. This will cost us 10 steps.
• (@, b) - robot0 stays where it's at, and robot1 goes to key b, unlocking door B when it gets popped from queue. This will cost us 3 steps.

Now imagine the queue pops the robot positions (@, b), implying robot0 is at @ and robot1 is at b, and door B is unlocked, with a total cost of 3 steps.

We again get the reachable keys for both robots, and now the reachable keys are:

• robot0 = [u, v] with steps [4, 40]
• robot1 = [c] with steps [10].

Now the possible routes we have are:

• (@, b) - This option implies both robots stay where they're at, which would lead to an infinite loop, so this is not an option.
• (@, c) - robot0 stays, robot1 advances.
• (u, b) - robot0 advances, robot1 stays.
• (u, c) - both robots advance.
• (v, b) - robot0 advances, robot1 stays.
• (v, c) - both robots advance.

All of those options get put into the queue! E.g., the option (u, c) will get put into the queue with a total step of 3 + 4 + 10 = 17, and keysObtained = b,u,c.

We keep dequeueing and enqueueing the queue until we get all keys obtained.

/*
Input: [
    [a, b],
    [c, d]
    [e]
]
Output: [
    [a, c, e],
    [a, d, e],
    [b, c, e],
    [b, d, e]
]
*/
export const combinations = <T>(keysReachableKeys: T[][]) => {
    const solutions: T[][] = [];

    const helper = (atKeyIndex: number, curr: T[]) => {
        if (curr.length === keysReachableKeys.length) {
            solutions.push([...curr]);
            return;
        }
        for (let i = atKeyIndex; i < keysReachableKeys.length; i++)
            for (let j = 0; j < keysReachableKeys[i].length; j++) {
                curr.push(keysReachableKeys[i][j]);
                helper(i + 1, curr);
                curr.pop();
            }
    };
    helper(0, []);
    return solutions;
};

export const solve = (keytoKeyMap: Map<string, IKeyToKeyInfo[]>, entrances: Map<string, IPoint>) => {
    type QueueState = {totalSteps: number; atKeys: string[]; keysObtained: string};
    const queue = new PriorityQueue<QueueState>(p => -1 * p.totalSteps);
    const visited = new Map<string, number>();
    const getReachableKeys = makeGetReachableKeys(keytoKeyMap);

    queue.enqueue({
        totalSteps: 0,
        atKeys: Array.from(entrances.keys()),
        keysObtained: ''
    });
    while (!queue.isEmpty()) {
        const { totalSteps, atKeys, keysObtained } = queue.dequeue()!;
        if (keysObtained.length === keytoKeyMap.size - entrances.size)
            return totalSteps;

        const keysObtainedSet = new GenericSet(k => k, [...keysObtained]);
        const allRouteOptionsForAllRobots =
            combinations(
                // we're adding the current key to reachable keys to include the option of "staying put"
                // obviously, staying put has 0 steps involved
                atKeys.map(k => [{toKey: k, steps: 0}].concat(getReachableKeys(k, keysObtainedSet)))
            ).slice(1); // remove the first one because it'll be identical to the current one

        for (const routeOptionForAllRobots of allRouteOptionsForAllRobots) {
            // 0th robot moves to key robotsMoveToKey[0]
            const robotsMoveToKey = routeOptionForAllRobots.map(r => r.toKey);
            const newKeysObtained = Array.from(new GenericSet(k => k,
                robotsMoveToKey
                    .filter(k => !entrances.has(k))
                    .concat([...keysObtained]))
                .values()).join('');
            const newCacheKey = getCacheKey(robotsMoveToKey.join(''), newKeysObtained);
            const newTotalSteps = routeOptionForAllRobots.reduce((a, c) => a + c.steps, totalSteps);
            if (!visited.has(newCacheKey) || visited.get(newCacheKey)! > newTotalSteps) {
                queue.enqueue({
                    totalSteps: newTotalSteps,
                    atKeys: robotsMoveToKey,
                    keysObtained: newKeysObtained
                });
                visited.set(newCacheKey, newTotalSteps);
            }
        }
    }
    return Infinity;
};