36
\$\begingroup\$

Introduction

Everyone knows that the possibility of successfully navigating an asteroid field is approximately 3,720 to 1. But despite your warning, Han Solo is still willing to try his luck.

Fearing for your artificial life, you decide to code, in the ship's peculiar dialect (read: your preferred Code Golf language), an asteroid avoidance program that will decide which path to take in an asteroid field ASCII maze.

Input

The Millenium Falcon has an asteroid field mapping program, that gives data similar to this:

|   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #        |
@              ##    ####       
|#   #   #       ###   ##      |
|##      ##      ####   #  #   |
|####           ##### #   ##   |

Top rows are left of the Falcon, bottom rows are right of the Falcon, and columns represent what is in front of the ship.

  • Each # is an obstacle.
  • Each space is empty space that the ship can fly in.
  • The input is always 7 characters high. This is the asteroid mapping width limit.
  • The input is always 32 characters long (30 for the field itself and 2 for the start and end limits). This is the asteroid mapping depth limit. Vertical bars | mark the beginning and the end of the mapping.
  • @ is the Falcon. It is always in the middle row (4th row) and first column in the input.
  • The space left in the vertical bars on the last column is the place the ship must arrive at. It is always in the middle row (4th row) and last column in the input.

The input can be taken as a multi-line string, an array of strings, from STDIN or a function parameters, or read from a file.

Possible maneuvers

You are pursued by TIE-Fighters, therefore you must always go forward. There are thus three ways the ship can fly at each step:

  • - Forward

  • / Forward and turn left

  • \ Forward and turn right

For example, these are valid paths:

@---

  --
 /  \ /
@    -

   -
  / \
 /   \
@     \

As you can see, there is always exactly one move per column. The Falcon is a piece of junk, therefore it cannot do violent turns. Which means moves such as /\ or \/ are disallowed. There must be atleast one pure forward - between two opposite turns. On the other hand, turning one way for multiple steps in a row is possible, as seen above.

The Falcon crashes if one move leads the ship to be in a spot where an obstacle is. For example, these moves lead to crashes:

@-#

@
 \
  #

  #
 /
@

Note that this is not a crash:

@-#
  \
   -

Output

You must output the same asteroid field ASCII, with a valid path to the end. The Falcon must be printed at the end spot instead of the start spot.

For example, a valid output for the input example given before would be:

|   #####           #########  |
| ######  #--------  ###   #   |
|   # #  #/ #  ####\  #        |
 ---------      ##  \ #### ----@
|#   #   #       ### \ ## /    |
|##      ##      #### \ #/ #   |
|####           ##### #-- ##   |

Your path only needs to not crash the falcon. It doesn't need to be the shortest path possible.

You can assume that there will always be at least one possible path to the end.

You can output to STDOUT, in a file or any equivalent as long as the asteroid field is printed exactly like they are in this post (e.g. outputting a list of coordinates for the path is not valid).

Test cases

  • A normal asteroid field

    |   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #        |
@              ##    ####       
|#   #   #       ###   ##      |
|##      ##      ####   #  #   |
|####           ##### #   ##   |

    Possible output

    |   #####           #########  |
| ######  #--------  ###   #   |
|   # #  #/ #  ####\  #        |
 ---------      ##  \ #### ----@
|#   #   #       ### \ ## /    |
|##      ##      #### \ #/ #   |
|####           ##### #-- ##   |

  • Hyperregular asteroid field

    |# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |
@ # # # # # # # # # # # # # #   
|# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |

    Possible output

    |# # # # # # # # # # # # # # # |
| # # # # # # # # # # # # # # #|
|# # # # # # # # # # # # # # # |
 -# #-# #-# #-# #-# #-# #-# #--@
|#\#/#\#/#\#/#\#/#\#/#\#/#\#/# |
| #-# #-# #-# #-# #-# #-# #-# #|
|# # # # # # # # # # # # # # # |

  • Death star's core

    |    #    #    #         #     |
|         #    #    #          |
|    #    #    #    #    #     |
@    #    #    #    #    #      
|    #    #         #    #     |
|    #    #    #    #    #     |
|    #         #    #    #     |

    Possible output

    |    #    #    #   --    #     |
