# Find the cheapest order placed out of all of the stores visited - follow-up #3

Made some adjustments to the previous code thanks to the helpful and thoughtful review by @SergeBallesta, @TobySpeight, @G.Sliepen, and @Edward.

Problem statement: This program should ask for the total number of shops that will be visited. At each shop, ask for the number of ingredients that need to be purchases. For each ingredient, ask for the price. Keep track of the total for the order so that you can write it down before leaving the shop. This program should also track with order was the cheapest and which shop the cheapest order was at.

• Code formatting
• Variable declarations moved into smaller scopes, e.g., made loop index variables local to the loops themselves
• Input validation
• Used integers for money instead of floating-point
• Used return instead of exit() if possible
• Eliminated unnecessary arrays as much my ignorance allowed me to
• Avoided size mistakes when allocating by using the sizeof the (pointed) object and not its type
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>

int validate_positive_integer(char *input)
{
char *p;

long result;
result = strtol(input, &p, 10);

while (true)
{
if (input[0] != '\n' && result > 0 && result < 100 && (*p == '\n' || *p == '\0'))
break;

else
{
result = 0;
break;
}
}
return result;
}

int * validate_real_positive(char *input)
{

char *p;
char *q;

long integer_part, fractional_part;

int decimal_index = strcspn(input, ".");

int *arr = (int*)calloc(2, sizeof(arr));

if (!arr)
{
fprintf(stderr, "Memory aldecimal_index failure!\n");
exit(1);
}

while (true)
{
if (decimal_index == 0)
{
fractional_part = strtol(input + 1, &p, 10);

if (input[decimal_index] != '\n' && fractional_part > 0 && fractional_part < 100 && (*p == '\0' || *p == '\n'))
{
*arr = 0;
*(arr + 1) = fractional_part;
break;
}

else
{
*arr = -1;
*(arr + 1) = -1;
break;
}
}

if (decimal_index > 0)
{
integer_part = strtol(input, &p, 10);
fractional_part = strtol(input + (decimal_index + 1), &q, 10);

if (input[0] != '\n' && integer_part >= 0 && integer_part < 10000 && fractional_part >= 0 && fractional_part < 100 && ( (*p == '.') && (*q == '\n') ))
{
*arr = integer_part;
*(arr + 1) = fractional_part;
break;
}

else
{
*arr = -1;
*(arr + 1) = -1;
break;
}
}

else
{
}
}
return arr;
free(arr);
}

{
printf ("%s", prompt);

char line[100];

int positive_integer;
positive_integer = 0;

while (positive_integer == 0)
{
fgets(line, sizeof(line), stdin);

positive_integer = validate_positive_integer(line);
}
return positive_integer;
free(line);
}

{
printf ("%s", prompt);

int *arr = (int*)calloc(2, sizeof(arr));

if (!arr)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

char line[100];

int integer_part;
int fractional_part;

integer_part = -1;
fractional_part = -1;

while (integer_part == -1 || fractional_part == -1)
{
fgets (line, sizeof(line), stdin);

arr = validate_real_positive(line);

integer_part = arr[0];
fractional_part = arr[1];
}
return arr;
free(arr);
}

