# Game of Kyles – HackerRank Solution

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

Bowling refers to a sport in which a player rolls or throws a bowling ball towards a group of pins. The target is usually to knock down the pins at the end of a lane.

Rules have been slightly modified for this problem. Now there areÂ NÂ pins and all the pins are arranged in a horizontal line, instead of a triangular formation. Two players have to play this game, and they alternate their turns. Whoever knocks down the last pin(s) will be declared the winner.

You and your friends are playing this game. Both of you have become proficient at the sport and can knock down any single pin, or any two adjacent pins at one throw of a bowling ball. You have already played some of the shots. Suddenly you realize that it is possible to find whether this game can be won or not. And luckily it’s your turn right now.

A configuration is represented by a string consisting of latin lettersÂ `X`Â andÂ `I`, whereÂ `I`Â represents a position containing a pin, andÂ `X`Â represents a position where a pin has been knocked down. An example of such a configuration is shown in the image below. HereÂ N = 13, andÂ 2ndÂ pin has been knocked down already.

It’s representation will be `IXIIIIIIIIIII`.

You are given the current configuration of the pins. If both of you play optimally, find whether you can win this game or not.

## Input Format

The first line will contain an integer,Â T, which represents the number of test cases. ThenÂ TÂ test cases follows.
For each test case, the first line contains an integerÂ N, which represents the number of pins before the start of the game. And the second line contains a string ofÂ NÂ letters, where each letter is eitherÂ `I`Â orÂ `X`.

## Constraints

• 1 <= T <= 1000
• 1 <= N <= 300
• Each letter of string (representing configuration) is eitherÂ `I`Â orÂ `X`.
• There will be at least oneÂ `I`Â in the string.

Note:
– A player has to knock down at least one pin in his chance.
– Both players play optimally.

## Output Format

For each test case, printÂ `WIN`Â if you can win this game, otherwise printÂ `LOSE`.

Sample Input 0

``````4
4
IXXI
4
XIIX
5
IIXII
5
IIIII``````

Sample Output 0

``````LOSE
WIN
LOSE
WIN``````

Explanation 0

Test Case #00:Â As theÂ 2Â pins are not adjacent, they can’t be knocked down in a single chance. Therefore you can only knock down one of the two pins. Then in next chance, your friend will knock down the last pin.
Test Case #01:Â You can knock down both the adjacent pins in your first turn.
Test Case #02:Â You can knock one or two pins from either side. Your friend can just copy your move on the other side and will be able to finish the game.
Test Case #03:Â You can knock middle pin, thus resulting into configurationÂ `IIXII`Â for your friend. Now this configuration is the same as the previous test case. The difference is that now it is your friend’s chance and you can copy his shot on the other side.

## Solution – Game of Kyles – HackerRank Solution

Scala

```import java.util.Scanner

import scala.collection.mutable

object Solution {
private val data = mutable.Map[Int, Int]()

def mex(states: Set[Int]): Int = LazyList.from(0).find(i => !states.contains(i)).get

def number(v: Int): Int = data.getOrElseUpdate(v, {
mex((0 until v).map(i => number(i) ^ number(v - i - 1)).toSet ++
(0 to v - 2).map(i => number(i) ^ number(v - i - 2)).toSet)
})

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

val t = sc.nextInt
(0 until t).foreach(_ => {
sc.nextInt
sc.nextLine
val s = sc.nextLine

val pins = {
case class Acc(pins: List[Int] = List(0))
s.foldLeft(Acc())((acc, c) => {
if (c == 'I') {
} else {
Acc(0 :: acc.pins)
}
}).pins
.filter(_ != 0)
}

println(if (pins.map(number).reduce(_ ^ _) == 0) "LOSE" else "WIN")
})
}
}
```

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