-1
\$\begingroup\$

Alice and Borys are playing tennis and it is unknown who served the first game. After each game, the serve changes to other player. If the server wins the game, then it is said that s/he holds the serve and if the receiver wins the game then it is said that s/he breaks the serve.

If Alice won a times and Borys won b times in (a+b) no of games then find all possible values of k such that exactly k breaks of serve occurred in the entire match.

I have written this code but I think I have missed some edge cases.

package com.company;

public class KBreaksInTennis {
    static int[] displayKBreaks(int a, int b) {
        int t = a + b;
        //it was  given k ranges upto a+b+1
        int[] arrayOfK = new int[t + 1];
        int lastIndex = -1;
        boolean isEven = false;
        if (t % 2 == 0) {
            isEven = true;
        }

        for (int k = 0; k <= t; k++) {
            System.out.println("For k = " + k);
            for (int i = 0; i <= k / 2; i++){
                // checks if the 'no_of_breaks' is more than the 'no of chances to break'
                if (!(k - i > (t / 2) + 1)) {
                    int j = k - i;
                    if (isEven) {
                        int c1 = (t / 2 - i) + j;
                        if (c1 == a || c1 == b) {
                            arrayOfK[++lastIndex] = k;
                        }
                    } else {
                        // all the possibilities of breaking the serve
                        //like who breaks the serve how many times
                        //is it the player occuring t/2 times or t/2 +1 times
                        //and who is it alice or borys( a or b respectively)
                        int c1 = ((t / 2) - i) + j;
                        int c2 = ((t / 2) + 1 - j) + i;
                        int c3 = ((t / 2) + 1 - i) + j;
                        int c4 = -1;
                        // since j can be more than t/2
                        if (j <= (t / 2)) {
                            c4 = ((t / 2) - j) + i;
                        }
                        if ((c1 == a && c2 == b) || (c1 == b && c2 == a) ) {
                            arrayOfK[++lastIndex] = k;
                        }
                        if (c4 != -1) {
                            if ((c3 == a && c4 == b) || (c3 == b && c4 == a)) {
                                arrayOfK[++lastIndex] = k;
                            }
                        }
                    }
                }
            }
        }
        return arrayOfK;
    }

    public static void main(String[] args) {
        int[] arrOfK = displayKBreaks(0, 5);
        System.out.println(arrOfK.length);
        for (int i : arrOfK) {
            System.out.print(i + " ");
        }
    }
}

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Unfortunately, Code Review requires that code must be working as intended, to the best of the author's knowledge. So, it would be better to fix those missing edge cases before asking here. \$\endgroup\$ Sep 20 at 22:15
  • 3
    \$\begingroup\$ What makes you think you have missed some cases? Is it just a general feeling, or are some of your tests failing? In the latter case, you are expected to fix the code before review. It's always a good idea to include your test program, as that will help reviewers see how much you should be confident of. \$\endgroup\$ Sep 21 at 7:55
  • 2
    \$\begingroup\$ This question seems to be taken from here: acm.njupt.edu.cn/problem/CF1558A. There are some test cases provided there. The first test case is for a=2, b=1 and the expected output is 4 and 0 1 2 3, but your program throws an ArrayIndexOutOfBoundsException. \$\endgroup\$ Sep 22 at 6:07
1
\$\begingroup\$

One thing that I often forget to do as well is to simply reference the source or reason of the program. If this was an assignment, you could include that in the JavaDoc of the class.

