Stuck on Sokoban

Question

In the classic game of Sokoban the player's character solves puzzles by pushing boxes around a warehouse onto designated targets. Take, for example, this ASCIIfied game level:

...x. ..B.. x.A.. ..... ..o..

This level could be solved by the player (o) pushing box A left 2 spaces onto the target x, then pushing box B up 1 space and right 1 space onto the other x. (This is one of many possible solutions.)

Stuck

The player has two important limitations, though: They can only push boxes (no pulling) and they can only push one box at a time. It's therefore possible to get "stuck":

...x. ..... x.o.B ....A .....

Here the player can't push A upward or B downward because the other box is in the way. They can't push either to the right because they're up against the "wall" (the boundary of the level). And they can't pull at all. They're stuck.

The challenge

For this code-golf challenge we'll look at a simplified version of the game with no targets. There are only boxes and a question to be answered: Could any of these boxes be moved?

Input

The input will be a rectangular matrix of arbitrary size with some elements representing boxes (say, 1s) and others representing empty spaces (0s), e.g.:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0

or

0 0 0 1 0 0 0 0 0

In practice, the input could be an array of arrays of integers or booleans, a string of 1s and 0s on multiple lines, or any other reasonable representation.

The input will always have at least one box (1) and at least one empty space (0).

Output

The output should be a boolean, or a designated "yes" value or "no" value, indicating whether, if a player was dropped somewhere in the level, they would be able to move any box. (By "dropped somewhere" we mean any empty space, even if in a real game of Sokoban it would not be possible for the player to arrive at that spot.)

Rules

Default I/O rules and standard rules apply. Standard loopholes are forbidden.
This is code-golf; shortest solution in bytes wins.

Test cases

Input: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 Output: false

Input: 0 0 0 1 0 0 0 0 0 Output: true

Input: 1 0 0 0 0 0 0 0 1 Output: false

Input: 1 1 1 1 1 0 1 0 1 1 1 1 Output: true

Input: 1 1 1 1 1 0 1 1 1 1 1 1 Output: false

Input: 1 0 Output: false

Input: 0 1 0 1 Output: true

Input: 0 1 1 0 Output: false

Dropped somewhere means 'there exist an empty spot somewhere where the player can be dropped'? Note that there exist configurations where the player may or may not be able to move a box depending on where they start. — quarague
– quarague, Commented Aug 29, 2024 at 9:38
Maybe another good test case would be to put a 2x2 block of 1's in the middle of at least a 4x4 grid. Or to make it a bit more complicated, something like 0 0 0 0 0 / 0 1 1 0 0 / 0 1 1 1 0 / 0 0 1 1 0 / 0 0 0 0 0 — Daniel Schepler
– Daniel Schepler, Commented Aug 29, 2024 at 17:01
Can the input use any two consistent values, or must they be 0/1? — aeh5040
– aeh5040, Commented Aug 29, 2024 at 17:13

att · Accepted Answer · 2024-08-28 19:19:25Z

Wolfram Language (Mathematica), 28 bytes

FreeQ[#|#,{___,,1,,___}]&

Try it online!

Input an array with 1 for boxes and Null for empty spaces. Returns True if all boxes are stuck, and False otherwise.  is \[Transpose].

Khuldraeseth na'Barya · Accepted Answer · 2024-08-28 19:55:37Z

Stax, 9 bytes

üo∟Ö╘└└⌂o

Run and debug it at staxlang.xyz! ^{with printable 0/1 output}

Takes input as a list of rows, each cell represented as integer 1 for empty and 2 for box. Output is falsy for stuck and truthy for not stuck.

I might be able to get away with â╧óΩ═àN♣ for 8 bytes, replacing the unpacked |I with just I. That would produce -1 for stuck and >=0 for not stuck, not quite as much a designated "yes" value or "no" value as falsy/truthy.

Unpacked (10 bytes)

cM+J11JE|I cM+ concat with transposed copy J join on 0 11JE literal [1,2,1] |I all indices of subarray

shape warrior t · Accepted Answer · 2024-08-28 23:51:38Z

Python, 95 81 bytes

lambda d:any(x>d[x,y]>d[x-1,y]<d[x-2,y]or y>d[x,y]>d[x,y-1]<d[x,y-2]for(x,y)in d)

Attempt This Online!

Takes a dict, with keys being (x, y) coordinates and values being either 0 for box or 1 for empty space. Returns false for stuck and true for non-stuck. -14 bytes after switching from (x, y) being the center square to (x, y) being the bottom right square, taking inspiration from Arnauld's JavaScript answer where (x, y) is the top left square.

Explanation: as was stated in the sandbox, this challenge boils down to finding a horizontal or vertical instance of the pattern [space] [box] [space] (one of the spaces gets filled in by the player; the box gets pushed into the other space). The code inspects every square to see if it's either the rightmost square of a horizontal (1, 0, 1) or the bottom square of a vertical (1, 0, 1). We can write (c, b, a) == (1, 0, 1) as c > b and b < a -- or (ab)using Python's chained comparisons, c > b < a.

There's a subtle, but neat thing going on with the short circuiting in the chained comparisons here: the x> and y> are there to prevent out-of-bounds indexing. If x = 0, then x>d[x,y] cannot be true, so d[x-1,y] and d[x-2,y] are never evaluated. If x = 1, then x>d[x,y]>d[x-1,y] cannot be true, so d[x-2,y] is never evaluated. (Recall that d[a,b] is always either 0 or 1.) The same logic applies to the other chain of comparisons.

Jonathan Allan · Accepted Answer · 2024-08-29 00:04:55Z

Jelly, 7 bytes

;ZK“]»ẇ

