Is this platform game level winnable?

Question

Given a level from a simple platform game, your task is to make a program or function to determine if a level is winnable. Platform game levels are 4 characters tall and any number of characters wide. There is exactly one platform for each horizontal space in a level:

           =======    =     
==    =           =         
   ===                 =====
  =    ====        ===      

The game consists of jumps. Jumps start from the space above the platform which is being jumped from, and end in the space above the platform which is being jumped to (these can be above the 4 platform height levels). To complete a jump, it must be possible to move from the start point to the end point in four or less (including the start/end points) up, down, left, and right moves which do not pass through a platform. Here are some examples (marked with A for start platform and B for end platform):

 >>>
 ^ B
=A
  =

 >>>>
=A  B=

>>
^B
A

Horizontal moves along a platform are just jumps which only move in one direction:

  >>
==AB===

The player would start on the leftmost platform, and wins by standing on the rightmost one (marked with vs):

v  === v
===   ==

Test cases

Winnable:

 ===      ==
=    =====  
    =       

    ==      

=         ==
 ===  ====  

   ==== =   
===         
       =    
         ===

  ==  ==  = 

=           
 =  ==  == =

Unwinnable:

      ======


======      

 =======   =
=         =
         =
        =

           =
   =        
=     =     
 == == ==== 

Rules

Your program should output one distinct value if a level is winnable, and a different one if it isn't. It can take input in any reasonable form, such as an ASCII art with any two distinct characters, a matrix, or a 2d array.

Code golf, so shortest answer per language wins.

Answer 1

Jelly, 23 22 bytes

ŒṪạþ`§<4NA1¦A»/T$¦ÐLṪṀ

Try it online!

New version, which now efficiently handles moves backwards. Takes input as a boolean matrix (row major). Returns 1 for winnable and 0 for not.

Thanks to @AZTECCO for first suggesting using the indices of platforms, and @tsh for a test case that made me rethink my approach.

Explanation

ŒṪ                     | Multidimensional truthy indices of each
  ạþ`                  | Outer table using absolute difference and with the same argument on both sides:
     §                 | Sum innermost lists
      <4               | - Less than 4
        N              | Negate
         A1¦           | Absolute top row
                  ÐL   | Apply the following until no changes:
            A   $¦     | Absolute the rows indicated by the following:
             »/        | - Max of each column
               T       | - Truthy indices (i.e. where there’s a 1 in the column)
                    Ṫ  | Finally take the last row
                     Ṁ | Max

Step b step

(each matrix shown collapsed as a grid, with - = -1):

1. Input

0010
0001
1000
0010
0001
1000

2.ŒṪ

Multidimensional indices.

[[1, 3], [2, 4], [3, 1], [4, 3], [5, 4], [6, 1]]

