15
\$\begingroup\$

Challenge

You've given a map to a friend that looks a bit like this:

      |
      /
     |
     /
    |
    \
     |
     \
      D

A simple map that starts at the top and ends at the bottom. Sadly, your friend doesn't get it. Can you decode the map so that he can read it?

Input

The input is a string of characters consisting of |, /, \, D, ^, Y, (space), and newlines.

  • | tells to stay in the same column.
  • \ tells to move to the column to the right and down 1.
  • / tells to move to the column to the left and down 1.
  • D marks the destination.
    • ^ (if present) tells of a split in the path.
    • Y (if present) tells of a rejoining of paths. Treat it like a |.

The input will be arranged so that it makes a kind of path:

   |
   |
   \
    |
    ^
   / \
  /   |
 D    |

There will always be a space between two paths, and all paths will either rejoin or reach the last line of the input. There will only be one split per map. There is no limit to the length of the input map. There will never be more than two paths.

Output

The output should be a string of directions.

  • "L" should tell your friend to move Left and take 1 step forward.
  • "R" should tell your friend to move Right and take 1 step forward.
  • "F" should tell your friend to move 1 step forward.

For the input example map, the output would be as follows:

F F L F R R R

Note that your friend is starting at the top of the map and facing down the map. Give the directions from his perspective. For an instance of "^", your program must be able to choose the path that leads to the destination (D). If the two paths recombine, your program must choose the straightest path (the one with the most |s) to follow. Directions must be separated by spaces, and must end on D.

Examples

Input

      |
      |
      \
       \
        ^
       / |
      |  |
      \  |
       \ \
        \ \
         \ /
          Y
          D

Output

F F L L L F F F L L R F

Since the leftmost path contains only 1 |, we use the rightmost path that has 3.


Input

\
 |
 /
|
\
 |
 /
D

Output

L F R F L F R

Input

    /
   \
    /
   \
    ^
   \ \
    D \

Output

R L R L R L

Other details

  • This is code golf, so the person with the shortest code by next Wednesday, the 19th of August, wins.
  • Constructive feedback welcome and greatly appreciated.
  • Partially inspired by A Map to Hidden Treasure
  • Feel free to change the title to something more creative.
  • If you find mistakes that I made, correct them.
  • And of course, have fun.

Thank you!

A bit late, maybe, but UndefinedFunction is the winner coding in JavaScript! Thanks to all who entered. No other entries will be accepted.

\$\endgroup\$
  • \$\begingroup\$ It still seems off. The first example ends in L L, which I think should be L L L. The example with Y still has a 1 at the end and also seems to have other errors. I read the map as F F R R R F F F R R L F if I understand the rules correctly. \$\endgroup\$ – Martin Ender Aug 12 '15 at 22:05
  • \$\begingroup\$ @MartinBüttner you're supposed to end on D, you would only need 2 Ls. 3 Ls would go past D. \$\endgroup\$ – The_Basset_Hound Aug 12 '15 at 22:11
  • 2
    \$\begingroup\$ Can a path ever reach a dead end before reaching the last line? Or will all paths reach the last line of the input? \$\endgroup\$ – jrich Aug 12 '15 at 22:12
  • \$\begingroup\$ @BassetHound shouldn't there be one L for the ^ and two L for the two /? And why did you add two more F to the end of the Y example? \$\endgroup\$ – Martin Ender Aug 13 '15 at 5:39
  • \$\begingroup\$ @ETHproductions Yes. \$\endgroup\$ – The_Basset_Hound Aug 14 '15 at 21:32
5
\$\begingroup\$

Javascript (ES6), 261 248 252 248 212 bytes

Since only one split has to be supported:

s=>(s=s.replace(/ /g,o="",d=0).split(`
`)).map((v,j)=>{if(v=="^")for(v="/\\";(w=s[++j])&&(x=w[1]);d=x=="D"?1:w[0]=="D"?0:x>"{"?d+1:w[0]>"{"?d-1:d);o+=(p=v[d>0?1:0]||v[0])<"0"?"R ":p<"E"?"":p=="\\"?"L ":"F "})?o:o


However, 240 bytes and we can deal with multiple splits:

s=>(s=s.replace(/ /g,o="").split(`
`)).map((v,j)=>{if(!v[1])t=d=0
else if(!t){for(t=1;(w=s[++j])&&(x=w[1]);d=x=="D"?1:w[0]=="D"?0:x>"{"?d+1:w[0]>"{"?d-1:d);o+=d>0?"L ":"R "}o+=(p=v[d>0?1:0])<"0"?"R ":p<"E"||p=="^"?"":p=="\\"?"L ":"F "})?o:o


Both programs define anonymous functions.

To use, give the function(s) a name by adding f= before the code.

Afterwards, they can be called with

alert(f(
`   |
   |
   \\
    |
    ^
   / \\
  /   |
 D    |`
))


Explanation

(outdated, but still the same concept. For the multiple split solution)

