Bathroom stalls in C (Google Code Jam 2017)

https://code.google.com/codejam/contest/3264486/dashboard#s=p2


Problem


A certain bathroom has N + 2 stalls in a single row; the stalls on the
left and right ends are permanently occupied by the bathroom guards.
The other N stalls are for users.


Whenever someone enters the bathroom, they try to choose a stall that
is as far from other people as possible. To avoid confusion, they
follow deterministic rules: For each empty stall S, they compute two
values LS and RS, each of which is the number of empty stalls between
S and the closest occupied stall to the left or right, respectively.
Then they consider the set of stalls with the farthest closest
neighbor, that is, those S for which min(LS, RS) is maximal. If there
is only one such stall, they choose it; otherwise, they choose the one
among those where max(LS, RS) is maximal. If there are still multiple
tied stalls, they choose the leftmost stall among those.


K people are about to enter the bathroom; each one will choose their
stall before the next arrives. Nobody will ever leave.


When the last person chooses their stall S, what will the values of
max(LS, RS) and min(LS, RS) be?


Input


The first line of the input gives the number of test cases, T. T lines
follow. Each line describes a test case with two integers N and K, as
described above.


Output


For each test case, output one line containing Case #x: y z, where x
is the test case number (starting from 1), y is max(LS, RS), and z is
min(LS, RS) as calculated by the last person to enter the bathroom for
their chosen stall S.


Limits


1 ≤ T ≤ 100. 1 ≤ K ≤ N.
1 ≤ N ≤ 10^18.

Input               Output 
5
4 2                 Case #1: 1 0
5 2                 Case #2: 1 0
6 2                 Case #3: 1 1
1000 1000           Case #4: 0 0
1000 1              Case #5: 500 499

Description of my algorithm

I attached a little graphic to show how the algorithm is suppose

A very nice question.

The question doesn't specify what exactly is desired from the code review, so just a few suggestions, but first I'm not sure the algorithm takes into account the guards in the 2 extra stalls. The graphic doesn't show them but they do affect the algorithm.

Memory Leaks

The following code allocates memory for the variable line N + 1 times where N is the number of test cases, but only frees the allocated memory once.

/**
 * Reads test cases from file and fills them into the preallocated memory
 */
void getTestCases(FILE *fp, TestCase_t testCases[], int nbrOfTestcases)
{
    char *line = malloc(MAX_LINE_LENGTH);
    int i = 0;

    while((getLine(line, MAX_LINE_LENGTH, fp) != -1) && (i < nbrOfTestcases))
    {
        testCases[i].stalls = getNumberOfStalls(line);
        testCases[i].customers = getNumberOfCustomers(line);

        i++;
        line = malloc(MAX_LINE_LENGTH);
    }
    free(line);
}

The testCases variable is never freed.

It May be Better to Use Standard C Library Functions for Input

The fgets(char buffer, int bufferLength, FILE stream) Standard C Library function has almost the same signature as int getLine(char line[], size_t buflen, FILE *stream) and performs almost exactly the same function. The difference is that fgets() returns a pointer to the filled string buffer. A
null pointer is returned where getLine() returns EOF.

The function fgets() may perform better than getLine() because it uses buffered input.

Reduce Complexity, Follow SRP

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows:


A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines in procedural languages like C as well.

The main function could be broken up into at least 2 more functions:

int getInput(int* nbrTestCases, TestCase_t* testCases[])       // return EXIT_SUCCESS or EXIT_FAILURE
int executeAlgorithm(int nbrTestCases, TestCase_t testCases[]) // return EXIT_SUCCESS or EXIT_FAILURE

Inconsistent Use of System Constants

The main() function may exit using EXIT_FAILURE, but it doesn't return EXIT_SUCCESS at the end.
It might be more readable if it used both constants.

Test for Input Errors

The while loop in the function getTestCases() tests the return value of getLine(), but the function getNumberOfTestCases() does not test the return value of getLine() before using the value of line which may be of length zero.

The length of line is not tested prior to use in getTestCases(), getNumberOfStalls() or getNumberOfCustomers().

There is no test to ensure that the contents of line are numeric before calling atoll() or atoi().

StackExchange Code Review Q#162744, answer score: 6