Skip to content

Latest commit

 

History

History
405 lines (347 loc) · 15.8 KB

18.md

File metadata and controls

405 lines (347 loc) · 15.8 KB

Day 18: Many-Worlds Interpretation - Code

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:

#########
#[email protected]#
#########

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:

########################
#[email protected].#
######################.#
#d.....................#
########################

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

########################
#[email protected].#
######################.#
#d.....................#
########################

Then, do the same with key b:

########################
#[email protected].#
######################.#
#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#
#.######################
#[email protected]#
########################

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

In your input, how many steps is the shortest path that collects all of the keys?

Solution

I learned the hard way that when trying to find the shortest distance between two points in a graph or a grid, do not use DFS! You have to use a special type of BFS. In BFS, we use a Queue, right? Well, in this one, we use a Priority Queue (or a Heap), which makes it a Dijkstra's Algorithm.

The solution is broken up into two parts

  1. For each key1 to key2 pair, get
    • Minimum Steps between key1 and key2.
    • Doors between key1 and key2.
    • Other keys inbetween key1 and key2.
  2. Starting from the @ key, traverse any reachable keys from it, keeping track of the min steps taken. Stop when all keys have been traversed. This can be solved using DFS, BFS, or Dijkstra's. I went with Dijstra's.

Here's a pseudocode for step 2:

distanceToCollectKeys(currentKey, keys): 

    if keys is empty:
        return 0

    result := infinity
    foreach key in reachable(keys):
       d := distance(currentKey, key) + distanceToCollectKeys(key, keys - key)
       result := min(result, d)

    return result;

Step 1: Key to Key Map

It's so important to do this via Dijkstra's instead of DFS. If you don't believe me, check out the the distance differences from '@' to all keys in the graph.

DFS

r: 16   l: 28   b: 42   p: 58   t: 78   q: 84   f: 100   x: 114   h: 132   g: 140   k: 158   m: 170   j: 182
u: 196  e: 208  d: 224  s: 244  c: 260  y: 270  i: 286   w: 296   v: 314   n: 328   o: 340   a: 354   z: 366

Dijkstra's Algorithm

r: 16   l: 28   b: 42   p: 54   t: 72   q: 80   f: 96   x: 110   h: 126   g: 138   k: 154   m: 170   j: 182
u: 196  e: 208  d: 222  s: 240  c: 254  y: 264  i: 280  w: 294   v: 308   n: 324   o: 336   a: 350   z: 362

// will return all short AND LONG paths fromKey to toKey

const getNearestKeysMap = (tunnel: ITunnel) => {
    const { keys, entrance } = tunnel;
    return new Map(Array.from(keys.entries())
        .map(([k, p]) => [k, getDistancesToAllKeys(p, tunnel)])
    ).set('@', getDistancesToAllKeys(entrance, tunnel));
};

const getDistancesToAllKeys = (from: IPoint, tunnel: IBaseTunnel) => {
    const queue = new PriorityQueue<IPriorityQueueState>(p => -1 * p.distance);
    const visited = new GenericSet<IPoint>(toString);
    const result: IKeyToKeyInfo[] = [];
    const isValid = makeIsValid(tunnel)(visited);
    const addPointInfo = makeAddPointInfo(tunnel);

    visited.add(from);
    queue.enqueue({
        point: from,
        distance: 0,
        keysObtained: new GenericSet(s => s),
        doorsInWay: new GenericSet(s => s)
    });

    while (!queue.isEmpty()) {
        const {point, distance, keysObtained, doorsInWay} = queue.dequeue()!;
        const neighbors = getNeighbors(point)
            .filter(isValid)
            .map(addPointInfo);

        for (let i = 0; i < neighbors.length; i++) {
            const neighbor = neighbors[i];
            const newKeysObtained = i === neighbors.length - 1 ? keysObtained : new GenericSet(keysObtained);
            const newDoorsInWay = i === neighbors.length - 1 ? doorsInWay : new GenericSet(doorsInWay);
            if (neighbor.door != null)
                newDoorsInWay.add(neighbor.door);
            if (neighbor.key != null)
                newKeysObtained.add(neighbor.key);

            visited.add(neighbor.point);
            queue.enqueue({
                point: neighbor.point,
                distance: distance + 1,
                keysObtained: newKeysObtained,
                doorsInWay: newDoorsInWay
            });

            if (neighbor.key != null) {
                const keysInWay = new GenericSet(keysObtained);
                keysInWay.delete(neighbor.key); // don't include toKey in keysInWay
                result.push({
                    toKey: neighbor.key,
                    steps: distance + 1,
                    doorsInWay: new GenericSet(doorsInWay),
                    keysInWay
                });
            }
        }
    }
    return result;
};