public class KBreaksInTennis {

This is not very clear to the user; it's better to call it CountBreaksInTennis or something similar.

static int[] displayKBreaks(int a, int b) {

A function that displays breaks is not expected to return any values. It is unclear to the user what a and b is supposed to be; try gamesWonByPlayerA and gamesWonByPlayerB.

    int t = a + b;

So t is the number of games I suppose. Guess the best variable name (hint: it's numberOfGames - boring huh?).

    //it was  given k ranges upto a+b+1

This comment is completely unclear to me.

    boolean isEven = false;
    if (t % 2 == 0) {
        isEven = true;
    }

What about boolean isEven = t % 2 == 0;? And this begs the question: what is even?

        System.out.println("For k = " + k);

Always try to avoid output except in specific functions. If you want to see where you are going, use logging / trace. About as much work as println with the added advantage that you can leave it in.

            // checks if the 'no_of_breaks' is more than the 'no of chances to break'

Here you actually think of good names for your variables - except that they are not camelCase of course.

                    // all the possibilities of breaking the serve
                    //like who breaks the serve how many times
                    //is it the player occuring t/2 times or t/2 +1 times
                    //and who is it alice or borys( a or b respectively)
                    int c1 = ((t / 2) - i) + j;

How does c1 etc. related to the comments above? That's completely unclear.

                }
                    }
                }
            }
        }
    }

When there are that many braces it is a hint that you've not managed to split your solution into enough methods.

    System.out.println(arrOfK.length);

This will always print t + 1 of course, so it doesn't tell you anything. That's why you should in this case use a List, not an array.

    for (int i : arrOfK) {

An array of k and you assign it to ... i?

\$\endgroup\$
0
\$\begingroup\$

I refactored your program while keeping the same logic and (IMO) made it significantly more readable.

import java.util.HashSet;
import java.util.Set;

public class PossibleServeBreaks {

    public static void main(String[] args) {
        Set<Integer> solutions = possibleServeBreaks(2, 1);
        System.out.println(solutions.size());
        for (int i : solutions) {
            System.out.print(i + " ");
        }
    }

    /**
     * Given the number of wins for each player, returns all possibilities for the
     * number of serves broken in the games.
     */
    public static Set<Integer> possibleServeBreaks(int aWins, int bWins) {
        Set<Integer> solutions = new HashSet<>();
        for (int candidate = 0; candidate <= aWins + bWins; candidate++) {
            if (isPotentialBreakCount(candidate, aWins, bWins)) {
                solutions.add(candidate);
            }
        }
        return solutions;
    }

    private static boolean isPotentialBreakCount(int candidate, int aWins, int bWins) {
        final int totalGames = aWins + bWins;
        final int chancesToBreak = totalGames / 2 + 1;

        /*
         * Algorithm for an even number of games.
         */
        if (totalGames % 2 == 0) {
            for (int i = 0; i <= candidate / 2; i++) {
                final int breaks = candidate - i;
                if (breaks > chancesToBreak) {
                    return false;
                }

                final int c1 = (totalGames / 2 - i) + breaks;
                if (c1 == aWins || c1 == bWins) {
                    return true;
                }
            }
            return false;
        }

        /*
         * Otherwise algorithm for the odd number of games.
         */
        for (int i = 0; i <= candidate / 2; i++) {
            final int breaks = candidate - i;
            if (breaks > chancesToBreak) {
                continue;
            }

            final int c1 = totalGames / 2 - i + breaks;
            final int c2 = chancesToBreak - breaks + i;
            if ((c1 == aWins && c2 == bWins) || (c1 == bWins && c2 == aWins)) {
                return true;
            }

            if (breaks <= (totalGames / 2)) {
                final int c3 = chancesToBreak - i + breaks;
                final int c4 = ((totalGames / 2) - breaks) + i;
                if ((c3 == aWins && c4 == bWins) || (c3 == bWins && c4 == aWins)) {
                    return true;
                }
            }
        }
        return false;
    }
}

When I started using solutions.add(candidate) instead of your arrayOfK[++lastIndex] == k it seems to have resolved the ArrayIndexOutOfBoundsException that you had on the a=2, b=1 test case. And your program seems to also be correct for the other test cases given in the original problem statement.

Even with this refactor, though, I still don't really understand how your program works. I don't know what i and c1 c2 c3 c4 really mean, which is the main problem with your code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.