Expogo is a problem from Google Code Jam 2020 - Round 1B

In this article I explore:

- The Problem
- A solution
- Interactive visualization

## The Problem

The full statement can be found here at the Code Jam site.

You have just received the best gift ever: an

Expogostick. You can stand on it and use it to make increasingly large jumps.

A few facts from the problem statement:

- You'll use the
**Expogo**in an infinite two-dimensional plane - You start at point
**P = (0, 0)** - Your goal is to reach point
**P = (X, Y)** - All coordinates are integers
- Land exactly at
**P = (X, Y)**, in as few jumps as possible - For the
**i-th**jump, the**Expogo**moves you**2**^{i - 1}- First jump moves you
**1 unit** - Second jump moves you
**2 units** - Third moves you
**4 units**, etc...

- First jump moves you
- You can aim the
**Expogo**in any cardinal direction:`North`

,`South`

,`East`

, or`West`

- If it is impossible to land at
**P = (X, Y)**, say it so by answering`IMPOSSIBLE`

- Otherwise, answer with a
**string of cardinal directions**ordered from first to last jump

For example, to arrive at **P = (2, 3)**, you'd do `South`

, `East`

, `North`

, then the answer is `SEN`

. Contrary, arriving at **P = (-1, -1)** is `IMPOSSIBLE`

.

## A solution

This solution uses coordinate transformations

Interestingly, the set of possible **Expogo** jumping lengths, has only one odd number, that is, **1**.

- Taking either
`North`

or`South`

, first, makes the**end Y coordinate odd**, and the**end X coordinate will be even**. - Taking either
`West`

or`East`

, first, makes the**end X coordinate odd**, and the**end Y coordinate will be odd**.

That means that jumping with the **Expogo** any number of times, ends up with an odd coordinate and an even coordinate.

- We can't have both even coordinates X, Y
- We can't have both odd coordinates X, Y

Immediately conclude that jumping to, for example, **(R, R)** or **(R, -R)** is impossible.

A quick way to see if a point **P** is made up of at both even and odd coordinates it to just add the components and check that the result is **NOT** even:

```
const isCoordinateOdd = ({ x, y }) => (x + y) % 2 !== 0;
```

Remember that

odd + even = odd,odd + odd = even, and of course,even + even = even

Let's explore the possibilities now. From any given point **P = (X, Y)**, there's is a set of four points where the **Expogo** can land us, call this set **Q**.

```
const Q = [
[x + Math.pow(2, i - 1), y],
[x - Math.pow(2, i - 1), y],
[x, y + Math.pow(2, i - 1)],
[x, y - Math.pow(2, i - 1)]
];
```

We can always move the coordinates origin to **P**, and have:

```
const Q = [
[Math.pow(2, i - 1), 0],
[-Math.pow(2, i - 1), 0],
[0, Math.pow(2, i - 1)],
[0, -Math.pow(2, i - 1)]
];
```

As we can see, after the first jump, if we keep moving the origin to the landing place after every jump, then the set of **Q** points where can land next, is always an even distance away.

#### Hypothesis

We can scale the coordinate system by dividing the coordinates by 2, but in order to do this, we need to make sure that the target coordinate is (even, even).

For example:

To arrive at

**P = (2, 3)**, from**(0, 0)**, lets first jump one unit`North`

, then we are at**(0, 1)**.Make

**(0, 1)**the new origin, then**P = (2, 2)**from this new originScale the coordinate system by half, then

**P = (1, 1)****In this new coordinate system, the Expogo moves again 1 unit!****In this new coordinate system, we are back at (0,0)**Move either,

`East`

to**(1, 0)**Make

**(1, 0)**the new origin, then**P = (0, 1)**Scaling the coordinate system by half is not impossible because 1 is odd

**Conclude that this path does not land at P = (2, 3), but rather it leads to P = (2, 1).**

In step 1, when we moved the origin to

(0, 1),Pbecame(2, 2). We should have concluded immediately that such a move is not good, because in the scaled coordinate system,(1, 1)is impossible to reach.In fact, any

Pwhere theX = Y, even, is already a bad option, no need to do the scale step.

Let's refine the hypothesis:

After moving the origin, we can scale the coordinate system by dividing the coordinates by 2, but in order to do this, we need to make sure that the new target coordinate is

(even, even), and that after scaling, the coordinate satisfiesX + Y = oddnumber.

Let's try to arrive at **P = (2, 3)** again:

- From
**(0, 0)**there's four moves, of one unit, we must move`North`

or`South`

because the odd coordinate, 3, lies in the Y axis - Try to jump
`North`

and move the coordinate system origin to**(0, 1)** - Scale by half,
**P = (1, 1)**, impossible - Try to jump
`South`

and move the coordinate system origin to**(0, -1)**, then**P = (2, 4)** - Scale by half, makes
**P = (1, 2)**, possible path - Try to jump
`East`

