17
\$\begingroup\$

You're at integer coordinates \$(x,y)\$ facing one of North, South, East, or West. Your goal is to walk home to \$(0,0)\$. At each step, you may do one of:

  • Walk one step in the current facing direction, that is to whichever of \$(x+1,y)\$, \$(x-1,y)\$, \$(x,y-1)\$, or \$(x,y+1)\$ you're facing.
  • Rotate 90 degrees left, staying in place.
  • Rotate 90 degrees right, staying in place.

Your goal is to write code that will eventually get you home to \$(0,0)\$ if called repeatedly, each time with your current position and facing. Your code must always give the same output for a given input, which precludes using randomness or past state.

Input:

Two integers \$(x,y)\$ and a facing direction. The 4 possible facing directions are given as numbers 0 through 3, or alternatively 1 through 4, matched as you choose. The position can also be taken as a vector or point or complex number.

You won't be given \$(0,0)\$ where you're already home. Don't worry about overflows caused by huge inputs.

Output:

One of three distinct consistent outputs corresponding to the possible actions of walking straight, turning left, and turning right.

\$\endgroup\$
  • \$\begingroup\$ Do we need three outputs if one is never used or will two be ok in that scenario? \$\endgroup\$ – Post Rock Garf Hunter Feb 1 at 2:09
  • \$\begingroup\$ @PostRockGarfHunter Definitely, I guess that's the same as having three output values one of which never happens. \$\endgroup\$ – xnor Feb 1 at 2:12
  • \$\begingroup\$ The distinction I would make is that it would allow statically typed languages to output booleans. There is no third value which is not output in that case. \$\endgroup\$ – Post Rock Garf Hunter Feb 1 at 2:17
  • 5
    \$\begingroup\$ @PostRockGarfHunter Ah, hadn't thought about that. Still totally fine. NASCAR drivers get home with only left turns! \$\endgroup\$ – xnor Feb 1 at 2:20
  • 1
    \$\begingroup\$ @xnor can the direction be a complex number too (1,-1,i,-i)? \$\endgroup\$ – ngn Feb 1 at 2:24

12 Answers 12

12
\$\begingroup\$

Haskell, 21 bytes

(!!).([(<0),(>0)]<*>)

Try it online!

Outputs a boolean with True being move forward and False being turn right.

Haskell, 28 bytes

Here's a version that is easy to understand / translate into any language.

f(x,y)d=[x<0,y<0,x>0,y>0]!!d

Try it online!

Explanation

The idea here is two-fold

  • We notice that we only ever need to turn in one direction. A turn left is just 3 turns right. So we will limit ourselves to only right turns.

  • Now we notice that given a direction there is a simple condition that can check if we ought to move forward. Namely the sign of one of the two variables.

With this information we construct out solution, by making a list of the conditions and indexing the list with the direction. True means the condition was passed and we can move forward (so we do), False means the condition was failed and we should not move forward, so we rotate.

Now the specification allows us to just output these values as is, since they are distinct and we have no intention of turning left.

\$\endgroup\$
  • \$\begingroup\$ so, if you're on one of the axes (x=0 or y=0, but not x=y=0), [x<0,y<0,x>0,y>0] would be [False,False,False,False] and you would never return True for "move forward"? \$\endgroup\$ – ngn Feb 1 at 3:21
  • \$\begingroup\$ @ngn If all four are false you must be on both of the axes. \$\endgroup\$ – Post Rock Garf Hunter Feb 1 at 3:41
  • \$\begingroup\$ oh.. you're right \$\endgroup\$ – ngn Feb 1 at 4:15
7
\$\begingroup\$

Pyth, 7 bytes

qi<L0E2

Try it online!

Input is in the form:

3
[3, 4]

The solution is simple:

  • <L0E maps each coordinate to 0 if the coordinate is positive, and 1 if the coordinate is nonpositive.

  • i ... 2 converts the list to a number by interpreting it as binary.

  • q checks whether the resulting number is equal to the other input.

  • True means forward, False means turn, the direction is irrelevant, the third output is irrelevant.

We use the following mapping:

  • 0: up - the positive y direction.
  • 1: right - the positive x direction.
  • 2: left - the negative x direction.
  • 3: down - the negative y direction.

The path the walk takes is a sort of a staircase - from the (-, -) quadrant to (-, 1) to (1, 1) to (0, 1) to (0, 0) for instance.

\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan Fixed, thanks. \$\endgroup\$ – isaacg Feb 2 at 2:50
4
\$\begingroup\$

Python 2, 30 bytes

lambda i,d:abs(i+1j**d)<abs(i)

Try it online!

Takes as input a Gaussian integer for position, and an integer in {0,1,2,3} for the direction; outputs True for forward, False for rotate counter-clockwise, and whatever you like for rotate clockwise, because that never happens :).

\$\endgroup\$
  • \$\begingroup\$ You need to take direction as a number. 1j**d should do. \$\endgroup\$ – xnor Feb 1 at 5:27
  • \$\begingroup\$ @xnor: Good catch! Thanks. \$\endgroup\$ – Chas Brown Feb 1 at 5:34
4
\$\begingroup\$

Jelly, 4 bytes

>-Ḅ⁼

Try it online!

A dyadic link taking the co-ordinates as the left argument and the direction faced as the right. Returns 0 for turn and 1 for move forwards.

The TIO footer picks a random starting point and demonstrates that the link will ultimately reach [0,0]

Based on @isaacg’s Pyth answer so be sure to upvote that one too!

Explanation

>-   | Greater than -1
  Ḅ  | Convert from binary time decimal integer
   ⁼ | Equal to right argument
