5
\$\begingroup\$

I typically use high level programming languages like C# and JavaScript, but today I was doing the "99 bottles of beer" kata for an event using C. Below is my solution, which seems to work. Please let me know if there's any egregious mistakes or non-idiomatic pieces in there?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXBOTTLES 9999

#define MAX_NR_OF_DIGIT_OCCURENCES 2 // Max nr of placeholders in any of the sentence formats
#define SENTENCE_FORMAT_BASE "%i bottles of beer on the wall, %i bottles of beer\nTake one down, pass it around, %i bottles of beer on the wall...\n"
#define SENTENCE_FORMAT_1 "1 bottle of beer on the wall, 1 bottle of beer\nTake one down, pass it around, no more bottles of beer on the wall...\n"
#define SENTENCE_FORMAT_0 "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, %i bottles of beer on the wall..."

int getNumberOfDigits(int number) {
    int numberWidth = 0;

    while (number) {
        numberWidth++;
        number /= 10;
    }

    return numberWidth;
}

char* createCouplet(const int i, char* format) {
    int length = getNumberOfDigits(i) * MAX_NR_OF_DIGIT_OCCURENCES + strlen(format);
    char* coupletBuffer = malloc(length * sizeof(char));

    sprintf(coupletBuffer, format, i, i, i-1);

    return coupletBuffer;
}

int main(int argc, char *argv[]) {
    int songSize = 13; // TODO: Retrieve from argv
    int limit = songSize + 1;

    if (songSize >= MAXBOTTLES) {
        return 42;
    }

    char* song[limit];

    for (int i = 2; i < limit; i++) {
        song[limit - i - 1] = createCouplet(i, SENTENCE_FORMAT_BASE);
    }

    song[limit - 2] = malloc(2500 * sizeof(char));
    strcpy(song[limit - 2], SENTENCE_FORMAT_1);

    song[limit - 1] = createCouplet(songSize, SENTENCE_FORMAT_0);

    for (int i = 0; i < limit; i++) {
        printf("%s\n", song[i]);
        free(song[i]);
    }

    return 0;
}

I welcome any feedback of course, but I'm particularly worried that I do silly things around buffers and handling memory correctly.

\$\endgroup\$
6
\$\begingroup\$

Logic

I find it counterintuitive that your main loop doesn't look like this:

for (int bottles = limit; bottles >= 0; bottles--) {
    …
}

The way you build the song backwards (with some index arithmetic), followed by two special cases, makes the code hard to follow.

You have a pluralization bug:

2 bottles of beer on the wall, 2 bottles of beer
Take one down, pass it around, 1 bottles of beer on the wall...

You used a special case for SENTENCE_FORMAT_1. Because the text happens to be constant, you call malloc() and strcpy() instead of createCouplet(). I don't recommend doing anything so drastically different. In fact, createCouplet() should be made responsible for choosing the right template to use based on the bottle count, such that the function "just works" for any i.

Memory management

I don't understand the appeal of storing all of the verses in a variable-length array. If you want to have the entire song at once, it would be better to build one huge contiguous string. Alternatively, if you are willing to write a loop that prints each verse (like my countdown loop above), then you don't even need to have the entire song in memory at any given time; you can just work one verse at a time.

In particular, the one-verse-at-a-time approach gives you the option to use one buffer, whose contents are overwritten repeatedly. I would just use a static buffer. In general any design in C that avoids malloc() altogether is highly appealing.

I'm not a fan of the technique you used to calculate the length of the output. It's a very manual process, requiring you to tell it how many numbers appear in the template, and calculating how many digits should be rendered. Rather, what you could do is take advantage of the return value of snprintf(), which tells you how long the output should be — and that technique works in general. (The whole issue would be a moot point with a static buffer: you just generously estimate the required space for any verse.)

Suggested design

int bottleVerse(int bottles, int init_bottles, char *buf, size_t bufsize)

This function generates one verse from the song 99 Bottles of Beer on the Wall, writing it to the given buffer. The output ends with a newline and a NUL terminator.

Parameters

  • bottles: The number of bottles of beer at the start of the verse
  • init_bottles: The initial number of bottles (traditionally 99)
  • buf: Pointer to a buffer to which the output should be written (possibly NULL, to obtain the output length without writing the output anywhere).
  • bufsize: The size of the buffer

Return value

On success, a positive value is returned, indicating the length of the string that was written to the buffer. A negative value indicates the number of bytes by which the buffer is undersized.

This design mimics the pattern followed by many functions in the C library. The caller is responsible for providing the buffer and its size; the function merely fills it in. The return value acts as a status indicator.

The memory management is very in-your-face. It seems more inconvenient to use than your createCouplet(). However, it has many advantages:

  • This function obviously allocates no memory. It's very clear what the memory ownership policy is: the caller provides and "owns" the memory.
  • The caller has the flexibility to provide several kinds of memory:
    • It could be a static buffer, reused between verses.
    • The caller could malloc() a buffer.
    • The caller could append this verse to the previous verse in one huge buffer for the song.
  • It can avoid some drawbacks of malloc() and free():
    • malloc() is a mildly expensive operation.
    • malloc() might allocate memory in non-consecutive chunks, reducing the efficiency of the memory cache.
    • Allocating many small chunks of memory with malloc() can lead to memory fragmentation, wasting memory.
    • Forgetting to free() a newly allocated string would cause a memory leak.
    • Accidentally using memory that has already been free()d could cause a security vulnerability.

Many of these issues are negligible concerns for a tiny program like this. However, if many functions in a large program were designed to use malloc(), then you would have a chaotic mess. For these reasons, idiomatic C functions generally have this kind of design where the caller provides the memory.

Here is an example of what the code might look like if you wanted to compose the entire song as one long string. Using a static buffer to print one verse at a time would result in a slightly simpler program.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// Left as an implementation exercise for you, using snprintf()
int bottleVerse(int bottles, int init_bottles, char *buf, size_t bufsize);

int main() {
    const int initBottles = 99;
    char *song, *verse;

    // Overestimate the length by one verse
    // (better than underestimating by one byte!)
    int estimatedVerseLen = -bottleVerse(initBottles, initBottles, NULL, 0);
    int bufsize = estimatedVerseLen * (initBottles + 2) + 1;

    if (NULL == (verse = song = malloc(bufsize))) {
        return 1;
    }
    for (int bottles = initBottles; bottles >= 0; bottles--) {
        int len = bottleVerse(bottles, initBottles, verse, bufsize);
        assert(len >= 0);
        verse += len;
        bufsize -= len;
    }
    fputs(song, stdout);
    free(song);
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ In main, you could rename bufsize to versesize to make the code clearer. \$\endgroup\$ – Roland Illig Nov 27 '17 at 7:04

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.