Can the cursor reach the bottom?

Question

In a matrix of characters, a cursor is a movable position between two adjacent characters, before the first character or after the last character in a line, like that "I"-shaped indicator which moves while you type.

In this challenge, a cursor position is considered valid if at least one of its two sides touches a space. The cursor travels through valid positions in a matrix, by moving up, down, left or right by one position each time. It could also move left or right though the line separator, to the end of the previous line, or the beginning of the next line respectively.

Given a character matrix as input, and a cursor initially at the top left corner, your task is to determine whether it can reach the bottom line.

This is a code-golf and decision-problem problem; the rules of this question is the same as what these two tags specified.

Rules

• You can assume that the input consists only of ., , and newlines. (Only these three characters and no more characters; otherwise its behavior is undefined.)
• You may require there must or must not be a trailing newline in the input, if you want to.
• Your code should output either a truthy value (if the condition is true), or a falsy value (if the condition is false).

Examples

Example input(where ░ is the space character):

░.....░
░......
.░.░.░.
.░░░░░░
......░

The cursor can reach the bottom in this case. This process of moving the cursor will work: down, right(touches spaces on the left), down(touches spaces on the right), down, right(touches spaces on both sides) 6 times, and down(touching spaces on the left).

This will also work(░ still represent spaces):

░░
.░
.░

The cursor starts at the up-left corner. After moving right two times, it can move down twice, which touches the bottom of the lines.

This example will not work(░ represent spaces again):

░...
...░

The cursor cannot move down, as there is no sufficient whitespace to be touched. There are only newline characters on the right of the input, and there are no newline characters on the left(otherwise a line would have spanned two lines.)

The cursor can also move up and left, in order to solve a maze-like input as in this one:

░....
░░░░.
...░.
.░░░.
░....
░░░░░

In this case, the cursor has to move left in order to get through spaces and get to the bottom line.

Here is another important test case: the cursor can move left or right to another line.

░░░░
...░
░...

In this case, the cursor can reach the last line, as the cursor can move left or right in order to get to the next line. Moving the cursor down is blocked on the right position of row 2, column 4; however, the cursor can still get to the last line if it moves right (touching spaces).

This is a fairly interesting test input:

░░..░
░...░
....░

In this case, the cursor can reach the last line, by moving down and left to the end of the first line, then down twice to reach the end of the bottom line.

Answer 1

APL (Dyalog Unicode), 60 bytes^SBCS

Full program. Prompts for character matrix from stdin. Prints 1 or 0 to stdout. Requires zero-indexing (⎕IO←0) which is default on many systems.

P←{' '0∊⍨s←(×⍨≢⍺)⊃,⍵:1∊⍵⋄s}
1∊⊢⌿{P⌺3 3⊢(⍴⍵)⍴1@0P⌺3,⍵}⍣≡3/3⌿⎕

Try it online! (space characters replaced by ░ for clarity)

The method here is basically to seed fill from the top left corner, but alternating between 1D and 2D seed fill to account for line wrapping and vertical/diagonal motion. Diagonal motion is simple horizontal motion followed by vertical motion, since the cursor sits in between adjacent characters.

The first line defines a helper function P(rocess) which will be called on each neighbourhood.

P←{…} "dfn"; ⍵ is the neighborhood, ⍺ is the number of padded elements for each dimension:

 ,⍵ ravel (flatten) the neighbourhood into a list

 (…)⊃ pick the following element from that:

  ⍺ the paddings per dimension (so a 1 or 2 element list, depending on ⍵ being 1D or 2D)

  ≢ the tally of that (1 or 2)

  ×⍨ the square of that (lit. multiplication selfie; 1 or 4)

 s← assign to s(elf; i.e. the centre of the neighbourhood)

' '0∊⍨ is that a member of [" ",0]?

 : if so:

  1∊⍵ return whether the neighbourhood has a one

 ⋄ else:

  s return s(elf unmodified, i.e. leave as-is for now)

The second line is the main part of the program:

⎕ prompt for evaluated input via the console (stdin)

3⌿ triplicate each row (ensures we have at least 3 — makes no difference to connectivity)

3/ triplicate each column (ensures we have at least 3 — makes no difference to connectivity)

{…}⍣≡ apply this function repeatedly until two successive results are identical (i.e. until stable):

 ,⍵ ravel (flatten) the matrix into a list

 P⌺3 apply P to each neighbourhood of 3 elements

 1@0 replace the current value at position 0 with a 1 (this seeds the top left corner)

 (…)⍴ reshape that into the following shape:

  ⍴⍵ the original shape of the matrix

⊢⌿ get the bottom row (lit. vertical right-reduction)

1∊ is there any 1 there?

Answer 2

Jelly, 47 43 bytes

p®§Qæ%L}>Ƈ0ịƇ
=⁶oŻ$€µZL;1;N$©ṛF1çƬFṀ’:®Ḣ‘=L

Try it online!

A full program that takes a list of strings as its argument and returns 1 if the bottom line is reachable and 0 if not.

Explanation

Helper link

Test moves up, down left and right and extend reachable position list. Left argument: most recently added reachable position list; right argument: boolean list of whether each possible position is valid

 p®            | Cartesian product with each of the values stored in the register (the width of the position list, 1 and the negation of each)
   §           | Sum each of these
    F          | Flatten
     Q         | Uniquify
      æ%L}     | Symmetric mod using the length of the valid position list: this will mean any positions that move off the top or bottom will be negative
          >Ƈ0  | Filter out those reachable positions which are negative
            ịƇ | Filter out those which are invalid

Main link

Takes a single argument, a list of Jelly strings representing the grid

=⁶                             | Check of equal to space
   oŻ$€                        | Logical or each row with itself prepended with zero; this yields rows 1 longer, and will indicate whether each cursor position is valid
       µ                       | Start a new monadic chain
        ZL                     | Zip and get the length (will be the length of each row)
          ;1                   | Concatenate 1
            ;N$©               | Concatenate the negations and store in the register (i.e. width, 1, -width, -1)
                ṛF             | Replace with the flattened grid of position validity
                  1çƬ          | Call the helper link, starting with 1 as left argument and using the flattened position validities as right. Repeat until unchanged. Return all collected values. 
                     F         | Flatten, getting all reachable positions (may include duplicates)
                      Ṁ        | Maximum position reached
                       ’       | Decrease by 1 (because of 1-indexing)
                        :®     | Integer divide by the register
                          Ḣ    | Head (will effectively be max position integer divided by width)
                           ‘   | Increase by 1
                            =L | Check if equal to length (i.e. height) of position grid