5
\$\begingroup\$

I need to find minimal date (year, month, day, hours, minutes, seconds).

My code is working, but it looks terrible and it's very long. What can I do to avoid this ladder and make my code readable? (I want to use only <stdio.h>)

#include <stdio.h>
typedef struct DateTime_s {
    int year , month , day ;
    int hours , minutes , seconds ;
} DateTime ;
void DataTime(const DateTime *mas , int x){
    int i;
    struct DateTime_s min={40000,400000,4000000,400000,400000,4000};
    for(i=0;i<x;i++){
        if(mas[i].year<min.year){
            min=mas[i];
        }
        else if(mas[i].year==min.year){
            if(mas[i].month<min.month){
                min=mas[i];
            }
            else if(mas[i].month==min.month){
                if(mas[i].day<min.day){
                    min=mas[i];
                }
                else if(mas[i].day==min.day){
                    if(mas[i].hours<min.hours){
                        min=mas[i];
                    }
                    else if(mas[i].hours==min.hours){
                        if(mas[i].minutes<min.minutes){
                            min=mas[i];
                        }
                        else if(mas[i].minutes==min.minutes){
                            if(mas[i].seconds<min.seconds){
                                min=mas[i];
                            }
                            else if(mas[i].seconds==min.seconds){
                                min=mas[i];
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d %d %d %d %d %d",min.year,min.month,min.day,min.hours,min.minutes,min.seconds);
}

int main() {
    int x,i;
    struct DateTime_s mas[50001];
    scanf("%d",&x);
    for(i=0;i<x;i++){
        struct DateTime_s b;
        scanf("%d %d %d %d %d %d",&b.year, &b.month,&b.day,&b.hours,&b.minutes,&b.seconds);
        mas[i]=b;
    }
    DataTime(mas,x);
    return 0;
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ How were you planning on handling switches to/from Daylight Savings Time or other time zone shenanigans? You may not think this is important now, but I guarantee it will come and bite you at some point. \$\endgroup\$
    – throx
    Commented Dec 22, 2021 at 1:29
  • \$\begingroup\$ Why is the datetime variable called mas? Is that a short form of something? \$\endgroup\$
    – user985366
    Commented Dec 22, 2021 at 10:26

4 Answers 4

9
\$\begingroup\$

Use Helper Functions

Although my coding style hasn’t caught on, I think ternary ? : expressions lend themselves very well to algorithms like this.

const DateTime* DateTime_min( const DateTime* const a,
                              const DateTime* const b )
{
    return (( a->year    > b->year    ) ? b :
            ( b->year    > a->year    ) ? a :
            ( a->month   > b->month   ) ? b :
            ( b->month   > a->month   ) ? a :
            ( a->day     > b->day     ) ? b :
            ( b->day     > a->day     ) ? a :
            ( a->hours   > b->hours   ) ? b :
            ( b->hours   > a->hours   ) ? a :
            ( a->minutes > b->minutes ) ? b :
            ( b->minutes > a->minutes ) ? a :
            ( a->seconds > b->seconds ) ? b :
                                          a
           );
}

I also separate out the code to print a DataTime structure. This version prints in ISO format.

int DateTime_fprint( FILE* const out, const DateTime* const x )
{
    return fprintf( out,
                    "%04d-%02d-%02dT%02d:%02d:%02d",
                    x->year,
                    x->month,
                    x->day,
                    x->hours,
                    x->minutes,
                    x->seconds
                  );
}

This lets your DataTime become:

const DateTime* DataTime( const DateTime *const mas, const size_t n )
{
    const DateTime* min = mas;
    
    for ( const DateTime* p = mas + 1; p < mas + n; ++p ) {
        min = DateTime_min( min, p );
    }
    
    return min;
}

This version returns a pointer to the minimal element, which you can pass to the output function, or do other things with.

In C, you could also write the function in C99 style, as

const DateTime* DataTime( const size_t n, const DateTime mas[n] );

In this version of the program, there was no problem returning a const pointer to the minimal element. If you need to be able to modify the minimum element that you find, so that you can either pass in a const array or get a modifiable element, your options include:

  • Write two functions with different names, one of which takes a non-const pointer and the other of which takes a const pointer. (In languages derived from C, this could be an overload with the same name.) The non-const version might call the const version and cast its return value to a non-const pointer. Since the maintainer of this code knows the internal implementation details, they know it’s actually safe, and the library itself can present a type-safe public interface.
  • Accept a const array, but return an argmin value for the index of the minimal element, which you can still use on your modifiable array without violating type safety.
  • Cast the returned element from const DateTime* to (DateTime*), if you know for sure that neither of your inputs was const.

Check for Buffer Overflow

I mean it. Always, always, always bounds check your array access in C. It is a huge security bug to let the user tell you how much data to write into a fixed-size buffer, and not check for buffer overflow.

If nothing else, throw in an assert to crash your program before this happens. This is vastly preferable to dealing with the kind of bugs memory corruption causes.

int main(void)
{
    static DateTime mas[NDATES];
    size_t n = 0;
    
    scanf( "%zu", &n );
    assert( n > 0 && n < NDATES );
    
    for( DateTime* b = mas, *const endp = mas+n; b < endp; ++b ){
        scanf( "%d %d %d %d %d %d",
               &b->year,
               &b->month,
               &b->day,
               &b->hours,
               &b->minutes,
               &b->seconds );
    }
    DateTime_fprint( stdout, DataTime( mas, n ) );    
    fputs( "\n", stdout );
    return EXIT_SUCCESS;
}

Another solution would be to declare mas dynamically, with calloc, once you know the required size. Again, check for overflow, both of the buffer itself and its size parameter.

Avoid Copying Arrays Unnecessarily

There are a few other tweaks to the algorithm here, but the main one was avoiding the extra copy of

mas[i]=b;

inside the initialization loop, which copies every element of the array from memory to memory an extra time. This version instead reads each element into its permanent location in memory.

In the code above, I declare an end pointer to tell the loop when to terminate. This is because neither clang 13.0.0 nor gcc 11.2 is smart enough to figure out that mas+n is a constant when n is not declared const. It’s hard to actually prove that the loop can never change the value of n during its execution. (In fact, there will always be cases where it doesn’t, but no computer program can ever prove it doesn’t.) You’ll notice that, in DataTime, where I declare both the mas and n arguments const, the compiler does not need this hint, and I can just write the termination clause as p < mas+n. It’s a good example of how declaring data const is not just safer, but enables optimizations. (The extra overhead is negligible, though.)

This could be a reason to move the initialization into a separate function, such as

 DateTime_read( mas, n, stdin );

Or to make n a static single assignment with

const size_t n = read_input_size(stdin);

It would also be possible to write the loop to increment a aize_t i value and include, within the loop, the alias

DateTime* const b = &mas[i];

You would then use &b->year, etc. as above. This is basically equivalent, and would make it easier to do multiple things with i within the loop.

ETA:

Peter Cordes in the comments identified the reason that compilers cannot properly optimize your original loop. You have

scanf("%d",&x);
for(i=0;i<x;i++){

Passing &x to scanf made it escape the loop. For all the compiler knows, that external function scanf that it knows nothing about could do anything with &x, such as store it in a global variable and change the value of x whenever you call it again inside your loop.

The overhead here is pretty minimal, but this is another reason you want to write variables as static single assignments, and possibly move loops into helper functions whose parameters can be passed by value or given the restrict qualifier. Either would make it possible for the compiler to deduce that the body of the loop cannot modify its control variable, and better optimize the loop. (My workaround essentially introduced a different static single assignment, but it probably would have been better to write n as one in the first place.)

Avoid Reinventing the Wheel

The <time.h> header has a struct tm that’s very similar to DateTime in this program. It could be used to convert input time strings to timestamps, which can be compared or sorted as integers, and converted back into a human-readable time string for output.

Consider a Different Naming Convention

You named your function DataTime, and I left that unchanged, but I gave all the new functions that manipulate DateTime structures, names like DateTime_min and DateTime_fprint. The name DataTime is not very descriptive of what the function does, and it is easy to confuse with DateTime.

It’s a common convention to give data types and modules names that start with capital letters, and name functions and variables in snake_case or camelCase. I split the difference, treating DateTime_ as a prefix for all the names I added and writing everything after it in snake_case. So pick a convention that you like, and stick with it.

Do at Least a Little Parsing, Maybe

The input format you’re implicitly expecting is used widely for programming-contest problems, and not so much in the real world. With an unformatted soup of numbers as your input, you can’t give useful error messages or recover if your input is badly-formatted.

If you’re not trying to win a programming contest by eliminating as much error-checking as possible, you might consider checking that each date is on its own input line, and checking the return value of scanf() to make sure that each line correctly parsed. That way, if any input line does not correctly parse, you can give an error message with a line number. It would then be possible to find the error in the input file.

Another common idiom is to read a chunk of input into a buffer, and parse that line of input with sscanf.

\$\endgroup\$
1
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – Mast
    Commented Dec 22, 2021 at 14:55
4
\$\begingroup\$

One of the most effective tools at improving readability is functions!

DateTime *min_dt(const DateTime *a, const DateTime *b) {
    if ( a->year    != b->year    ) return (DateTime *)( a->year    < b->year    ? a : b );
    if ( a->month   != b->month   ) return (DateTime *)( a->month   < b->month   ? a : b );
    if ( a->day     != b->day     ) return (DateTime *)( a->day     < b->day     ? a : b );
    if ( a->hours   != b->hours   ) return (DateTime *)( a->hours   < b->hours   ? a : b );
    if ( a->minutes != b->minutes ) return (DateTime *)( a->minutes < b->minutes ? a : b );
    if ( a->seconds != b->seconds ) return (DateTime *)( a->seconds < b->seconds ? a : b );
    return a;
}

void DataTime(const DateTime *mas, size_t n) {
    if (n == 0)
        return;  // Or whatever

    const DateTime *min = &mas[0];
    for (size_t i=1; i<n; ++i)
        min = min_dt(min, &mas[i]);

    // ...
}

Unfortunately, the const removal makes the lines a bit long. But it's required for the function to work with both pointers to constants and pointers to non-constants.[1] The issue could be dodged by returning a boolean or a tri-state value.

int cmp_dt(const DateTime *a, const DateTime *b) {
    if ( a->year    != b->year    ) return a->year    < b->year    ? -1 : +1;
    if ( a->month   != b->month   ) return a->month   < b->month   ? -1 : +1;
    if ( a->day     != b->day     ) return a->day     < b->day     ? -1 : +1;
    if ( a->hours   != b->hours   ) return a->hours   < b->hours   ? -1 : +1;
    if ( a->minutes != b->minutes ) return a->minutes < b->minutes ? -1 : +1;
    if ( a->seconds != b->seconds ) return a->seconds < b->seconds ? -1 : +1;
    return 0;
}

void DataTime(const DateTime *mas, size_t n) {
    if (n == 0)
        return;  // Or whatever

    size_t min_i = 0;
    for (size_t i=1; i<n; ++i) {
        if ( cmp_dt(&mas[min_i], &mas[i]) < 0 ) {
            min_i = i;
        }
    }

    const DateTime *min = &mas[min_i];

    // ...
}

Bonus: This is more reusable! You could use it for a sorting or searching.

Don't worry about performance. Under -Ofast on an x86/x86-64, gcc inlines the function, performs only one comparison per field (instead of the two found in the source code), and it doesn't even bother generating the tri-state return since we only need a boolean (less than or not). Demo, lines 52..70.


  1. It's far better to remove the cast in one place that's easily testable than to force the caller to cast away the const themselves at multiple call sites. It's far too likely to get this wrong, either from the start (in ways that are possibly subtle and not immediately detected), or in the long run as a the code is maintained and modified.

    Some might suggest creating duplicate functions, one for const types and one for non-const types. This, however, violate the fundamental Don't Repeat Yourself principle. And to what end? To avoid accidentally writing to a read-only variable? There is such a low chance of that happening, especially compared to getting a var or type name wrong. And the repercussions usually amount to an easily debuggable crash the first time you run the program.

    Sure, that's a risk, but you can't entirely eliminate risks. You can only strive to minimize both the risks and the consequences of those risks.

\$\endgroup\$
10
  • \$\begingroup\$ You inspired me to come up with my own refactoring. \$\endgroup\$
    – Davislor
    Commented Dec 21, 2021 at 20:20
  • \$\begingroup\$ I have to respectfully, but firmly, disagree with the function casting away const on its return value, however. First, you don’t even need to cast away const in this program. More importantly, it’s dangerous. The programmer could pass in a DateTime that genuinely is const, possibly stored in a read-only segment of memory, get back a non-const pointer, modify its contents, and crash the program. If you really, truly need to shoot yourself in the foot that way, you should have to do it explicitly and blatantly, by having the caller cast const away on the return value. \$\endgroup\$
    – Davislor
    Commented Dec 21, 2021 at 21:04
  • 2
    \$\begingroup\$ It hasn’t been a standard practice for more than thirty years. The only reason strchr does that is that it’s older than the const keyword, and the standard library couldn’t break backward compatibility. C++ does define an overload for strchr that returns const char*. The fact that, for backward compatibility with K&R C, you can still assign a string constant to a char* rather than a const char* is a perfect analogy: never, ever do that in new code! It’s a legacy of the ’70s, not a model to follow today. If you actually modify those pointers, it’s undefined behavior. \$\endgroup\$
    – Davislor
    Commented Dec 21, 2021 at 21:41
  • 1
    \$\begingroup\$ @Davislor & ikegami, with _Generic magic, a wrapper around min_dt() can achieve const correctness, without repeated code all in C. You both win. \$\endgroup\$ Commented Dec 21, 2021 at 23:38
  • 1
    \$\begingroup\$ @chux-ReinstateMonica Yeah, that’s what I was thinking of when I talked about limited support for overloading. I don’t think that’s an option here, unfortunately. The C17 standard says, “No two generic associations in the same generic selection shall specify compatible types.” I have not tested whether any compilers would support this as an extension. Even if compilers do, it’s really intended to allow portable implementations of <math.h>. \$\endgroup\$
    – Davislor
    Commented Dec 22, 2021 at 4:14
2
\$\begingroup\$

This code is not robust:

scanf("%d",&x);
for(i=0;i<x;i++){

We're ignoring the return value from scanf() and just assuming that x is assigned. We need to be testing - for example:

if (scanf("%d", &x) != 1) {
    fputs("Error reading input\n", stderr);
    return 1;
}
for (int i = 0;  i < x;  ++i) {

Similarly, if the other scanf() doesn't return 6, then our structure b is not initialised and we can't safely use its value.


Ikegami's answer shows how to create a comparison function for two DateTime values (with an interface like strcmp()), but an alternative inline loop takes advantage of continue to move to the next iteration:

for (size_t i = 0; i < x;  ++i) {
     const struct DateTime this_one = mas[i];
     if (this_one.year < min.year) {
         min = this_one;
     }
     if (this_one.year != min.year) {
         continue;
     }
     /* if we get here, years are equal */
     if (this_one.month < min.month) {
         min = this_one;
     }
     if (this_one.month != min.month) {
         continue;
     }
     /* if we get here, years and months are equal */
    ⋮

    ⋮
    /* until we get to seconds */
}
\$\endgroup\$
2
  • \$\begingroup\$ You can also place a continue in the ifs where you assign min. \$\endgroup\$
    – raznagul
    Commented Dec 22, 2021 at 13:58
  • \$\begingroup\$ You can, but since you then need to continue if the field is greater than the other object's, it made sense to reduce the duplication. Both forms are likely to compile to the same code with any reasonable optimising compiler, so choose whichever you think is clearest. \$\endgroup\$ Commented Dec 22, 2021 at 14:00
2
\$\begingroup\$

Priorities

OP has "What can I do to avoid this ladder and make my code readable?" is common misguided aim. Top goal should be: function correctness.

Correct compare

I assert that the multi-level compares of the 6 members is fundamentally wrong as is does not compare time-stamps properly when member values are not in the primary range.

Out of primary range values

How should code compare Yesterday:24:00:00 versus Today:00:00:00?

In comparing time, the timestamps should not be assumed to only encode primary time values.

A common work-around is to convert to a uniform scale - the number of seconds - then the compare is trivial.

long long dt_day(int y, int m, int d); //TBD code

long long dt_secs(const DateTime *mas) {
  long long sum = dt_day(mas->year, mas->month, mas->day);
  sum = sum*24 + mas->hours;
  sum = sum*60 + mas->minutes;
  sum = sum*60 + mas->seconds;
  return sum;
}

void DataTime(const DateTime *mas , int x){
  if (x > 0) {
    int min_index = 0;
    long long min = dt_secs(mas[0]);
    for (int i = 1; i < x; i++) {
      long long t = dt_secs(mas[i]);
      if (t < min) {
        min = t;
        min_index = i;
      }
    }
    printf("%d %d %d %d %d %d", //
        mas[min_index].year, mas[min_index].month, mas[min_index].day, //
        mas[min_index].hours, mas[min_index].minutes, mas[min_index].seconds);
  }  
}

Of course there are nuance issues like leap seconds and non-Gregorian calendar and odd cases like February 30th. Further issues occur when int and long long are both 64-bit.

\$\endgroup\$
4
  • \$\begingroup\$ I’d made the same suggestion, but it’s buried in the middle of a long post. The algorithm I used (and I believe the OP’s, although I haven’t rigorously checked) works if, and only if, the program maintains the invariant that all dates are formatted correctly. But this is hard to ensure, unless you modify the instances only through an API that maintains the invariants. Here, we aren’t. We could also warn: if you set the date to something invalid, all bets are off. \$\endgroup\$
    – Davislor
    Commented Dec 22, 2021 at 9:46
  • \$\begingroup\$ A good solution to the problem of weird time zones is to interpret all times as UTC. Since the problem statement doesn’t specify a different one, it appears that the OP is allowed to do so. \$\endgroup\$
    – Davislor
    Commented Dec 22, 2021 at 9:47
  • \$\begingroup\$ According to ISO 8601, the beginning of the branch cut is always 00, thus 24 is invalid. I would argue that raising an exception is the most correct approach vs silently trying to correct. (Otoh, leap seconds can have a value of 60.) \$\endgroup\$
    – Neil
    Commented Dec 23, 2021 at 18:49
  • 1
    \$\begingroup\$ @Neil My ISO 8601 is old given Earlier versions of the standard allowed "24:00" corresponding to the end of a day, but this is explicitly disallowed by the 2019 revision.} IAC, OP's DateTime is not spec'd as ISO 8601. C's struct tm accounts for out of primary range values with mkitme() and can serve as a model as to what is allowed here. \$\endgroup\$ Commented Dec 23, 2021 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.