Shortest path to the finish (Taxicab Geometry / Manhattan Problem)

instructions.md

You are facing north, you can either turn left (L) or right (R) 90 degrees and walk forward the given number of blocks, ending at a new intersection.

given: R1, R1, R3, R1, R1, L2, R5, L2, R5, R1, R4, L2, R3, L3, R4, L5, R4, R4, R1, L5, L4, R5, R3, L1, R4, R3, L2, L1, R3, L4, R3, L2, R5, R190, R3, R5, L5, L1, R54, L3, L4, L1, R4, R1, R3, L1, L1, R2, L2, R2, R5, L3, R4, R76, L3, R4, R191, R5, R5, L5, L40, L5, L3, R1, R3, R2, L2, L2, L4, L5, L4, R5, R4, R4, R2, R3, R4, L3, L2, R5, R3, L2, L1, R2, L3, R2, L1, L1, R1, L3, R5, L5, L1, L2, R5, R3, L3, R3, R5, R2, R5, R5, L5, L5, R25, L3, L5, L2, L1, R2, R2, L2, R2, L3, L2, R3, L5, R4, L4, L5, R3, L4, R1, R3, R2, R4, L2, L3, R2, L5, R5, R4, L2, R4, L1, L3, L1, L3, R1, R2, R1, L5, R5, R3, L3, L3, L2, R4, R2, L5, L1, L1, L5, L4, L1, L1, R1

What is the shortest path to the finish?

For example:

• R2, L3 leaves you 2 blocks east and 3 blocks north (shortest path would be 5)
• R2, R2, R2 leaves you 2 blocks south of start (shortest path would be 2)
• R5, L5, R5, R3 would give you a shortest path of 12

method.md

I found the simplest way for me to solve this was to treat it like a 2D grid and walk the path to find the final X and Y position relative to the whole grid (since in the given data, each movement is relative to the previous). I tried to keep things as succinct and readable as possible, I also tried to keep it functionally pure and immutable.

On line 37 - 44 I added basic tests in the script just to verify that it matched the original examples.

The final answer my script gave was: 254

script.js

#!/usr/bin/env node

// Walk each instruction to find it's 2D co-ordinate
//  position relative to the start point
const getShortestPath = (instructions) =>
  instructions
    .split(', ')
    .reduce((prev, cur) => {
      
        // Get the turn direction and number of steps from the string
        const turn = cur[0];
        const steps = cur.slice(1);

        // Flip the direction from the previous point
        const dir = turn === 'R'
              ? [prev.dir[1], -prev.dir[0]]
              : [-prev.dir[1], prev.dir[0]];

        // Calculate the new position factoring the number
        //  of steps and the direction
        const pos = [
          prev.pos[0] + (dir[0] * steps),
          prev.pos[1] + (dir[1] * steps),
        ];
        return { dir, pos }
      },

      // For the initial state, start at x: 0, y: 0 (the center of the virtual grid),
      //  facing north (x: 0, y: 1)
      { dir: [0, 1], pos: [0, 0] })

    // Finally, sum the absolute X and Y values to get the grid distance from 0,0
    .pos
    .reduce((a, b) => Math.abs(a) + Math.abs(b));


// Tests to verify it's working correctly
const assertEqual = (a, b, message) => {
  if (a === b) return true;
  throw new Error(message)
}
assertEqual(getShortestPath('R2, L3'), 5, 'R2, L3 should equal 5');
assertEqual(getShortestPath('R2, R2, R2'), 2, 'R2, R2, R2 should equal 2');
assertEqual(getShortestPath('R5, L5, R5, R3'), 12, 'R5, L5, R5, R3 should equal 12');


const answer = getShortestPath('R1, R1, R3, R1, R1, L2, R5, L2, R5, R1, R4, L2, R3, L3, R4, L5, R4, R4, R1, L5, L4, R5, R3, L1, R4, R3, L2, L1, R3, L4, R3, L2, R5, R190, R3, R5, L5, L1, R54, L3, L4, L1, R4, R1, R3, L1, L1, R2, L2, R2, R5, L3, R4, R76, L3, R4, R191, R5, R5, L5, L40, L5, L3, R1, R3, R2, L2, L2, L4, L5, L4, R5, R4, R4, R2, R3, R4, L3, L2, R5, R3, L2, L1, R2, L3, R2, L1, L1, R1, L3, R5, L5, L1, L2, R5, R3, L3, R3, R5, R2, R5, R5, L5, L5, R25, L3, L5, L2, L1, R2, R2, L2, R2, L3, L2, R3, L5, R4, L4, L5, R3, L4, R1, R3, R2, R4, L2, L3, R2, L5, R5, R4, L2, R4, L1, L3, L1, L3, R1, R2, R1, L5, R5, R3, L3, L3, L2, R4, R2, L5, L1, L1, L5, L4, L1, L1, R1'); // => 254
console.log(`answer: ${answer}`); // => answer: 254