int *find_minimum(int *arr)
{
int minimum_integer_part = arr[0];
int minimum_fractional_part = arr[1];

int minimum_index = 1;
int size_index = 0;

int count = 5;
while (true)
{
if (arr[count] == '*')
{
size_index = count - 1;
break;
}
count++;
}

int size = arr[size_index];
int len = ((size - 2)/2) - 1;

size = ((size - 2)/2) + len;

int *arr_return = (int*)calloc(size, sizeof(arr_return));

if (!arr_return)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

arr_return[size - 2] = size;
arr_return[size - 1] = '*';

int *minimum_indices = (int*)calloc(len, sizeof(minimum_indices));

if (!minimum_indices)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

for (int m = 1; m < size - len; m++)
{
if ( ( (m & 1) != 0 )  && (m + 2 < (size + 1)/2) )
{
if ( (arr[m + 1] == minimum_integer_part) && (arr[m + 2] == minimum_fractional_part) )
minimum_indices[m - 1] = m + 1;
else
{
if ( (arr[m + 1] <= minimum_integer_part) && (arr[m + 2] < minimum_fractional_part) )
{
minimum_integer_part = arr[m + 1];
minimum_fractional_part = arr[m + 2];
minimum_index = m + 1;
}
}
}

if ( ( (m & 1) != 0 )  && (m + 2  >= (size + 1)/2) )
{
if ( (arr[m + 3] == minimum_integer_part) && (arr[m + 4] == minimum_fractional_part) )
minimum_indices[m - 1] = m + 1;
else
{
if ( (arr[m + 3] <= minimum_integer_part) && (arr[m + 4] < minimum_fractional_part) )
{
minimum_integer_part = arr[m + 1];
minimum_fractional_part = arr[m + 2];
minimum_index = m + 1;
}
}
}

if ( ( (m & 1) == 0 ) && (m + 2 < (size + 1)/2) )
{
if ( (arr[m + 2] == arr[m]) &&  (arr[m + 3] == arr[m + 1]) )
minimum_indices[m - 1] = m + 1;
else
{
if ( (arr[m + 2] <= minimum_integer_part) &&  (arr[m + 3] < minimum_fractional_part) )
{
minimum_integer_part = arr[m + 2];
minimum_fractional_part = arr[m + 3];
minimum_index = m;
}
}
}

if ( ( (m & 1) == 0 ) && (m + 2 >= (size + 1)/2) )
{
if ( (arr[m + 4] == minimum_integer_part) && (arr[m + 5] == minimum_fractional_part) )
minimum_indices[m - 1] = m + 1;
else
{
if ( (arr[m + 4] <= minimum_integer_part) && (arr[m + 5] < minimum_fractional_part) )
{
minimum_integer_part = arr[m + 2];
minimum_fractional_part = arr[m + 3];
minimum_index = m;
}
}
}
}

*arr_return = minimum_integer_part;
*(arr_return + 1) = minimum_fractional_part;
*(arr_return + 2) = minimum_index;

for (int i = 0; i < len; i++)
{
if (minimum_indices[i] != 0)
*(arr_return + (i + 3)) = minimum_indices[i];
}

for (int j = size - 1; j > 4; j--)
{
if (arr_return[j - 2] == 0)
{
arr_return[j - 2] = arr_return[j - 1];
arr_return[j - 1] = arr_return[j];
if (j == (size - 1))
arr_return[j] = 0;
if (j < size - 1)
{
arr_return[j] = arr_return[j + 1];
arr_return[j + 1] = 0;
}
}
}

count = 4;
while (true)
{
if (arr_return[count] == '*')
{
size = count + 1;
break;
}
count++;
}

*(arr_return + (size - 2)) = size;
return arr_return;

free(arr_return);
free(minimum_indices);
}

int *find_cheapest_order (const char *prompt)
{
printf ("%s", prompt);

int *arr = (int*)calloc(2, sizeof(arr));

if (!arr)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

int *arr_sum = (int*)calloc(2*num_shops + 2, sizeof(arr_sum));
if (!arr_sum)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

*(arr_sum + (2*num_shops)) = 2*num_shops + 2;
*(arr_sum + (2*num_shops + 1)) = '*';

int *arr_return = (int*)calloc(num_shops + 4, sizeof(arr_return));

if (!arr_return)
{
fprintf(stderr, "Memory allocation failure!\n");
exit(1);
}

for (int i = 0; i < num_shops; i++)
{
printf("You are at shop #%d.\n", i + 1);

int num_ingredients = read_positive_integer("How many ingredients are needed? ");

for (int j = 0; j < num_ingredients; j++)
{
printf("What is the cost of ingredient %d", j + 1);
*(arr_sum + 2*i) += *arr;
*(arr_sum + (2*i + 1)) += *(arr + 1);
}

if (num_shops == 1)
{
*arr_return = 1;
*(arr_return + 1) = arr_sum[0] + arr_sum[1]/100;
*(arr_return + 2) = arr_sum[1]%100;
break;
}

if ( (arr_sum[(2*i + 1)]%100) == 0 )
printf("The total cost at shop #%d is $%d.00\n", i + 1, arr_sum[2*i] + arr_sum[(2*i + 1)]/100); else printf("The total cost at shop #%d is$%d.%d.\n", i + 1, arr_sum[2*i] + arr_sum[(2*i + 1)]/100, arr_sum[(2*i + 1)]%100);

if (i == num_shops - 1)
{
arr_return = find_minimum(arr_sum);
}
}
return arr_return;

free(arr);
free(arr_sum);
free(arr_return);
}

int main (void)
{
int *cheapest_order = find_cheapest_order("How many shops to visit? ");

int size_location = 0;
int count = 4;

while (true)
{
if (cheapest_order[count] == '*')
{
size_location = count - 1;
break;
}
count++;
}

int size = cheapest_order[size_location];
int minimum_indices_len = size - 5;

int minimum_indices[minimum_indices_len];

if (size > (size - minimum_indices_len))
{
for (int m = 0; m < minimum_indices_len;  m++)
{
minimum_indices[m] = cheapest_order[m + 3];
}
}

if (cheapest_order[1] == 0)
{
printf("The cheapest order(s) were at shop(s) #%d,", cheapest_order[2]);

if (size > (size - minimum_indices_len))
{
for (int i = 0; i < minimum_indices_len; i++)
{
if ( i == minimum_indices_len - 1)
{
printf(" and #%d,", minimum_indices[i]);
}
else
printf(" #%d,", minimum_indices[i]);
}
}
printf(" The total cost of the cheapest order was $%d.00.", cheapest_order[0]); } else { printf("The cheapest order(s) was/were at shop(s) #%d,", cheapest_order[2]); if (size > (size - minimum_indices_len)) { for (int i = 0; i < minimum_indices_len; i++) { if (i == minimum_indices_len - 1) { printf(" shop #%d.", minimum_indices[i]); } else printf(" #%d,", minimum_indices[i]); } } printf(" The total cost of the cheapest order was$%d.%d.", cheapest_order[0], cheapest_order[1]);
}
return 0;
}


