Permutation game HackerRank Solution

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

1. They choose a permutation of the numbers  to .
2. Alice plays first and they alternate.
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 of  or more numbers. The person who played the turn that leaves an increasing sequence wins the game.

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

Permutation game HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

def permutationGame(arr):
    memo = {}


    def winner(nums):
        if tuple(nums) in memo:
            return memo[tuple(nums)]


        if sorted(nums) == nums:
            memo[tuple(nums)] = 'Bob'
            return 'Bob'


        for i in range(len(nums)):
            if winner(nums[:i] + nums[i+1:]) == 'Bob':
                memo[tuple(nums)] = 'Alice'
                return 'Alice'


        memo[tuple(nums)] = 'Bob'
        return 'Bob'


    return winner(arr)

function permutationGame(arr) {
    const memo = {}
    const inc = arr => arr.every((v, i, a) => i === a.length - 1 || a[i] < a[i + 1] )
    function rec(arr) {
        let key = arr.join('|')
        if (memo[key]) return memo[key]        
        if (inc(arr)) return memo[key] = true
        for (let idx = 0; idx < arr.length; idx++)
            if (rec(arr.slice(0, idx).concat(arr.slice(idx + 1))))
                return memo[key] = false
           
        return memo[key] = true
    }
   
    return rec(arr) ? 'Bob' : 'Alice'
}