# 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)
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)){
cache.put(list,Boolean.TRUE);
return true;
}
if(!isWinning(list)){
cache.put(list,Boolean.TRUE);
return true;
}
}
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++){
}
if(isWinning(list)){
}else {
}
}
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;
}```