14
\$\begingroup\$

Many of us are familiar with the game Tron. You control a "lightcycle" placed on a grid. The lightcycle always moves forward (though you control the direction) and leaves a permanent trail behind it. If you run into a trail, you crash!

The goal here is to determine if a given path is a valid loop, that is, it returns to its starting point without "crashing". To do this, we assume we start at the point (0,0). An input is given in the form N2E1S2W1, with a series of cardinal directions (N is north, E is east, and so on), each followed by the distance to travel that direction. In this example, you would travel

N2 : North 2 to (0,2)
E1 : East 1  to (1,2)
S2 : South 2 to (1,0)
W1 : West 1  to (0,0)

A path is considered valid if it ends at (0,0) without visiting any other coordinate more than once (it visits (0,0) exactly twice. Once at the start, and once at the end). Keep in mind than in the above example, to get from (0,0) to (0,2), we necessarily visit (0,1) as well.

Other examples:

input        -> output
N1E1S1W1     -> true
N1E1N1E1S2W2 -> true
N1S1E1W1     -> false     // Visits (0,0) 3 times
N4E2S2W4S2E2 -> false     // Visits (0,2) twice
N3E2S3       -> false     // Does not return to (0,0)
N1S1         -> anything  //I don't care how you evaluate this case

Your output can be in any form so long as it gives the same output for any truthy or falsey value.

The input can be taken as a string or as a list of characters, either in the form S1N2E3... or SNNEEE... There's is also no hard limit on the grid size, but assume the input isn't going to overflow anything. As long as the code is fundamentally sound, It's not crucial to handle cases like N99999999999999.

NOTE: You may evaluate the cases N1S1, E1W1, S1N1, and W1E1 however you would like. They're technically valid paths, but they go against the "Tron" spirit of the challenge.

Scoring

This is , so the shortest answer wins!

\$\endgroup\$
9
  • \$\begingroup\$ N1S1 should be true to be consistent with your definitions because it reaches (0, 0) twice and (0, 1) once, which is valid under your definition. \$\endgroup\$
    – hyper-neutrino
    Jul 17, 2017 at 19:34
  • \$\begingroup\$ Can I take N as 1j, E as 1, S as -1j, and W as -1? \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 19:35
  • \$\begingroup\$ @LeakyNun I think I'm ok with that, since everyone should more or less be doing something like this the hood anyway. Just make sure you specify that in your answer. \$\endgroup\$ Jul 17, 2017 at 19:38
  • 1
    \$\begingroup\$ @HyperNeutrino but from a Tron standpoint, your lightcycle goes through (0, 0.5) twice, even if the input will never put you at such a point. That's why I think that one has flexible output (even though for most languages it'll be easier to return true) \$\endgroup\$
    – Value Ink
    Jul 17, 2017 at 19:38
  • 1
    \$\begingroup\$ @steenbergh (0,0) is not in the corner, so you can go under or to the left of it; even both if you're feeling crazy! Also, there's no hard limit on the grid size, but just assume the input isn't going to overflow anything. As long as the code is fundamentally sound, I don't care if it can't handle inputs like N99999999999999 \$\endgroup\$ Jul 17, 2017 at 20:00

6 Answers 6

8
\$\begingroup\$

Pyth, 44 39 bytes

