# “Restaurant” HackerRank challenge in C

I don't write C all that often, so things to look for would be memory leaks and such. I also recognize that I'm not validating the user input as well as I could - I could use some feedback on how I might do better at that with this particular problem. I'm interested in hearing everything you find wrong with this code, however.

The problem, in so many words, is, given a list of dimensions for rectangular bread slices, what's the fewest number of pieces I could make to divide up each slice into perfect squares without wasting any bread (0 cuts being 1 piece).

Input should look like:

2
2 2
6 9


where the first line provides the number of bread slices, and the subsequent lines provide the length and width of each slice.

Output:

1
6


Original problem description

Note: I'm aware I could have used Lehmer's or the Euclidean methods for finding the GCD, but I wanted to implement the problem this way first just for the challenge of writing the brute force implementation. Other than alternative GCD algorithms, though, I would be interested in any opportunities found for performance improvement.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <stdarg.h>

void free_2d_array(int** arr) {
int i = 0;
while (arr[i]) {
free(arr[i]);
i++;
}
free(arr[i]);

free(arr);
}

void flag_error(char msg[]) {
puts(msg);
exit(EXIT_FAILURE);
}

// Gets the number of slices for this test according to the first input value from stdin.
int num_slices = 0;

scanf("%i", &num_slices);

if (num_slices == 0) {
goto error;
}

return num_slices;

error:
flag_error("ERROR: Could not parse the number of entries from first input line.");
return 1;
}

// Gets a single line from stdin and attempts to parse it into a 2D int array representing the dimensions of a slice.
//  Returns [0,0] on error.
static int loaf_dimension = {0};

scanf("%i %i", &loaf_dimension, &loaf_dimension);

return loaf_dimension;
}

// Gets all of the bread slices to be processed.
//
// This function reads from stdin.  The first line should be a single integer that specifies the number of slices to be
// processed by this current test.  The subsequent lines should be two integers separated by a space which represent
// the 2D dimensions of each slice.
//
// The last dimension pair in the array will always be [0,0] so that it is easy to find the end of it.
int** get_slices() {
static int** slices;
slices = (int**) malloc((num_slices + 1) * sizeof(int*));

int i;
for (i = 0; i < num_slices; i++) {
slices[i] = (int*) calloc(2, sizeof(int));

// If there was an error, set the last element to {0,0} to set the stopping point for the free function, then
// gracefully exit.
if (!(slices[i] && slices[i])) {
slices[i] = 0;
slices[i] = 0;
goto error;
}
}

// [0,0] terminate the array so that one can find the end without calculating the length.
slices[i] = (int*) calloc(2, sizeof(int));

return slices;

error:
free_2d_array(slices);
flag_error("ERROR: Could not parse line entered into a 2 integer array representing the slice's dimensions.");
return NULL;
}

int next_square(int index, int num_elems) {
int num = num_elems - index;
return num * num;
}

bool is_perfect_slice_dimension(int square, int slice) {
int area = slice * slice;
int num = sqrt(square);

return !((area % square) || (slice % num) || (slice % num));
}

int find_largest_square(int slice_dimension) {
int num_squares = slice_dimension < slice_dimension ? slice_dimension : slice_dimension;

int i;
for (i = 0; i < num_squares; i++) {
int square = next_square(i, num_squares);
if (is_perfect_slice_dimension(square, slice_dimension)) {
return square;
}
}

// if we get here, there was an error.
return -1;
}

int find_min_number_of_slices(int slice_dimension) {
int num_slices = 0;
if (slice_dimension == slice_dimension) {
num_slices = 1;
} else {
int area = slice_dimension * slice_dimension;
num_slices = area / find_largest_square(slice_dimension);
}

return num_slices;
}

int main() {
int** slices = get_slices();

int i = 0;
while (slices[i]) {
printf("%i\n", find_min_number_of_slices(slices[i]));
i++;
}

free_2d_array(slices);

return 0;
}

• Just as an update, I'm still watching this for an answer and will choose a correct answer no later than 40 days after first posting of this question (timeline depends some on when I get an answer). – Josiah Dec 18 '14 at 16:04

# Profiling & Testing Your Approach

• Valgrind test:

