23
\$\begingroup\$

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.

||improve this question
\$\endgroup\$
  • 3
    \$\begingroup\$ There should be a testcase where the player needs to move left to complete the level \$\endgroup\$ – Embodiment of Ignorance Dec 3 '19 at 4:21
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Dec 3 '19 at 5:38
  • 3
    \$\begingroup\$ Suggested testcase: \$ \begin{bmatrix} &&=&&&=\\\\=&&&=\\&=&&&=\end{bmatrix} \$ \$\endgroup\$ – tsh Dec 3 '19 at 8:23
  • 3
    \$\begingroup\$ Suggested testcase: \$ \begin{bmatrix} &=&&&=&&&=&&&=\\\\\\=&&=&=&&=&=&&=&=&& \end{bmatrix} \$ \$\endgroup\$ – tsh Dec 3 '19 at 9:07
  • 4
    \$\begingroup\$ @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.) \$\endgroup\$ – Nitrodon Dec 3 '19 at 18:34
9
\$\begingroup\$

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!

||improve this answer
\$\endgroup\$
  • \$\begingroup\$ ṙ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?) \$\endgroup\$ – Jonathan Allan Dec 3 '19 at 20:07
  • \$\begingroup\$ (...edit: a 0 below the starting 5 becomes a 1) \$\endgroup\$ – Jonathan Allan Dec 3 '19 at 20:16
  • \$\begingroup\$ @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. \$\endgroup\$ – Nick Kennedy Dec 3 '19 at 21:21
  • \$\begingroup\$ Ah, well in that case I«0^Ʋ1¦%7 would save two; there is probably something shorter. \$\endgroup\$ – Jonathan Allan Dec 3 '19 at 22:26
  • 1
    \$\begingroup\$ @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! \$\endgroup\$ – Nick Kennedy Dec 3 '19 at 23:12
5
\$\begingroup\$

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()
||improve this answer
\$\endgroup\$
  • \$\begingroup\$ It is possible that you'll need to move left at some point to win the level. This solution does not account for that. \$\endgroup\$ – Nitrodon Dec 3 '19 at 19:51
  • \$\begingroup\$ @Nitrodon Thanks for reporting this. Now fixed. \$\endgroup\$ – Arnauld Dec 4 '19 at 9:14
4
\$\begingroup\$

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
||improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ z -> Õ -1 byte \$\endgroup\$ – Embodiment of Ignorance Dec 4 '19 at 5:31
  • 1
    \$\begingroup\$ ®raÃx <4 -> x_raÃ<4 -1 byte\ \$\endgroup\$ – Embodiment of Ignorance Dec 4 '19 at 5:42
  • 1
    \$\begingroup\$ @Nick Kennedy now I see.. It has to jump backwards to reach higher blocks.. I try to fix it ASAP! thank you \$\endgroup\$ – AZTECCO Dec 4 '19 at 9:45
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Nick Kennedy Dec 4 '19 at 12:52
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Nick Kennedy Dec 7 '19 at 17:24
2
\$\begingroup\$

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.

||improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

||improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Nitrodon Dec 3 '19 at 21:38
  • \$\begingroup\$ I see it now, thanks! \$\endgroup\$ – Seb Dec 4 '19 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.