Bitter Chocolate – HackerRank Solution

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

Task

Shashank and Arpith are both fond of chocolate, where a chocolate bar can be represented as a 3xN block of bars. On a particular day the leftmost-lowest block has been mixed with a very bitter ingredient by a not-so-good Prashant. He then gave that chocolate to them and told about this.

Prashant asked them to play a game with it, where a move of game consists of eating a block of bar along with all the blocks of bar which lies on the right and above it. Player alternate moves, and the person who eats the leftmost-lowest (bitter) block of bar is declared loser.

Example:
Let the size of chocolate be 3×8. Block (1, 1) had been bittered. Player 1 starts the game, then they alternate moves.

Player 1: Choses a block at (2, 6) to eat.

    _ _ _ _ _ _ _ _
3  |_|_|_|_|_|_|_|_|
2  |_|_|_|_|_|x|_|_|
1  |$|_|_|_|_|_|_|_|
    1 2 3 4 5 6 7 8

Player 2: Choses a block at (3, 3) to eat.

    _ _ _ _ _
3  |_|_|x|_|_|
2  |_|_|_|_|_|_ _ _
1  |$|_|_|_|_|_|_|_|
    1 2 3 4 5 6 7 8

Player 1: Choses a block at (1, 2) to eat.

    _ _
3  |_|_|_ _ _
2  |_|_|_|_|_|_ _ _
1  |$|x|_|_|_|_|_|_|
    1 2 3 4 5 6 7 8

Player 2: Choses a block at (2, 1) to eat.

    _
3  |_|
2  |x|
1  |$|
    1

Player 1: Doesn’t have any option. So had to eat the bitter part of chocolate and be the loser.

    _
1  |$|
    1

Of course this is not an optimal game.

As player 1 realised that he is noob after playing some steps, he asked you to help him to find whether now there exists any chance for him to win. Player 2 is expert at this game.

Given number of bar blocks in row₁, row₂ and row₃ (row₁ ≥ row₂ ≥ row₃) and its player 1 turn, find that if from now on he plays optimally whether he can win the game or not.

Input Format

First line of input contains number of test cases T. Then follows T lines, each line containing three positive integers row₁, row₂ and row₃, number of blocks of bar in row 1, row 2 and row 3 respectively.

Output Format

For each input, tell whether player 1 can win if he play optimally or not. Print WIN if player 1 can win, otherwise print LOSE.

Constraints

• 1 ≤ row1 ≤ 25
• 25 ≥ row₁ ≥ row₂ ≥ row₃ ≥ 0
• Currently it’s player 1′ turn.
• 0 < T ≤ 100
• Both players play optimally.

Sample Input

2
1 1 1
2 2 1

Sample Output

WIN
LOSE

Explanation

Test Case #00: Player 1 can easily win this game.

Player 1: Eats block (2, 1).

    _
3  |_|
2  |x|
1  |$|
    1

Player 2: Does’nt have any option other than to eat block (1, 1) and lose, thus Player 1 WIN.

    _
1  |$|
    1

Test Case #01: Player 1 is doomed to lose this game for any of his move. Let us explain what happen if he eats block (1, 2).

Player 1: Eats block (1, 2)

    _
3  |_|_
2  |_|_|
1  |$|x|
    1 2

Player 2: Eats block (2, 1).

    _
3  |_|
2  |x|
1  |$|
    1

Player 1: Doesn’t have any option other than to eat block (1, 1) and LOSE.

    _
1  |$|
    1

Solution – Bitter Chocolate – HackerRank Solution

Scala

import java.util.Scanner

import scala.collection.mutable

object Solution {

  private val data = mutable.Map[State, Boolean]()

  def solve(state: State): Boolean = data.getOrElseUpdate(state, state == State(0, 0, 0) ||
    state.a > 0 && (0 until state.a).exists(x => !solve(eat(Coord(x, 0), state))) ||
    state.b > 0 && (0 until state.b).exists(x => !solve(eat(Coord(x, 1), state))) ||
    state.c > 0 && (0 until state.c).exists(x => !solve(eat(Coord(x, 2), state)))
  )

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

    val t = sc.nextInt
    println((0 until t).map(_ => State(sc.nextInt, sc.nextInt, sc.nextInt))
      .map(s => if (solve(s)) "WIN" else "LOSE").mkString("\n"))
  }

  private def eat(coord: Coord, state: State): State = coord.y match {
    case 2 => State(state.a, state.b, coord.x)
    case 1 => State(state.a, coord.x, math.min(state.c, coord.x))
    case _ => State(coord.x, math.min(state.b, coord.x), math.min(state.c, coord.x))
  }

  case class State(a: Int, b: Int, c: Int)

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

}

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