7
\$\begingroup\$

Is the path correct ?

Given a string, your program must determine whether or not Alice can reach Bob, following the signs on the map. You must return a truthy or falsy value.

The input string will contain the following characters :

  • (space) and \n. Only used for padding.
  • >, <, ^, v, are the "signs". They show the direction.
  • &. Ignore next char, whatever it is (including spaces and Bob)
  • A and B respectively Alice and Bob.

The map is a torus. If Alice reaches the end of a row, then she is teleported back to the beginning of that row. Same applies for columns.

Examples

Given those examples as input, your program must return a truthy value (each input is separated with a - line):

A>B
-----------------
<BA
-----------------
A       B
-----------------
BA
-----------------
Av  >B
 >  ^
-----------------
Av
 B
-----------------
A>v
  >B
-----------------
A>v>   v>B
 v< > &<^
 > ^
-----------------
A>v>   v
 v< >B&<
 > ^
-----------------
A&<B
-----------------
A&B<
-----------------
<A       &B

For the following, your program must output a falsy value or nothing :

AvB
-----------------
A&B
-----------------
A><B
-----------------
A>v
 ^<B

Path viewer

You can have a visual representation of the input here. Thanks to arnemart for this.

Some rules

  • The input may be padded with spaces to form a rectangle
  • Initially, Alice goes straight forward (from above, she goes to the right)
  • Your program should handle infinite loop cases (see Hint)
  • A is not always the first character, as you may have seen, however, you may write a program that handles only input with A being the first char, but 20 bytes will be added to your score.
  • A map (the input) is considered invalid in case there are other characters than those specified above. Your program won't have to handle them.
  • This is , so shortest code in bytes wins.

Hint

Your program will most likely be a loop, unless you find a more mathematical solution to this challenge. To handle infinite path, I recommend using a finite loop (e.g for) instead of a potentially infinite one (e.g while).

Therefore, the maximum iteration of the loop I can think of (I did not do any maths, any correction is welcome) is (length of input)*4

\$\endgroup\$
12
  • \$\begingroup\$ Closely related -- codegolf.stackexchange.com/q/57952/42963 \$\endgroup\$ Apr 7, 2016 at 13:21
  • \$\begingroup\$ Can the input be padded with spaces so that it forms a rectangle and each line is the same length? \$\endgroup\$
    – user81655
    Apr 7, 2016 at 14:41
  • \$\begingroup\$ @user81655 Yes it can \$\endgroup\$
    – THC
    Apr 7, 2016 at 15:03
  • \$\begingroup\$ If only there was a way to replace a few chars then exec in ><>... \$\endgroup\$
    – mbomb007
    Apr 7, 2016 at 15:33
  • \$\begingroup\$ @mbomb007 Sorry :D \$\endgroup\$
    – THC
    Apr 7, 2016 at 15:37

2 Answers 2

2
\$\begingroup\$

C, 250 bytes

#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j
char a[999],b[999];x,i,d=2,k,f;main(j){for(;gets(a+j*i);)j=strlen(a+j*i++);for(x=strchr(a,65)-a,i=x/j,x=x%j;!k*d;h)k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,(f=a[f])&16?d=f:f&4?h:f&2?d=0:0;putchar(48+!k);}

This also requires that the input is padded with spaces.

Ungolfed:

#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j 
char a[999],b[999];x,i,d=2,k,f;
main(j){
 for(;gets(a+j*i);)j=strlen(a+j*i++); //read lines and determine line length
 for(x=strchr(a,65)-a,i=x/j,x=x%j;    //the current position is 'A'
 !k*d; //as long as we have not arrived at 'B' 
       //and not travelled through the same cell and in the same direction twice
 h)    //advance one in the current direction
   k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,  //if we have already travelled  
                                       //through this cell in this direction
   (f=a[f])&16?d=f //change direction if this cell is one of <>^v
   :f&4?h          //if this cell is '&', advance one in the current direction
   :f&2?d=0:0;     //if we have reached 'B'
 putchar(48+!k);
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 176 bytes

m=>[...m,q=~m.length,l=~m.search`
`||q,a=m.search`A`,p=d=r=1].map(_=>(a+=d,a-=d*((a-l+1)%l?m[a]?0:q/l:~l),c=m[a],p=="&"?0:d={">":1,"<":-1,"^":l,v:-l}[c=="B"?r=0:c]||d,p=c))&&!r

Explanation

Requires the input to be space-padded to form a rectangle (I hope this is OK).

var solution =

m=>[
    ...m,                           // iterate m.length times
    q=~m.length,                    // q = total length of m
    l=~m.search`\n`||q,             // l = line length
    a=m.search`A`,                  // a = index of Alice
    p=                              // p = previous character
    d=                              // d = direction offset
    r=1                             // r = result
  ].map(_=>(                        // loop
    a+=d,                           // move Alice
    a-=d*((a-l+1)%l?m[a]?0:q/l:~l), // wrap
    c=m[a],
    p=="&"?0:                       // do nothing after &
    d={">":1,"<":-1,"^":l,v:-l}     // set the new direction
      [c=="B"?r=0:c]                // if on Bob, r = 0
    ||d,
    p=c
  ))&&!r                            // return result

var testCasesTrue =
`A>B
-----------------
<BA
-----------------
A       B
-----------------
BA
-----------------
Av  >B
 >  ^ 
-----------------
Av
 B
-----------------
A>v 
  >B
-----------------
A>v>   v>B
 v< > &<^ 
 > ^      
-----------------
A>v>   v
 v< >B&<
 > ^    
-----------------
A&<B
-----------------
A&B<
-----------------
<A       &B`
.split("\n-----------------\n");

var testCasesFalse =
`AvB
-----------------
A&B
-----------------
A><B
-----------------
A>v 
 ^<B`
.split("\n-----------------\n");

var test = (cases, expected) => cases.map((t,i)=>++i+": "+(solution(t)==expected?"Pass":"Fail")).join`\n`;
document.write(`<pre>${test(testCasesTrue,true)}\n\n${test(testCasesFalse,false)}</pre>`);

\$\endgroup\$
1
  • \$\begingroup\$ Congratulations ! \$\endgroup\$
    – THC
    Apr 7, 2016 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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