Sliding Puzzle

You happen upon a puzzle box that unlocks... Something. You aren't quite sure what just yet. The puzzle is a 2 x 3 box, and there are 5 square sliding bricks labelled conveniently with 1 to 5. It looks something like this:

It can be represented as a 2 x 3 matrix containing numbers from 0 to 5, where 0 represents an empty space. For example, the pattern above can be represented by [[4, 1, 3], [2, 0, 5]].

The tiles are interlocked with each other, so you cannot take the tiles out. However, the tiles can move freely horizontally and vertically, so each turn, you can move a tile to an adjacent empty space. You have a feeling that when you move the tiles to the position [[1, 2, 3], [4, 5, 0]], the puzzle will be solved and unlock the "something". Like this:

You need to be quick about solving this puzzle, though, as you might attract the attention of someone who doesn't like you poking around in their dungeon. You wonder whether it is possible to solve this puzzle, and if so, how many steps you need to move in order to do so.

Input

  • init_pos: an integer matrix representing the initial position of the puzzle.

Output

The number of steps required to solve this puzzle, or -1 if the puzzle is impossible to solve.

Examples

Example 1:

Input:

init_pos = [[4, 1, 3], [2, 0, 5]]

Output: 5

Explanation:

Constraints

  • The input must be a 2 x 3 integer matrix containing exactly one of each from 0 to 5

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade