[Hackerrank] Manasa and Prime Game

Problem Description (Credited to Hackerrank)
Manasa loves the NIM Game, but having played the same game so many times, she gets bored one day. So she wants to change the rules of the game. As she loves prime numbers, she makes a new rule: any player can remove only prime number of balls from a bucket. But there are infinite prime numbers. So to keep the game simple, a player can remove only x number of balls from a bucket, where x belongs to the set S.




 S={2,3,5,7,11,13}

Now whole game can be described as follows:
Given N number of buckets and kth bucket having Ak number of balls, a player can choose a bucket and remove x number of balls from that bucket where x belongs to S. Manasa plays the first move against Sandy. Who will win if both of them play optimally?

Input Format 
The first line contains an integer T i.e. the number of test cases.
First line of each test case will contain an integer N i.e. number of buckets.
Next lines will contain N integers.

Output Format 
Print the name of the winner - "Manasa" or "Sandy".

Constraints
1≤T≤10 
1≤N≤104 
1≤Ak≤1018

Sample Input

2
2
10 10
3
2 2 3

Sample Output

Sandy
Manasa

Solution

This is another example of problems in game theory. If Permutation Game is solved using Minimax algorithm, this problem requires some knowledge about Nim games, and Grundy number (or Nimber).
You can read more about Nim Games and Grundy number using reference links at the end of the post, but I will describe it shortly so that you get how to do (even without understanding Nim Games and Grundy numbers!!!).

In this type of problem, one game is a combination of multiple sub-games. At each time, a player chooses a sub-game to play. Who is the last person to make a move is the winner. And to decide who is the winner, we need to calculate Grundy numbers for all the sub-games, and take the XOR value of them. If this value > 0, then the first player is the winner. Otherwise, the second player is the winner !!! Sound like magic? Again, I suggest you read through everything I put in reference links to understand the theory behind.

So what is the sub-games here? Assuming that the 2 players play only with a bucket. So this is a sub-game.

Now, how to calculate Grundy number for a sub-game? Call C is the current state of the sub-game (In this problem, C is the number of balls in the bucket). Call T1, T2, ..., Tn are all possible states can be reached from C within a single move. And call G is a function on these states. G is defined as followed:

G map a state to non-negative integer.
G(losing state) = 0
G(C) = smallest number that not in the set {G(T1), G(T2), ..., G(Tn)} where T1, T2, ..., Tn are all possible states reached from current state C by a single move.

How to apply for this problem?
First, we need to define losing state. Losing state is the state a player cannot remove balls. In this problem, losing states are 0 and 1. Therefore, we have G(0) = G(1) = 0.

So we have: G(2) = 1. (Why?), G(3) = 1 (Why?), G(4) = 2 (Why?), and so on.

And the problem ask us to calculate Grundy number for 1<=Ak <= 10^18!
The Grundy number G(Ak) can be calculated using Dynamic Programming if Ak is small. But 10^18 is way too big. We have to find another way.

We see that, from the current state C, we can only move to maximum 6 other states. This means that the Grundy numbers may be at most 6 (Why?). That means there is a high chance that they are periodic! Yes, they are periodic.

Hence, I wrote a quick Python script to see if it is periodic.

def run():
  n = 100
  dp = [0]*(n+1)
  a = [2,3,5,7,11,13]
  b = [0] * (23)
  for i in range(2, n+1):
    for k in a:
      if i >= k:
        b[dp[i-k]]= 1
    for k in range(len(b)):
      if b[k] == 0: 
        dp[i] = k
        break
    for k in range(len(b)): b[k] = 0
  print dp
if __name__ == "__main__":
  run()

And the result is

[0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1
, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0, 1, 1, 2,
2, 3, 3, 4, 0, 0]

So the period will be values = [0, 0, 1, 1, 2, 2, 3, 3, 4]. Simple, isn't it?
And G(Ak) = values[ Ak % 9].
Now, we just need to XOR up all Grundy numbers G(A1) ^ G(A2) ^ ... ^ G(An).

Below is the code in java for your reference.
Before seeing the solution, try yourself with the following test case:

5
10
84 87 78 16 94 36 87 93 50 22
10
63 28 91 60 64 27 41 27 73 37
10
12 69 68 30 83 31 63 24 68 36
10
30 3 23 59 70 68 94 57 12 43
10
30 74 22 20 85 38 99 25 16 71

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        int t = ni();
        for(int i=0; i<t; i++){
            System.out.println(solve());
        }
    }
    
    public static int[] values = new int[]{0, 0, 1, 1, 2, 2, 3, 3, 4};
    public static String solve(){
        int n = ni();
        long ak;
        long nimber = 0; //or grundy number
        for(int i=0; i<n; i++){
            ak = nl();
            nimber ^= values[(int) (ak % values.length)];
        }
        if(nimber > 0) return "Manasa";
        return "Sandy";
    }
    
    public static Scanner sc = new Scanner(System.in);
    public static int ni(){
        return sc.nextInt();
    }
    public static long nl(){
        return sc.nextLong();
    }
}