s=>
    //Remove all spaces from the input
    (s=s.replace(/ /g,o="",
                 //Define function c, to convert symbols to directions
                 c=p=>p<"0"?"R ":p<"E"||p=="^"?"":p=="\\"?"L ":"F "
    //Split input into an array by newlines
    ).split(`
`))
    //for each string v in the input array, at index j:
    .map((v,j)=>{
        //if v is only one character long:
        if(!v[1]){
            t=1     //assign t to 1 (true) - we need to test if multiple paths
            d=0     //assign d to 0 - reset the counter for determining shortest path
        }
        //if v is two characters long, and we have not tested which path is shorter yet:
        else if(t){
            for(    t=0;    //assign t to 0 - we will have tested which path is longer

                    //for each string left in the input, while the input still has two characters:
                    (w=s[++j]) && w[1];
                    //assign d to determine which direction to go. This will be conveyed by if d>0
                    d=
                        w[1]=="D"?1:    //if the dest. is only on one side, choose that side.
                        w[0]=="D"?0:
                        w[1]=="|"?d+1:  //otherwise add/subtract from d (like a tug of war) to determine which side has more "|"
                        w[0]=="|"?d-1:
                        d
               );
            o+=d>0?"L ":"R "    //append to the output which direction was taken
        }

        o+=c(v[d>0?1:0])    //append to the output the characters from the correct path in any case, determined by d calculated above 
                            //(or defaulting to 0, if path is not split, in which case the only character is appended)

    }) ? o : o  //coerce the result, which will evaluate to an array of the input, to the output (o) and implicitly return


Notes

  • All backslashes (\) in the input are escaped as \\, so that javascript can recognize them.

  • Both outputs contain a trailing space.

\$\endgroup\$
  • \$\begingroup\$ Dang it, thought I had it all fixed. \$\endgroup\$ – The_Basset_Hound Aug 18 '15 at 1:15
9
\$\begingroup\$

PHP, 634 631 607 396 382 381 347 338 330 337 324 bytes

My first ever golf so be gentle. Any tips are greatly appreciated.

<?php
foreach(str_split(strtr(fgets(STDIN),[' '=>'']))as $i){if($i!=D){$z=$i=='^';$x=$i==Y;$s=!$z&&!$x?($i=='/'?R:($i=='|'?F:($i=='\\'?L:$s))):$s;$a.=$z?R:($x?F:(($c==1||!$c)?$s:''));$b.=$z?L:($x?F:(($c==2||!$c)?$s:''));$c=$z?1:($x?0:($c==1?2:($c==2?1:$c)));}else{echo(substr_count($a,F)<substr_count($b,F)&&$c==0||$c==2)?$b:$a;}}

Short Explanation:
I have a count which is 0 if the Input has only one path. When the path splits the count is 1 for the left path and 2 for the right path. After defining both paths (or only one) I check which path has more "F's".

Ungolfed Version:

<?php
$input = fgets(STDIN);
$inputArray = str_split($input);
foreach ($inputArray as $currentChar) {
    if ($currentChar != 'D') {
        if ($i == '^') {
            $firstPath .= 'R';
            $secondPath .= 'L';
            $count = 1;
        } elseif ($i == 'Y') {
            $secondPath .= 'F';
            $firstPath .= 'F';
            $count = 0;
        } else {
            if ($i == ' ') {
                continue;
            }
            if ($i == '/') {
                $direction = 'R';
            } else {
                if ($i == '|') {
                    $direction = 'F';
                } else {
                    if ($i == '\\') {
                        $direction = 'L';
                    } else {
                        $direction = '';
                    }
                }
            }
            if ($count == 1) {
                $firstPath .= $direction;
                $count = 2;
            } elseif ($count == 2) {
                $secondPath .= $direction;
                $count = 1;
            }
            if (!$count) {
                $firstPath .= $direction;
                $secondPath .= $direction;
            }
        }
    } else {
        echo (substr_count($firstPath, 'F') < substr_count($secondPath, 'F')) || $count == 2 ? $secondPath : $firstPath;
    }
};


Log:
Saved 36 Bytes thanks to Kamehameha.
Saved many many bytes by changing the logic a bit.
Saved 42 Bytes thanks to axiac.
Replaced every if statment with ternary operators.

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to the site! \$\endgroup\$ – isaacg Aug 18 '15 at 7:36
  • 2
    \$\begingroup\$ You can try $a=$b=''; instead of - $a='';$b=''; Saves around 3 bytes. \$\endgroup\$ – Kamehameha Aug 18 '15 at 7:53
  • 1
    \$\begingroup\$ Also, concatenation like $a=$a.'L '; can be reduced to $a.='L '. You seem to have done that in a couple of places. That'll save around 6 bytes :) \$\endgroup\$ – Kamehameha Aug 18 '15 at 7:56
  • 1
    \$\begingroup\$ I don't know PHP very well, but I believe you can drop the space after "as" in your foreach (foreach($e as$i)); I have tested that and it appears to work fine. \$\endgroup\$ – ProgramFOX Aug 18 '15 at 8:39
  • 1
    \$\begingroup\$ A couple more tips to save a few bytes, as @ProgramFox mentioned about the as in the foreach, the spaces between echo and the variable name can be removed to so you have echo$b. Also, a couple of equality tests can be shorter too, $c==0 could be !$c and if that's the case, you can initialise $c to '' with $a and $b! \$\endgroup\$ – Dom Hastings Aug 18 '15 at 8:56