|  ---    #    #  / #\   -     |
| /  #\   #    # /  # \ /#\    |
 -   # \  #    #/   #  - # ----@
|    #  \ # ----    #    #     |
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

  • Death star trench

    |##############################|
|##############################|
|##############################|
@                               
|##############################|
|##############################|
|##############################|

    Output

    |##############################|
|##############################|
|##############################|
 ------------------------------@
|##############################|
|##############################|
|##############################|

  • Asteroid cave

    |### ##########################|
|## # ############### ## ######|
|# ###  ######## ### ## # #####|
@ ###### ###### ### ## ###      
|########  ### ### ## #########|
|########## # ### ## ##########|
|###########              #####|

    Possible output

    |###-##########################|
|##/#\############### ##-######|
|#/###--######## ### ##/#\#####|
 -######\###### ### ##/###-----@
|########--### ### ##/#########|
|##########\# ### ##/##########|
|###########--------      #####|

Scoring

R2D2 is busy swimming in swamps, so you're going to have to program the Falcon's controller by yourself, which is tedious. Therefore the shortest code wins.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ @DJMcMayhem: Technically the first line is "Introduction" ;) \$\endgroup\$
    – Alex A.
    Jul 8, 2015 at 15:20
  • 2
    \$\begingroup\$ I sort of get how it's supposed to look based on the examples, but the encoding of the moves is still somewhat confusing to me. If you look for example at the "hyperregular" example, except for the first/last move, you always move diagonal. Yet it has - in the path at each turn, which is defined as a "forward" move. But the actual moves are always two diagonal-left followed by two diagonal-right. \$\endgroup\$
    – Reto Koradi
    Jul 8, 2015 at 16:47
  • \$\begingroup\$ @RetoKoradi I can understand that it's not all that obvious but the basic idea is that all moves make you travel the width of a character to the right. The path has to look continuous, which is why the previous/next move after right and left turns are one line above/below the previous one. \$\endgroup\$
    – Fatalize
    Jul 8, 2015 at 16:58
  • \$\begingroup\$ @apsillers Both are valid, if I understand you correctly your answer should be good \$\endgroup\$
    – Fatalize
    Jul 8, 2015 at 18:41

4 Answers 4

Reset to default
11
\$\begingroup\$

JavaScript (ES6), 186 201

f=([...s])=>(g=(i,l,c=k=" ")=>s[i]!=k&&s[i]!="@"?0:(i-130)?(s[i]=c,([..."/-\\"].some((c,j)=>!((--j&l&&j!=l)||!g(i+33*(l||j)+1,j,c)))||!(s[i]=k))):(s[i]="@",!console.log(s.join(""))))(99)

Runnable snippet:

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><textarea cols="33" rows="7" id="t"></textarea><br><button><b>Solve &gt;&gt;&gt;</b></button><hr><button id="1">Normal</button> <button id="2">Hyperregular</button> <button id="3">Death Star core</button> <button id="4">Death Star trench</button> <button id="5">Asteroid cave</button><script>f=(function($__0){var $__2,$__3,$__4,$__5;s = $__4 = $__0.split("");return (g = (function(i, l) {var c = arguments[2] !== (void 0) ? arguments[2] : k = " ";return s[i] != k && s[i] != "@" ? 0 : (i - 130) ? (s[i] = c, ("/-\\".split("").some((function(c, j) {return !((--j & l && j != l) || !g(i + 33 * (l || j) + 1, j, c));})) || !(s[i] = k))) : (s[i] = "@",$("#t").val(s.join("")));}))(99);});$("button").click(function() {this.id?$("#t").val(inputs[this.id]):f($("#t").val());});inputs = [,`|   #####           #########  |\n| ######  #          ###   #   |\n|   # #  #  #  ####   #        |\n@              ##    ####       \n|#   #   #       ###   ##      |\n|##      ##      ####   #  #   |\n|####           ##### #   ##   |`,`|# # # # # # # # # # # # # # # |\n| # # # # # # # # # # # # # # #|\n|# # # # # # # # # # # # # # # |\n@ # # # # # # # # # # # # # #   \n|# # # # # # # # # # # # # # # |\n| # # # # # # # # # # # # # # #|\n|# # # # # # # # # # # # # # # |`,`|    #    #    #         #     |\n|         #    #    #          |\n|    #    #    #    #    #     |\n@    #    #    #    #    #      \n|    #    #         #    #     |\n|    #    #    #    #    #     |\n|    #         #    #    #     |`,`|##############################|\n|##############################|\n|##############################|\n@                               \n|##############################|\n|##############################|\n|##############################|`,`|### ##########################|\n|## # ############### ## ######|\n|# ###  ######## ### ## # #####|\n@ ###### ###### ### ## ###      \n|########  ### ### ## #########|\n|########## # ### ## ##########|\n|###########              #####|`];$("#t").val(inputs[1]);</script

