Bathroom stalls in C (Google Code Jam 2017)

Question

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 supposed to work. That's maybe quicker to understand than reading through the algorithm.

/* 
Definitions:
 Group =    A number of consecutive free stalls, in the beginning there is only one group.
 Layer =    A new layer is started when all groups of the previous layer are split up.
            Each layer holds therefore 2^(layer - 1) customers
            e.g.    1st layer: 1 customer
                    2nd layer: 2 customers
                    3rd layer: 4 customers
                    .
                    nth layer: 2^(n-1) customers

 With the above definitions it can be calculated how many layers are necessary.
     (Eq. 1) lastLayer = ceil(log(numberCustomers)/log(2))

 To calculate the size of the group, the last customer will be assigned to, the size of the
 groups in the last layer must be calculated. To do so, we need the following:
 - number of stalls in the last layer
     (Eq. 2) custPrevLayers = 2^(lastLayer - 1) - 1
     (Eq. 3) stallsLastLayer = totalStalls - custPrevLayers
 - the number of groups
     (Eq. 4) nbrGroupsLastLayer = 2^(lastLayer - 1)
 - and the number of customers in the last layer
     (Eq. 5) custLastLayer = totalCustomers - custPrevLayers

 Thus, the average group size is
     (Eq. 6) avgGroupSizeLastLayer = stallsLastLayer / nbrGroupsLastLayer

 Since avgGroupSizeLastLayer will in most cases not be an integer, we end up with two different
 group sizes:
     (Eq. 7) largeGroupSize = ceil(avgGroupSizeLastLayer)
     (Eq. 8) smallGroupSize = largeGroupSize - 1

 The last step is to figure out how many large groups are present in the last layer. This can
 be calculated by means of (Eq. 9) and (Eq. 10):
     (Eq. 9)  stallsLastLayer    = largeGroupSize * nbrLargeGroups + smallGroupSize * nbrSmallGroups
     (Eq. 10) nbrGroupsLastLayer = nbrLargeGroups + nbrSmallGroups

     Solving (Eq. 9) for nbrSmallGroups and inserting it into (Eq. 10) leaves us with
     (Eq. 11) nbrLargeGroups = (stallsLastLayer - (nbrGroupsLastLayer * smallGroupSize))/(largeGroupSize - smallGroupSize);

 If custLastLayer is smaller than the nbrLargeGroups min and max is to be calculated
 with the largeGroupSize, otherwise with the smallGroupSize.*/

Implementation:

/****************************************************************************************
 Includes
*****************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stddef.h>
/****************************************************************************************
 Defines
*****************************************************************************************/
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define MAX_LINE_LENGTH (80)

/****************************************************************************************
 Structs and typedefs
*****************************************************************************************/
typedef unsigned long long uint64;

typedef struct TestCase_s
{
    uint64 stalls;
    uint64 customers;
    uint64 max;
    uint64 min;
} TestCase_t;

/****************************************************************************************
 Forward declarations
*****************************************************************************************/

static void   getTestCases(FILE *fp, TestCase_t testCases[], int nbrOfTestcases);
static int    getNumberOfTestCases(FILE *fp);
static uint64 getNumberOfStalls(char line[]);
static uint64 getNumberOfCustomers(char line[]);
static int    getLine(char line[], size_t buflen, FILE *stream);

static uint64 getNumberOfLargeGroups(uint64 sizeLargeGroup, uint64 sizeSmallGroup, uint64 stallsFree, uint64 totalGroups);
static uint64 getLayers(uint64 customers);
static void   calcStallsLeftRight(uint64 stalls, uint64 *stallsLeft, uint64 *stallsRight);

static void outputToFile(TestCase_t testCases[], int entries, char *outputFile);
/****************************************************************************************
 Public functions
*****************************************************************************************/
int main (void)
{
    FILE *fp;
    int nbrTestCases = 0;

    char input[] = "Debug/C-large-practice.in";

    char output[] = "Debug/output.txt";

    fp = fopen(input, "r");

    if (fp == NULL)
    {
       perror("Error while opening the file.\n");
       exit(EXIT_FAILURE);
    }

    nbrTestCases = getNumberOfTestCases(fp);

    TestCase_t *testCases = calloc(nbrTestCases, sizeof(*testCases));

    getTestCases(fp, testCases, nbrTestCases);

    fclose(fp);

    int currentCase = 0;

    while (currentCase < nbrTestCases)
    {
        uint64 stallsToLeft;
        uint64 stallsToRight;
        TestCase_t *curTC = &testCases[currentCase];

        uint64 lastLayer = getLayers(curTC->customers);
        uint64 custPrevLayers = pow(2, lastLayer - 1) - 1;
        uint64 stallsLastLayer = curTC->stalls - custPrevLayers;
        uint64 nbrGroupsLastLayer = pow(2, lastLayer - 1);
        uint64 sizeLargeGroup = stallsLastLayer/nbrGroupsLastLayer + (stallsLastLayer % nbrGroupsLastLayer != 0); // ciel

        if (sizeLargeGroup == 1)
        {
            stallsToLeft = 0;
            stallsToRight = 0;
        }
        else
        {
            uint64 customersLastLayer = curTC->customers - custPrevLayers;
            uint64 sizeSmallGroup = sizeLargeGroup - 1; // size of small group is always one less than number of big group
            uint64 largeGroups = getNumberOfLargeGroups(sizeLargeGroup, sizeSmallGroup, stallsLastLayer, nbrGroupsLastLayer);

            if (largeGroups >= customersLastLayer)
            {
                calcStallsLeftRight(sizeLargeGroup, &stallsToLeft, &stallsToRight);
            }
            else
            {
                calcStallsLeftRight(sizeSmallGroup, &stallsToLeft, &stallsToRight);
            }
        }

        curTC->max = MAX(stallsToLeft, stallsToRight);
        curTC->min = MIN(stallsToLeft, stallsToRight);

        currentCase++;
    }

    outputToFile(testCases, nbrTestCases, output);

    printf("done");

    return 0;
}
/****************************************************************************************
 Private functions
*****************************************************************************************/
/**
 * Calculates the number of layers needed for a number of customers.
 */