There is much more to OP's code to review - I only took time for this.

Do not free memory that was not allocated

Even though code is hiding after a return, just delete this code.

char line[100];
...
return positive_integer;

// Delete the following
free(line);


while not needed if there is no looping

  // A loop is not possible as loop breaks in all cases.
while (true) {
if (input[0] != '\n' && result > 0 && result < 100 && (*p == '\n' || *p == '\0'))
break;
else {
result = 0;
break;
}
}
return result;
}


Whoa there, that's a lot of code for such a simple problem.

As a reader I don't understand what arr in find_minimum is and what each of its elements means. You as the author must document this since it is by no means obvious from the code. It's as if I gave you a sheet of paper, and instead of saying "hey, look at this nice story I wrote" I would say "hey, I have printed a number of digits for you".

I also don't understand the count = 5 in the same function. There is no 5 mentioned in the problem statement, and having a 5 there just doesn't make any sense. Therefore it is a magic number. Same for the '*'.

Instead of an int array, you should use a struct for your data. For example:

typedef struct {
int     dollars;
int     cents;
} money;

typedef struct {
int     number_of_shops;
int     current_shop_no;
money   cheapest_shop;
} shops_data;


Then you can write shops_data.cheapest_shop.dollars instead of the cryptic arr[m + 4].

Still in find_minimum, there are four large blocks of cryptic calculations that look very similar, but I have no chance of understanding them since they all access the mysterious arr variable. I also don't see at first glance why you need four very similar blocks. That's just not included in the problem statement.

To get you started, I wrote the code for entering and validating a monetary amount. I had to fiddle quite a long time with the "magic" string for sscanf, so don't worry if it's hard to read. The scanf family of functions is powerful for extracting data from strings, but also easy to get wrong.

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

typedef struct {
int dollars;
int cents;
} money;

static int in_cents(money m) {
return 100 * m.dollars + m.cents;
}

static int prompt_int(const char *prompt, int min, int max) {
char line[100];

while (printf("%s: ", prompt) != -1 && fgets(line, sizeof line, stdin) != NULL) {
int num;
char end;

if (sscanf(line, "%d %c", &num, &end) != 1) {
fprintf(stderr, "error: Please enter a whole number.\n");

} else if (num < min) {
fprintf(stderr, "error: The number must be at least %d.\n", min);

} else if (num > max) {
fprintf(stderr, "error: The number must be at most %d.\n", max);

} else {
return num;
}
}

exit(0);
}

static money prompt_money(const char *prompt, money min, money max) {
char line[100];

while (printf("%s: ", prompt) != -1 && fgets(line, sizeof line, stdin) != NULL) {
money amount;
char ten_cents[2], one_cent[2], end;

if (sscanf(line, "%d.%1[0123456789]%1[0123456789] %c",
&amount.dollars, ten_cents, one_cent, &end) != 3) {

fprintf(stderr, "error: Please enter a monetary amount (such as 5.24).\n");
continue;
}

amount.cents = 10 * (ten_cents[0] - '0') + (one_cent[0] - '0');

if (in_cents(amount) < in_cents(min)) {
fprintf(stderr, "error: The amount must be at least %d.%02d.\n", min.dollars, min.cents);

} else if (in_cents(amount) > in_cents(max)) {
fprintf(stderr, "error: The number must be at most %d.%02d.\n", max.dollars, max.cents);

} else {
return amount;
}
}

exit(0);
}

int main(int argc, char **argv) {
while (true) {
int count = prompt_int("How many shops? ", 1, 100);
printf("Got %d shops.\n", count);

money amount = prompt_money("Please enter an amount", (money) {0, 0}, (money) {100, 0});
printf("You entered %d.%02d.\n", amount.dollars, amount.cents);
}
}