\$\endgroup\$
3
\$\begingroup\$

J, 12 11 bytes

[>&|[+0j1^]

Try it online!

idea

Our idea is simple: Walk straight, and see if that gets us closer in Euclidean distance. If yes, return "walk straight". If not, return "turn left".

input / output

Take position as a complex number (left arg) and direction as a 0-indexed int (right arg). Similar to @PostRockGarfHunter's answer, we constrain our output to two values:

  1. 1 - Walk straight
  2. 0 - Turn left

how

  1. [+0j1^] First we convert our right arg integer to a complex number by raising i 0j1 to the right arg 0j1^]. Then we add that + to the left arg [. This represents our "next position", if we were to walk straight.

  2. [>&| Is the left arg [ (current position) greater than > the next position after converting both to Euclidean distance from origin &|?

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Classic), 10 9 bytes

⊣⊃0(>,<)⊢

Try it online!

all credit to Post Rock Garf Hunter's answer

the tio link shows numbers of steps for the square area around (0,0) for the 4 initial directions

left arg: direction

right arg: coord pair

, concatenation

0(>,<)⊢ is equivalent to (0>⊢),(0<⊢), i.e. the 4-vector (0>x),(0>y),(0<x),(0<y)

⊣⊃.. indexing with the left arg

\$\endgroup\$
  • 6
    \$\begingroup\$ (>,<) <- emoji here \$\endgroup\$ – tsh Feb 1 at 5:28
  • 2
    \$\begingroup\$ @tsh ..trying to stuff a shovel (⊣⊃) in its ear (0) \$\endgroup\$ – ngn Feb 1 at 5:40
3
\$\begingroup\$

JavaScript (Node.js), 26 25 24 bytes

(x,y,d)=>--d%2*x<--d%2*y

Try it online!

d is direction one of [0, 1, 2, 3] for [west, north, east, south]

The expression
(d - 1) % 2 gives deltaX one of [-1, 0, 1, 0]and
(d - 2) % 2 gives deltaY one of [0, -1, 0, 1]

Either x * deltaX or y * deltaY will be non zero and will be negative if we are heading towards home. So if
(deltaX * x + deltaY * y < 0) also expressed as
(deltaX * x < deltaY * -y) we go forward = true, else we turn left = false.

To get to 24 I swapped north and south to change '-y' to 'y'

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer and nice test suite! \$\endgroup\$ – Arnauld Feb 1 at 15:19
2
\$\begingroup\$

JavaScript (ES6),  28  27 bytes

Takes input as (x,y,d) with \$d=0\$ for North, \$1\$ for South, \$2\$ for West, \$3\$ for East.

Output:

  • true : turn right
  • false : walk straight
(x,y,d)=>(x&&2|x<0||y<0)!=d

Try it online!

How?

This is parsed as:

           +--------------------> 0 if x = 0, 3 if x < 0, 2 if x > 0
           |                +---> 1 if the first expression is 0 and y < 0, 0 otherwise
   ________|_______        _|_
  /                \      /   \
((x && (2 | (x < 0))) || (y < 0)) != d
\$\endgroup\$
  • \$\begingroup\$ Looks like your directions are actually [south,north,west,east] and true means turn left. \$\endgroup\$ – James Feb 1 at 12:01
  • 1
    \$\begingroup\$ @James Your interpretation is equivalent to mine, except you seem to assume that \$y>0\$ means South, while I assumed it means North. \$\endgroup\$ – Arnauld Feb 1 at 12:56
1
\$\begingroup\$

Retina 0.8.2, 38 35 bytes

. (-?).*( -?).*
$*-$2$1$1
^(-*) \1$

Try it online! Link includes demonstration of path taken from 5 3 to the origin. Takes input as direction first, then coordinates. Edit: Saved 3 bytes by porting @isaacg’s Pyth answer. Direction encodes as y--, x--, x++, y++. Outputs 1 to move, 0 to turn. Explanation:

. (-?).*( -?).*

Capture the signs of the coordinates.

$*-$2$1$1

Convert the direction to unary, and convert the coordinate signs from base 2, discarding everything else.

^(-*) \1$

Compare the direction to the base 2 decoded signs.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 4 bytes

d2βQ

Port of @NickKennedy's Jelly answer, so make sure to upvote him as well!

First input is the coordinate, second input is the current direction digit (in the range [0,3]).
Outputs 0 to turn, and 1 to move forward.

Try it online or verify a random coordinate will eventually result in [0,0] or verify all coordinates in the range [[-1,1],[1,1]] with all possible directions [0,3].

Explanation:

d     # Check for both values in the (implicit) input-coordinate whether it's non-negative (>=0)
 2β   # Convert this from a binary-list to an integer
   Q  # And check whether it's equal to the (implicit) direction input-integer
      # (after which this is output implicitly)
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 13 9 bytes

⁼↨E²›⁰N²N

Try it online! Link is to verbose version of code. Edit: Saved 4 bytes by porting @isaacg’s Pyth answer. Uses the same "move or turn" approach; - means move, no output means turn. The directions encode as y--, x--, x++, y++. Explanation:

   ²        Literal 2
  E         Map over implicit range
     ⁰      Literal 0
    ›       Is greater than
      N     Input coordinate
 ↨     ²    Convert from base 2
⁼           Equals
        N   Input direction
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 47 bytes

z;m(x,d)int*x;{x=abs(z=x[d/2])>abs(z+d%2*2-1);}

Returns 0 to move forward and 1 to turn clockwise. It never moves counterclockwise but let's just call that 2.

North is 3, south is 2, east is 1, and west is 0.

-2 bytes thanks to ceilingcat!

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.