Permutation game Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Permutation game
  5. Discussions

Permutation game

Sort by

recency

|

36 Discussions

|

  • abdr_elhassani
     + 0 comments

    I could ot understand what the function should do. here is my Java function 

    public static String permutationGame(List<Integer> arr) {
    int turn =0;

    for (int i = arr.size()-1; i >0; i--) {
        turn++;
        if(arr.get(i)>arr.get(i-1)){
            break;
        }
    }

  • andrewferdinanto
     + 0 comments

    C# Solution **using System; using System.Collections.Generic; using System.Linq;

    public class Solution { private static Dictionary memo = new Dictionary();

    private static bool IsIncreasing(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (arr[i] >= arr[i + 1])
        {
            return false;
        }
    }
    return true;
}

private static bool FindWinner(int[] arr)
{
    string key = string.Join("|", arr);
    if (memo.ContainsKey(key))
    {
        return memo[key];
    }

    if (IsIncreasing(arr))
    {
        return memo[key] = true;
    }

    for (int idx = 0; idx < arr.Length; idx++)
    {
        var newArr = arr.Where((val, index) => index != idx).ToArray();
        if (FindWinner(newArr))
        {
            return memo[key] = false;
        }
    }

    return memo[key] = true;
}

public static string PermutationGame(int[] arr)
{
    memo.Clear(); // Clear the memo dictionary for each test case
    return FindWinner(arr) ? "Bob" : "Alice";
}

public static void Main(string[] args)
{
    int t = Convert.ToInt32(Console.ReadLine());
    while (t-- > 0)
    {
        int n = Convert.ToInt32(Console.ReadLine());
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        Console.WriteLine(PermutationGame(arr));
    }
}

    }**

  • doukutsutoyomum1
     + 0 comments

    Python3 solution:

    from functools import cache
def permutationGame(arr):
    def is_increasing(remain):
        return all(remain[i] < remain[i+1] for i in range(len(remain)-1))
    def new_perm(remain, removed):
        return tuple(e - 1 if e > removed else e for e in remain if e != removed)
    @cache
    def first_wins(remain):
        if is_increasing(remain):
            return False
        return any(not first_wins(new_perm(remain, e)) for e in remain)
    return 'Alice' if first_wins(tuple(arr)) else 'Bob'

  • alexey_shayakhm1
     + 0 comments

    Combination of previous answers, C++.

    class PermutationGame
{
private:
    unordered_set<string> _winningNumbers;

    bool isIncreasing(string str)
    {
        if (str.size() == 1) return 1;        
        auto it = str.begin();
        int prev = *it++;
        for (; it != str.end(); it++)
        {
            if (*it <= prev) return false;
            prev = *it;
        }
        return true;
    }

    string encode(vector<int> arr)
    {
        string s;
        for (auto number : arr)
            s.push_back(number < 10 ? (number + '0') : 
                                      (number - 10 + 'A'));
        return s;
    }

    bool checkCurrentPlayerWins(string numbers)
    {
        // With this sequence, the current player has already won 
        // => player wins
        if (_winningNumbers.find(numbers) !=_winningNumbers.end())
            return true;

        // Sequence increases after opponent's turn =>
				// current player loses
        if (isIncreasing(numbers))
            return false;

        for (int i = 0, len = (int)numbers.size(); i < len; i++)
        {
            char erased = numbers[i];
            // Making a move
            numbers.erase(i, 1);     
            
            // Checking if the opponent wins
            bool opponentWins = checkCurrentPlayerWins(numbers);
            
            // Reverse the move
            numbers.insert(i, 1, erased);

            // If the opponent loses, then the current player wins
            if (!opponentWins)
            {
                // Keeping the Winning Sequence
                _winningNumbers.insert(numbers);                      
                return true;
            }           
        }
        // None of the moves resulted in the player's victory => 
        // player loses
        return false;
    }

public:
    bool checkCurrentPlayerWins(vector<int> arr)
    {                
        bool result = checkCurrentPlayerWins(encode(arr));
        _winningNumbers.clear();
        return result;
    }
};

string permutationGame(vector<int> arr) 
{
    PermutationGame pg;
    return pg.checkCurrentPlayerWins(arr) ? "Alice" : "Bob";
}

  • evgeniantonov55a
     + 0 comments

    why there are no comments on anyones code.... It's extremely frustrating for newbies, it would be very helpful if you explained each line. So please add comments