Klotski – HackerRank Solution

In this post, we will solve Klotski HackerRank Solution. This problem (Klotski) is a part of HackerRank Functional Programming series.

Task

Klotski is a classical puzzle. In this puzzle, you are given a rectangle box of a fixed size with some blocks inside of it. One of these blocks is special, we will call it the “target” block. To solve this puzzle, you will need to slide blocks within this box to move the target block to a specified place.

To slide a block, you must follow certain rules:

• Blocks can only be moved in four directions: up, down, left and right.
• Overlapping blocks are not allowed.
• Blocks can never be moved outside of the box.

Your task is to find one optimal solution for the Klotski puzzle. A solution consists of a sequence of moves that takes the puzzle from its initial state, to a solved state.
For a solution to be considered optimal, there should not be another sequence of moves whose length is less than the current solution.

Note that the definition of “one move” might be different from what you might expect. In the puzzle, you might choose one block and move it anywhere, as long as the above rules are followed. As long as you don’t change the block you are currently moving, the whole sequence of movements counts as only one move, regardless of how far that block has moved. Examples will be given in following sections.

Input Format

Two integers, m and n, are given in the first line, where m is the number of rows and n is the number of columns.
In the following m lines, each line contains n strings separated by spaces.
Each character in the string describes one cell of the Klotski puzzle.
A string consists only of ‘.’s (e.g. “.”, “…”), which stands for empty cells, while other strings encode blocks.
The next line contains one string, which indicates the target block.
The last line contains a coordinate that specifies the place where the target block should be moved to. This coordinate is the top-left corner where the target block should be placed.

For example, you might be given a puzzle like this:

3 4
A A C .
A B C .
B B . .
B
0 1

This Klotski puzzle consists of 3 blocks:

Note that the top-left corner means the topmost and leftmost coordinate of a block, which might be outside of the block. See block B for an example.

# Block "A", top-left corner is (0,0)

A A . .
A . . .
. . . .

# Block "B", top-left corner is (1,0)

. . . .
. B . .
B B . .

# Block "C", top-left corner is (0,2)

. . C .
. . C .
. . . .

To solve this puzzle, block B should be placed in the following place:

. . B .
. B B .
. . . .

Output Format

The first line is an integer k, indicating the number of moves in an optimal solution.
In the following k lines, you should output a sequence of moves indicating one possible optimal solution. Each line describes a move in the following format:

<block name> <from> <to>

which means to move the block <block name> whose top-left corner is <from> to a place where its top-left corner is <to>.

For example, with the example input above:

3 4
A A C .
A B C .
B B . .
B
0 1

One of the possible outputs is:

2
C (0,2) (1,3)
B (1,0) (0,1)

This means one optimal solution consists of 2 moves.
First we move block C from (0, 2) to (1, 3):

A A . .
A B . C
B B . C

And then we move block B from (1, 0) to (0, 1):

A A B .
A B B C
. . . C

Constraints

• 1 <= m, n <= 6
• Block size won’t exceed 3 x 3.
• All inputs are guaranteed to be solvable within 201 steps, i.e. 0 <= k <= 200.

Notes

• In the case where there are multiple solutions to the puzzle, you only need to print one of them.
• Test cases will not be overly difficult, being a little wise about states and your program should have enough time to work out this challenge.
• If you want to do a search, taking block shapes into account will save you some space.

Sample Input

3 4
A A C .
A B C .
B B . .
B
0 1

Sample Output

2
C (0,2) (1,3)
B (1,0) (0,1)

Solution – Klotski – HackerRank Solution

Scala

import java.util.Scanner

import scala.collection.mutable

object Solution {

  private val data = mutable.Map[State, Acc]()
  private val dirs = List(Coord(-1, 0), Coord(1, 0), Coord(0, -1), Coord(0, 1))

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val m = sc.nextInt
    val n = sc.nextInt
    sc.nextLine

    case class Cell(x: Int, y: Int, c: String)

    val field = (0 until m).flatMap(y => sc.nextLine.split(" ").zipWithIndex
      .map { case (s, x) => Cell(x, y, s) }
    )

    val targetChar = sc.nextLine

    val targetCoord = {
      val (targetY, targetX) = (sc.nextInt, sc.nextInt)
      Coord(targetX, targetY)
    }

    val tempList = field
      .filter(_.c.exists(_ != '.'))
      .groupBy(_.c)
      .toSeq
      .map { case (c, list) =>
        val leftX = list.map(_.x).min
        val topY = list.map(_.y).min

        val coords = list.map(cell => Coord(cell.x - leftX, cell.y - topY))

        def toId(coords: Seq[Coord]): Int = coords.map(coord => 1 << (3 * coord.y + coord.x)).sum

        (Coord(leftX, topY), Block(c, coords.toList, toId(coords)))
      }