&!eJsM._smm^.j)x"NESW"hdstd:z".\d+"1{IJ

Test suite.

\$\endgroup\$
6
\$\begingroup\$

JavaScript, 247 200 bytes

n=s=>{r=s.match(/\w\d+/g)
x=y=z=0
e=""
for(d of r){a=d[0]
b=d.slice(1)
while(b--){
y+=a=="N"
y-=a=="S"
x+=a=="E"
x-=a=="W"
p=[x,y]+";"
if(~e.indexOf(p))if(!x&!y)z++
else return 0
e+=p}}return!x&!y&!z}

n is a function of input string s that returns 1 for true and 0 for false

Here's an ungolfed version for reference/explanation:

function n(s)
{
    var dir = s.match(/\w\d+/g);
    var x = y = z = 0;
    var been = "";
    for (d of dir)
    {
        var a = d[0];
        var b = 1*d.substring(1);
        while(b-- > 0)
        {
            if (a == "N") y++;
            if (a == "S") y--;
            if (a == "E") x++;
            if (a == "W") x--;
            var pt = [x,y] + ";";
            if (~been.indexOf(pt))
                if (x==0 && y==0)
                    z++;
                else
                    return false;
            been += pt;
        }
    }
    return (x == 0 && y==0 && z == 0);
}

n=s=>{r=s.match(/\w\d+/g)
x=y=z=0
e=""
for(d of r){a=d[0]
b=d.slice(1)
while(b--){
y+=a=="N"
y-=a=="S"
x+=a=="E"
x-=a=="W"
p=[x,y]+";"
if(~e.indexOf(p))if(!x&!y)z++
else return 0
e+=p}}return!x&!y&!z}

console.log(n("N1E1S1W1"))
console.log(n("N1E1N1E1S2W2"))
console.log(n("N1S1E1W1"))
console.log(n("N4E2S2W4S2E2"))
console.log(n("N3E2S3"))

\$\endgroup\$
15
  • \$\begingroup\$ Remove some whitespace \$\endgroup\$
    – hyper-neutrino
    Jul 17, 2017 at 20:25
  • \$\begingroup\$ didn't notice that, thanks \$\endgroup\$
    – WaffleCohn
    Jul 17, 2017 at 20:47
  • \$\begingroup\$ It seems that contains isn't a function in any dialect of javascript. Could you specify the dialect? \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 20:57
  • \$\begingroup\$ I was just using the chrome console to test - it works perfectly there \$\endgroup\$
    – WaffleCohn
    Jul 17, 2017 at 20:57
  • \$\begingroup\$ Actually it works in my chrome console also... but maybe you would consider changing it into a more universal answer? \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 21:01
5
\$\begingroup\$

Python 3, 236 161 150 bytes

import re
p=0
a=[]
for i in''.join(s[0]*int(s[1:])for s in re.findall(r".\d+",input())):p+=1j**"NESW".find(i);a+=[p]
print(len({*a})-len(a)==0==a[-1])

Try it online!

-75 bytes thanks to Leaky Nun
-11 bytes thanks to Leaky Nun Or, if we're allowed to take input as a list of run length decoded complex numbers:

Python 2, 85 73 bytes

c=0;k=[]
for i in input():c+=i;k+=[c]
print(k[-1]==0==len(set(k))-len(k))

Try it online!

-12 bytes thanks to Mr. Xcoder / -9 bytes thanks to Leaky Nun (merged into one edit)

This feels too long to me lol

\$\endgroup\$
10
  • 3
    \$\begingroup\$ As long as it is shorter than 10 times the Pyth solution, it isn't too long. \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 20:18
  • \$\begingroup\$ @LeakyNun lol okay :P \$\endgroup\$
    – hyper-neutrino
    Jul 17, 2017 at 20:19
  • \$\begingroup\$ 161 bytes \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 20:25
  • \$\begingroup\$ @LeakyNun oh snap nice. see too long, as I said :P \$\endgroup\$
    – hyper-neutrino
    Jul 17, 2017 at 20:26
  • \$\begingroup\$ 76 bytes \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 20:28
3
\$\begingroup\$

Jelly, 14 12 bytes

Œṙ+\µQ⁼ȧṛ/¬$

This is my first time golfing in Jelly. Suggestions are welcome.

Input is as an array of [direction, distance] pairs, where the direction is given as a complex number.

Explanation:

Œṙ+\µÇȧṛ/¬$   Main link. Argument: n     = [[i, 3], [1, 2], [-i, 3]]
Œṙ            Run-length decode          = [i, i, i, 1, 1, -i, -i, -i]
  +\          Cumulative sum             = [i, 2i, 3i, 3i+1, 3i+2, 2i+2, i+2, i]
    µ         Begin a new monadic chain
     Q        Remove duplicates          = [i, 2i, 3i, 3i+1, 3i+2, 2i+2, i+2]
      ⁼       Equal to original?         = 0
           $  Make a monadic link:
        ṛ/      Reduce by right argument   = i
                (Gets the last element)
          ¬     Logical NOT:               = 0
       ȧ      Logical AND the two values = 0
\$\endgroup\$
1
  • \$\begingroup\$ Should fail the last case. \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 20:39
0
\$\begingroup\$

Retina, 86 bytes

\d+
$*
1(1*)
$1
+`(.)1
$1$1
.
 $`$&¶
%O`.
+`NS|E(.*)W
$1
M`\w$|(?m)(^.+$)(?s).+^\1$
^0

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert the numbers to unary.

1(1*)
$1
+`(.)1
$1$1

Run-length decode the letters. N111 needs to turn into NNN, so one is subtracted from each unary number and then each 1 duplicates the previous letter.

.
 $`$&¶

Generate all the prefixes (i.e. points on the path) as separate lines. A space is prefixed to avoid issues with empty lines.

%O`.
+`NS|E(.*)W
$1

Sort all the letters in each line into order and then delete matching pairs. We end up with a unique code for any given point on the grid.

M`\w$|(?m)(^.+$)(?s).+^\1$

Check for one of two things: a) the last point doesn't end in a space (i.e. the loop didn't close), or two duplicate points in the path. If the path is valid, all checks fail and the result is zero.

^0

Invert the result.

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

Perl, 140

Works with string input. Perhaps I can shorten with array,but I doubt it. Happy for any further golfing help :)

sub w{$i=$_[0];%d=(E,[0],S,[1,-1],W,[0,-1]);$i=~s/(.)(.)/($d,$o)=(@{$d{$1}},1,1);for(1..$2){$s[$d]+=$o;$r+=$d{"@s"}++}/eg;!($s[0]+$s[1]+$r)}
\$\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.