5
\$\begingroup\$

Challenge

Given two strings, determine if the second string is a rotation of the first.

Specifications

  1. The first argument is a path to a file.
  2. The file contains multiple lines.
  3. Each line is a test case represented by two comma separated strings.
  4. For each test case print out True/False if the second string is a rotation of the first.

Sample Input

Code,deCo
Review,wRevie
testcase,casetoast

Sample Output

True
True
False

Source

My solution

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

#define LINE_LENGTH 64

char* str_mul(char* str, int times) {
    char *string_multiplied = malloc(sizeof(str) * times + 1);
    for (int i = 1; i <= times; i++) {
        strcat(string_multiplied, str);
    }
    return string_multiplied;   
}

bool is_rotated(char *original, char *test_case) {
    int original_length = strlen(original);
    char *rotation_superset = str_mul(original, 2);
    bool is_substring = strstr(rotation_superset, test_case) != NULL;
    return original_length == strlen(test_case) && is_substring;
}

char* parse_and_evaluate(char *line) {
    const char tokens[] = ",\n\r";
    char *original = strtok(line, tokens);
    char *test_case = strtok(NULL, tokens);
    return is_rotated(original, test_case) ? "True" : "False";
}

int main(int argc, char *args[]) {
    if (argc < 2) {
        fprintf(stderr, "File path not provided. Exiting...\n");
        return 1;
    }

    if (argc > 2) {
        puts("Excessive arguments, only the first will be considered.");
    }

    FILE *file = fopen(args[1], "r");
    if (file == NULL) {
        perror("Error");
        return 1;
    }

    char line[LINE_LENGTH];
    while (fgets(line, LINE_LENGTH, file)) {
        printf("%s\n", parse_and_evaluate(line));
    }

    fclose(file);
}
\$\endgroup\$
5
\$\begingroup\$

You're bleeding memory for every line in the file. This is probably ok for the challenge, however it's a good idea to get into the habit of cleaning up after yourself.

The call to malloc in str_mul needs to have a corresponding free call somewhere to release the memory. Looking at your program in it's current state, the easiest way to do that is probably in the is_rotated method like so:

bool is_rotated(char *original, char *test_case) {
    int original_length = strlen(original);
    char *rotation_superset = str_mul(original, 2);
    bool is_substring = strstr(rotation_superset, test_case) != NULL;
    free(rotation_superset);
    return original_length == strlen(test_case) && is_substring;
}

I'd be tempted to actually move the malloc into the same method and pass the buffer into the str_mul method so that the allocation and release are at the same level. This would also allow you to simply declare a local on the stack in is_rotated, rather than needing to use malloc:

void str_mul(char* str, char *string_multiplied, int times) {
    string_multiplied[0] = '\0';
    for (int i = 1; i <= times; i++) {
        strcat(string_multiplied, str);
    }
}

bool is_rotated(char *original, char *test_case) {
    int original_length = strlen(original);
    char rotation_superset[LINE_LENGTH*2];
    str_mul(original, rotation_superset, 2);
    bool is_substring = strstr(rotation_superset, test_case) != NULL;
    return original_length == strlen(test_case) && is_substring;
}

malloc Vs calloc

malloc isn't guaranteed to return zero initialized memory. Since you're using strcat to append to the buffer, you should really ensure that the memory is a null terminated array. You can either do that by initially null terminating it (as in my example above), or by using calloc instead.

\$\endgroup\$
  • \$\begingroup\$ char rotation_superset[LINE_LENGTH*2]; --> char rotation_superset[LINE_LENGTH*2 + 1]; \$\endgroup\$ – chux Sep 22 '16 at 12:43
  • \$\begingroup\$ @chux the original contains a maximum string of LINE_LENGTH - 1 (it already contains a null terminator from the fgets call). str_mul copies the string into the buffer twice, so really we need (LINE_LENGTH - 1)*2 + 1 or (LINE_LENGTH * 2) - 1, but (LINE_LENGTH*2) seemed close enough. Am I missing something? \$\endgroup\$ – forsvarir Sep 22 '16 at 13:02
  • \$\begingroup\$ My error, thought code was char rotation_superset[original_length*2]; (a VLA). but I see this answer well uses the macro LINE_LENGTH. Part of the source of my error was OP using ...LENGTH when ....SIZE better matches. ...LENGTH with string code hints at the length of a string, not its size. \$\endgroup\$ – chux Sep 22 '16 at 13:36
3
\$\begingroup\$

In addition to @forsvarir good answer:

Code is broken

str is a pointer. malloc(sizeof(str) * times + 1); allocates memory for a bunch of pointers

char* str_mul(char* str, int times) {

    // bad
    // char *string_multiplied = malloc(sizeof(str) * times + 1);

    // Corrected
    size_t len = strlen(str);
    char *string_multiplied = malloc(len * times + 1);
    string_multiplied[0] = '\0';  // also null character terminate

    for (int i = 1; i <= times; i++) {
        strcat(string_multiplied, str);
    }
...

Efficiency, do string length compare test original_length == strlen(test_case) first. With mis-matched lengths, call to str_mul() not needed.

\$\endgroup\$

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.