Can Gravity Guy Make It?

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

 ###
#
####

----------

### ###

----------

#
### ###

#### ###
#

----------

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

----------

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

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

----------

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

• Are we allowed the grid in columnar format? – Neil Apr 22 '16 at 12:15
• @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. – user81655 Apr 22 '16 at 12:27
• Is it possible for the # in the first column to be in the first row? – feersum Apr 22 '16 at 12:53
• @feersum No, you can assume the grid will include space for the Gravity Guy to "stand" in. – user81655 Apr 22 '16 at 12:57
• Shame; the transposition increases my byte count by 20%. – Neil Apr 22 '16 at 19:45

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

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

Perl, 938981777675 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  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; }  Pip, 856862 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).