27
\$\begingroup\$

Gravity Guy is a game where the only user input is a single key that flips the direction of gravity. Given an ASCII art level, determine if it is possible for Gravity Guy to reach the end.


Rules

  • The initial direction of gravity is down.
  • The first column of the input will always contain only one #, which Gravity Guy starts on top of.
  • Each iteration, he moves to the character directly on his right.
  • If his path is blocked and he moves into a #, the player loses.
  • After moving, the player can optionally switch gravity from down to up, or up to down.
  • Gravity Guy then falls on to the next # (in the current direction of gravity).
  • If there is no # to fall on to and he falls off the grid, the player loses.
  • If Gravity Guy moves off the right side of the input grid, the player wins.

Example

If this was the input grid:

  ### 

#  # #
 ###  

Gravity Guy would start at the x and the be at these positions after each iteration. ^ = switch gravity to up and v = switch gravity to down.

v                        ^                               v
-------------------------------------------------------------
  ###   |    ###   |    ###   |    ###   |    ###   |    ### 
x       |          |    x     |     x    |      x   |        
#  #    |  #x #    |  #  #    |  #  #    |  #  #    |  #  # x
 ### #  |   ### #  |   ### #  |   ### #  |   ### #  |   ### #

As you can see, by switching gravity at these times Gravity Guy reaches the end, so this input would return a truthy value.

Specifications

  • Input grid can be in any appropriate "grid" format (multiline string padded with spaces, array of line strings, array of array of characters, etc).
  • If it is possible for the player to win the level, output a truthy value. If not, output a falsey value.
  • The width and height of the grid will be 50 characters at most.
  • This is , may the shortest code in bytes win!

Test Cases

(each case separated by ----------, any blank lines should also be padded with spaces)

True

 #########   ########      ######     ######    
          #  #       #    #      #   #      #   
###    #   # #    #   #  #       #  #        #  
  #    ##  # #    ##  # #     # #  #      ##    
  #    #   # #    #   # #    #     #     #######
  #       #  #       #  #     ###  #          # 
  #    ##    #    ##     #       #  #         # 
  #    #          #              #        #   # 
  #    ####################################   # 
  #                                           # 
  ############################################# 

----------


###

----------

   #####

####    

----------

 #####
 # # #

# # # 
 #####

----------

   ############   

######      ######

   ############   

----------

  ###   ###  
     # #     
####  #  ####
    #   #    
     # #     
      #      

----------

    ######  
   #        
 ##         
     #######
###     #   
   #    #   
    #####   


----------

    #####   
   #    #   
 ##     #   
     #######
###         
   #        
    ######  

----------

  ### 

#  # #
 ###  

----------

  ###  ###

###     ##
   #    # 
    ##### 

----------

  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         

----------

    ##### ####   
   #     #    #  
  #   # #  ##  # 
             #  #
#####  ####   #  
               # 
     #########   

----------

 ########################### 
 #   #   #   #     #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 

False

 ###
   #
####

----------


### ###

----------

    #   
 ### ###

#### ###
    #   

----------

  ###     ###  
     # # #     
####  # #  ####
    #     #    
     #   #     
      # #      
       #       

----------

  ####### 
  #     # 
 ## ##### 

### ######
  #     # 
  ####### 

----------

 ########################### 
 #   #   #   #  #  #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
\$\endgroup\$
5
  • \$\begingroup\$ Are we allowed the grid in columnar format? \$\endgroup\$
    – Neil
    Apr 22, 2016 at 12:15
  • \$\begingroup\$ @Neil You mean a transposed/rotated array? I'm going to say no, since it's altering the input. But if your language has a special column type, that would be OK to use I guess. \$\endgroup\$
    – user81655
    Apr 22, 2016 at 12:27
  • \$\begingroup\$ Is it possible for the # in the first column to be in the first row? \$\endgroup\$
    – feersum
    Apr 22, 2016 at 12:53
  • \$\begingroup\$ @feersum No, you can assume the grid will include space for the Gravity Guy to "stand" in. \$\endgroup\$
    – user81655
    Apr 22, 2016 at 12:57
  • \$\begingroup\$ Shame; the transposition increases my byte count by 20%. \$\endgroup\$
    – Neil
    Apr 22, 2016 at 19:45

