[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));
    }
}