3. ạþ`§<4N

Convert to initial outer table with -1 for possible moves between columns and 0 where no move possible.

--0-00
--0--0
00--0-
-----0
0-0--0
00-00-

4. A1¦A»/T$¦ÐL

Absolute first row, then iteratively take each column with at least one 1 in it, and absolute the rows at those indices; results after each iteration shown.

Absolute row 1 ->

110100
--0--0
00--0-
-----0
0-0--0
00-00-

-> Absolute rows 1, 2, 4 ->

110100
110110
00--0-
111110
0-0--0
00-00-

-> Absolute rows 1, 2, 3, 4, 5 ->

110100
110110
001101
111110
010110
00-00-

-> Absolute rows 1, 2, 3, 4, 5, 6 ->

110100
110110
001101
111110
010110
001001

5. ṪṀ

Finally, take the max of the last row

1

My previous 61 byte version has explanation in the edit history; thanks to @JonathanAllan for golfing 3 bytes off that one!

Answer 2

JavaScript (ES6),  129  126 bytes

Takes input as a binary matrix. Returns either \$0\$ or \$1\$.

f=(a,x=0,m,d=4,g=d=>k=a.findIndex(r=>r[x+d]))=>!~g(1)|[...'1350531'].some(v=>~g(--d)&&m^(M=m|1<<x+d)&&(k-=g``)*k<v&f(a,x+d,M))

Try it online!

How?

Given the current column \$x\$ and a horizontal jump distance \$dx\$, the helper function \$g\$ returns the 0-indexed row of the platform at column \$x+dx\$, or \$-1\$ if \$x+dx\$ is outside the playfield.

g = d =>             // d = dx
  k =                // save the result in k
    a.findIndex(r => // for each row r in a[]:
      r[x + d]       //   test whether r[x + dx] is truthy
    )                // end of findIndex()

Starting with \$x=0\$, the recursive function \$f\$ attempts to find a way to the last column by trying all valid jumps and keeping track of visited columns.

f = (                // f is a recursive function taking:
  a,                 //   a[] = input matrix
  x = 0,             //   x = current column
  m,                 //   m = bit-mask of visited columns
  d = 4,             //   d = dx
  g = …              //   g = helper function (see above)
) =>                 //
  !~g(1) |           // success if g(1) is equal to -1
  [...'1350531']     // list of exclusive upper bounds for dy²
                     // corresponding to dx = +3, +2, +1, 0, -1, -2, -3
  .some(v =>         // for each upper bound v:
    ~g(--d) &&       //   decrement d; success if g(d) is not equal to -1
    m ^ (            //   AND m is different from
      M = m |        //     the new bit-mask M
          1 << x + d //     where the bit corresponding to x + d is set
    ) &&             //   AND
    (k -= g``) * k   //   dy² = (g(d) - g(0))²
    < v &            //   is less than v
    f(a, x + d, M)   //   AND a recursive call at the new position is also true
  )                  // end of some()

Answer 3

Japt, 42 bytes

Õcð í
o
v
à cá ®pV uWÃd_äÈcY ó x_raÃ<4 Ãr*

Try it

Test 1

Test 2

Test 3

Temporarily fixed by using permutations to allow backwards jumps (really inefficient) , going to try @Nick Kennedy solution soon.

z cð í  // get each column height and pair with column index
o       // save end position and remove from array
v       // same for start pos

à  cá        // combinations of permutations 
  ®pV uWÃ  // restore end and start

d          // return true if any returns true to..
 _  ...  Ãr* // reduce result
  ä          // pass each consecutive x,y
   ÈcY ó     // 'reshape~transpose' => [ platform pair, index pair]
         x_raà // sum of absolute difference of each pair
               <4 // return if less for each pair

Saved 2 thanks to @Embodiment of Ignorance

Answer 4

R, 137 136 bytes

function(a,e=abs(outer(b<-which(a,T),b,`-`)),g=-(e[,1,,1]+e[,2,,2]<4),h=1){while(any(g<{g[h,]=abs(g[h,]);g}))h=colSums(g>0)>0;rev(g)[1]}

Try it online!

Essentially an R translation of my Jelly answer, but with some R golfs to take advantage of the way outer works on arrays. A function that takes as its argument a logical matrix with the rows corresponding to the rows of the original question. Returns 1 for winnable and -1 for non-winnable.

Answer 5

Python 3, 199 bytes

A messy solution with NumPy, takes a list of strings as input:

w=lambda l:t(g(array(where((array(list(map(list,l)))=='=').T)).T))
from numpy import*
g=lambda p:abs(p[:,None]-p).sum(2)<4
t=lambda m,x=0:x+1==len(m)or max([t(m,p) for p in where(m[x])[0]if p>x]+[0])

Try it online!

This assumes that no levels exist for which the bolded part here is of importance:

To complete a jump, it must be possible to move from the start point to the end point in four or less (including the start/end points) up, down, left, and right moves which do not pass through a platform.

I have been unable to imagine such a level and none are given as a test case. Likewise I can't imagine a level that requires a leftwards move so an appropriate test case there would be welcome also, if I'm mistaken. Thanks to Nitrodon for pointing me in the right direciton.

Python 3, 217 bytes

w=lambda l:t(g(array(where((array(list(map(list,l)))=='=').T)).T),[])
from numpy import*
g=lambda p:abs(p[:,None]-p).sum(2)<4
t=lambda m,v,x=0:x+1==len(m)or max([t(m,v+[x],p) for p in where(m[x])[0]if x not in v]+[0])

Try it online!

A solution that incorporates leftwards movement, with tsh's test cases included. This cost quite a few bytes, I'll have to sleep on it to golf it more.