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*.Â

**Â denotes the size of the board.**

*N = 2*^{M}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^{2} = 4**, board is of sizeÂ

**4**Â and you are not allowed cover top-left cell. You will need 5 trominoes to cover whole board, except cell (1, 1).

*x*4`2 3 3 2 3 3`

: This tromino will cover points (2, 3), (3, 2), (3, 3).`1 2 2 1 2 2`

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

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

: This tromino will cover points (3, 1), (4, 1), (4, 2).`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.