# 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.

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 = 2MÂ 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 <= 2M

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 = 22 = 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.