21
\$\begingroup\$

Where am I now?

Given a string d, containing only the letters NSWE, determine the coordinates I've traveled (from left to right, consuming greedily) and the final coordinate where I reside.

The rules for reading coordinates from left-to-right:

  • If the next character is N or S:
    • If the character after the N or S is another N or S:
      • Consume only the first N or S.
      • Output [0,1] for N
      • Output [0,-1] for S
    • If the character after the N or S is W or E:
      • Consume both the N or S and the W or E.
      • Output [1,1] or [-1,1] for NE and NW, respectively.
      • Output [1,-1] or [-1,-1] for SE and SW, respectively.
  • If the character is an E or W not preceded by an S or N:
    • Consume the E or W.
    • Output [1,0] for E.
    • Output [-1,0] for W.

Worked Example

NSWE

[0,1]   (North      N)
[-1,-1] (South-west SW)
[1,0]   (East       E)
[0,0]   (N+SW+E = Didn't actually move)

Note this can be in any format, here are other examples of valid output:

[[0,1],[-1,-1],[1,0],[0,0]]


[[[0,1],[-1,-1],[1,0]],[0,0]]


"0,1\n0,-1\n-1,0\n1,0\n0,0"

Etc...


More Examples

SWSENNESWNE

[-1,-1]
[1,-1]
[0,1]
[1,1]
[-1,-1]
[1,1]
[1,0]

NNEESESSWWNW

[0,1]
[1,1]
[1,0]
[1,-1]
[0,-1]
[-1,-1]
[-1,0]
[-1,1]
[0,0]

NENENEE

[1,1]
[1,1]
[1,1]
[1,0]
[4,3]

NEN

[1,1]
[0,1]
[1,2]

EEE

[1,0]
[1,0]
[1,0]
[3,0]

Rules

  • You may output in any convenient format that doesn't violate loopholes.
  • You must consume greedily, NWE is never N,W,E, it is always NW,E.
    • This applies to: SW*, SE*, NW*, NE*.
    • You are consuming left to right, greedily.
  • The is , lowest byte-count wins.
\$\endgroup\$
  • \$\begingroup\$ "determine the coordinates I've traveled": I'm not sure if it does really match what's described afterwards. It's more like "determine the vectors of all my moves". Only the final output is actual coordinates. \$\endgroup\$ – Arnauld Apr 24 '18 at 20:08
  • 1
    \$\begingroup\$ A test case that walks to [4, 3] or so would make it a little easier to see what's going on in the test output. \$\endgroup\$ – Lynn Apr 24 '18 at 20:49
  • 3
    \$\begingroup\$ Are complex numbers formatted as 1, -1j, (-1+1j) etc a valid output format? \$\endgroup\$ – Lynn Apr 24 '18 at 22:34
  • 2
    \$\begingroup\$ Based on the absence of this case in both the rules and examples given I assume the input-String will never end in an 'N' or 'S'? \$\endgroup\$ – Kevin Cruijssen Apr 25 '18 at 7:51
  • 1
    \$\begingroup\$ Is consuming greedily actually different than not? Since NE is just N+E shouldn't it not matter? \$\endgroup\$ – Wheat Wizard Apr 25 '18 at 15:08

14 Answers 14

7
\$\begingroup\$

Python 2, 116 bytes

import re
a=[(int(s,35)%5-3,('N'in s)-('S'in s))for s in re.findall('[NS][EW]?|.',input())]
print a,map(sum,zip(*a))

Try it online!

With output as [(3+4j), 1, -1j, …], 91 bytes

lambda x:[sum(1j**(ord(c)%8%5)for c in s)for s in[x]+re.findall('[NS][EW]?|.',x)]
import re

Try it online!

This lambda returns a list of Gaussian integers: the first is the final coordinate, and all others are the steps required to get there.

\$\endgroup\$
5
\$\begingroup\$

Attache, 80 bytes

V#Sum##{Chop[1-ToBase[22260446188,3],2][Sum@Ords=>MatchAll[_,/"[NS][WE]|."]%11]}

Try it online!

This is an anonymous function which takes one string argument.

Explanation

The first task is to implement the parsing phase of this question. I found it shortest to use a simple Regex to parse the input (_):

MatchAll[_,/"[NS][WE]|."]

This matches all occurrences of the regex [NS][WE]|., as seen in many other answers. This greedily yields the requested directions.

Now, we're going to apply a hash function to each direciton. We take the codepoints of each direction and sum them. This gives the following mapping:

Direction       Ord-sum
E               69
N               78
S               83
W               87
NE              147
SE              152
NW              165
SW              170

We shall try to map these values to a smaller domain; modulo is useful for this, and we can demonstrate that the smallest modulo which results in unique values for all given inputs is 11. Sorting by remainders, this gives us the following table:

Direction       Ord-sum         % 11
NW              165             0
N               78              1
E               69              3
NE              147             4
SW              170             5
S               83              6
SE              152             9
W               87              10

Now, we have an input correspondence, as encoding by Sum@Ords=>[...]%11. Next, we have to transform these remainders into points. We shall try to derive another mapping, which means inserting "sparse-filling values" to hashes which do not correspond to directions shall be useful:

Direction       Hash        Coordinates
NW              0           [-1, 1]
N               1           [0, 1]
--             (2)          [0, 0]
E               3           [1, 0]
NE              4           [1, 1]
SW              5           [-1, -1]
S               6           [0, -1]
--             (7)          [0, 0]
--             (8)          [0, 0]
SE              9           [1, -1]
W               10          [-1, 0]

We currently have a series of points, which can gives a list indexable by the hash:

[-1, 1] [0, 1] [0, 0] [1, 0] [1, 1] [-1, -1] [0, -1] [0, 0] [0, 0] [1, -1] [-1, 0]

Now, we shall compress this, seeing as how its only composed of -1s, 0s, and 1s. Since the list represents pairs, we can flatten the list without losing data. Then, if we take each number x and calculate 1-x, we get the following list:

2 0 1 0 1 1 0 1 0 0 2 2 1 2 1 1 1 1 0 2 2 1

We can convert this into a base 3 number:

20101101002212111102213

Converting to base 10:

20101101002212111102213 ≡ 2226044618810

To summarize, we've taken our points, un-paired them, took each element subtracted from 1, and converted from base 3, giving us 22260446188. We can decompress as such:

  1. Convert to base 3: ToBase[22260446188,3]
  2. Take each number subtracted from one (self-inverse): 1-ToBase[22260446188,3]
  3. Re-pair the list: Chop[1-ToBase[22260446188,3],2]

This gives us our original set of pairs. Then, we can perform the aforementioned indexing like this:

(chopped value)[hashes]

Since, in Attache, indexing by an array returns all elements corresponding to those indices. (So, [1,2,3,4][ [0,0,-1,1] ] = [1,1,4,2].) Now, we have the directions of the path that the OP walked. What's left is to calculate the sum.

So we capture this result in a lambda {...} and put it as the first function in a function composition (a##b), with the second being V#Sum. This is a fork, which, given input x, expands to be:

V[x, Sum[x]]

Sum, when given an 2D array, happens to sum every column in the array (as a result of vectorized summation). So, this pairs the directions with the final destination, and we have our final result.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 102 bytes

Returns a string.

s=>s.replace(/[NS][EW]|./g,s=>(D=d=>!!s.match(d),x+=h=D`E`-D`W`,y+=v=D`N`-D`S`,[h,v]+`
`),x=y=0)+[x,y]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I like the use of template functions! :D \$\endgroup\$ – Conor O'Brien Apr 24 '18 at 21:44
  • \$\begingroup\$ @ConorO'Brien Yeah, they're pretty handy here. All the hashing sorcery spells that I've summoned so far are at least a bit longer. \$\endgroup\$ – Arnauld Apr 24 '18 at 21:52
4
\$\begingroup\$

MATL, 45 bytes

'NS' 'WE'Z*Z{2MhX{h'eklihfmj'X{YX9\3_2&YAqts

Try it online! Or verify all test cases.

Explanation (with example)

Consider input 'NSWE' as an example.

'NS' 'WE'  % Push these two strings
           % STACK: 'NS', 'WE'
Z*         % Cartesian product. Gives a 4×2 char matrix
           % STACK: ['NW'; 'NE'; 'SW'; 'SE']
Z{         % Cell array of rows (strings)
           % STACK: {'NW', 'NE', 'SW', 'SE'}
2M         % Push again the inputs of the second-last function call
           % STACK: {'NW', 'NE', 'SW', 'SE'}, 'NS', 'WE'
h          % Concatenate horizontally
           % STACK: {'NW', 'NE', 'SW', 'SE'}, 'NSWE'
X{         % Cell array of individual elements (chars)
           % STACK: {'NW', 'NE', 'SW', 'SE'}, {'N', 'S', 'W', 'E'}
h          % Concatenate horizontally
           % STACK: {'NW', 'NE', 'SW', 'SE', 'N', 'S', 'W', 'E'}
'eklihfmj' % Push this string
           % STACK: {'NW', 'NE', 'SW', 'SE', 'N', 'S', 'W', 'E'}, 'eklihfmj'
X{         % Cell array of individual elements (chars)
           % STACK: {'NW','NE','SW','SE','N','S','W','E'},{'e','k','l','i','h','f','m','j'}
YX         % Implicit input. Regexp replace: replaces 'NW' by 'e', then 'NE' by 'k', etc.
           % Note that the two-letter combinations are replaced first, which implements
           % the greediness; and the target letters do not appear in the source, which
           % avoids unwanted interactions between replacements
           % STACK: 'hlj'
9\         % Modulo 9 (of codepoints), element-wise
           % STACK: [5, 0, 7]
3_2&YA     % Convert to base 3 with 2 digits. Gives a 2-column matrix
           % STACK: [1, 2; 0, 0; 2, 1]
q          % Subtract 1, element-wise
           % STACK: [0, -1; -1, -1; 1, 0]
tXs        % Duplicate. Sum of each column
           % STACK: [0, -1; -1, -1; 1, 0], [0, 0]
           % Implicit display
\$\endgroup\$
4
\$\begingroup\$

Java (JDK 10), 171 bytes

s->{var r="";int i=0,l=s.length,c,x=0,y=0,Y,X;for(;i<l;X=c>1||i<l&&(c=~-s[i]/6%4)>1&&++i>0?c*2-5:0,r+=X+","+Y+" ",x+=X,y+=Y)Y=(c=~-s[i++]/6%4)<2?1-c*2:0;return r+x+","+y;}

Try it online!

Explanations

Thanks to c=~-s[i]/6%4, the following mapping is done:

'N' -> ascii: 78 -> -1 = 77 -> /6 = 12 -> %4 = 0
'S' -> ascii: 83 -> -1 = 83 -> /6 = 13 -> %4 = 1
'W' -> ascii: 87 -> -1 = 86 -> /6 = 14 -> %4 = 2
'E' -> ascii: 69 -> -1 = 68 -> /6 = 11 -> %4 = 3
  • NS is checked with c<2 and mapped to +1/-1 using 1-c*2;
  • EW is checked with c>1 and mapped to +1/-1 using c*2-5.

Credits

\$\endgroup\$
  • \$\begingroup\$ Ah, you posted your Java answer while I was typing the explanation of mine. :) Since we both use a completely different approach I'll leave mine for now. Too bad variables used in lambdas need to be effectively final, otherwise you could have returned a String instead of a List to save bytes. \$\endgroup\$ – Kevin Cruijssen Apr 25 '18 at 8:40
  • \$\begingroup\$ Thanks, it only saved a few bytes (4), but it's better than nothing ;) \$\endgroup\$ – Olivier Grégoire Apr 25 '18 at 9:06
  • \$\begingroup\$ @KevinCruijssen Thanks, it seemed rather obvious at first, but I was working on another approach which reduced my byte-count by more than 30. A "parsing" one, not a "matching" one. \$\endgroup\$ – Olivier Grégoire Apr 25 '18 at 9:28
  • 1
    \$\begingroup\$ Sigh.. 172 bytes \$\endgroup\$ – Kevin Cruijssen Apr 25 '18 at 11:37
  • 1
    \$\begingroup\$ @KevinCruijssen Sorry, it's a mess integrating your changes... I'm taken at work and I forget to refresh this page... Thanks for all anyways ^^' The credit count is very likely below your actual credit. Sorry for that too :s \$\endgroup\$ – Olivier Grégoire Apr 25 '18 at 11:53
3
\$\begingroup\$

Retina 0.8.2, 93 bytes

.+
$&¶$&
\G[NS]?[EW]?
$&¶
G`.
W
J
%O`.
+`EJ|NS

m`^((J)?[EJ]*)((S)?[NS]*)
$#2$*-$.1,$#4$*-$.3

Try it online! Explanation:

.+
$&¶$&

Duplicate the input.

\G[NS]?[EW]?
$&¶

Split the first copy up into directions.

G`.

Remove extraneous blank lines created by the above process.

W
J

Change W into J so that it sorts between E and N. (Moving E to between S and W would also work.)

%O`.

Sort each line into order.

+`EJ|NS

Delete pairs of opposite directions (this only affects the last line of course).

m`^((J)?[EJ]*)((S)?[NS]*)
$#2$*-$.1,$#4$*-$.3

Count the number of horizontal and vertical movements, adding signs where necessary.

Those of you who know the differences between Retina 0.8.2 and Retina 1 will want to point out that I can save 2 bytes in Retina 1 because it uses * instead of $*. While I was there I tried to simplify the splitting process but I was unable to reduce the byte count further, I was only able to equal it with this:

L$`$(?<=(.*))|[NS]?[EW]?
$&$1
\$\endgroup\$
3
\$\begingroup\$

Java 10, 269 265 243 bytes

s->{var r="";int x=0,y=0,t,X,Y,a;for(;!s.isEmpty();r+=X+"|"+Y+" ",s=s.substring(++t),x+=X,y+=Y){a=s.charAt(t=0);if(s.matches("[SN][WE].*")){X=s.charAt(1)<70?1:-1;Y=1-a%2*2;t++;}else{X=a<70?1:a>86?-1:0;Y=a>69&a<87?1-a%2*2:0;}}return r+x+"|"+y;}

Definitely not the right language for this challenge..

Try it online.

Explanation:

s->{                  // Method with String as both parameter and return-type
  var r="";           //  Result-String, starting empty
  int x=0,            //  Ending `x`-coordinate, starting at 0
      y=0,            //  Ending `y`-coordinate, starting at 0
      t,X,Y,a;        //  Temp-integers
  for(;!s.isEmpty()   //  Loop as long as the input-String is not empty yet
      ;               //    After every iteration:
       r+=X+"|"+Y+" ",//     Append the current steps to the result-String
       s=s.substring(t),
                      //     Remove the first `t` characters from the input-String
       x+=X,y+=Y){   //      Append the ending `x`,`y` coordinates with the steps
    a=s.charAt(0);   //    Set `a` to the first character of the input-String to save bytes
    t=1;             //    Set `t` to 1
    if(s.matches("[SN][WE].*")){
                     //   Else-if the input-String starts with N/S followed by E/W:
      X=s.charAt(1)<70?1:-1;
                     //    Set `X` to 1 if 'E', -1 if 'W'
      Y=1-a%2*2;     //    Set `Y` to 1 if 'N', -1 if 'S'
      t++;}          //    Increase `t` by 1
    else{            //   Else:
      X=a<70?1:a>86?-1:0;
                     //    Set `X` to 1 if 'E', -1 if 'W', 0 if 'N' or 'S'
      Y=a>69&a<87?1-a%2*2:0;}}
                     //    Set `Y` 1 if 'N', -1 if 'S', 0 if 'E' or 'W'
  return r+x+"|"+y;} //  Append the ending coordinates, and return the result-String
\$\endgroup\$
  • 1
    \$\begingroup\$ Java answers get points though cause everyone gets them :). \$\endgroup\$ – Magic Octopus Urn Apr 25 '18 at 23:29
  • \$\begingroup\$ @MagicOctopusUrn True. :) And I still enjoy golfing in Java, even though you'll never be the shortest.. Unless you're the only one to answer (got two accepted Java answers.. XD). For this challenge however, the Java answer by OlivierGrégoire is about 70 bytes shorter, so most upvotes should go to him. \$\endgroup\$ – Kevin Cruijssen Apr 26 '18 at 6:37
2
\$\begingroup\$

Perl 5 -n, 94 bytes

$x=$y=0;%X=qw/E ++ W --/;%Y=qw/N ++ S --/;s%(N|S)?(E|W)?%"say $X{$2}\$x.','.$Y{$1}\$y"if$&%gee

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 102 bytes

f=
s=>s.replace(/((N)|(S))?((E)|(W))?/g,(m,v,n,s,h,e,w)=>(x+=h=!w-!e,y+=v=!s-!n,m?[h,v]+`
`:[x,y]),x=y=0)
<input oninput=o.textContent=/[^NSEW]/.test(this.value)?``:f(this.value)><pre id=o>0,0

Returns a string.

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

Ruby, 75 71 bytes

->x{[*x.scan(/[NS][EW]?|./),x].map{|s|s.chars.sum{|c|1i**(c.ord%8%5)}}}

Try it online!

-4 bytes thanks to benj2240.

Since returning complex numbers looks to be an acceptable output format, I guess it won't get much golfier than just making a port of the very nice Lynn's answer.

\$\endgroup\$
  • \$\begingroup\$ Very nice. you can save a few bytes by skipping the inner map, passing its block directly to sum: Try it online! \$\endgroup\$ – benj2240 Apr 25 '18 at 14:59
1
\$\begingroup\$

F# (Mono), 269 bytes

let f s=
 let l,h=(string s).Replace("NW","A").Replace("NE","B").Replace("SW","C").Replace("SE","D")|>Seq.map(function 'N'->0,1|'S'->0,-1|'W'-> -1,0|'E'->1,0|'A'-> -1,1|'B'->1,1|'C'-> -1,-1|'D'->1,-1)|>Seq.mapFold(fun(x,y) (s,t)->(s,t),(x+s,y+t))(0,0)
 Seq.append l [h]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Hi, welcome to PPCG. Unfortunately your're missing the last item of your output, which should be the position where you ended. So for the NSWE you are currently outputting (0,1), (-1,-1), (1,0), but a fourth output should be the sum of those coordinates, so (0,0) (because 0+-1+1 = 0 and 1+-1+0 = 0). \$\endgroup\$ – Kevin Cruijssen Apr 25 '18 at 14:20
  • \$\begingroup\$ @KevinCruijssen OK, I didn't catch that. Made an update. \$\endgroup\$ – Henrik Hansen Apr 25 '18 at 14:42
  • 1
    \$\begingroup\$ Seems to work great now, so +1 from me. Enjoy your stay! :) And in case you haven't seen it yet, Tips for golfing in F# and Tips for golfing in <all languages> might be interesting to read through. \$\endgroup\$ – Kevin Cruijssen Apr 25 '18 at 15:53
1
\$\begingroup\$

sed, 125

The taking liberties with output format version:

Score includes +1 for the -r parameter to sed.

s/(N|S)(E|W)/\L\2,\1 /g
s/N|S/,& /g
s/E|W/&, /g
s/N|E/A/gi
s/S|W/a/gi
p
:
s/(\S*),(\S*) (\S*),(\S*)/\1\3,\2\4/
t
s/Aa|aA//
t

Try it online.

Output is as follows:

  • coordinate elements are comma-separated
  • each set of coordinates are TAB-separated
  • the final coordinate is on a new line
  • all numbers are in ℤ-unary:
    • a string of A characters represents the +ve integer len(string)
    • a string of a characters represents the -ve integer -len(string)
    • the empty string represents 0

For example:

  • , is [0,0]
  • ,AA is [0,2]
  • aaa, is [-3,0]

sed 4.2.2 including GNU exec extension, 147

The sensible output format version:

Score includes +1 for the -r parameter to sed.

s/(N|S)(E|W)/\L\2 \1\n/g
s/N|S/0 &\n/g
s/E|W/& 0\n/g
s/N|E/1/gi
s/S|W/-1/gi
p
:
s/(\S+) (\S+)\n(\S+) (\S+)/\1+\3 \2+\4/
t
s/\S+/$[&]/g
s/^/echo /e

Output is given as space-separated coordinates, one per line. There is an extra newline between the penultimate and ultimate sets of coordinates - not sure if that is problematic or not.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 153 bytes

let a regex do the splitting; loop through the matches, print and sum up the intermediate results:

preg_match_all("/[NS][EW]?|E|W/",$argn,$m);foreach($m[0]as$s){$x+=$p=strtr($s[-1],NEWS,1201)-1;$y+=$q=strtr($s[0],NEWS,2110)-1;echo"$p,$q
";}echo"$x,$y";

Run as pipe with -nR or try it online.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 173 bytes

It's interesting doing this one in a language with no regex support!

f(char*s){char*t="[%d,%d]\n";int x[4]={0},i;for(;*s;*x=x[1]=!printf(t,x[1],*x))for(i=-1;i<5;)if(*s=="S NW E"[++i]){x[i/3+2]+=x[i/3]=i%3-1;i+=2-i%3;s++;}printf(t,x[3],x[2]);}

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.