Grade school : ARM64 - Some tests fail when run online

[cgimenez]

Hi all !
I'm having a strange problem (but it might be my mistake) : tests 14 and 20 won't passe online.

I'm using a Mac M2, and the problem occurs both under MacOS and Debian 10 (vm)
I tried both clang and gcc compilers on MacOS by modifying the Makefile

Versions are

cc -v
Apple clang version 15.0.0 (clang-1500.1.0.2.5)
Target: arm64-apple-darwin22.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

gcc --version
gcc (MacPorts gcc12 12.3.0_4+stdlib_flag) 12.3.0

Then I launched the tests on my Debian 10 VM (ARM64) with gcc

gcc --version
gcc (Debian 8.3.0-6) 8.3.0

All tests are green on Macos (clang or gcc) and Debian - even with memcheck

[siebenschlaefer]

Can you show your solution and the error you got from Exercism's test runner?

[cgimenez]

Test 14 (test_students_are_sorted_by_grades_and_then_by_names_in_roster)

• Expected 'Anna' Was 'Barb'

Test 20 (test_students_are_sorted_by_name_in_grade)

• Expected 'Bradley' Was 'Franklin'

For example, test 14 expects

roster_t expected = {7,
                         {(student_t){1, "Anna"},
                          (student_t){1, "Barb"},
                          (student_t){1, "Charlie"},
                          (student_t){2, "Alex"},
                          (student_t){2, "Peter"},
                          (student_t){2, "Zoe"},
                          (student_t){3, "Jim"}}};

And when I print the roster's state during test 14 I get

[Anna                ]  1
[Barb                ]  1
[Charlie             ]  1
[Alex                ]  2
[Peter               ]  2
[Zoe                 ]  2
[Jim                 ]  3

My solution
grade_school.h

#ifndef GRADE_SCHOOL_H
#define GRADE_SCHOOL_H

#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

#define MAX_NAME_LENGTH 20
#define MAX_STUDENTS 20

typedef struct {
    uint8_t grade;
    char    name[MAX_NAME_LENGTH];
} student_t;

typedef struct {
    size_t    count;
    student_t students[MAX_STUDENTS];
} roster_t;

int name_comparator(const void* first, const void* second);
int grade_comparator(const void* first, const void* second);

void     init_roster(roster_t* roster);
bool     add_student(roster_t* roster, char* name, int grade);
roster_t get_grade(roster_t* roster, uint8_t desired_grade);

#endif

grade_school.c

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

#include "grade_school.h"

roster_t result;
void     print_roster(roster_t* roster);
void     print_roster(roster_t* roster) {
    size_t i = 0;
    for (i = 0; i < roster->count; i++) {
        printf("[%-20s] %2d\n", roster->students[i].name, roster->students[i].grade);
    }
    printf("-------------\n");
}

int name_comparator(const void* first, const void* second) {
    student_t* s1 = (student_t*)first;
    student_t* s2 = (student_t*)second;
    return strncmp(s1->name, s2->name, MAX_NAME_LENGTH);
}

int grade_comparator(const void* first, const void* second) {
    student_t* s1 = (student_t*)first;
    student_t* s2 = (student_t*)second;
    return s1->grade - s2->grade;
}

void init_roster(roster_t* roster) {
    memset((void*)roster, 0, sizeof(roster_t));
}

bool add_student(roster_t* roster, char* name, int grade) {
    size_t i = 0;
    for (i = 0; i < roster->count; i++) {
        if (strncmp(roster->students[i].name, name, MAX_NAME_LENGTH) == 0)
            return false;  // forbid adding student twice
    }

    i = 0;
    while (roster->students[i].grade != 0) {
        i++;
        if (i == MAX_STUDENTS)
            return false;
    }
    roster->students[i].grade = grade;
    strncpy(roster->students[i].name, name, MAX_NAME_LENGTH);
    roster->count++;

    qsort((void*)roster->students, roster->count, sizeof(student_t), name_comparator);
    qsort((void*)roster->students, roster->count, sizeof(student_t), grade_comparator);
    print_roster(roster);
    return true;
}

roster_t get_grade(roster_t* roster, uint8_t desired_grade) {
    result.count = 0;
    for (size_t i = 0; i < roster->count; i++) {
        if (roster->students[i].grade == desired_grade) {
            memcpy((void*)&result.students[result.count], (void*)&roster->students[i], sizeof(student_t));
            result.count++;
        }
    }
    return result;
}

[siebenschlaefer]

The problem is that add_student() calls qsort() twice, But qsort() does not necessarily (or usually) use a stable sorting algorithm.

After the first call to qsort() the students are sorted by their names.
After the second call to qsort() the students are sorted by their rank ... but within the same rank they are no longer necessarily sorted by their names.

The standard does not specify the implementation of qsort(), so the implementations vary. That's why you get different results on different platforms, they rely on an implementation detail.

The simplest fix is to merge the two comparison functions into one.

[cgimenez]

Djizz I wasn't aware of this subtle detail about qsort (and didn't see anything related in the online docs or ref, or maybe I missed it)

[cgimenez]

Advice applied : tests passe online ;-)

Thanks !