• Not Magic. I know for sure, that if arr_sums goes into that function, it will have at least 4 elements because otherwise you only have 1 store. so 2 stores at minimum = arr_sum = { {first int}, {first fract}, {second int}, {second frac}, {size}, {} }. Thefore, if I'm searching for '", start at element 5 =) I'll read the rest later I'm finishing up at work, but thank you! Oct 14, 2018 at 7:18
• Because I'm passing pointers from function to function, I can't know the size of arrays at the other end, so I put 'size' at the second to last element, and '' at the last element of my dynamic allocated memory, and then searched for '' so I can find the size at one element down from it Oct 14, 2018 at 7:28
• Inside find_min, one block finds not only the minimum, but also if there are more than 1 minimum. The other blocks removes any zero element between the minimum value and the size of the array and only keeps the indicex of any other shop with the same min value. If there arent any, it simply returns an array of 5 elements with the first three elements containing [min_int][min_frac][index to store with min cost] and the last two been the [size of the array][*]. In between those there can only be at most num_shops - 1 elements. Oct 14, 2018 at 7:33
• Regarding the special * value: did you test what happens if you have 42 ingredients in one of the shops, or if you buy something for 42.42 money? That might lead to wrong results because 42 is exactly the Unicode code point for *. Oct 14, 2018 at 9:14
• printf("%s: ", prompt) && is strange. Why test the return value of printf() for non-zero-ness? printf("%s: ", prompt) > 0 && or printf("%s: ", prompt), might make sense. Robust code would print, flush and then get. Oct 14, 2018 at 18:25

Here's a bug:

    int *arr = (int*)calloc(2, sizeof(arr));


You probably meant

    int *arr = calloc(2, sizeof *arr);


There's no need for the cast, and you meant to use the size of *arr rather than the size of the pointer. This error is repeated throughout the code.

But really, there's no need for all this memory allocation at all. We don't need to retain the individual item prices from every shop we visit; just keep a running track of the cheapest one. Consider this version as a much simpler starting point:

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

/* Read a positive number from stdin */
/* Returns zero on failure */
{
do {
if (printf("%s ", prompt) < 0) { return 0; }
fflush(stdout);

char line[12];
if (!fgets(line, sizeof line, stdin)) {
return 0;
}

if (line[0] != '\0' && line[strlen(line) - 1] != '\n') {
/* consume rest of line that didn't fit in buffer */
scanf("%*[^\n]");
getchar();          /* and the newline */
} else {
unsigned int n;
char last;
int items_read = sscanf(line, "%u%c", &n, &last);
if (items_read == 2  &&  last == '\n') {
return n;
}
}
puts("You must enter a positive number!");
} while (true);
}

/* Read a positive price from stdin */
/* Returns zero on failure */
{
/* if your currency isn't subdivided into hundredths,
change these values */
static const int decimal_places = 2;
static const unsigned int multiplier = 100;

do {
if (printf("%s ", prompt) < 0) { return 0; }
fflush(stdout);

char line[32];
if (!fgets(line, sizeof line, stdin)) {
return 0;
}

if (line[0] != '\0' && line[strlen(line) - 1] != '\n') {
/* consume rest of line that didn't fit in buffer */
scanf("%*[^\n]");
getchar();          /* and the newline */
} else {
int dot_pos, end_pos;
char last;
/* check format first */
if (sscanf(line, "%*9u.%n%*2[0-9]%n%c", &dot_pos, &end_pos, &last) == 1
&& dot_pos + decimal_places == end_pos
&& last == '\n')
{
unsigned int pounds, pence;
if (sscanf(line, "%u.%u", &pounds, &pence) == 2)
{
/* valid input; exit the loop */
return pounds * multiplier + pence;
}
}
}

puts("You must enter a valid amount!");
} while (true);
}

int main()
{
unsigned shop_count = read_count("How many shops to visit?");
if (!shop_count) { return 1; } /* I/O failure */

unsigned cheapest_shop = 0;
unsigned cheapest_order = UINT_MAX;

for (unsigned i = 0;  i < shop_count;  ++i) {
printf("Now visiting shop %u\n", i);
unsigned item_count = read_count("How many ingredients from this shop?");
if (!item_count)  { return 1; } /* I/O failure */
puts("Enter prices of ingredients");
unsigned order_cost = 0;
for (unsigned j = 0;  j < item_count;  ++j) {
if (!item_cost) { return 1; } /* I/O failure */
order_cost += item_cost;
}
if (order_cost < cheapest_order) {
cheapest_shop = i;
cheapest_order = order_cost;
}
}

printf("The cheapest order was %u.%02u, at shop %u.\n",
cheapest_order / 100, cheapest_order % 100, cheapest_shop);
}


There's no dynamic memory allocation at all there - let's keep it simple!

• I would use fgets() and scan it for textually correctness (e.g. "%9[0-9]%n.%2[0-9]%n"), and then numerically convert. Oct 18, 2018 at 15:34
• That makes sense - edited to be more robust. Oct 18, 2018 at 16:16
• Watch out reading pathological strings that begin with a null character - ub with 'strlen- 1'. Could instead use strcspn Oct 19, 2018 at 18:15
• Thanks @chux; fixed. I/O is always hard in C! Oct 22, 2018 at 7:51