$valgrind ./original ==43831== Memcheck, a memory error detector ==43831== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==43831== Using Valgrind-3.11.0.SVN and LibVEX; rerun with -h for copyright info ==43831== Command: ./original ==43831== --43831-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option --43831-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 2 times) --43831-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 4 times) 2 2 2 6 9 ==43831== Conditional jump or move depends on uninitialised value(s) ==43831== at 0x1003FBC3F: _platform_memchr$VARIANT$Haswell (in /usr/lib/system/libsystem_platform.dylib) ==43831== by 0x1001EFBB6: __sfvwrite (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x1001FA005: __vfprintf (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x10021F9CE: __v2printf (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x10021FCA0: __xvprintf (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x1001F5B91: vfprintf_l (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x1001F39F7: printf (in /usr/lib/system/libsystem_c.dylib) ==43831== by 0x100000E27: main (main.c:132) ==43831== 1 6 ==43831== ==43831== HEAP SUMMARY: ==43831== in use at exit: 43,127 bytes in 427 blocks ==43831== total heap usage: 512 allocs, 85 frees, 49,319 bytes allocated ==43831== ==43831== LEAK SUMMARY: ==43831== definitely lost: 16 bytes in 1 blocks ==43831== indirectly lost: 0 bytes in 0 blocks ==43831== possibly lost: 13,090 bytes in 117 blocks ==43831== still reachable: 30,021 bytes in 309 blocks ==43831== suppressed: 0 bytes in 0 blocks ==43831== Rerun with --leak-check=full to see details of leaked memory ==43831== ==43831== For counts of detected and suppressed errors, rerun with: -v ==43831== Use --track-origins=yes to see where uninitialised values come from ==43831== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)  Now, Valgrind is not just a leak checker. It can give us a lot of useful insights into your program and how it's working internally. For instance, you see this little snippet that Valgrind output after I gave your program some input? It's pointing us to this line in your code: printf("%i\n", find_min_number_of_slices(slices[i]));  We now know that we are possibly accessing the contents of something that is unassigned on this line and that it could result in undefined behavior. My guess to Valgrind's issue with this line has something to do with slices[i], but I can't quite say for sure since I am just starting out with my use of this tool in everyday programming. • Bash time test: $ printf '2\n2 2\n6 9' | time ./original
1
6
1
1925460560
Command terminated abnormally.
0.16 real         0.00 user         0.00 sys


So your program runs pretty fast, but we seemed to have uncovered some sort of strange behavior that causes a segmentation fault in your program.

• You have no need for the stdarg.h heading that you include since you do not accept a variable amount of arguments in any of your functions.

• I notice in some areas that you use while loops instead of for loops, but you still have the counter variable in which you don't use after the loop has concluded.

int i = 0;
while (arr[i]) {
free(arr[i]);
i++;
}
free(arr[i]);
free(arr);


Why was this not written as a for loop?

for (int i = 0; arr[i]; i++)
{
free(arr[i]);
}
free(arr);

• Your flag_error() function declaration accepts a char array, but in your free_2d_array() you accept a double pointer to an int. I would change the flag_error declaration to accept a char pointer instead. Also, since you don't modify this array in any way within the function, it should be declared as a const parameter.

• The goto in your read_num_slices() function is useless. Always try to avoid goto, since it leads to spaghetti code. Rewritten function:

int read_num_slices()
{
int num_slices = 0;

scanf("%i", &num_slices);
if (!num_slices)
{
flag_error("ERROR: Could not parse the number of entries from first input line.");
return -1;
}

return num_slices;
}

• You declare the loaf_dimension variable in your read_slice_dimension() to be static, but do you really want it to retain the values every time you run through the function? My guess is not, so I would remove that identifier.

int loaf_dimension = {};

• In your get_slices() method, merge the declaration and assignment of slices that are on two separate lines into an initialization declaration of one line.

• Again, there is no need for the goto in your get_slices() function.

• Use the pow() function in next_square() since you have included the math.h header anyways and it should be a bit faster.

• Declarer your counter variable whenever you can within the for loop to reduce its scope.

• You don't have to return 0 at the end of main(), just like you wouldn't bother putting return; at the end of a void-returning function. The C standard knows how frequently this is used, and lets you not bother.

C99 & C11 §5.1.2.2(3)

...reaching the } that terminates the main() function returns a value of 0.

• Always declare what parameters your function takes in, even if nothing.

int main(void)


You might wonder why we have to do this. Imagine we have the function foo() declared as such:

int foo()


In C, this is known as an identifier list and means that it "can take any number of parameters of unknown types". We can actually pass values to the function even though we don't mean to or intend to. If the caller calls the function giving it some argument, the behavior is undefined. The stack could become corrupted for example, because the called function expects a different layout when it gains control.

Using identifier lists in function parameters is depreciated. It is much better to do something like:

int foo(void)


In C, this is known as a parameter type list and defines that the function takes zero arguments (and also communicates that when reading it) - like with all cases where the function is declared using a parameter type list, which is called a prototype. If the caller calls the function and gives it some argument, that is an error and the compiler spits out an appropriate error.

The second way of declaring a function has plenty of benefits. One of course is that amount and types of parameters are checked. Another difference is that because the compiler knows the parameter types, it can apply implicit conversions of the arguments to the type of the parameters. If no parameter type list is present, that can't be done, and arguments are converted to promoted types (that is called the default argument promotion). char will become int, for example, while float will become double.

# My Approach

For my approach, I only stored the maximum possible side length for the cut bread dynamically. This helped simplify things down a bit and makes for mess manual "labor" having to be done by me, since I have to manage less memory. I also refined down the algorithm calculating of the maximum possible side length.

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

typedef struct
{
int length;

// simple greatest common divisor algorithm
unsigned int gcd (int a, int b)
{
int c = 0;
while (a)
{
c = a;
a = b % a;
b = c;
}
return b;
}

int main(void)
{
int runs = 0;

// get the number of times input will be entered
scanf("%d", &runs);

// dynamically allocate memory for the number of calculations to be made
int *maxSideLen = malloc(runs * sizeof(int));

// get input, calculate and store the maximum side length
for(int i = 0; i < runs; i++)
{
}

// output maximum side length in separate loop so that it appears after all the input is intaken
for(int i = 0; i < runs; i++)
{
printf("%d\n", *(maxSideLen + i));
}

// cleanup and exit
free(maxSideLen);
}


I could further speed up my approach by implementing a faster GCD algorithm, such as the binary GCD algorithm. If I wanted my program to consume less memory, I could also remove the reusable struct since I only have one declaration of it.

# Profiling & Testing My Approach

• Valgrind test:

$valgrind ./mine ==50350== Memcheck, a memory error detector ==50350== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==50350== Using Valgrind-3.11.0.SVN and LibVEX; rerun with -h for copyright info ==50350== Command: ./mine ==50350== --50350-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option --50350-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 2 times) --50350-- UNKNOWN mach_msg unhandled MACH_SEND_TRAILER option (repeated 4 times) 2 2 2 6 9 ==50350== Conditional jump or move depends on uninitialised value(s) ==50350== at 0x1003FBC3F: _platform_memchr$VARIANT$Haswell (in /usr/lib/system/libsystem_platform.dylib) ==50350== by 0x1001EFBB6: __sfvwrite (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x1001FA005: __vfprintf (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x10021F9CE: __v2printf (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x10021FCA0: __xvprintf (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x1001F5B91: vfprintf_l (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x1001F39F7: printf (in /usr/lib/system/libsystem_c.dylib) ==50350== by 0x100000EFE: main (main.c:44) ==50350== 1 6 ==50350== ==50350== HEAP SUMMARY: ==50350== in use at exit: 43,127 bytes in 427 blocks ==50350== total heap usage: 509 allocs, 82 frees, 49,279 bytes allocated ==50350== ==50350== LEAK SUMMARY: ==50350== definitely lost: 16 bytes in 1 blocks ==50350== indirectly lost: 0 bytes in 0 blocks ==50350== possibly lost: 13,090 bytes in 117 blocks ==50350== still reachable: 30,021 bytes in 309 blocks ==50350== suppressed: 0 bytes in 0 blocks ==50350== Rerun with --leak-check=full to see details of leaked memory ==50350== ==50350== For counts of detected and suppressed errors, rerun with: -v ==50350== Use --track-origins=yes to see where uninitialised values come from ==50350== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)  I find these results curious, since I get roughly the same output from Valgrind that you did. I'll have to do some more digging to really understand why Valgrind is saying that I'm depending on uninitialised value(s). • Bash time test: $ printf '2\n2 2\n6 9' | time ./mine
1
6
0.00 real         0.00 user         0.00 sys


As you can see, my code performs faster than your method. This is probably due to my calculations having a complexity of $O \left( 1 \right)$ time to your complexity of $O \left( n^2 \right)$ (someone correct me if I'm wrong on this). Also notice that my program doesn't exhibit any strange behavior, like your program did.

• Good point about foo() versus foo(void). I program more often in C++ than in C and forget about that one. – Edward Dec 25 '14 at 19:36
• The valgrind messages you're getting are pointing to a problem within the Mac OS (or more precisely within the associated libraries), and not within this code. – Edward Dec 25 '14 at 19:43
• @Edward Thanks! I was confused as to why I was getting that little snippet from Valgrind – syb0rg Dec 25 '14 at 19:45
• I appreciate all the feedback. valgrind is a useful tool I now have in my arsenal, so that's great, plus the other feedback was also excellent. However, 2 things. 1, you implemented the Euclidean GCD algorithm in your example - I already explained in the OP why I didn't use it (better practice with C), 2, I used while loops so I could null-terminate my arrays. Using your method, I would get an index out of bounds error because C would not know when to stop iterating. – Josiah Jan 4 '15 at 3:46
• @Josiah I saw in the OP why you didn't use the GCD method, but ultimately the idea here on Code Review is to create the most efficient and beautiful code possible which is why I implemented it in my answer. As for your while() loops, I don't see any loops that are used so you can terminate your arrays at the end. I see a while loop that is used to free an array and one that prints out data. My for loop transformation of these doesn't result in an array-indexing error. – syb0rg Jan 4 '15 at 19:02

## free_2d_array

In your code you have the following function to free your array

void free_2d_array(int** arr) {
int i = 0;
while (arr[i]) {
free(arr[i]);
i++;
}
free(arr[i]);

free(arr);
}


I find it a bit dangerously written, your while condition dereferences the pointer and checks whether it points to \0. But it would be arguably better just setting the array pointer to NULL when you allocate it in get_slices. Then you could just do while (arr[i] != NULL) instead of adding some extra memory that is not really used. I would write it as a for-loop instead since you have a variable you increment for each iteration.

The read_num_slices function that have written to take user input uses a scanf to read the number, what it does not do is to remove the additional \n that is in the buffer from the user. So it may happen that you can get some problems with this. Personally I find using fgets together with sscanf to be a better way to read user input. That way there is no risk of stack overflow and you still have the convenience of scanf parsing.

Remove the goto from the function, there is no reason to have a goto there, a simple if statement should handle the case if 0 slices is entered - you should check for negative values as well. e.g.

// this handles if user presses enter without writing a number,
// if an invalid char/string was entered or the value is out of range.
char line;

if ( fgets( line, sizeof(line), stdin) != NULL )
{
if (sscanf( line, "%i", &num_slices ) == 1)
{
if (num_slices < 1)
{
flag_error(...);
return -1;
}
else
{
return num_slices;
}
}
else
{
flag_error("enter a value larger than 0" );
return -2;
}
return 0; // no input
}


sidenote: when you declare functions that do not take parameters, write void as argument. In C when you write e.g. read_num_slices() it means that the function can take any number of arguments (as opposed to C++). Writing read_num_slices(void) makes it clear it takes no arguments.

## get_slices

There is no reason to declare slices as static, better to have a local variable that you return. You should also check return values of allocations, they may in some cases return NULL so that must be handled.

also again, lose the gotos

generally speaking it is good to check arguments to functions so that they are sane. e.g. with asserts assert(index>=0);

• I missed that good point you made about fgets() and scanf(), +1 – syb0rg Dec 25 '14 at 18:58

## Check the return value of scanf

The current code for read_num_slices uses the value of 0 as a sentinel to detect that an error occurred, but the more straightforward way to do that would be to examine the return value of scanf which returns the number of items successfully parsed.

## Avoid the use of goto

One of the most famous of Edsger Dijkstra's publications was a relatively short letter to the Communications of the ACM titled Go To Statement Considered Harmful which is still worth reading and pondering. In that same vein, I'll note that goto is best avoided when possible for the same reasons as were true in 1968 and a couple more, including cache locality, that did not much affect systems in 1968. With that said here's one possible rewrite of read_num_slices:

int read_num_slices() {
int num_slices = 0;

if (1 == scanf("%i", &num_slices) && num_slices)
return num_slices;

flag_error("ERROR: Could not parse the number of entries from first input line.");
}


This code make a few changes. The first is that we check scanf to see if it returned a value. The next is that the code now ends with flag_error(1) rather than returning 1 since flag_error does not return. If your compiler complains about this (because the function does not return a number in this case) you can either ignore the error or re-insert a dummy return.

## Minimize coupling between functions

Reducing the coupling between modules or functions is usually desirable because it improve readability and simplifies maintenance. It also often has the happy byproduct of running faster, which is of interest to you. With that in mind, the read_slice_dimension() and get_slices routines have an unusual kind of coupling in which the shared data is neither a parameter nor return value but a pointer to a static variable. There is precedent for this even in the standard library (as with the time function) but it is not good practice because it means that the resulting code is not thread-safe. The workaround is to pass in a pointer and to use the return value as an error indicator. One way to rewrite it would be this:

int read_slice_dimension(int loaf_dimension) {
return 2 == scanf("%i %i", &loaf_dimension, &loaf_dimension);
}


with loaf_dimension moved into get_slices and no longer static.

## Always check the return value of malloc or calloc for NULL

The primary way that the system has to alert the program that it has run out of memory is to return NULL from a call to malloc or calloc. You simply must not ignore it when that happens because the result is almost guaranteed to be a crash of your program; possibly a crash of the system depending on operating system. For that reason, you should never simply use the value returned from malloc without first checking to see that it is not NULL.

## Simplify memory allocations

Since both the width (2) and the length (num_slices) is known to the program before any memory allocation calls are done, it would make most sense to simply allocate a single chunk of memory with those dimensions. It would considerably simplify both memory allocation and access. Even better, see the next suggestion.

## Use a struct to better manage data

In a number of places, the code has int slice_dimension as a parameter to a function. Really, this represents not two ints but rather one dimensional pair. We can use it that way by instead using a struct:

typedef struct {
int width;
int height;
} dim_t;


Now we can refer to a dimension type, dim_t throughout the code, making a number of things easier to write and to read.

A rewritten version of the find_min_number_of_slices might look like this:

int find_min_number_of_slices(dim_t *slice_dimension) {
if (slice_dimension->width == slice_dimension->height)
return 1;
int area = slice_dimension->width * slice_dimension->height;
return area / find_largest_square(slice_dimension);
}


## Omit return 0 at the end of main

For over a decade, the C standard has said that getting to the end of main implicitly generates the equivalent of return 0; so it can safely be omitted.

## Use either a sentinel value or the length of array but not both

The main routine contains this code:

int i = 0;
while (slices[i]) {
printf("%i\n", find_min_number_of_slices(slices[i]));
i++;
}


It's looking for the sentinel value of {0,0} at the end of the list, but really, the program already knows the size of the array, and we are already using i anyway, so the program could use the length of the list as a way to know when to finish and skip both the generation and use of the sentinel value.

An alternative approach would simplify main to look like this:

int main() {
dim_t* slices;
int lines = get_slices(&slices);
for (int i = 0; i < lines; ++i) {
printf("%i\n", find_min_number_of_slices(&slices[i]));
}
free(slices);
}


## Use const where possible

Nearly every place in the code that takes slice_dimension as an argument could have taken that argument as const because it doesn't alter the underlying data. Declaring the code that way will help prevent errors that could creep in during program maintenance, so using const where possible is good general practice to follow to write bug-free programs.

## Avoid floating point math

On modern machines, floating point math is very fast, but it remains faster still if you can avoid it. In particular, this code uses sqrt to get the dimension of a square. But it's a square! The code has already calculated the dimension of it, so it really doesn't make sense to multiply the dimensions together and then take the square root. Instead, pass the length rather than the area of the square to is_perfect_slice_dimension.

## Use MIN macro to clean up code

It's very common to define macros for MIN and MAX in C:

#define MIN(a,b) (a < b) ? a : b


However, I'll note that one must be careful with such macros. They cannot be called reliably with arguments with side effects. For example, MIN(x++, ++x) would almost certainly not return anything useful.

## Count down rather than up when it makes sense

Consider this rewritten find_largest_square routine:

int find_largest_square(const dim_t *slice_dim) {
for (int square_dim = MIN(slice_dim->width, slice_dim->height); square_dim; --square_dim) {
if (is_perfect_slice_dimension(square_dim, slice_dim)) {
return square_dim*square_dim;
}
}
// if we get here, there was an error.
return -1;
}


Note that next_square() is no longer needed with this version and it presumes that the sqrt call has been eliminated from is_perfect_slice_dimension as previously mentioned.

• A lot of good points that I missed, +1. – syb0rg Dec 25 '14 at 18:34
• const only exists in c++, right? – Josiah Jan 16 '15 at 17:15
• @Josiah: no, const is also a C keyword. – Edward Jan 16 '15 at 17:24

There is no solution which both satisfies the stated question and generates the sample output.

You asked: "...given a list of dimensions for rectangular bread slices, what's the fewest number of cuts I could make to divide up each slice into perfect squares without wasting any bread"

For the 2 x 2 slice, the correct answer is zero cuts (not 1), because it is already square.

For the 6 x 9 slice, the answer is 3 cuts (not 6), because it takes only 3 cuts to cut the slice into 6 squares.

• In the original problem in the given link, it states that the output will be an integer that denotes the number of squares of maximum size, when the bread is cut as per the given condition. – syb0rg Dec 25 '14 at 6:20
• My bad on the poor wording... – Josiah Jan 4 '15 at 3:30