4 Answers 4

19
\$\begingroup\$

Snails, 15 bytes

Try it online?

^
\ n\ ,=\#r}+~

​​ ​ ​ 0​. ^ is an option that requires the pattern to start at the top left.

  1. \ ​: match space

  2. n: Turn 90 degrees in either direction

  3. \ ,​: match space zero or more times

  4. =\# check that there is a # in front of us

  5. r: set the direction to right

  6. }+: do all of the preceding one or more times

  7. ~ match a cell which is out of the grid bounds

\$\endgroup\$
4
  • \$\begingroup\$ This gives 0 for most of the True test cases \$\endgroup\$ Apr 22, 2016 at 14:48
  • \$\begingroup\$ @Bas Have you padded the empty lines with spaces? \$\endgroup\$ Apr 22, 2016 at 14:51
  • \$\begingroup\$ @MartinBüttner I directly copied some of the inputs, doing so indeed removed some of the spaces. It works indeed after adding spaces \$\endgroup\$ Apr 22, 2016 at 14:55
  • 5
    \$\begingroup\$ Since nobody's said it yet: This is Awesome! \$\endgroup\$
    – DLosc
    Apr 23, 2016 at 2:37
9
\$\begingroup\$

Perl, 93 89 81 77 76 75 74 bytes

Includes +2 for -0p

Run with the input pattern (with all lines space padded to the same length) on STDIN:

gravity.pl < gravity.txt

gravity.pl:

#!/usr/bin/perl -0p
/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w

This file based version needs the final newline, so that is really 75 bytes. But the commandline based version doesn't need that extra newline so this counts as 74 bytes:

perl -0pe '/
/;$n=".{@-}";s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es&&redo;$_=m;w' < gravity.txt

Explanation:

This will construct a string with a w in each positions gravity guy can reach. So for the second to last truthy example it will construct:

     #########   
    ##### ####   
   #wwwww#wwww#  
  #w  # #w ##ww# 
wwwww wwwwwww#ww#
#####  ####  w#ww
     wwwwwwwwww# 
     #########   

So gravity guy can make it if and only if there is a w in the last column. The string will be constructed by replacing one reachable space by w in each round.

Each replacement will be of the form

s/prefix \K space postfix/ w | $& /e

which will demand that the space is preceded by prefix and followed by postfix but replace only the space by w without needing lots of advanced grouping.

Assume $n contains a regex that will progress just enough that the left and right sides are exactly below each other. Then the relevant regexes are:

/^( $n)*\K $n#/       From the first position drop down as long as you
                      encounter spaces until you encounter a #. 
                      This puts gravity guy on his starting platform

/#$n\K( $n)*\b /      A space immediately below a # and if you (optionally)
                      go down further from there (as as the descent is
                      over spaces) you get to a space that follows a word
                      boundary. The only way to get a word boundary is if 
                      there is a w in front of that space. This selects the
                      position gravity guy ends up on if starting from that
                      w and gravity is up
/w([w ]$n)*\K $n#/    A w followed by a space (or w) and if you go down from
                      there as long as it is over spaces (or w) you finally
                      end up on a space directly above a #. This handles the
                      gravity down case. The test uses "space or w" instead
                      of just space to handle this case:

                       #
                      ww
                      #x  
                       #

                      Position x is currently a space and must be replaced by a
                      w but the gravity up regex has already put a w directly
                      after the w gravity guy takes off from. So for gravity
                      down we must handle w as if it is still a space. This
                      is not needed for gravity up because regex always matches
                      starting at the earliest possible character, so 
                      gravity up matches before gravity down

With that out of the way the program is easy:

#!/usr/bin/perl -0p   Slurp all of STDIN into $_, at the end print $_

/\n/                  Match the first newline (needed to measure the row
                      length)
$n=".{@-}"            $n effectively becomes rowlength-1 times ".". This
                      will be the regex that goes one step down a column

