C the large print

Question

This is the Longest lines challenge from CodeEval:

Challenge

Write a program which reads a file and outputs a specified number of lines, sorted on length in descending order.

Specifications

1. The first argument is a path to a file.
2. The file contains multiple lines.
3. The first line indicates the number of lines to output.
4. The following lines are of differing lengths and presented randomly.
5. Print the specified number of lines in descending order of length.

Constraints

1. The number in the first line is a valid positive integer.
2. The input file is correctly formatted.

Sample Input

3  
Longest Lines Challenge
Hodor
Code Review is incredible  
Test Cases are difficult to write  
Hello World
Simple Overlord

Sample Output

Test Cases are difficult to write  
Code Review is incredible  
Longest Lines Challenge

My solution:

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

#define LINE_BUFFER 128

void initialize(char lines_to_print[][LINE_BUFFER], int number_of_lines, FILE *file) {
    for (int i = 0; i < number_of_lines; i++) {
        fgets(lines_to_print[i], LINE_BUFFER, file);
    }
}

int compare(const void *first_line, const void *second_line) {
    size_t first_line_length = strlen(first_line);
    size_t second_line_length = strlen(second_line);
    // Descending order
    return first_line_length < second_line_length;
}

void sort_lines(char lines_to_print[][LINE_BUFFER], int number_of_lines) {
    qsort(lines_to_print, number_of_lines, LINE_BUFFER, compare);
}

void print_lines(char lines_to_print[][LINE_BUFFER], int number_of_lines) {
    for (int i = 0; i < number_of_lines; i++) {
        fputs(lines_to_print[i], stdout);
    }
}

int main(int argc, const char * argv[]) {
    FILE *file;
    if (argc < 2 || !(file = fopen(argv[1], "r"))) {
        puts("No argument provided / File not found.");
        return 1;
    }

    file = fopen(argv[1], "r");
    char line[LINE_BUFFER];
    fgets(line, LINE_BUFFER, file);
    int number_of_lines = atoi(line);

    char lines_to_print[number_of_lines][LINE_BUFFER];
    initialize(lines_to_print, number_of_lines, file);
    sort_lines(lines_to_print, number_of_lines);

    int end = number_of_lines - 1;
    int shortest_long_line_length = strlen(lines_to_print[end]);
    int line_length;
    while (fgets(line, LINE_BUFFER, file)) {
        if ((line_length = strlen(line)) > shortest_long_line_length) {
            strcpy(lines_to_print[end], line);
            sort_lines(lines_to_print, number_of_lines);
            shortest_long_line_length = strlen(lines_to_print[end]);
        }
    }

    print_lines(lines_to_print, number_of_lines);
    return 0;
}

Answer 1

Algorithm

Let's redo our processing a bit, shall we? Let's read the file line by line, parse the necessary data, and then process that data for optimal speed. You should only need two for loops in this code, one to parse input and one to output data.

• In order to do this, lets create a struct that contains two members, the string from the file and the length of the line. We want to store the string so we don't have to go back into our file and try to seek the line we need, and the length we are going to store for fewer calls overall to strlen().

• Use a for loop to parse all this data quickly. We compute the length in place to speed up future comparisons:

  for(size_t i = 0; fgets(buf, MAX_LINE_LENGTH, file); ++i) 
  {
      lineData[i].str = strdup(buf);
      lineData[i].len = strlen(buf) - 1;  // lose the newline
  }
  

• Now we have all the data we need. Let's sort our data, as you do! But we are going to have to rework the callback function qsort() uses to sort based on that lineData.len member from above.

• Now that we have a sorted array, we can loop over the array with a for loop and use the counter variable to access the first items in the array up until that specified number input at the beginning.

Miscellaneous

• Don't abstract too much. I don't think you need a separate method like sort_lines().

• On the other hand, you could move more of your processing outside of main(). Parse the command line arguments if there are any and then call another function to handle the rest.

• Don't forget to close your file (although this might add time to your program).

• You don't have to return 0 at the end of main(). The C standard knows how frequently this is used, and lets us omit it.

  C99 & C11 §5.1.2.2(3)

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

Answer 2

In addition to syb0rg (nice idea of having separate struct for lines)

Limitations

You're presuming, that the line is not going to be longer than 128 symbols. 126. Both, \n and \0 is stored in the buffer as well. Also, it fails if the number of lines to print is bigger than number of actual lines of text.

Hygiene

You're not closing input file after successfully reading it. Why are You repeating Yourself? strlen() on each qsort() iteration? Another strlen() in the main loop?

In general, constructs like this:

if (argc < 2 || !(file = fopen(argv[1], "r"))) {
    puts("No argument provided / File not found.");
    return 1;
}

does not look neither nice, nor readable at all. But yeah, that's just a quick code for competition.

Idea

Why not just mmap() the file in question and sort its index by length of lines? You'll save some IO, memory space, the code is going to be shorter and, I presume, faster. And for the structure You're only gonna save the length of line and the index.