3
\$\begingroup\$

PHP, 281 bytes

$b=0;$p=['|'=>'$a[$b].="F ";$f[$b]++;','/'=>'$a[$b].="R ";','\\'=>'$a[$b].="L ";','^'=>'$d.=$a[0];$n=2;$a=["R ","L "];$f=[];$b=1;','Y'=>'$d.=$a[$f[0]<$f[$n=1]]."F ";$a=[];','D'=>'$d.=$a[$b];exit(rtrim($d));'];foreach(str_split($argv[$n=1])as$c){if($x=$p[$c]){eval($x);$b=++$b%$n;}}

It is the result of two golfing iterations. The ungolfed version is:

$a=$f=[];       // these assignments are not required (they were suppresed in v2)
$n=1;           // this assignment can be squeezed into $argv[$n=1]
$b=0;           // if this assignment is suppressed $b becomes '' and breaks the logic
$code = [
    '|' => '$a[$b].="F ";$f[$b]++;',
    '/' => '$a[$b].="R ";',
    '\\'=> '$a[$b].="L ";',
    '^' => '$d.=$a[0];$n=2;$a=["R ","L "];$f=[];$b=1;',
    'Y' => '$d.=$a[$f[0]<$f[$n=1]]."F ";$a=[];',
    'D' => '$d.=$a[$b];echo(rtrim($d));',
];
foreach (str_split($argv[1]) as $char) {
    // ignore input characters not in the keys of $code
    if ($x = $code[$char]) {
        eval($x);
        $b = ++ $b % $n;   // cycles between 0 and 1 ($n == 2) or stays 0 ($n == 1)
    }
}

It is pretty golfed itself and it emerged as an improvement of the following golfed program (312 bytes):

$b=0;foreach(str_split($argv[$n=1])as$c){if($c=='|'){$a[$b].='F ';$f[$b]++;}elseif($c=='/'){$a[$b].='R ';}elseif($c=='\\'){$a[$b].='L ';}elseif($c=='^'){$d.=$a[0];$n=2;$a=['R ','L '];$f=[];$b=1;}elseif($c==Y){$d.=$a[$f[0]<$f[$n=1]].'F ';$a=[];}elseif($c==D){$d.=$a[$b];exit(rtrim($d));}else continue;$b=++$b%$n;}

It is the golfed version of the original:

$map = $argv[1];

$dir = '';              // the already computed directions
$nb = 1;                // the number of branches
$branches = [ '' ];     // the branches (2 while between '^' and 'Y', 1 otherwise)
$nbF = [ 0, 0 ];        // the number of 'F's on the branches (used to select the branch)
$curr = 0;              // the current branch
foreach (str_split($map) as $char) {
    if ($char == '|') {             // go 'F'orward
        $branches[$curr] .= 'F ';       // put it to the current branch
        $nbF[$curr] ++;                 // count it for the current branch
    } elseif ($char == '/') {       // go 'R'ight
        $branches[$curr] .= 'R ';
    } elseif ($char == '\\') {      // go 'L'eft
        $branches[$curr] .= 'L ';
    } elseif ($char == '^') {       // fork; choose the path ('L' or 'R') that contains the most 'F'orward segments
        $dir .= $branches[0];           // flush the current path (it was stored as the first branch)
        $nb = 2;                        // start two branches
        $branches = [ 'R ', 'L ' ];     // put the correct directions on each branch
        $nbF = [ 0, 0 ];                // no 'F's on any branch yet
        $curr = 1;                      // need this to let it be 0 on the next loop
    } elseif ($char == 'Y') {       // join
        $dir .= $branches[$nbF[0] < $nbF[1]];   // flush; choose the branch having the most 'F's
        $dir .= 'F ';                           // treat it like a "|"
        $branches = [ '' ];                     // back to a single, empty branch
        $nb = 1;
    } elseif ($char == 'D') {       // finish
        $dir .= $branches[$curr];       // flush
        break;                          // and exit; could use 'return' but it's one byte longer; use exit() in the final program and save 5 bytes
    } else {
        continue;
    }
    $curr = ++ $curr % $nb;
}
echo rtrim($dir);

Example execution:

$ php -d error_reporting=0 directions.php '
      |
      |
      \
       \
        ^
       / |
      |  |
      \  |
       \ \
        \ \
         \ /
          Y
          D
'; echo
F F L L L F F F L L R F
$

It also handles multiple forks correctly (need to join before the next fork in order to have at most two branches any time). I asked about multiple forks in a comment but the code was already done when the answer ("not needed") came.

The complete code with test suite and more comments can be found on github.

\$\endgroup\$
  • \$\begingroup\$ Wow good job! I still need to learn quite a few things! \$\endgroup\$ – jrenk Aug 18 '15 at 19:53

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.