# Is this platform game level winnable?

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.

• There should be a testcase where the player needs to move left to complete the level Dec 3, 2019 at 4:21
• Another good pair of test cases would be where platforms alternate between the top and bottom position for a while, and you need to choose the upper or lower path at the start but only one of them gets to the finish.
– xnor
Dec 3, 2019 at 5:38
• Suggested testcase: $\begin{bmatrix} &&=&&&=\\\\=&&&=\\&=&&&=\end{bmatrix}$
– tsh
Dec 3, 2019 at 8:23
• Suggested testcase: $\begin{bmatrix} &=&&&=&&&=&&&=\\\\\\=&&=&=&&=&=&&=&=&& \end{bmatrix}$
– tsh
Dec 3, 2019 at 9:07
• @tsh The "[moves] which do not pass through a platform" rule can be safely ignored because of the "one platform per column" rule. You can simply jump on any platform that blocks an otherwise legal jump. (In the proposed counterexample, the platform in column 3 does not block a jump from column 1 to column 2.) Dec 3, 2019 at 18:34

# 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! • ṙ1¬a4$+Ʋ€1¦ can be replaced with ^I$1¦%7 saving four bytes (so long as it is OK that a 1 below the starting 5 becomes a 0 - which I think it is, right?) Dec 3, 2019 at 20:07 • (...edit: a 0 below the starting 5 becomes a 1) Dec 3, 2019 at 20:16 • @JonathanAllan Thanks. I originally had something like that, but it means that the player can start by travelling down which isn’t allowed I don’t think it affects the test cases, but might alter edge cases. Dec 3, 2019 at 21:21 • Ah, well in that case I«0^Ʋ1¦%7 would save two; there is probably something shorter. Dec 3, 2019 at 22:26 • @JonathanAllan thanks. I’ve yet to find a test case where moving down at the start makes a difference. Still, it does mean we’re sticking to the official rules of the challenge re moving through blocks! Dec 3, 2019 at 23:12 # 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()  • It is possible that you'll need to move left at some point to win the level. This solution does not account for that. Dec 3, 2019 at 19:51 • @Nitrodon Thanks for reporting this. Now fixed. Dec 4, 2019 at 9:14 # 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 # Japt-Q, 76 bytes Õcð í ïÈcY ó x_raÃ<4Ã®*JÃòUÎl g0_ma @T=Uc x UgUy_x_>0}Ãð _maÃT¥Uc x}a o x >0  Try it Translation of Jelly answer of @Nick Kennedy , a lot more efficient but longer , I think it can be shortened. ## Explanation / translation Jelly => Japt (taken from Nick answer) ŒṪ => Õcð í M ultidimensional truthy indices of each ạþ => ïÈcY òUÎl O uter table using absolute difference and with the same argument on both sides: § => ó x_ra Sum innermost lists <4 => Ã<4Ã Less than 4 N => ®*JÃ Negate A1¦ => g0_ma Absolute top row ÐL => @T=Uc x...T¥Uc x}a Apply the following until no changes: On my side I used T to store the total of the whole matrix to check if it changed because g() modify the original matrix. A$¦ => Ug..._maÃ   Absolute the rows indicated by the following:
»/   => Uy_x_>0}    Max of each column :
on my side I rotated the table and reduced to get the positive rows
T    => Ãð          Truthy indices (i.e. where there’s a 1 in the column)
Ṫ    => o           Finally take the last row
Ṁ    => x >0        Max : on my side >0

• z  -> Õ -1 byte Dec 4, 2019 at 5:31
• ®raÃx <4 -> x_raÃ<4 -1 byte\ Dec 4, 2019 at 5:42
• @Nick Kennedy now I see.. It has to jump backwards to reach higher blocks.. I try to fix it ASAP! thank you Dec 4, 2019 at 9:45
• @AZTECCO I don’t know any Japt, but I expect my approach in Jelly could be translated. I build a table of which columns can reach which, and then iteratively extend paths from the first row. Dec 4, 2019 at 12:52
• @AZTECCO nice idea. Sorry I’d not seen it - I think putting the space in my name may have confused the way it picks up usernames. Dec 7, 2019 at 17:24

# 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.

# Python 3, 198 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, 214 bytes

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.

• A 2 up, 1 left move can be useful to reach a higher level. The six-column test case posted by tsh in a comment is an example where this is required. Dec 3, 2019 at 21:38
• I see it now, thanks!
– Seb
Dec 4, 2019 at 0:41