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\$
  • \$\begingroup\$ Closely related -- codegolf.stackexchange.com/q/57952/42963 \$\endgroup\$ – AdmBorkBork Apr 7 '16 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 '16 at 14:41
  • \$\begingroup\$ @user81655 Yes it can \$\endgroup\$ – FliiFe Apr 7 '16 at 15:03
  • \$\begingroup\$ If only there was a way to replace a few chars then exec in ><>... \$\endgroup\$ – mbomb007 Apr 7 '16 at 15:33
  • \$\begingroup\$ @mbomb007 Sorry :D \$\endgroup\$ – FliiFe Apr 7 '16 at 15:37
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\$
  • \$\begingroup\$ Congratulations ! \$\endgroup\$ – FliiFe Apr 7 '16 at 15:02

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.