[Question]
  [
[Gravity Guy](http://www.miniclip.com/games/gravity-guy/en/) 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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), may the shortest code in bytes win!
## Test Cases
(each case separated by `----------`, any blank lines should also be padded with spaces)
### True
```
 #########   ########      ######     ######    
          #  #       #    #      #   #      #   
###    #   # #    #   #  #       #  #        #  
  #    ##  # #    ##  # #     # #  #      ##    
  #    #   # #    #   # #    #     #     #######
  #       #  #       #  #     ###  #          # 
  #    ##    #    ##     #       #  #         # 
  #    #          #              #        #   # 
  #    ####################################   # 
  #                                           # 
  ############################################# 
----------
###
----------
   #####
####    
----------
 #####
 # # #
# # # 
 #####
----------
   ############   
######      ######
   ############   
----------
  ###   ###  
     # #     
####  #  ####
    #   #    
     # #     
      #      
----------
    ######  
   #        
 ##         
     #######
###     #   
   #    #   
    #####   
----------
    #####   
   #    #   
 ##     #   
     #######
###         
   #        
    ######  
----------
  ### 
#  # #
 ###  
----------
  ###  ###
###     ##
   #    # 
    ##### 
----------
  #        
     #   # 
       #   
#   #     #
        #  
   #       
      #    
 #         
----------
    ##### ####   
   #     #    #  
  #   # #  ##  # 
             #  #
#####  ####   #  
               # 
     #########   
----------
 ########################### 
 #   #   #   #     #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
```
### False
```
 ###
   #
####
----------
### ###
----------
    #   
 ### ###
#### ###
    #   
----------
  ###     ###  
     # # #     
####  # #  ####
    #     #    
     #   #     
      # #      
       #       
----------
  ####### 
  #     # 
 ## ##### 
### ######
  #     # 
  ####### 
----------
 ########################### 
 #   #   #   #  #  #   #   # 
 # # # #   #   # #   #   # # 
 # # # ######### ########### 
 # # # #  #       #     #  # 
   # # # ## ##### ### #      
## #   #    #          ## ###
 # ##### #### ###########  # 
 # #     #  #     #     ## # 
 # # #####  ### # # # # #  # 
 #              #   # #   ## 
 ########################### 
```
  
[Answer]
# [Snails](https://github.com/feresum/PMA), 15 bytes
[Try it online?](http://snails.tryitonline.net/#code=XgpcIG5cICw9XCNyfSt-&input=ICMjIyMjIyMjIyAgICMjIyMjIyMjICAgICAgIyMjIyMjICAgICAjIyMjIyMgICAgCiAgICAgICAgICAjICAjICAgICAgICMgICAgIyAgICAgICMgICAjICAgICAgIyAgIAojIyMgICAgIyAgICMgIyAgICAjICAgIyAgIyAgICAgICAjICAjICAgICAgICAjICAKICAjICAgICMjICAjICMgICAgIyMgICMgIyAgICAgIyAjICAjICAgICAgIyMgICAgCiAgIyAgICAjICAgIyAjICAgICMgICAjICMgICAgIyAgICAgIyAgICAgIyMjIyMjIwogICMgICAgICAgIyAgIyAgICAgICAjICAjICAgICAjIyMgICMgICAgICAgICAgIyAKICAjICAgICMjICAgICMgICAgIyMgICAgICMgICAgICAgIyAgIyAgICAgICAgICMgCiAgIyAgICAjICAgICAgICAgICMgICAgICAgICAgICAgICMgICAgICAgICMgICAjIAogICMgICAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjICAgIyAKICAjICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgCiAgIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIA)
```
^
\ 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
[Answer]
# 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
```
[Answer]
## 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;
}
```
[Answer]
# [Pip](http://github.com/dloscutoff/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!](http://pip.tryitonline.net/#code=RmNaZ3tZbEZ4aUljQHhRc3lQQihKY0A8eEA_YCMgKiRgKSsxUEIoY0A-eEA_JyMpK3gtMWk6VVF5fWk&input=ICAgICMjIyMjICAgCiAgICMgICAgIyAgIAogIyMgICAgICMgICAKICAgICAjIyMjIyMjCiMjIyAgICAgICAgIAogICAjICAgICAgICAKICAgICMjIyMjIyAg&args=LXI)
**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 `Y`anking `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 `P`ush`B`ack 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).
]