Reference links:
Combinatorial Games - PDF (Standford course)
Sprague-Grundy Theorem (Wiki)
Grundy Numbers (Nice blog post)

[Hackerrank] Permutation Game

Problem Description (Credited to Hackerrank)

Alice and Bob play the following game:

1. They choose a permutation of the first N numbers to begin with.
2. They play alternately and Alice plays first.
3. In a turn, they can remove any one remaining number from the permutation.
4. The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.

Assuming both play optimally, who wins the game?
Input Format: 
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by a permutation of the integers 1..N on the second line.

Output Format: 

Output T lines, one for each test case, containing "Alice" if Alice wins the game and "Bob" otherwise.

Constraints:

1<=T<=100
2<=N<=15
The permutation will not be an increasing sequence initially.

Solution

Hackerrank is a very good place for training our programming ability. However, one thing I realize is that its discussion is not really helpful, and many problems lack editorials. So I decided to start writing analysis on the website's problems with the hope that it can help someone on their joyful journey of studying algorithms.

This problem is categorized as a game theory problem. Most of the times, game theory problems can be solved either using Minimax algorithm or with Nim game knowledge ( with Grundy numbers which I'll cover in a future post), so as long as we equip ourselves with these kinds of knowledge, game theory is not hard at all.

For this problem, we can solve it by Minimax algorithm (or shortly Minimax).

To be simple, Minimax can be described as: My current state is S, and I need to calculate the score f(S). Consider all the possible states T1, T2, ..., Tn that I can make a move from S, then I have:
f(S) = - min ( f(T1), f(T2), ..., f(Tn))
Note on the minus sign. Why it is minus? The explanation is that we are playing 2-play games. So next turn is my opponent turn, isn't it? Therefore, if he wins in the next state, that means I lose in the current state.

And often, Minimax can be solved simply by recursion with memoization!!! So keep in mind, M&M (Minimax & Memoization) is the normal way to solve this kind of problems.

Go back to our problem. How can we define a state in this game? Simply, the state is all the available numbers! However, in order to easily using memoization, we need a better way to represent states here. You got the idea right? (^_^) Let's use a polynomial to map an array of numbers to a number, then we can use hash table for memoization - this technique we can reuse a lot and alot!

Since the constraint here is N <= 15, so we can use 16 as base (since 16 ^ 15 = 2^60 is in range of a long integer) . Why 16, not N+1? Because using 16 enables fast multiplication by bit manipulation.
So for example, given array: [1, 3, 2], its equivalent numbers is 1 * 16^2 + 3*16 + 2 = 306, and we can do bit manipulation by ((((1 << 4) + 3) << 4) + 2).

With the above analysis, I hope you get an idea to solve the problem. Below is the code for your reference.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int t = ni();
        for(int i=0; i<t; i++){
            int n = ni();
            Map<Long, Boolean> map = new HashMap<Long, Boolean>();
            int[] numbers = new int[n];
            for(int j=0; j<n; j++){
                numbers[j] = ni();
            }
            if(aliceWin(numbers, map)) System.out.println("Alice");
            else System.out.println("Bob");
        }
    }
    
    public static boolean aliceWin(int[] a, Map<Long, Boolean> map){
        long h = hashCode(a); int temp; 
        if(map.containsKey(h)) return true;
        
        for(int i=0; i<a.length; i++){
            if(a[i]>0){
                temp = a[i] ;
                a[i] = 0;
                if(isIncreasing(a)){
                    map.put(h, true);
                    a[i] = temp;
                    return true;
                }
                if(!aliceWin(a, map)) {
                    map.put(h, true);
                    a[i] = temp;
                    return true;
                }
                a[i] = temp;
            }
        }
        return false;
    }
    
    public static long hashCode(int[] a){
        long result = 0;
        for(int i=0; i<a.length; i++){
            result = (result << 4) + a[i];
        }
        return result;
    }
    public static boolean isIncreasing(int[] a){
        int last = 0;
        for(int i=0; i<a.length; i++){
            if (a[i] > 0){
                if(last > a[i]) return false;
                last = a[i];
            }
        }
        return true;
    }
    public static int ni(){
        return sc.nextInt();
    }
    
    public static void print(Object... args){        
        System.out.println(Arrays.deepToString(args));
    }
}