s/#$n\K( $n)*\b |(^|w)([w ]$n)*\K $n#/w|$&/es

                     This is the 3 regexes shown above combined. The s 
                     modifier is needed so the . in $n also matches newline

    &&redo           Keep looping as long as w's keep getting added

$_=m;w\n;            Check if the last column contains a w: He made it!
                     The \n; at the end is not written. These 2 bytes sneakily
                     come from the -p option for the ; and the -e option
                     for the \n
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 174 bytes

a=>[...a[0]].map((_,i)=>[...t].map(x=>s[x]<'#'&&g(s.indexOf('#',x),-1)&&g(s.lastIndexOf('#',x),1),s=a.map(s=>s[i]),t=new Set),t=new Set([0]),g=(i,d)=>i<0||t.add(i+d))&&t.size

Takes a horizontal array of strings and returns the number of exit points. Transposing the array costs me 29 bytes. Ungolfed:

function gravity(array) {
    var set = new Set;
    set.add(0); // starting point
    for (var i = 0; i < array[0].length; i++) {
        var s = array.map(s => s[i]); // transpose array
        var old = set;
        set = new Set;
        for (var x of old) {
            if (s[x] == '#') continue; // hit wall
            var j = s.indexOf('#', x); // try downward gravity
            if (j >= 0) set.add(j - 1);
            j = s.lastIndexOf('#', x); // try upward gravity
            if (j >= 0) set.add(j + 1);
        }
    }
    return set.size;
}
\$\endgroup\$
3
\$\begingroup\$

Pip, 85 68 62 59 + 1 = 60 bytes

Uses the -r flag to read all lines of stdin.

FcZg{YlFxiIc@xQsyPB(Jc@<x@?`# *$`)+1PB(c@>x@?'#)+x-1i:UQy}i

Try it online!

Brief explanation

The strategy is essentially a breadth-first search. We transpose the input and loop over the lines (columns), keeping a list of the y-positions the player could reach in that column. The output after the last column is a non-empty list if the player can win, or an empty list (which prints as just a trailing newline) if the player loses.

Full explanation

Built-in variables used in this program: i == 0, l == [], s == " ".

The -r flag puts a list of the lines of input into g. FcZg{...} zips g and loops over each column c. (Unary Z, when applied to a list of iterables, acts like Python zip(*g), neatly transposing a 2D array.) Note that c will be a list, not a string.

Inside the column loop, we reset y to the empty list by Yanking l. Fxi loops over i. In later iterations, i will be a list of the y-coordinates the player was able to reach in the previous column. The first time through, we want to start with just 0 (upper left corner). The variable is preinitialized to a Scalar 0, not a List [0], but Pip iterates over it just fine either way.

For each of the valid positions in the last column, Ic@xQs checks whether there is a space in that position in the current column. If not, the player just ran into a wall and we go on to try the next possibility. If so, then we want to find the positions the player will fall to in this column for each direction of gravity, and add them to the list y using the PushBack operator.

Gravity going up (left, in the transposed version):

(Jc@<x@?`# *$`)+1
  c@<x             Slice everything left of x in the column
 J                 Join into a string so we can do a regex search on it
      @?`# *$`     Find index of the last # in this string
(             )+1  The player's index is the space below/to the right of this #

Gravity going down (right, in the transposed version):

(c@>x@?'#)+x-1
 c@>x              Slice everything right of x in the column
     @?'#          Find index of the first # in this list (no need to join into string)
(        )+x       Translate to index number in entire column
            -1     The player's index is the space above/to the left of this #

If the player falls off the grid in a particular direction, the respective @? operation will not find a # and will give nil. This is not a valid index and will generate some warnings in the next iteration--which, however, are not visible without the -w flag. For our purposes, these cases are essentially eliminated from consideration.

After the inner loop, i:UQy takes the list y of positions we've built, eliminates duplicates, and assigns it to i. (Eliminating duplicates is necessary because otherwise the list balloons exponentially.) We then go to the next column. When we have looped through all columns, if there was a valid path through, i will be a nonempty list of positions (truthy); if not, it will be an empty list (falsey).

\$\endgroup\$

Your Answer

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

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