10
\$\begingroup\$

I am trying to write a solution to the following problem using as few characters as possible (to meme my friend and introduce him to golfing). Can any improvements be done to my code?

So the problem requires us to write a function called navigate in Python 3.6 (language of the judge, sorry, no walruses) that takes two arguments:

  • the first is a list of strings called "commands", which can be chosen from the following: Drive, TurnL, TurnR
  • the second is a tuple of three element, the first two are integers describing, respectively, the x and y coordinates of a "car", and the third element of the tuple is a single-character string chosen out of N, E, S and W, describing the direction which the car is facing initially

and returns a tuple with the same format as the second argument, which denotes the final coordinates and orientation of the car.

The commands are defined as follows (I tried to make them rigorous):

  • TurnL: change the orientation of the car with the following map: f:{N->W->S->E->N}
  • TurnR: change the orientation of the car with the inverse of f
  • Drive: increment or decrement the value of x or y by 1, depending on the current orientation (see below table)
orientation change in x change in y
N 0 1
E 1 0
S 0 -1
W -1 0

My current progress is 189 Bytes:

N,E,S,W='NESW'
def navigate(c,s):
 x,y,d=s
 for i in c:
  if i[4]=='L':d={N:W,W:S,S:E,E:N}[d]
  elif i[4]=='R':d={N:E,E:S,S:W,W:N}[d]
  else:x+=(d==E)-(d==W);y+=(d==N)-(d==S)
 return x,y,d

I do not think typing out the long word "navigation" is avoidable. However, although the question asks for an implementation of a function, I do believe any callable, including anonymous functions, methods, etc., would be accepted.


Below is a test case

>>> navigate(['Drive', 'TurnR', 'Drive'], (0, 0, 'E'))
(1, -1, 'S')
\$\endgroup\$
7
\$\begingroup\$

Flip comparisons

You can remove the space after if if you swap the order of the string comparisons, so if i[4]=='L' becomes if'L'==i[4].

String ordering

Because strings in Python can be compared, and are ordered alphabetically (with lowercase coming after uppercase, according to their ASCII codes), and we know the 5th character of each input string will always be L, R, or e, we can change == to > and compare with the next letter in the alphabet in each case. if'L'==i[4] becomes if'M'>i[4].

Unpacking i

Thanks to @ovs for this suggestion

Because i[4] is always the last character in the string i, we can unpack it with Python's * syntax in the for loop (for*_,i in c:), and remove both instances of [4]. The first 4 characters are stored in _ - which we just ignore - and the last becomes i.

Complex numbers

Complex numbers are often useful in problems like this, because you can do arithmetic with them like you can with vectors. This avoids the need for two separate variables, and eliminate the costly direction maps you used (d={N:W,W:S,S:E,E:N}).

1j**'ENW'.find(D) converts a direction character into a complex number which points in that direction. 'ENW'.find(d) returns the index of D in that string, so 0 for E, 1 for N, 2 for W, and, because S is not present, it returns -1. When we use 1j**, this gets the complex number with the right direction using the fact that \$ i \$ (1j), when exponentiated, returns different rotations of the complex numbers. \$ i^{-1} \$ is the same as \$ i^3 \$, so that handles the S case.

d*=1j and d/=1j turn d by 90° anticlockwise and clockwise respectively, again using \$ i \$'s rotation-like properties.

Python, 167 bytes

def navigate(c,s):
 x,y,D=s;p=0;d=1j**'ENW'.find(D)
 for*_,i in c:
  if'M'>i:d*=1j
  elif'S'>i:d/=1j
  else:p+=d
 return p.real+x,p.imag+y,'WESN'['-1-1j'.find(str(d))]

Attempt This Online!

This is a start. I feel like I'm missing a trick in converting p back to a coordinate pair, because .real .imag is quite verbose.

Thanks to @ovs for the slightly better way of converting the complex numbers back to compass directions, by storing overlapping string representations of the possible values, and searching within it.


Also, I don't know if it's possible to switch to Python 2, but if you can, you can save some bytes:

  • 2 bytes by extracting the s tuple inside the function argument list
  • 3 bytes using the expression for converting values to strings

Python 2, 162 bytes

def navigate(c,(x,y,D)):
 p=0;d=1j**'ENW'.find(D)
 for*_,i in c:
  if'M'>i:d*=1j
  elif'S'>i:d/=1j
  else:p+=d
 return p.real+x,p.imag+y,'WESN'['-1-1j'.find(`d`)]