Utility functions for the method above:

interface IPriorityQueueState {
    point: IPoint;
    distance: number;
    keysObtained: GenericSet<string>;
    doorsInWay: GenericSet<string>;
}

interface IKeyToKeyInfo {
    toKey: string;
    steps: number;
    doorsInWay: GenericSet<string>;
    keysInWay: GenericSet<string>;
}

const getNeighbors = ({row, col}: IPoint, exclude?: IPoint | null): IPoint[] =>
    exclude == null ?
        [{row: row - 1, col}, {row: row + 1, col}, {row, col: col + 1}, {row, col: col - 1}] :
        getNeighbors({row, col}, null).filter(p => p.row !== exclude.row || p.col !== exclude.col);

const makeIsValid = ({grid, keys, doors}: IBaseTunnel) => (visited: GenericSet<IPoint>) => (p: IPoint) => {
    const cell = grid[p.row][p.col];
    if (cell == null ||
        visited.has(p) ||
        cell !== '.' &&
        cell !== '@' &&
        !equals(keys.get(cell), p) && // stepping on a key is valid
        !equals(doors.get(cell), p) // stepping on a door is valid. We don't care about doors right now
    )
        return false;
    return true;
};

const makeAddPointInfo = ({grid, keys, doors}: IBaseTunnel) => (p: IPoint) => {
    const cell = grid[p.row][p.col];
    return {
        point: p,
        key: equals(p, keys.get(cell)) ? cell : null,
        door: equals(p, doors.get(cell)) ? cell : null
    };
};

There are cases where the above code won't do so well. E.g., imagine the grid

[2, 20 steps]
##########
#.a###.Ab#
#.B..@.###
#...######
##########

It'd say @ -> a equals 4, and @ -> b equals 4. However, each key requires the other key, resulting in failure.

To avoid this, the getDistancesToAllKeys would have to return the following:

  • @ -> a equals 4
  • @ -> a equals 6
  • @ -> a equals 8
  • @ -> b equals 4

We can do this by removing the visited Set from the equation, allowing us to find all routes. However, since it passes the test case without this issue, we won't add this constraint.

Step 2: Traversing the Transformed Map

Now that we have transformed the plane from a grid to a graph of keys to keys, we can solve this using any graph traversal we want. I implemented all three solutions. Here's what I learned

  • Dijkstra was the fastest, then DFS, then BFS.
  • BFS and Dijkstra's are almost identical. The key differences are:
    • BFS uses a normal queue, Dijkstra's uses a PriorityQueue, dequeuing the element with the fewest steps first.
    • Because of this, Dijkstra can terminate as soon as it finds a solution, BFS has to traverse the entire map.
    • DFS also has the traverse the entire graph.

Here is the Dijkstra and BFS solution (see comments to see how to convert it to BFS):

const solve = (keytoKeyMap: Map<string, IKeyToKeyInfo[]>) => {
    type QueueState = {totalSteps: number; keysObtained: string; atKey: string};
    // const queue = new Queue<QueueState>(); FOR BFS
    const queue = new PriorityQueue<QueueState>(p => -1 * p.totalSteps);
    const visited = new Map<string, number>();
    const getReachableKeys = makeGetReachableKeys(keytoKeyMap);
    let minSteps = Infinity;

    queue.enqueue({totalSteps: 0, keysObtained: '', atKey: '@'});
    while (!queue.isEmpty()) {
        const { totalSteps, keysObtained, atKey } = queue.dequeue()!;
        if (keysObtained.length === keytoKeyMap.size - 1) {
            minSteps = Math.min(totalSteps, minSteps);
            return minSteps; // for BFS, remove this line.
        }

        const reachableKeys = getReachableKeys(atKey, new GenericSet(k => k, [...keysObtained]));
        for (const key of reachableKeys) {
            const newKeysObtained = keysObtained + key.toKey;
            const newCacheKey = getCacheKey(key.toKey, newKeysObtained);
            const newTotalSteps = totalSteps + key.steps;
            // the visited.get(newCacheKey)! > newTotalSteps is crucial, because you may find a later route that has
            // fewer steps
            if (!visited.has(newCacheKey) || visited.get(newCacheKey)! > newTotalSteps) {
                queue.enqueue({
                    totalSteps: newTotalSteps,
                    atKey: key.toKey,
                    keysObtained: newKeysObtained
                });
                visited.set(newCacheKey, newTotalSteps);
            }
        }
    }
    return minSteps;
};

