Hackerrank: Xoring Ninja Solution in Ocaml

Problem Statement
https://www.hackerrank.com/challenges/xoring-ninja

Given a list containing N integers, calculate the XOR_SUM of all the non-empty subsets of the list and print the value of sum % (109 + 7).

XOR operation on a list (or a subset of the list) is defined as the XOR of all the elements present in it.
E.g. XOR of list containing elements {A,B,C} = ((A^B)^C), where ^ represents XOR.

E.g. XOR_SUM of list A having three elements {X1, X2, X3} can be given as follows.
All non-empty subsets will be {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

Input Format

An integer T, denoting the number of testcases. 2T lines follow.
Each testcase contains two lines, first line will contains an integer N followed by second line containing N integers separated by a single space.

Output Format

T lines, ith line containing the output of the ith testcase.

Constraints

1 <= T <= 5
1 <= N <= 105
0 <= A[i] <= 109

let large_number = 1000000007 ;;

let compute n k =
  if k = 0 then
    0
  else
    let result = ref 1 in
    for i = 1 to (n - 1) do
      result := (!result lsl 1) mod large_number
    done;
    !result
;;

let process arr length =
  let max_elem = ref (-1) in
  for i = 0 to (length - 1 ) do
    if (arr.(i) > !max_elem) then
      max_elem := arr.(i)
  done;
  let level = ref 0
  and result = ref 0 in
  while !max_elem > 0 do

    let count = ref 0 in
    for i = 0 to (length - 1) do
      count := !count + (1 land arr.(i));
      arr.(i) <- (arr.(i) lsr 1)
    done;
    (* Printf.printf "max_elem: %d, level: %d, result: %d, count: %d\n" !max_elem !level !result !count; *)
    let res = compute length !count in
    result := (!result + (res lsl !level) ) mod large_number;
    level := !level + 1 ;
    max_elem := !max_elem lsr 1 ;
  done;
  !result
;;


(* main *)

let num_case = read_int () ;;

for i = 1 to num_case do
  let n = read_int () in
  let line = read_line () in
  let lst_string = Str.split (Str.regexp " ") line in
  let lst_int = List.map int_of_string lst_string in
  let arr = Array.of_list lst_int in
  let result = process arr n in
  Printf.printf "%d\n" result
done ;;

Hackerrank: AND Product Solution in Ocaml

AND product

Problem Statement

You will be given two intergers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

Input Format

First line of the input contains T, the number of testcases to follow.
Each testcase in a newline contains A and B separated by a single space.

Constraints

1 <= T <= 200
0 <= A <= B <= 2^32

Output Format

Output one line per test case with the required bitwise AND

let read_line_int () =
  let line = read_line () in
  let lst = Str.split (Str.regexp " ") line in
  let lst_int = List.map int_of_string lst in
  let arr = Array.of_list lst_int in
  arr
;;


let number_of_bits n =
  let rec num_of_bits count n =
    match n with
    | 0 -> count
    | n -> num_of_bits (count + 1) (n lsr 1)
  in
    num_of_bits 0 n ;;


let rec process result a b =
  let n_bits_a = number_of_bits a
  and n_bits_b = number_of_bits b in
  match n_bits_a = n_bits_b with
  | false -> result
  | true ->
    let m = 1 lsl (n_bits_a - 1) in
    process (result + m) (a - m) (b - m)
;;

let process_main a b =
  process 0 a b ;;



(* main part *)

let num_case = read_int () ;;

for i = 1 to num_case do
  let arr = read_line_int () in
  let result = process_main arr.(0) arr.(1) in
  Printf.printf "%d\n" result
done;;

Hackerrank: Permutation game

Permutation game
https://www.hackerrank.com/challenges/permutation-game

Problem Statement
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: 
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: 
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.

Sample Input:

2
3
1 3 2
5
5 3 2 1 4

Sample Output:

Alice
Bob

Explanation: 
For the first example, Alice can remove the 3 or the 2 to make the sequence increasing and wins the game. 

For the second example, if 4 is removed then the only way to have an increasing sequence is to only have 1 number left, which would take a total of 4 moves, thus allowing Bob to win. On the first move if Alice removes the 4, it will take 3 more moves to create an increasing sequence thus Bob wins. If Alice does not remove the 4, then Bob can remove it on his next turn since Alice can not win in one move.

Solution: To solve this problem, we will use recursion and memorization. Given a list we will determine if the player starts from that position can win the game. In my algorithm, I tested all the possibilities. For example, let say Alice starts from (5 3 2 1 4), the algorithm will test all available choices, therefore we will test if (3 2 1 4) (5 2 1 4) (5 3 2 4) (5 3 2 1) are winnable positions.

Notice that (5 2 1 4) is equivalent to (4 2 1 3) = (5-1 2 1 4-1) and it is here that the recursion comes in.

Code:

(defvar num-case)       ;; denotes the number of test case in the online judgement

(defvar tab)            ;; we will use a hash table to store all the results that have been calculated
                        ;; we expect that during the recursion we will meet the same configuration many times
                        ;; hence, use a hash table to memorize results can accelerate the algorithm


(setq tab (make-hash-table :test 'equal)) ;; we use 'equal test, because we want to compare the contents of two list



(defun test-lst (lst)
  "this function test if the lst reaches a terminal condition"
  (if (= 1 (length lst))      
    t                             ;; if the list has only one element, then this is a terminal condition 
    (let ((ref (first lst))       ;; otherwier, we will check if the list is in a increasing order
          (terminated t))
      (dolist (it (rest lst))
        (if (< it ref)
          (setq terminated nil))
        (setq ref it))
      terminated)))
        

 (defun is-win-position(lst) 
   (if (gethash lst tab)          
     (gethash lst tab)                       ;;; if we have already calculated the result
     (let ((test-res (test-lst lst)))        ;;; otherwise, test every possibility
       (if test-res
         (setf (gethash lst tab) nil)
      (let ((this-is-a-win-position nil))
       (dolist (element lst)
         (let ((new-lst ()))
           (dolist (x lst)                   ;;; here we will create a new list and it is here that 
             (cond                           ;;; the recursion involves
               ((< x element) (push x new-lst))
               ((> x element) (push (1- x) new-lst))
               (t ())))
                  (setf new-lst (reverse new-lst))
               (let ((tmp-result (is-win-position new-lst)))
                 (if (null tmp-result)
                   (progn
                     (setf this-is-a-win-position t)
                     (return))))))
        (setf (gethash lst tab) this-is-a-win-position))))))


 (setq tab (make-hash-table :test 'equal))         
          


;;; main part

(setq num-case (read))

(dotimes (i num-case)
  (let ((n (read))
        (my-lst ()))
    (dotimes (j n)
      (push (read) my-lst))
    (setq my-lst (reverse my-lst))
    (let ((res (is-win-position my-lst)))
      (if res
        (format t "Alice~%")
        (format t "Bob~%")))))

          
          

          
         
             

Hackerrank: Stone Piles

Problem Statement

Stone Piles

 https://www.hackerrank.com/challenges/stone-piles
 
There are N piles of stones where the ith pile has xi stones in it. Alice and Bob play the following game:

1. Alice starts, and they alternate turns.
2. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 
3. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Input:
The first line contains the number of test cases T. T test cases follow. The first line for each test case contains N, the number of piles initially. The next line contains N space delimited numbers, the number of stones in each of the piles.

Output:
Output T lines, one corresponding to each test case containing "ALICE" if Alice wins the game and "BOB" otherwise.

Constraints:
1 ≤ T ≤ 50
1 ≤ N ≤ 50
1 ≤ x_i ≤ 50
Sample Input

4  
1  
4  
2  
1 2  
3  
1 3 4  
1  
8

Sample Output

BOB  
BOB  
ALICE  
BOB

Explanation
For the first case, the only possible move for Alice is (4) -> (1,3). Now Bob breaks up the pile with 3 stones into (1,2). At this point Alice cannot make any move and has lost.

Solution:
To solve this problem we need some basic knowledge in game theory. There is a well-written tutorial about impartial games online. (http://web.mit.edu/sp.268/www/nim.pdf)

Now back to our problem. The basic idea is to compute the Sprague-Grundy function. We can apply the same argument about the Nim game mentioned in the tutorial, meaning if we have SG function eaqual to zero in the current step, we will get a non-zero value in the next step and if we have a non-zero value at current step, we can always construct a strategy  that brings the value to zero again.

Given the initial array, we can compute the SG value, if it is zero then print "BOB", otherwise print "ALICE".

Code:

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <unordered_map>
#include <algorithm>

using namespace std;


typedef vector< vector<bool> > myVector;


void compute_sg_fun(int prev, int start, int rest, int key, vector<int>& sg_fun, myVector& record) {

 for (int i = start; i <= rest / 2; i++) {
  if (rest-i > i) {
   int res = prev ^ sg_fun[i] ^ sg_fun[rest-i];
   record[key][res] = true;
   compute_sg_fun(prev ^ sg_fun[i], i+1, rest - i,key, sg_fun, record);
  }
 }

 int k = 0;

 while (record[key][k]) ++k;

 sg_fun[key] = k;
}






int main(void)


{

 myVector record(51, vector<bool>(51,false));
 vector<int> sg_fun(51,-1);
 sg_fun[0] = 0;
 sg_fun[1] = 0;
 sg_fun[2] = 0;
 sg_fun[3] = 1;


 for (int i = 4; i <= 50; i++) compute_sg_fun(0,1,i,i,sg_fun,record);
 
 int t; cin >> t;

 for (int i = 0; i < t; i++) {
  int n;
  cin >> n;

  int res = 0;

  for (int j = 0; j < n; j++) {
   int c; cin >> c;
   res = res ^ sg_fun[c];
  }

  printf("%s\n", res == 0 ? "BOB" : "ALICE");

 }

 return 0;

}