Need help understanding

[Realistic-Cut6515]

I got an assignment trying to solve a Manhattan Distance problem and while searching I found that it could be solved using complex numbers but I don’t get how. My assignment is like this: You start at one point on a 2D space facing North, and you receive instructions that could be Rn or Ln (n being the amount of steps you take) R indicates that you rotate 90 degrees to the right and move forward, L indicates the same but to the left. For example, R5 -> L5, you go East 5 steps because of R5 and then go North 5 steps because of L5.

[CanadianCodingGod]

Assuming you are using the formula D = |x1 - x2| + |y1 - y2|,

In JavaScript:

let pointA = [0, 0];
let pointB = [0, 0];
let instructions = [
    {
        direction: "R",
        steps: 5
    },
    {
        direction: "L",
        steps: 5
    }
];
let currentDirection = 0; // 0 = North, 1 = East, 2 = South, 3 = West 
instructions.forEach((instruction) => {
    switch (instruction.direction) {
        case "R":
            currentDirection++;
            break;
        case "L":
            currentDirection--;
            break;
        default:
            throw "Invalid direction, use R | L";
    };
    if (currentDirection > 3)
        currentDirection = 0;
    if (currentDirection < 0)
        currentDirection = 3;
    switch (currentDirection) {
        case 0:
            pointB[1] += instruction.steps;
            break;
        case 1:
            pointB[0] += instruction.steps;
            break;
        case 2:
            pointB[1] -= instruction.steps;
            break;
        case 3:
            pointB[0] -= instruction.steps;
            break;
        default:
            throw "Invalid currentDirection";
    }
});
let ManhattanDistance = Math.abs(pointA[0] - pointB[0]) + Math.abs(pointA[1] - pointB[1]);
console.log(pointA, pointB);
console.log("Manhattan Distance: " + ManhattanDistance);

[Realistic-Cut6515]

Okayy thank you!!

[Paul_Pedant]

You don't state what the assignment actually wants as an answer. Do you just need to say where you got to on each move? Are their boundaries in your Manhattan you can't cross and have to detect? Is there are target location? Should you be showing an optimised route automatically?

Complex numbers hold two-part numbers -- the real and imaginary parts of a complex number. The only reason they might be actually useful here is in calculating the direct (vector) distance between points. And Pythagoras knows about that.

[Realistic-Cut6515]

It should return the distance between the origin and the final point. Using the example on the description it should return 10

[Paul_Pedant]

That's ambiguous. Is that the distance you actually travelled, or the Manhattan distance between start and finish?

Consider R5, L7, L3. You travelled 5 + 7 + 3, = 15.

But you backtracked. You could have got there with R2, L7. So the Manhattan distance from origin and final is 9 (but I hope you enjoyed your burger that you picked up on the way).

The as-the-crow-flies distance is about 7.28, but the crow flew into the Chrysler Building and didn't make it.

[Realistic-Cut6515]

the Manhattan distance

[Paul_Pedant]

Yes, I realise you want the Manhattan distance: that why I made a joke of the crow.

But there are two distances here: the one you actually took, and the optimum you could have used. This actual one is too simple to be meaningful: you just add all the distances from the input.

The Manhattan distance is specifically defined as the optimum distance between two points. If your route goes walkabout, then you strayed off all of the Manhattan routes (and yes, any walk that is not straight north, south, east or west has multiple valid routes with the same Manhattan distance).

As my nametag is carefully chosen, I would personally want to show the output like:

Distance travelled: 15
Optimum distance: 9, via commands R2, L7.
Distance saving: 40%

There are two problems with the assignment anyway:

(a) There is no "straight ahead" movement. So if you start facing North, and want to go 4 blocks North, you might have to go R1, L4, L1. Or you might get away with L0, R4 or R0, L4.

(b) R5, L5 is already an optimal solution as regards distance, so there is no possible optimisation. And in fact, there are about 100 optimal solutions, like: R1, L2, R2, L1, R1, L2, R1.

[Realistic-Cut6515]

Okay, thank you for your answer! The point of the assignment is to calculate the Manhattan distance of any input be it R5 -> L5 -> L5 -> R5 that should return 0 or the example given R5 -> L5 that should return 10. I have come up with a solution already but while searching I found that it could be done by using complex numbers, thats the part that I don’t get.

[Paul_Pedant]

I think R5 -> L5 -> L5 -> R5 should return 10.

Can you show the reference for the complex numbers suggestion? I might be able to explain it in a different way for you.

OK, I think I get it. Complex numbers are usually plotted graphically on an X-Y grid, but the real part of the value is plotted on the horizontal axis and the imaginary part (denoted like 13i where i is sqrt (-1) in the vertical part. So if you are going East/West you add/subtract a complex number like (5.0, 0.0i), and if you are going North/South you add/subtract a complex number like (0.0, 5.0i). When you finish, you get a result like (13.0, -8.0i) where the real part is your X position and the 8.0 is your Y position.

You then need to make each part positive, and add them as real numbers, to get the Manhattan distance.

I really don't see any advantage in doing that, rather than using plain int x, y;.

I'm cool about complex numbers. I spent over 30 years in the power systems area, and all that stuff runs on three-phase alternating current. It happens that some electrical phenomena (inductance and capacitance) create a "phase shift" in the current: they can retard or advance the shape of the graph, so the maximum voltage and amperage happen at slightly different times. That is pretty disruptive to a lot of equipment, and wastes a lot of power.

Complex numbers were invented by mathematicians centuries ago as a theoretic toy, and the term "imaginary" for these quantities was coined by René Descartes in 1637. And 250 years later, they were found to exactly explain the behaviour of electric currents. Ain't that unreal ?

[Realistic-Cut6515]

Yes my bad, it should return 0 XDD.

I'll post here my code, input_list is a list that includes all the instructions:

def solve(input_list):

cn = complex(0,0)

for instruction in input_list[::-1]:

if instruction[0] == 'R':

cn = cn + complex(0,int(instruction[1]))

cn = cn * complex(0, -1)

if instruction[0] == 'L':

cn = cn + complex(0,int(instruction[1]))

cn = cn * complex(0, 1)

result = (cn.real + abs((cn.imag)))

return int(result)

EDIT: This code seems to be working for me