Esercizio 24C, lanterne estive (lista concatenata)

Testo (scritto del 09/09/2025, parte 3, in C). La Festa delle Lanterne Estive. Svolgi il seguente esercizio sviluppando le funzioni richieste in C. I prototipi delle funzioni non possono essere modificati. Durante l'esame non è possibile consultare appunti o materiale didattico; è consentito utilizzare la documentazione di Linux da terminale con man.

Una famiglia ha decorato il giardino con lanterne luminose appese lungo un sentiero. Ogni lanterna può essere blu, verde o rossa. La disposizione è rappresentata da una lista concatenata: ogni nodo contiene color, il colore della lanterna (di tipo intero). Il colore è rappresentato con tre bit, ciascuno per un colore: 001 blu, 010 verde, 100 rosso.

Si deve verificare che il numero di lanterne di ciascun colore sia lo stesso. Se non lo è, il programma cambia il colore di tutte le lanterne in questo modo: se il numero di lanterne verdi è dispari le colora tutte di rosso; altrimenti (considera pari lo zero) ripete il colore delle prime tre lanterne per tutte le altre (ad esempio con prime tre lanterne blu, verde, rossa: la quarta sarà blu, la quinta verde, la sesta rossa, e così via).

La lista è fornita già implementata: typedef struct node { int color; struct node *next; } Node;. Funzioni da implementare:

1. void countColors(Node *node, int *colors) conta le lanterne di ciascun colore: colors è un array di $3$ interi e la funzione lo aggiorna (blu in colors[0], verde in colors[1], rosso in colors[2]); per ogni nodo, se color & 001 incrementa colors[0], se color & 010 incrementa colors[1], se color & 100 incrementa colors[2]; poi richiama se stessa sul nodo successivo;
2. int checkLanternColors(Node *head) restituisce TRUE (non zero) se i tre conteggi sono uguali, FALSE altrimenti; in questo caso applica le regole sopra (se colors[1] è pari: legge i colori dei primi tre nodi in un array pattern di $3$ interi inizializzato a $0$ e chiama applyPattern(head, pattern); altrimenti chiama uniformColor(head, 100));
3. void uniformColor(Node *node, int color) imposta color su ogni nodo collegato a node (ricorsiva);
4. void applyPattern(Node *node, int *pattern) imposta il colore di ogni nodo in base al pattern, con indice che scorre $0, 1, 2, 0, 1, 2, \dots$ (index <- (index + 1) % 3).

Lo pseudocodice non è codice C completo: non considera i tipi, l'uso di puntatori e quindi l'operatore -> al posto di .. Si possono creare struct e funzioni ausiliarie.

#define BLU    1   /* 001 */
#define VERDE  2   /* 010 */
#define ROSSO  4   /* 100 */

typedef struct node {
    int color;
    struct node *next;
} Node;

void countColors(Node *node, int *colors) {
    if (node == NULL)
        return;
    if (node->color & BLU)   colors[0]++;
    if (node->color & VERDE) colors[1]++;
    if (node->color & ROSSO) colors[2]++;
    countColors(node->next, colors);
}

void uniformColor(Node *node, int color) {
    if (node == NULL)
        return;
    node->color = color;
    uniformColor(node->next, color);
}

void applyPattern(Node *node, int *pattern) {
    int index = 0;
    for (Node *cur = node; cur != NULL; cur = cur->next) {
        cur->color = pattern[index];
        index = (index + 1) % 3;
    }
}

int checkLanternColors(Node *head) {
    int colors[3] = {0, 0, 0};
    countColors(head, colors);
    if (colors[0] == colors[1] && colors[1] == colors[2])
        return 1;
    if (colors[1] % 2 == 0) {                 /* verdi pari (anche zero) */
        int pattern[3] = {0, 0, 0};
        Node *cur = head;
        for (int i = 0; i < 3 && cur != NULL; i++) {
            pattern[i] = cur->color;
            cur = cur->next;
        }
        applyPattern(head, pattern);
    } else {
        uniformColor(head, ROSSO);
    }
    return 0;
}