This function accepts a single string with newlines. The function splits the string into an array using the ... operator and gets the index for (x,y) coordinates by (33 * y) + x.

The function runs recursively, testing out different possible moves for each space. When it encounters an obstacle, it returns a falsy value, and when it reaches the end goal space, it returns true. (In the golfed code, this true is created by !console.log(...).)

Note that this code does not use long runs of right-turn moves, but punctuates them with straight moves. That is, it does the second option below, not the first:

\                       \
 \   (<= not this!)      -   (<= yes this!)
  \                       \

This seems to be legal, since - can legally come before or after a turn, so why not both at once? That looks especially strange at the end, when the final move is \ but is displayed as @:

|  --#    #    #   ------#  -  |
| /  \    #    #  / #    \ / \ |
|/   #-   #    # /  #    #-   -|
     # \  #    #/   #    #     @
|    #  - # ----    #    #     |
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

My favorite nasty golf hack here is default argument abuse with c=k=" ". The arguments (i,l,c=" ") would say "use the string " " for c if f is not supplied a third argument". However, by doing c=k=" ", we say "if c is not supplied, store " " in the global variable k and then store that value in c as well". Since the recursion begins with only a single argument, k is always initialized at the first function call.

Mildly ungolfed:

// `i` - index in the string we're working on
// `l` - move character for this space (`/`, `\`, or `-`)
search = (i,l,c)=>{

  // not an open space; nip this recursive branch
  if(s[i]!=" "&&s[i]!="@") { return 0; }

  // we made it! the 130th space is (31,3)
  if(i==130) {
      s[i]="@";
      console.log(s.join(""));
      return true;
  }

  // fill in space with move character or a blank
  // (the space is only to blank out the initial `@`)
  s[i] = c || " ";

  // iterate through the 3 options and recursively explore the map
  return ['/','-','\\'].some((c,j)=>{
    --j;
    // if last move was sideways, and this is the opposite move, skip it
    if(l && j && j!=l) { return 0; }

    // recursively call search function on space pointed to by this move or the last move
    return search(i+33*(l||j)+1, j, c);
  })

  // if the `some` call is false (i.e. all options fail for this space)
  // then blank out this space and return false
  || !(s[i]=" ");

}
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @vihan1086 Right, I totally missed those spaces when golf-ifying. D: And switching from an array to a split string is an nice change as well. Thanks. :) I've also made a few other changes (making the current move-character a third argument instead of determined within the function, and storing " " in a variable) that brought my score down even lower. \$\endgroup\$
    – apsillers
    Jul 9, 2015 at 13:06
7
\$\begingroup\$

C (complete program), 249 247 235 bytes

This is a complete program reading the input from a file and outputting the result to stdout. The name of the file is passed as a parameter to the program.

char f[7][33];g(i,j,c){return(i<0|i>6|f[i][j]%32?0:j<31?c%45-2?g(i,j+1,c)||g(i+1,j+1,92)||g(i-1,j+1,47):g(i+c/30-2,j+1,c)||g(i+c/30-2,j+1,45):1)?f[i][j]=j?j-31?c:64:32:0;}main(int p,char**v){read(open(v[1],0),f,231);g(3,0,45);puts(f);}

Ungolfed:

/* the field */
char f[7][33];

/* i - row
 * j - col
 * c - movement
 */