static uint64 getLayers(uint64 customers)
{
    uint64 layers = 1;
    uint64 possibleCustomers = 1;

    while (customers > possibleCustomers)
    {
        layers++;
        possibleCustomers = possibleCustomers << 1;
        possibleCustomers = possibleCustomers | 1;
    }

    return layers;
}

/**
 * Calculate the number of large groups
 */
static uint64 getNumberOfLargeGroups(uint64 sizeLargeGroup, uint64 sizeSmallGroup, uint64 stallsFree, uint64 totalGroups)
{
    return (stallsFree - (totalGroups * sizeSmallGroup))/(sizeLargeGroup - sizeSmallGroup);
}

/**
 * Calculates the max number of stalls to the left and right of the stall in the middle.
 * If stalls is an even number the stall to the left is chosen to base the calculation on.
 */
static void calcStallsLeftRight(uint64 stalls, uint64 *stallsLeft, uint64 *stallsRight)
{
    *stallsLeft = (stalls - 1)/2;
    *stallsRight = stalls/2;
}

/**
 * Reads test cases from file and fills them into the preallocated memory
 */
static 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);
}

/**
 * Number of stalls is the first number in a line
 */
static uint64 getNumberOfStalls(char line[])
{
    return atoll(line);
}

/**
 * Number of customers is the second number in a line
 */
static uint64 getNumberOfCustomers(char line[])
{
    int i = 0;
    while(line[i] != ' ')
    {
        i++;
    }
    i++;

    return atoll(&line[i]);
}

/**
 * Number of test cases is the first line in a file.
 */
static int getNumberOfTestCases(FILE *fp)
{
    char *line = malloc(MAX_LINE_LENGTH);

    getLine(line, MAX_LINE_LENGTH, fp);

    return atoi(line);
}

static int getLine(char line[], size_t buflen, FILE *stream)
{
    int i = 0;
    char c = getc(stream);

    if (c == EOF)
    {
        return EOF;
    }

    while(c != EOF && c != '\n' && i < buflen)
    {
       line[i++] = c;
       c = getc(stream);
    }

    line[i] = '\0';

    return 0;
}

/**
 * Writes the test results to an output file
 */
static void outputToFile(TestCase_t testCases[], int entries, char *outputFile)
{
    FILE *fp;
    fp = fopen(outputFile,"wb"); // read mode

    if (fp == NULL)
    {
       perror("Error while opening the file.\n");
       exit(EXIT_FAILURE);
    }

    for (int i = 0; i < entries; i++)
    {
        fprintf(fp, "Case #%d: %I64d %I64d\n", i + 1, testCases[i].max, testCases[i].min);
    }

    fclose(fp);
}

Answer 1

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().

Answer 2

Your getLine is broken:

If your buffer is too small, it will discard the last-read byte and write a NUL behind the buffer!
Also, it mixes int and size_t with potentially fatal consequences.

80 bytes is a fairly small amount of memory. Getting it from the stack is no trouble, and far more efficient than asking malloc.

Answer 3

• char c is incorrect. The reason is that it is implementation defined where char is signed or unsigned. On a platform with char being unsigned, it will never compare equal to EOF. It is strongly recommended to declare it int c.

• Combining test case data and results in the same structure is another SRP violation. I recommend to separate them into

  struct TestCase {
      uint64 stalls;
      uint64 customers;
  }
  

  and

  struct Result {
      uint64 max;
      uint64 min;
  }
  

• Reading in all test cases in advance leads to unnecessary complications. I recommend to restructure the code as

      TestCase_t testCase;
      Result_t result;
      for (int i = 0; i < nbrTestCases; i++) {
          getTestCase(&testCase);
          solveTestCase(&testCase, &result);
          printResults(i + 1, &result);
      }
  

• atoll returns the long long, while your values are unsigned long long. Mixing signed and unsigned is generally unsafe. Even though in this case you are OK, I recommend using stroull instead. Another reason to use strtoull is that it tells you where the token ended, so there's no need to manually search for it:

      char * end;
      testCase.stalls = strtoull(line, &end, 10);
      testCase.customers = strtoull(end, NULL, 10);