Programming challenge: Competition for the best cat is coming

user_1638596 0
Viewed 1134

Recently I have attended a coding challenge and I was able score only 50%. There were few test cases failed executing my code, I am unable to find reasons for the failure in my code. So I have added the question and my code below. I appreciate your help in find the reason for the failed test cases.

Requirement

Competition for the best cat is coming. The competition consists of several duels. In each duel both cats are standing on an infinite line facing each other. The older cat starts - it has to move towards his opponent by 1 or 2 cat-units. Neither of them can go back, jump over his opponent or share the same spot. The cat owners trained their cats the best they could, so their pets play optimally. The cat that is unable to make a move loses.

Input

First line of the input contains number of tests t (t ≤ 1000). Each test consists of 4 integers: age and position of the first cat and then age and position of the second cat. No two cats have the same age. No calculations in this task will exceed the number 2**31 - 1.

Output

For each test print 1 if the first cat wins and 0 otherwise.

Example

Input:

1
10 1 9 5

Output:

0

Explanation: Cat 1 can move to either field 2 or 3. In the next move cat 2 regardless of the opponent's decision can block him and win.

My Code

using System;
using System.Linq;

namespace Solution
{
    class Solution
    {
        static void Main(string[] args)
        {
            var input1 = Console.ReadLine().Trim();
            var numOfTest = Convert.ToInt32(input1);

            for (int i = 0; i < numOfTest; i++)
            {
                var input2 = Console.ReadLine().Trim();
                var catDetails = input2.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => Convert.ToInt32(x)).ToArray();
                int result = -1;

                if (catDetails[0] == catDetails[2])
                {
                    Console.WriteLine(-1);
                    break;
                }

                if(catDetails[0] > catDetails[2])
                    result = CalculateWinningResult(catDetails[0], catDetails[1], catDetails[2], catDetails[3], 1);
                else
                    result = CalculateWinningResult(catDetails[0], catDetails[1], catDetails[2], catDetails[3], 2);

                Console.WriteLine(result);
            }
        }

        private static int CalculateWinningResult(int cat1Age, int cat1Position, int cat2Age, int cat2Position, int moveCat)
        {

            switch (moveCat)
            {
                case 1:

                    cat1Position = CalculateCatPosition(cat1Position, cat2Position);
                    if (cat1Position == 0)
                        return 0;
                    else
                        return CalculateWinningResult(cat1Age, cat1Position, cat2Age, cat2Position, 2);
                case 2:
                    cat2Position = CalculateCatPosition(cat2Position, cat1Position);
                    if (cat2Position == 0)
                        return 1;
                    else
                        return CalculateWinningResult(cat1Age, cat1Position, cat2Age, cat2Position, 1);
            }
            return 0;
        }

        private static int CalculateCatPosition(int currentCatPosition, int opponentCatPosition)
        {
            int tempPosition;
            if (currentCatPosition > opponentCatPosition)
            {
                tempPosition = (currentCatPosition - 1);

                if (tempPosition <= opponentCatPosition)
                    return 0;
                else
                {
                    tempPosition = (currentCatPosition - 2);
                    if (tempPosition >= opponentCatPosition)
                        return 0;
                    else
                        currentCatPosition = tempPosition;
                }
            }
            else
            {
                tempPosition = (currentCatPosition + 1);

                if (tempPosition <= opponentCatPosition)
                    return 0;
                else
                {
                    tempPosition = (currentCatPosition + 2);
                    if (tempPosition >= opponentCatPosition)
                        return 0;
                    else
                        currentCatPosition = tempPosition;
                }
            }

            return currentCatPosition;
        }
    }
}

Resulttest case result

algorithm c#
2 Answers

Let's analyze the game. When a cat to move loses the game? First, it doesn't matter the positions of each cat but the distance between cats: if in 10 1 9 5 test a cat on move loses than 10 101 9 105 a cat on move loses as well.

Now, let's draw a simple table:

   distance | cat on move
   ----------------------
          0 | Loses (evident: he is blocked)
          1 | Wins
          2 | Wins
          3 | Loses
          4 | Wins
          5 | Wins
          6 | Loses 
          7 | Wins
          8 | Wins
          9 | Loses 
         10 | Wins
         11 | Wins
         12 | Loses 
....

Can you see the pattern? if distance between cats is divisible by 3 the cat on move loses; otherwise he (cat is "he" or "she", never "it"!) wins, his strategy is to keep distance between he and his opponent be divisible by 3. You can prove it by induction.

For Instance: for 10 1 9 5 case the distance is 5 - 1 - 1 == 3 and 3 % 3 == 0 (the distance is divisible by 3) so the cat on move (10 years old one) looses.

Pseudo Code: (let's not spoil the fun; please, implement C# code yourself). When given 4 numbers age1 x1 age2 x2 for cats' ages and initial locations we can find out the winner as followes:

 if ((Abs(x2 - x1) - 1) % 3 == 0) then // if distance divisible by 3?
   // Yes: Cat's on move loses
   if (age1 > age2) then 
     return 1
   else      
     return 0
 else  
   // No: Cat's on move wins
   if (age1 > age2) then 
     return 0
   else      
     return 1
user_23194070

I tried below code and it passed all the test scenarios for me.

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String n = sc.nextLine().trim();
    // Enter total number of tests
    int numOfTest = Integer.parseInt(n);
    // read cat details
    String catDetails = "";
    String[] catDetailsArr = new String[1];
    int[] catDetailsData = new int[4];
    for (int i = 0; i < numOfTest; i++) {

        catDetails = sc.nextLine().trim();

        catDetailsArr = catDetails.split(" ");



        for (int x = 0; x < catDetailsArr.length; x++) {
            catDetailsData[x] = Integer.parseInt(catDetailsArr[x]);
        }

        if (Math.abs(catDetailsData[3] - catDetailsData[1]) % 2 == 0)
            // Yes: Cat's on move loses
            if (catDetailsData[0] > catDetailsData[2])
                System.out.println("1");
            else
                System.out.println("0");
        else
        if (catDetailsData[0] > catDetailsData[2])
            System.out.println("0");
        else
            System.out.println("1");

    }

As per our understanding if diff in positions-1 is odd then the cat with lesser age will win else the older cat will win.

user_122901080
Related