one unit, and move the coordinate system origin to**(0, 1)**, then**P = (0, 2)** - Scale by half, makes
**P = (0, 1)**, possible path - Try to jump
`North`

, one unit, and we've reached**P**. **Then the answer is**`SEN`

The strategy to follow then is:

- Check if the target
**P**has become**(0 , 0)** - If not, check if
**P**is odd coordinate - if so, move towards the odd coordinate of
**P** - Transform the coordinate system, accumulating the steps taken
- Repeat

With **JavaScript**, we can write `moveExpogo`

which does this recursively.

```
const moveExpogo = ({ x, y, steps = "" }) => {
if (x === 0 && y === 0) {
return steps;
}
const isOddCoordinate = isCoordinateOdd({ x, y });
if (!isOddCoordinate) {
return IMPOSSIBLE;
}
const { step, nextX, nextY } = moveTowardsOdd({ x, y });
return moveExpogo({ x: nextX, y: nextY, steps: `${steps}${step}` });
};
```

Let's write the `moveTowardsOdd`

function, where the magic happens.

```
const scale = n => n / 2;
function moveTowardsOdd({ x, y }) {
if (x === 1 && y === 0) {
// can be finished in one move by moving EAST
return { step: EAST, nextX: scale(x - 1), nextY: y };
}
if (x === -1 && y === 0) {
// can be finished in one move by moving WEST
return { step: WEST, nextX: scale(x + 1), nextY: y };
}
if (x === 0 && y === 1) {
// can be finished in one move by moving NORTH
return { step: NORTH, nextX: x, nextY: scale(y - 1) };
}
if (x === 0 && y === -1) {
// can be finished in one move by moving SOUTH
return { step: SOUTH, nextX: x, nextY: scale(y + 1) };
}
if (x % 2 !== 0) {
// move EAST
const wouldBeOdd = isCoordinateOdd({ x: scale(x - 1), y: scale(y) });
if (wouldBeOdd) {
return { step: EAST, nextX: scale(x - 1), nextY: scale(y) };
}
// better to move WEST
return { step: WEST, nextX: scale(x + 1), nextY: scale(y) };
}
if (y % 2 !== 0) {
// move NORTH
const wouldBeOdd = isCoordinateOdd({ x: scale(x), y: scale(y - 1) });
if (wouldBeOdd) {
return { step: NORTH, nextX: scale(x), nextY: scale(y - 1) };
}
// better to move SOUTH
return { step: SOUTH, nextX: scale(x), nextY: scale(y + 1) };
}
}
```

Since `moveTowardsOdd`

is called by `moveExpogo`

only if the coordinate is odd, then we can conclude that the `if`

branches cover all possible cases.

Remember, odd coordinates

(X, Y)in this context are, those whereX + Y = odd

The properties `nextX`

and `nextY`

represent **P** when the origin is moved to a new position.

- Check if the
**P**coordinate is odd, if not, conclude the whole job is`IMPOSSIBLE`

. - If so move towards the odd coordinate
- Check if there's such a move that ends the jump sequence
- In either case, move the origin to the landing point,
- and scale the coordinate system by half
- Repeat until you arrive at the target
**P**

These two functions solve the problem, for all test sets of Code Jam, even when the coordinates get pretty large.

## Test set 3 (Visible Verdict)

1 ≤

T≤ 100.

-10^{9}≤X≤ 10^{9}.

-10^{9}≤Y≤ 10^{9}.

My Code Jam

`JavaScript`

implementation, that takes cases from`stdin`

, can be found here.A full implementation to run to your hearts desire can be found in this REPL.

## Visualization

These type of problems are challenging but also very fun!

Since we've got a string containing the jumping directions at ever i-th step, we can derive the coordinates where the **Expogo** lands us to reach point P.

JavaScript'sarray indexing is zero based, so there's no need to subtract one from it when calculating theExpogojumping distance

```
const dir2Coords = (directions) =>
directions.split("").reduce((prev, curr, index) => {
const [[x, y] = [0, 0]] = prev.slice(-1);
switch (curr) {
case NORTH:
return [...prev, [x, y + Math.pow(2, index)]];
case SOUTH:
return [...prev, [x, y - Math.pow(2, index)]];
case EAST:
return [...prev, [x + Math.pow(2, index), y]];
case WEST:
return [...prev, [x - Math.pow(2, index), y]];
default:
throw new Error("Invalid direction");
}
}, []);
```

This REPL does just that! Now we can use any graphical tool to draw the path taken!

I'll try out three.js for this. In particular the Voxel example, which already makes use of plane and targets coordinates given by the mouse position.

When the user holds down the shift key and clicks on a point, the **Expogo** path is drawn. Additionally, the mouse is followed by a cube, which is colored red if its impossible for the **Expogo** to reach it, otherwise it is colored green.

Live version here.

I also try to increase browser support as much as possible by avoiding arrow functions, though this might be futile.

Have you ever tried to compete in Code Jam? I assure you it is very fun!

Happy Hacking!

## Discussion