A monadic Link that accepts a list of lists of characters:

A : space
B : box

and yields an integer:

\$1\$ : possible
\$0\$ : impossible

Try it online! Or see the test-suite.

How?

;ZK“]»ẇ - Link: list of lists of characters, Rows Z - transpose {Rows} -> Columns ; - {Rows} concatenate {Columns} K - join {that} with space characters “]» - compressed string = "ABA" ẇ - is {"ABA"} a sublist of {the space separated rows & columns}?

Also \$7\$ bytes accepting a list of lists of integers where \$1\$ are spaces and \$0\$ are boxes:

;ZK5B¤ẇ ¤ - nilad followed by link(s) as a nilad: 5 - five B - cast to binary -> [1,0,1]

Try it online!

Arnauld · Accepted Answer · 2024-08-29 15:26:05Z

5

JavaScript (ES11), 73 bytes

-2 thanks to shape warrior t

Expects a binary matrix (1 for empty, 0 for filled) and returns a Boolean value.

m=>m.some((r,y)=>r.some((v,x)=>v&&r[x+1]<r[x+2]|m[y+1]?.[x]<m[y+2]?.[x]))

Attempt This Online!

edited Aug 29, 2024 at 15:26

answered Aug 28, 2024 at 20:58

Arnauld

206k21 gold badges187 silver badges670 bronze badges

1

\$\begingroup\$ -2 bytes by replacing both instances of !a&b with a<b (which returns false if either operand is undefined instead of treating undefined as 0, but this doesn't affect correctness). \$\endgroup\$

shape warrior t
– shape warrior t

2024-08-29 13:40:24 +00:00
Commented Aug 29, 2024 at 13:40

Add a comment |

alephalpha · Accepted Answer · 2024-08-29 01:40:44Z

Nekomata + `-e`, 7 bytes

Ť?~q5Ƃ=

Attempt This Online!

Take input as a list of lists with 0 for boxes and 1 for empty spaces.

Ť?~q5Ƃ= Ť? Optionally transpose the input ~ Take any row q Take any contiguous subsequence 5Ƃ= Check if it is equal to [1,0,1]

-e checks if there is a solution.

Kevin Cruijssen · Accepted Answer · 2024-08-30 07:50:55Z

05AB1E (legacy), 6 bytes

ø«»тÁå

Input as a list of strings without delimiter, using 1/0 like in the challenge description.

Try it online or verify all test cases.

Explanation:

ø # Zip/transpose the (implicit) input-list of strings, swapping rows/columns « # Merge it to the (implicit) input-list » # Join this list of strings by newlines т # Push 100 Á # Rotate it once towards the right: "010" å # Check if the multiline string contains "010" as substring # (after which the result is output implicitly)

Uses the legacy version of 05AB1E, since ø works on a list of strings, whereas the new 05AB1E version would require a matrix (in the new version of 05AB1E, taking a matrix of bits as input, this would have been +1 byte: ø«J»тÁå).

akamayu · Accepted Answer · 2024-08-30 01:43:11Z

K (ngn/k), 19 bytes

It takes input as array of characters, and checks if every row and column stays the same when splitted with 010. It outputs 0 for yes instance and 1 for no instance.

{i~,/"010"\'i:x,+x}

Try it online!

Neil · Accepted Answer · 2024-08-28 22:54:02Z

Charcoal, 20 bytes

ＷＳ⊞υι⊙⁺υＥθ⭆υ§λκ№ι010

Try it online! Link is to verbose version of code. Takes input as a string of 0s and 1s with a newline after each row and outputs a Charcoal boolean, i.e. - if a box can be moved, nothing if not. Explanation:

ＷＳ⊞υι

Input the level.

⊙⁺υＥθ⭆υ§λκ№ι010

Concatenate it to its transpose and check any of the rows for the substring 010.

(My experimental transpose branch of Charcoal could perform the transpose operation in five fewer bytes.)

l4m2 · Accepted Answer · 2024-08-29 01:21:28Z

2

JavaScript (Node.js), 52 bytes

x=>x.match(`010|0[^]{${n=x.indexOf` `}}1[^]{${n}}0`)

Try it online!

Regex-based

answered Aug 29, 2024 at 1:21

l4m2

32.5k2 gold badges26 silver badges116 bronze badges

\$\begingroup\$ I didn’t know about [^]. Nice trick. \$\endgroup\$

Jordan
– Jordan

2024-08-29 01:31:48 +00:00
Commented Aug 29, 2024 at 1:31

Add a comment |

akamayu · Accepted Answer · 2024-08-29 02:58:59Z

APL(Dyalog Unicode), 15 bytes ^SBCS

A 3-train that checks if 0 1 0 is a substring of any row or column.

⊢∨⍥(1∊0 1 0∘⍷)⍉

Try it on APLgolf!

Albert.Lang · Accepted Answer · 2024-08-29 06:47:24Z

Python, 53 55 bytes

Thanks @att for finding a bug (+2).

lambda d:"010"in((n:=d.find("\n"))*(d+n*"\n"))[::n+1]+d

Attempt This Online!

Expects a single string consisting of newline-terminated lines of 0s and 1s.

Python, 65 62 bytes

Thanks @att for -3.

lambda d:any((0,1,0)in zip(a,a[1:],a[2:])for a in[*zip(*d)]+d)

Attempt This Online!

Expects a list-of-lists of integers.

Any similarities of test code with that of shape warrior t's are mere coincidence =-P

How?

Essentially an exercise in performing the transpose.

1st is broken on e.g. tc4 transposed since [] has higher precedence than *. -3 on the second — att
– att, Commented Aug 29, 2024 at 3:07

138 Aspen · Accepted Answer · 2024-08-29 16:19:47Z

Scala 3, 129 101 bytes

Saved 28 bytes thanks to @shape warrior t

Golfed version. Attempt This Online!

g=>g.keys.exists{case(x,y)=>x>1&&g((x,y))*g((x-2,y))>g((x-1,y))||y>1&&g((x,y))*g((x,y-2))>g((x,y-1))}

Ungolfed version. Attempt This Online!

object Main { def checkPattern(grid: Map[(Int, Int), Int]): Boolean = { for ((x, y) <- grid.keys) { if (x > 1 && grid((x, y)) > grid((x - 1, y)) && grid((x - 1, y)) < grid((x - 2, y))) { return true } if (y > 1 && grid((x, y)) > grid((x, y - 1)) && grid((x, y - 1)) < grid((x, y - 2))) { return true } } false } def convert(testcase: String): Map[(Int, Int), Int] = { val rows = testcase.stripMargin.trim.split("\n") (for { (row, y) <- rows.zipWithIndex if row.trim.nonEmpty (char, x) <- row.trim.split("\\s+").zipWithIndex } yield (x, y) -> (1 - char.toInt)).toMap } def main(args: Array[String]): Unit = { val testcases = List( """ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 """, """ 0 0 0 1 0 0 0 0 0 """, """ 1 0 0 0 0 0 0 0 1 """, """ 1 1 1 1 1 0 1 0 1 1 1 1 """, """ 1 1 1 1 1 0 1 1 1 1 1 1 """, "1 0", "0 1 0 1", "0 1 1 0" ) for (testcase <- testcases) { println(s"Input:\n ${testcase.trim}\n\nOutput: ${checkPattern(convert(testcase))}\n") } } }

Comparing against (1,0,1) is at least 1 byte shorter than doing a chained comparison, and you don't need the parentheses around && since it binds more tightly than ||. — shape warrior t
– shape warrior t, Commented Aug 29, 2024 at 12:38
...Actually, in the absence of chained comparisons, the shortest way to test (a, b, c) = (1, 0, 1) (with a, b, c in {0, 1}) in most languages should be a*c>b. To test (a, b, c) = (0, 1, 0), a+c<b. — shape warrior t
– shape warrior t, Commented Aug 29, 2024 at 12:59

bleep · Accepted Answer · 2024-08-30 05:31:34Z

GNU sed, 53 bytes

s/^|\n/f/g :a /010|f0[01]*f1[01]*f0/ct s/f./f/g ta

Online Editor. Run using gsed -zEf <program>. The program itself is 51 bytes; adding 2 bytes for options zE. Reads input of form

000 111 000

Outputs t if a move exists, f if we are stuck.

Explanation

-z option reads the entire input file into pattern space
s/^|\n/f/g reshapes input to format f000f111f000
/010|f0[01]*f1[01]*f0/ tests if any row or first column contains sequence 010
- On match, ct replaces pattern with t. Following substitution then fails and program exits
- On no match, s/f./f/g removes the first column and we try the match again. When no data remains, this substitution then removes fs until one is left, then fails allowing the program to exit.

nyxbird · Accepted Answer · 2024-08-28 21:57:10Z

Uiua, 23 bytes

¬≍×⍉∩(>1×/+◫¯3⊂⊂,,1)⍉..

Try it!

¬≍×⍉∩(>1×/+◫¯3⊂⊂,,1)⍉.. ∩( )⍉. # for both the array and its transposition: ⊂⊂,,1 # join a row of 1s above and below it /+◫¯3 # sum three windows of it >1× # and find the cells that are boxes have sums >1 ⍉ # de-transpose the transposition × # find the cells that are stuck on both ¬≍ # and check if they don' match the original array

Or 12 bytes if you swap 1s and 0s in input and start with bits5 instead of mod2ran3 — Tbw
– Tbw, Commented Aug 30, 2024 at 12:36

Neil · Accepted Answer · 2024-08-28 22:49:01Z

Retina 0.8.2, 57 bytes

1`010|(?<=(.)*)0.*¶(?<2-1>.)*(?(1)^)1.*¶(?<-2>.)*(?(2)^)0

Try it online! Takes input as a string of 0s and 1s with newlines between each row. Explanation:

1`

Only bother checking for one match.

010|

Search for the string 010 horizontally, or...

(?<=(.)*)0.*¶(?<2-1>.)*(?(1)^)1.*¶(?<-2>.)*(?(2)^)0

... search for the string 010 vertically.

G B · Accepted Answer · 2024-08-29 07:48:27Z

1

Ruby, 41 bytes

->s{(s+s.transpose).any?{|l|/010/=~l*''}}

Try it online!

answered Aug 29, 2024 at 7:48

G B

23.4k1 gold badge24 silver badges55 bronze badges

Add a comment |

doubleunary · Accepted Answer · 2024-08-30 09:58:55Z

Google Sheets, 101 bytes

=let(m,A1:F6,f,lambda(a,join(,index(if(len(a),a,"_")))),regexmatch(f(torow(m))&f(tocol(m,,1)),"010"))

Put the matrix in cells A1:E5 and the formula in cell A7.

screenshot

Stack Exchange Network

Stuck on Sokoban

Stuck

The challenge

Input

Output

Rules

Test cases

18 Answers 18

Wolfram Language (Mathematica), 28 bytes

Stax, 9 bytes

Unpacked (10 bytes)

Python, 95 81 bytes

Jelly, 7 bytes

How?

JavaScript (ES11), 73 bytes

Nekomata + `-e`, 7 bytes

05AB1E (legacy), 6 bytes

K (ngn/k), 19 bytes

Charcoal, 20 bytes

JavaScript (Node.js), 52 bytes

APL(Dyalog Unicode), 15 bytes ^SBCS

Python, 53 55 bytes

Thanks @att for finding a bug (+2).

Python, 65 62 bytes

Thanks @att for -3.

How?

Scala 3, 129 101 bytes

GNU sed, 53 bytes

Explanation

Uiua, 23 bytes

Retina 0.8.2, 57 bytes

Ruby, 41 bytes

Google Sheets, 101 bytes

Hot Network Questions

Stuck on Sokoban

Stuck

The challenge

Input

Output

Rules

Test cases

18 Answers 18

Wolfram Language (Mathematica), 28 bytes

Stax, 9 bytes

Unpacked (10 bytes)

Python, 95 81 bytes

Jelly, 7 bytes

How?

JavaScript (ES11), 73 bytes

Nekomata + -e, 7 bytes

05AB1E (legacy), 6 bytes

K (ngn/k), 19 bytes

Charcoal, 20 bytes

JavaScript (Node.js), 52 bytes

APL(Dyalog Unicode), 15 bytes SBCS

Python, 53 55 bytes

Thanks @att for finding a bug (+2).

Python, 65 62 bytes

Thanks @att for -3.

How?

Scala 3, 129 101 bytes

GNU sed, 53 bytes

Explanation

Uiua, 23 bytes

Retina 0.8.2, 57 bytes

Ruby, 41 bytes

Google Sheets, 101 bytes

Related

Hot Network Questions

Nekomata + `-e`, 7 bytes

APL(Dyalog Unicode), 15 bytes ^SBCS