counting coaches in a circular train!

coaches.c

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct coach;
struct coach {
    struct coach* prev;
    struct coach* next;
    _Bool light;
};

const int max_len = 10000;

struct coach* make_random_train(int* len) {
    int length = 0;
    while (length < 2) {
        length = rand() % (max_len + 1);
        *len = length;
    }

    struct coach* head = malloc(sizeof(struct coach));
    struct coach* last = head;
    head->light = rand() % 2;
    head->prev = NULL;
    for (int i = 0; i < length - 1; i++) {
        struct coach* coach = malloc(sizeof(struct coach));
        coach->light = rand() % 2;
        last->next = coach;
        coach->prev = last;
        last = coach;
    }
    last->next = head;
    head->prev = last;
    return head;
}

int find_number_of_coaches(struct coach* head) {
    /*
     * Start at head. Make sure light is ON.
     * Go forward one car. If light is ON, switch OFF. If light is OFF, continue
     * to next car until light is found. When light is found, switch off. Go
     * back n cars (n coaches since head). Check if light is on. If not, we were
     * in the head coach and have found the number of cars. Otherwise, go
     * forward n cars again and continue.
     */
    struct coach* current = head->next;
    head->light = true;
    int n = 1;
    while (true) {
        // Look for first car with light. That could be head.
        while (!current->light) {
            n += 1;
            current = current->next;
        }
        assert(current->light);
        current->light = false;

        // Walk back.
        int walk_n = n;
        for (; walk_n > 0; walk_n--) current = current->prev;
        assert(current == head);
        if (!current->light) {
            // Found!
            return n;
        }

        // Walk forward again.
        for (; walk_n < n; walk_n++) current = current->next;
        assert(!current->light);

        // Check next coaches...
    }
}

int main(void) {
    srand(time(NULL));
    int expected = 0;
    struct coach* head = make_random_train(&expected);
    int counted = find_number_of_coaches(head);
    printf("Expected: %d Counted: %d\n", expected, counted);
}

@zpolina look! :))