And lastly, the DFS solution is as follows:

const solve = (keyToKeyMap: Map<string, IKeyToKeyInfo[]>) => {
    const getReachableKeys = makeGetReachableKeys(keyToKeyMap);
    const cache: {[key: string]: number} = {};

    const helper = (fromKey: string, keysObtained: string): number => {
        if (keysObtained.length === keyToKeyMap.size - 1) {
            return 0;
        } // minus 1 because @ is in keysToKeysSteps
        const cacheKey = getCacheKey(fromKey, keysObtained);
        if (cache[cacheKey] != null)
            return cache[cacheKey];
        // has to be uppercased so it can be compared against doors
        const reachableKeys = getReachableKeys(fromKey, new GenericSet(k => k, [...keysObtained]));
        let totalSteps = Infinity;
        for (const reachableKey of reachableKeys) {
            const steps =
                reachableKey.steps +
                Math.min(totalSteps, helper(reachableKey.toKey, keysObtained + reachableKey.toKey));
            totalSteps = Math.min(totalSteps, steps);
        }
        cache[cacheKey] = totalSteps;
        return totalSteps;
    };

    return helper('@', '');
};

Helper functions used by both:

export const makeGetReachableKeys =
    (keyToKeyMap: Map<string, IKeyToKeyInfo[]>) =>
    (fromKey: string, keysObtained: GenericSet<string>) =>
        keyToKeyMap.get(fromKey)
            ?.filter(k => !keysObtained.has(k.toKey))
            ?.filter(k => k.doorsInWay.subsetOf(keysObtained, k => k.toString().toLowerCase()))
            ?.filter(k => k.keysInWay.subsetOf(keysObtained)) ?? [];
            // if you skip over keysInWay, you'e looking at a suboptiaml route because you'll examine routes
            // like a -> c, when there is key b between a -> c

export const getCacheKey = (fromKey: string, keysObtained: string) =>
    `${fromKey},${[...keysObtained].sort().toString()}`;

Appendix

Dijkstra's Algorithm

Dijkstra's Algorithm is great for two things:

  1. Finding shortest distance from source node s to a destination node
    • Some would say A-star (A*) algorithm works better for this since it will add a heuristic on top of the total distance, allowing you to scan fewer routes.
    • For this, you don't have to wait until the queue is empty. As soon as you get to your destination, you return out of that and forget whatever is still in the queue.
  2. Finding shortest distance from source node s to all other destination nodes
    • Most would say Dijkstra is better for this than A* because you have to scan a lot more of the plane for both A* and Dijkstra.
    • For this you have two options:
      • Scan the entire domain (what I do in getDistancesToAllKeys above). I.e., keep scanning until your queue is empty. This works great if you don't know what all your destinations are. In my case, I was just lazy because I actually did know all my destinations.
      • Scan until you get all destinations, and then return out and forget whatever is left in your queue. I do this in my first solve.

Two things are needed:

  • Ability to get neighbors / adjacency list of any node
  • Using a Priority Queue or Min Heap, so that nodes with the lowest cost are dequeued first.

Let us understand with the following example. Let the given source vertex be 0

Initially, distance value of source vertex is 0 and INF (infinite) for all other vertices. So source vertex is extracted from Min Heap and distance values of vertices adjacent to 0 (1 and 7) are updated. Min Heap contains all vertices except vertex 0. The vertices in green color are the vertices for which minimum distances are finalized and are not in Min Heap

Since distance value of vertex 1 is minimum among all nodes in Min Heap, it is extracted from Min Heap and distance values of vertices adjacent to 1 are updated (distance is updated if the a vertex is not in Min Heap and distance through 1 is shorter than the previous distance). Min Heap contains all vertices except vertex 0 and 1.

Pick the vertex with minimum distance value from min heap. Vertex 7 is picked. So min heap now contains all vertices except 0, 1 and 7. Update the distance values of adjacent vertices of 7. The distance value of vertex 6 and 8 becomes finite (15 and 9 respectively).

Pick the vertex with minimum distance from min heap. Vertex 6 is picked. So min heap now contains all vertices except 0, 1, 7 and 6. Update the distance values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated.

Above steps are repeated till min heap doesn’t become empty. Finally, we get the following shortest path tree.