Puzzle and PC – HackerRank Solution

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

Task

Mom has to go to work and she doesn’t want little Johnny to get bored. So she gives him a simple puzzle to solve. She also tells him that he can play a PC game only if he solves this problem. Johnny loves PC games and wants to solve this puzzle quickly. So he asks you for help.

You are given a square NxN board divided into single cells, where N is always a power of 2. You are also given an infinite number of L-shaped trominoes:

Note that each tromino can covers three cells.

The board has one special cell S on which you are not allowed to place any tromino. Your task is to cover the whole board with trominoes in such a way that any two trominoes don’t overlap, and every cell (except cell S) is covered by some tromino.

Indexing starts from 1, and top-left cell is indexed (1, 1).

Input

In the first line, there is an integer M. N = 2^M denotes the size of the board.
In the second line, there are two integers, r c, denoting the row and the column of cell S.

Output

For every tromino placed, print one line containing 6 space separated numbers, denoting the coordinates (in row major form) of 3 cells covered by this block.

Constraints

• 1 <= M <= 9
• 1 <= r, c <= 2^M

Note

• You are also allowed to rotate the trominoes.
• There may be multiple solution for a case. All valid solutions will be considered correct.

Sample Input #00

1
2 2

Sample Output #00

1 1 1 2 2 1

Sample Input #01

2
1 1

Sample Output #01

2 3 3 2 3 3
1 2 2 1 2 2
1 3 1 4 2 4
3 1 4 1 4 2
3 4 4 3 4 4

Explanation #00

Sample Case #00: Since you are not allowed to cover bottom-right cell, you will cover points (1,1), (1,2) & (2,1) with a single tromino.

    1   2
1 | 1 | 1 |
2 | 1 | x |

Sample Case #01: Since N = 2² = 4, board is of size 4x4 and you are not allowed cover top-left cell. You will need 5 trominoes to cover whole board, except cell (1, 1).

1. 2 3 3 2 3 3: This tromino will cover points (2, 3), (3, 2), (3, 3).
2. 1 2 2 1 2 2: This tromino will cover points (1, 2), (2, 1), (2, 2).
3. 1 3 1 4 2 4: This tromino will cover points (1, 3), (1, 4), (2, 4).
4. 3 1 4 1 4 2: This tromino will cover points (3, 1), (4, 1), (4, 2).
5. 3 4 4 3 4 4: This tromino will cover ponits (3, 4), (4, 3), (4, 4).

    1   2   3   4
1 | x | 2 | 3 | 3 |
2 | 2 | 2 | 1 | 3 |
3 | 4 | 1 | 1 | 5 |
4 | 4 | 4 | 5 | 5 |

Note that there can be multiple configurations to this input, and all will be considered correct

Solution – Puzzle and PC – HackerRank Solution

Scala

import java.util.Scanner

object Solution {

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

    val m = sc.nextInt
    val r = sc.nextInt - 1
    val c = sc.nextInt - 1

    sc.close()

    val n = BigInt(2).pow(m).toInt
    println(solve(n, Coord(r, c)).mkString("\n"))
  }

  def solve(n: Int, empty: Coord): List[Trimino] = {
    def inner(n: Int, empty: Coord, origin: Coord = Coord(0, 0), acc: List[Trimino] = Nil): List[Trimino] = if (n == 2) {
      ((empty match {
        case Coord(0, 0) => Trimino(Coord(0, 1), Coord(1, 0), Coord(1, 1))
        case Coord(0, 1) => Trimino(Coord(0, 0), Coord(1, 0), Coord(1, 1))
        case Coord(1, 0) => Trimino(Coord(0, 1), Coord(0, 0), Coord(1, 1))
        case Coord(1, 1) => Trimino(Coord(0, 1), Coord(1, 0), Coord(0, 0))
        case _ => throw new Exception("Impossible")
      }) + origin) :: acc
    } else {
      val nextN = n / 2
      val inLeft = empty.c < nextN
      val inTop = empty.r < nextN

      val topLeftAcc = inner(nextN, if (inLeft && inTop) empty else Coord(nextN - 1, nextN - 1), origin, acc)

      val localTopRightOrigin = Coord(0, nextN)
      val topRightOrigin = origin + localTopRightOrigin
      val topRightAcc = inner(nextN, if (!inLeft && inTop) empty - localTopRightOrigin else Coord(nextN - 1, 0), topRightOrigin, topLeftAcc)

      val localBottomLeftOrigin = Coord(nextN, 0)
      val bottomLeftOrigin = origin + localBottomLeftOrigin
      val bottomLeftAcc = inner(nextN, if (inLeft && !inTop) empty - localBottomLeftOrigin else Coord(0, nextN - 1), bottomLeftOrigin, topRightAcc)

      val localBottomRightOrigin = Coord(nextN, nextN)
      val bottomRightOrigin = origin + localBottomRightOrigin
      val bottomRightAcc = inner(nextN, if (!inLeft && !inTop) empty - localBottomRightOrigin else Coord(0, 0), bottomRightOrigin, bottomLeftAcc)

      val trimino = ((inLeft, inTop) match {
        case (true, true) => Trimino(Coord(nextN - 1, nextN), Coord(nextN, nextN - 1), Coord(nextN, nextN))
        case (false, true) => Trimino(Coord(nextN - 1, nextN - 1), Coord(nextN, nextN - 1), Coord(nextN, nextN))
        case (true, false) => Trimino(Coord(nextN - 1, nextN), Coord(nextN - 1, nextN - 1), Coord(nextN, nextN))
        case (false, false) => Trimino(Coord(nextN - 1, nextN), Coord(nextN, nextN - 1), Coord(nextN - 1, nextN - 1))
      }) + origin

      trimino :: bottomRightAcc
    }

    inner(n, empty)
  }

  case class Coord(r: Int, c: Int) {
    def +(that: Coord): Coord = Coord(r + that.r, c + that.c)

    def -(that: Coord): Coord = Coord(r - that.r, c - that.c)

    override def toString: String = s"${r + 1} ${c + 1}"
  }

  case class Trimino(coord0: Coord, coord1: Coord, coord2: Coord) {
    def +(coord: Coord): Trimino = Trimino(coord0 + coord, coord1 + coord, coord2 + coord)

    override def toString: String = s"$coord0 $coord1 $coord2"
  }

}

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