    val tempBlocks = tempList.map(_._2).toIndexedSeq
    val symbols: mutable.Map[Coord, String] = mutable.Map[Coord, String]() ++ tempBlocks.indices.map(index => tempList(index)._1 -> tempBlocks(index).symbol)
    val blocks: Map[Int, Set[Coord]] = tempList.map(_._2).groupBy(_.id).map { case (id, list) => id -> list.head.coords.toSet }
    val initialCoord = tempList(tempBlocks.indexWhere(_.symbol == targetChar))._1
    val initialState = State(Coord(-1, -1), initialCoord,
      tempList.map { case (coord, block) => block.id -> coord }
        .groupBy(_._1)
        .map { case (id, list) => id -> list.map(_._2).toSet }
    )

    val answer = solve(blocks, initialState, initialCoord, targetCoord, n, m)

    print(answer.length)
    println(
      answer
        .map(
          mv => {
            val symbol = symbols(mv.prevCoord)
            symbols -= mv.prevCoord
            symbols += mv.nextCoord -> symbol
            s"\n$symbol (${mv.prevCoord.y},${mv.prevCoord.x}) (${mv.nextCoord.y},${mv.nextCoord.x})"
          })
        .mkString("")
    )
  }

  def solve(blocks: Map[Int, Set[Coord]], initialState: State, initialCoord: Coord, targetCoord: Coord, xSize: Int, ySize: Int): List[Movement] = {
    def worldCoord(coords: Set[Coord], topLeft: Coord): Set[Coord] = coords.map(coord => Coord(coord.x + topLeft.x, coord.y + topLeft.y))

    def isCorrect(id: Int, topLeft: Coord, field: Set[Coord]): Boolean =
      worldCoord(blocks(id), topLeft)
        .forall(coord => coord.x >= 0 && coord.x < xSize && coord.y >= 0 && coord.y < ySize && !field.contains(coord))

    data += initialState -> Acc(
      initialState.topLefts.flatMap { case (id, topLefts) => topLefts.flatMap(topLeft => worldCoord(blocks(id), topLeft)) }.toSet,
      Item(0, Nil))
    val queue = mutable.PriorityQueue[State](initialState)

    var bestMovements: List[Movement] = Nil
    var bestStep = Int.MaxValue

    while (queue.nonEmpty) {
      val state = queue.dequeue()

      val nextPairs = state.topLefts.flatMap { case (id, topLefts) => topLefts.flatMap(topLeft => {
        dirs.map(dir => {
          val nextTopLeft = Coord(topLeft.x + dir.x, topLeft.y + dir.y)
          val nextState = State(nextTopLeft,
            if (topLeft == state.currentCoord) nextTopLeft else state.currentCoord,
            state.topLefts + (id -> (state.topLefts(id) - topLeft + nextTopLeft))
          )

          val acc = data(state)
          val tempField = acc.field -- worldCoord(blocks(id), topLeft)
          val nextField = tempField ++ worldCoord(blocks(id), nextTopLeft)

          if (isCorrect(id, nextTopLeft, tempField)) {
            val isSame = topLeft == state.lastCoord
            val nextStep = if (isSame) acc.item.step else acc.item.step + 1
            val nextMovement = Movement(id, topLeft, nextTopLeft)
            val nextAcc = Acc(nextField,
              Item(nextStep,
                if (isSame) Movement(id, acc.item.movements.head.prevCoord, nextMovement.nextCoord) :: acc.item.movements.tail
                else nextMovement :: acc.item.movements
              )
            )

            nextState -> nextAcc
          }
        })
      })
      }
        .collect { case (nextState: State, nextAcc: Acc) => nextState -> nextAcc }

      nextPairs.foreach { case (nextState, nextAcc) =>
        val existingAccOpt = data.get(nextState)

        if (existingAccOpt.isEmpty || nextAcc.item.step < existingAccOpt.get.item.step) {
          if (nextAcc.item.step < bestStep) {
            if (nextState.currentCoord == targetCoord) {
              bestMovements = nextAcc.item.movements
              bestStep = nextAcc.item.step
            }

            data(nextState) = nextAcc
            queue += nextState
          }
        }
      }
    }

    bestMovements.reverse
  }

  case class Coord(x: Int, y: Int)

  case class Block(symbol: String, coords: List[Coord], id: Int) {
    def worldCoord(topLeft: Coord): List[Coord] = coords.map(coord => Coord(coord.x + topLeft.x, coord.y + topLeft.y))
  }

  case class State(lastCoord: Coord, currentCoord: Coord, topLefts: Map[Int, Set[Coord]]) extends Ordered[State] {
    lazy val _hashCode: Int = topLefts.hashCode()

    override def hashCode(): Int = 31 * lastCoord.hashCode() + _hashCode

    override def compare(that: State): Int = data(that).item.step.compareTo(data(this).item.step)
  }

  case class Movement(id: Int, prevCoord: Coord, nextCoord: Coord)

  case class Item(step: Int, movements: List[Movement])

  case class Acc(field: Set[Coord], item: Item)

}

Note: This problem (Klotski) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.