Did you twist my words?

Question

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);
}

Answer 1

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.

Answer 2

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.