Attempt This Online!

\$\endgroup\$
4
  • 2
    \$\begingroup\$ if'e'>i:d*=(-1j,1j)['M'>i] as ternary expression can also save some bytes \$\endgroup\$
    – chnmasta05
    Jan 9 at 15:09
  • \$\begingroup\$ I swear this is my last observation. Getting rid of p completely and swapping its usage with x can save some bytes because x.real is what we needed \$\endgroup\$
    – chnmasta05
    Jan 9 at 15:27
  • \$\begingroup\$ @ovs it turns out that doesn't actually work because d, when stringified, has a .0 on the end because it's not an integer \$\endgroup\$
    – pxeger
    Jan 9 at 15:41
  • \$\begingroup\$ Ahh I see, also -1j seems to be represented by (-0-j) at times: ato.pxeger.com/… \$\endgroup\$
    – ovs
    Jan 9 at 15:57
6
\$\begingroup\$

pxeger's answers covers how this problem would best apporached on our site, where input and output formats are often flexible. However, with your fixed format we can do a bit better by mostly working within the format.

Our starting point is your function with a few improvements taken from the other answer (182):

N,E,S,W='NESW'
def navigate(c,s):
 x,y,d=s
 for*_,i in c:
  if'L'==i:d={N:W,W:S,S:E,E:N}[d]
  elif'R'==i:d={N:E,E:S,S:W,W:N}[d]
  else:x+=(d==E)-(d==W);y+=(d==N)-(d==S)
 return x,y,d

Try it online!


First, lets focus on the rotations. Dictionaries are convenient data structures to implement lookup tables, but are a bit lengthy. Using strings instead can help here:

  if'L'==i:d='WSEN'['NWSE'.find(d)]
  elif'R'==i:d='ESWN'['NESW'.find(d)]

With a bit of reordering, we can use the same value for the '...'.find expression:

  j='NWSE'.find(d)
  if'L'==i:d='WSEN'[j]
  elif'R'==i:d='ENWS'[j]

And str.find returns -1 if the value is not in the string, which means E can be removed.

The two cases are now quite similar and can be combined into one by shifting the index based on i:

  j='NWS'.find(d)
  if'e'>i:d='WSEN'[j-(2 if i>'L' else 0)] # shorter with j-2*(i>'L')

Plugging this into our starting point, we get to 155 bytes:

def navigate(c,s):
 x,y,d=s
 for*_,i in c:
  j='NWS'.find(d)
  if'e'>i:d='WSEN'[j-2*(i>'L')]
  else:x+=(d=='E')-(d=='W');y+=(d=='N')-(d=='S')
 return x,y,d

Try it online!


Now we can look at the moving part. The value of j can be used here as well, to get expressions to update the position:

d j='NWS'.find(d) j%2*j ~j%2*~-j
N 0 0 -1
W 1 1 0
S 2 0 1
E -1 -1 0

Python 3, 134 bytes

def navigate(c,s):
 x,y,d=s
 for*_,i in c:
  j='NWS'.find(d)
  if'e'>i:d='WSEN'[j-2*(i>'L')]
  else:x-=j%2*j;y-=~j%2*~-j
 return x,y,d

Try it online!

Finally, a few more bytes can be saved by using ord(d) instead of 'NWS'.find(d) and using short position and direction update formulas found by a brute force search: 131 bytes

\$\endgroup\$
4
  • \$\begingroup\$ This solution is very amazing! However, the 133 Byte version does not work for navigate(['TurnL', 'Drive', 'TurnR'], (0, 0, 'E')). \$\endgroup\$
    – chnmasta05
    Jan 9 at 16:45
  • 1
    \$\begingroup\$ @chnmasta05 thanks for catching that, should be fixed now. TBH I'm surprised the other version handles this the right way, as I thought North would be negative y. \$\endgroup\$
    – ovs
    Jan 9 at 16:54
  • 1
    \$\begingroup\$ but now the first case breaks, unfortunately because now the third column of your table becomes 1, 2, -1, 2, so every Drive when the direction is E or W increments y by 2 \$\endgroup\$
    – chnmasta05
    Jan 9 at 16:57
  • 1
    \$\begingroup\$ @chnmasta05 Yeah that formula didn't make much sense on second thought. Now added a new version with proper testing \$\endgroup\$
    – ovs
    Jan 9 at 22:17

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.