HackerRank Permutation game problem solution

In this HackerRank Permutation game problem solution Alice and Bob play the following game:

1. They choose a permutation of the numbers 1 to N.
2. Alice plays first and they alternate.
3. In a turn, they can remove anyone remaining number from the permutation.
4. The game ends when the remaining numbers from an increasing sequence of 1 or more numbers. The person who played the turn that leaves an increasing sequence wins the game.

Assuming both plays optimally, who wins the game? Return Alice or Bob.

Problem solution in Python.

from copy import copy
from collections import defaultdict

def renumber(arr):
    l=len(arr)
    old_num=sorted(arr)
    return [old_num.index(x)+1 for x in arr]

def F(arr):
    if tuple(arr) in d:
        return d[tuple(arr)]
    elif arr==sorted(arr):
        d[tuple(arr)]=0
        return d[tuple(arr)]
    else:
        ans=set()
        for x in arr:
            temp=copy(arr)
            temp.remove(x)
            temp=renumber(temp)
            ans.add(F(temp))
        result=0
        while result in ans:
            result+=1
        d[tuple(arr)]=result   
        return d[tuple(arr)]

d=defaultdict(int)
d[tuple([1])]=0
for _ in range(int(input())):
    arr_count = int(input())
    arr = list(map(int, input().rstrip().split()))
    print('Alice') if F(arr) else print('Bob')

Problem solution in Java.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Solution {
	private static HashMap cache=new HashMap<ArrayList<Integer>, Boolean>();

	private static boolean isSorted(ArrayList<Integer> list){
		int l=list.size();
		for(int i=0;i<l-1;i++){
			if(list.get(i)>list.get(i+1))return false;
		}
		return true;
	}

	
	
	private static boolean isWinning(ArrayList<Integer> list){
		if(cache.containsKey(list)){
			return (boolean) cache.get(list);
		}
		int l=list.size();
		int val;
		for(int i=0;i<l;i++){
			val=list.get(i);
			list.remove(i);
			if(isSorted(list)){
				list.add(i, val);
				cache.put(list,Boolean.TRUE);
				return true;
			}
			if(!isWinning(list)){
				list.add(i,val);
				cache.put(list,Boolean.TRUE);
				return true;
			}
			list.add(i,val);
		}
		cache.put(list,Boolean.FALSE);
		return false;
	}
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt(),N;
		ArrayList<Integer> list;
		ArrayList<String> result=new ArrayList<String>();
		for(int t=0;t<T;t++){
			N=sc.nextInt();
			sc.nextLine();
			list=new ArrayList<Integer>();
			for(int i=0;i<N;i++){
				list.add(sc.nextInt());
			}
			if(isWinning(list)){
				result.add("Alice");
			}else {
				result.add("Bob");
			}
		}
		for(String s:result){
			System.out.println(s);
		}
	}
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

const int MAXN = 15;
const int MAXS = 1 << MAXN;

int n, s;
int a[MAXN], lg2[MAXS];
bool sg[MAXS];

bool Check(int st)
{
	int z, x;
	z = a[lg2[x=(st&(-st))]];
	for (st -= x; st; st -= x)
		if (a[lg2[x=(st&(-st))]] <= z)  return false;
		else z = a[lg2[x]];
	return true;
}

bool Work()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i ++)
		scanf("%d", &a[i]);
	s = 1 << n;

	for (int k = 1, z, x; k < s; k ++)
	{
		sg[k] = false;
		if (Check(k))
			continue;
		for (z = k; z > 0 && !sg[k]; z -= x)
		{
			x = (z & (-z));
			if (!sg[k-x])  sg[k] = true;
		}
	}

	return sg[s-1];
}

int main()
{

	for (int i = 0; i < MAXN; i ++)
		lg2[1<<i] = i;

	int T;
	scanf("%d", &T);

	for (int i = 0; i < T; i ++)
		printf((Work()? "Alice\n": "Bob\n"));

	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <time.h>
int puiss(int a, int b){
    int i;
    int po = 1;
    for(i=0;i<b;i++){
        po *=a;
    }
    return po;
}

int gagnant(int *Perm, int N,int *tab, int K){
    int flag = 1;
    int i,j;    
    if(*(tab+K)!=2){
        return *(tab+K);
    }
    for(i=0;i<N-1;i++){
        if(*(Perm+i)>*(Perm+i+1)){
            flag = 0;
            break;
        }
    }
    if(flag==1){
        *(tab+K)=0;
        return 0;
    }else{
        int Perm2[N-1];
        for(i=0;i<N;i++){
            for(j=0;j<i;j++){
                Perm2[j]=*(Perm+j);
            }
            for(j=i+1;j<N;j++){
                Perm2[j-1]=*(Perm+j);
            }
            if(gagnant(&Perm2[0],N-1,tab,K+puiss(2,*(Perm+i)-1))== 0){
                *(tab+K)=1;
                return 1;
            }
        }
        *(tab+K)=0;        
        return 0;
    }
}
void scanner(int N){
    int Perm[N];
    int i;
    int A = puiss(2,N);
    int tab[A];
    for(i=0;i<A;i++){
        tab[i]=2;
    }
    for(i=0;i<N;i++){
        scanf("%d",&Perm[i]);
    }
    if(gagnant(&Perm[0],N,&tab[0],0)==1){
        printf("Alice\n");
    }else{
        printf("Bob\n");
    }
}

int main(void){
    int T,N,i,j;
    time_t debut, fin;
    debut=time(NULL);
    scanf("%d",&T);
    for(i=0;i<T;i++){
        scanf("%d",&N);
        scanner(N);
    }
    fin=time(NULL);
    return 0;
}