g(i,j,c)
{
    return
            /* if we're in bounds and not on an obstacle */
            (i >= 0 & i<7 & f[i][j] % 32 == 0 ?
                    /* if we haven't reached the end */
                    j < 31 ?
                            /* are we going straight ahead? */
                            c%45-2 ?
                                    /* try to go straight */
                                    g(i,j+1,c)
                                    /* try to turn right */
                                    || g(i+1,j+1,92)
                                    /* try to turn left */
                                    || g(i-1,j+1,47)
                            /* turning */
                            :
                                    /* try to keep turning */
                                    g(i+c/30-2,j+1,c)
                                    /* try to go straight */
                                    || g(i+c/30-2,j+1,45)
                    /* done */
                    :1 /* replace this with c==45 to better represent the last move being a turn */
            /* invalid move, fail */
            :0)
            /* add the correct movement to the field */
            ? f[i][j] = j ? j - 31 ? c : 64 : 32
            /* no path, much sads :( */
            :0;
}

main(int p,char*v[])
{
    /* read input file */
    read(open(v[1],0),f,231);

    /* calculate the path */
    g(3,0,45);

    /* print it out */
    puts(f);
}

Output:

$ ./a.out test.inp
|   #####           #########  |
| ######  #          ###   #   |
|   # #  #  #  ####   #      --|
 ------------- ##----####   /  @
|#   #   #    \ /### \ ##  /   |
|##      ##    - #### \ # /#   |
|####           ##### #---##   |

$ ./a.out test2.inp
|# # # # #-# # # # # #-# # # # |
| # # # #/#\# # # # #/#\# # # #|
|# # # #/# #\# # # #/# #\# # # |
 -# # #/# # #\# # #/# # #\# #  @
|#\# #/# # # #\# #/# # # #\# #/|
| #\#/# # # # #\#/# # # # #\#/#|
|# #-# # # # # #-# # # # # #-# |

$ ./a.out test3.inp
|    #    #    #   ------#     |
|    -    #    #  / #    \     |
|   /#\   #    # /  #    #\    |
 --- # \  #    #/   #    # \   @
|    #  \ #    /    #    #  \ /|
|    #   \#   /#    #    #   - |
|    #    ---- #    #    #     |

$ ./a.out test4.inp
|##############################|
|##############################|
|##############################|
 ------------------------------@
|##############################|
|##############################|
|##############################|

$ ./a.out test5.inp
|###-##########################|
|##/#\############### ##-######|
|#/###--######## ### ##/#\#####|
 -######\###### ### ##/###-----@
|########--### ### ##/#########|
|##########\# ### ##/##########|
|###########--------      #####|
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Looks like you missed the end point in the first test. \$\endgroup\$
    – Reto Koradi
    Jul 9, 2015 at 16:40
  • \$\begingroup\$ @RetoKoradi It's a - followed by a \, but the \ is covered up by the @. (My program does the same thing.) \$\endgroup\$
    – apsillers
    Jul 9, 2015 at 16:49
  • 1
    \$\begingroup\$ @RetoKoradi Earlier iterations of this handled that case better. It's +4 bytes. I noticed apsillers' solution behaved similarly so I opted to save the space. \$\endgroup\$
    – Cole Cameron
    Jul 9, 2015 at 17:27
  • \$\begingroup\$ I see. It doesn't look right to me, but it's up to the OP to decide what is allowed. I saw that they gave some liberty on how the moves are represented. I would have liked to see a clear and unique definition from the start. It looked like a fun problem, but it's not nearly as interesting with the ambiguity. \$\endgroup\$
    – Reto Koradi
    Jul 9, 2015 at 17:56
3
\$\begingroup\$

Common Lisp, 303 bytes

Had lots of fun with this challenge, it's the first codegolf task I did. Basically there's a simple recursive function that tries every viable move until the end position is reached.

Golfed/Minified

(let((s(open "i"))(n nil)(f(make-string 231)))(read-sequence f s)(labels((r(p s u d)(and(< 0 p 224)(find(aref f p)" @")(setf(aref f p)(cond((= 130 p)#\@)((or(unless d(r(- p 32)#\/ t n))(unless u(r(+ p 34)#\\ n t))(r(+ p(cond(u -32)(d 34)(t 1)))#\- n n))s)((return-from r)))))))(r 99 #\- n n)(princ f)))

Reads input from a file i in working directory. I'm pretty sure there's still room for improvement.

Plain code

(defun run-test (file)
  (let ((stream (open file)) ;;should use with-open-file for autoclose..
        (no nil) ;; alias for brevity
        (field (make-string 231)))
    (read-sequence field stream)
    (labels ((doit (pos sym going-up going-down)
               (and
                 (< 0 pos 224)
                 (find (aref field pos) " @")
                 (setf (aref field pos)
                       (cond
                         ((= 130 pos) #\@)
                         ((or
                            (unless going-down (doit (- pos 32) #\/ t no))
                            (unless going-up (doit (+ pos 34) #\\ no t))
                            (doit (+ pos (cond (going-up -32)
                                               (going-down 34)
                                               (t 1)))
                                  #\- no no))
                          sym)
                         ((return-from doit)))))))
      (doit 99 #\- no no)
      (princ field)
      nil)))

Sample output

|   #####       --  #########  |
| ######  #    /  \  ###   # - |
|   # #  #  # /####\  #     / \|
--   -       / ##   \####  /   @
|#\ /#\  #  /    ### \ ## /    |
|##-   \ ##/     #### \ #/ #   |
|####   ---     ##### #-- ##   |

|  --#    #    #   --    #-    |
| /  \    #    #  / #\   / \   |
|/   #\   #    # /  # \ /#  \  |
-    # \  #    #/   #  - #   \ @
|    #  \ # ----    #    #    -|
|    #   \#/   #    #    #     |
|    #    -    #    #    #     |

|# #-# # # # # #-# # # # # #-# |
| #/#\# # # # #/#\# # # # #/#\#|
|#/# #\# # # #/# #\# # # #/# #\|
--# # #\# # #/# # #\# # #/# #  @
|# # # #\# #/# # # #\# #/# # # |
| # # # #\#/# # # # #\#/# # # #|
|# # # # #-# # # # # #-# # # # |
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

ActionScript 3, 364 bytes

I split this into two functions; one to change the array into an array of arrays, and one recursive one to compute the flight path.

function m(f){for(var i=0;i<f.length;i++){f[i]=f[i].split("");}n(f,0,3,0);return f;}function n(f,x,y,m){var P=f[y][x],X=x+1,A=y-1,B=y,C=y+1,T=true,F=false,E='-';if (y<0||y>6||P=='#'||P=='|')return F;if (x==31){f[y][x]='@';return T;}if(m<0&&y>0){B=A;C=9;E='/';}else if(m>0&&y<6){A=9;B=C;E='\\';}if (n(f,X,B,0)||n(f,X,A,-1)||n(f,X,C,1)){f[y][x]=E;return T;return F;}

Ungolfed version in a program with one sample asteroid field defined:

package
{
    import flash.display.Sprite;

    public class AsteroidNavigator extends Sprite
    {
        var field:Array;
        public function AsteroidNavigator()
        {
            field = [
"|   #####           #########  |",
"| ######  #          ###   #   |",
"|   # #  #  #  ####   #        |",
"@              ##    ####       ",
"|#   #   #       ###   ##      |",
"|##      ##      ####   #  #   |",
"|####           ##### #   ##   |"];
            m(field);
            printField();
        }

        function m(f){
            for(var i=0;i<f.length;i++){
                f[i]=f[i].split("");\
            }
            n(f,0,3,0);
            return f;
        }

        private function n(field,x,y,m) {
            var C = field[y][x];
            if (x > 31 || C == '#' || C == '|') {
                return false;
            }
            if (x == 31 && y == 3) {
                field[y][x] = '@';
                return true;
            }
            if (m == 0) {
                if (n(x+1, y, 0) || ((y>0) && n(x+1, y-1, -1)) || ((y<6) && n(x+1, y+1, 1))) {
                field[y][x] = '-';
                return true;
                }
            } else if ((m<0) && (y>0)) {
                if ((n(x+1, y-1, -1) || n(x+1, y-1, 0))) {
                    field[y][x] = '/';
                    return true;
                }
            } else if ((m>0) && (y<6)) {
                if ((n(x+1, y+1, 1) || n(x+1, y+1, 0))) {
                    field[y][x] = '\\';
                    return true;
                }
            }
            return false;
        }

        private function printField() {
            var sb = "";
            for each (var row:Array in field) {
                sb += row.join("") + "\n";
            }
            trace(sb);
        }
    }
}
Improve this answer
\$\endgroup\$

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.