Esercizio 24C, lanterne estive (lista concatenata)

Richiami

Liste concatenate in C, ricorsione sulle liste (vedi Liste concatenate in CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C →) e operatori bit a bit (&) su interi (vedi Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C → per puntatori e array; gli operatori bit a bit sono in Tipi, operatori e controllo del flusso in CTipi interi e reali del C con dimensioni e limiti, conversioni implicite e cast, divisione intera, operatori di incremento, logici e bit a bit; if, switch, while, do-while, for, break e continue.Tipi, operatori e controllo del flusso in C →, la rappresentazione binaria in Rappresentazione binaria dei datiBasi 2, 8 e 16; interi senza segno e in complemento a 2 con overflow; virgola mobile IEEE 754 e sue approssimazioni; caratteri ASCII, Unicode e UTF-8.Rappresentazione binaria dei dati → e l'AND logico in Algebra di Boole e porte logicheVariabili booleane, operatori AND, OR, NOT e derivati (NAND, NOR, XOR, XNOR) con tabelle di verità; assiomi e teoremi dell'algebra di Boole, De Morgan; porte logiche e completezza di NAND e NOR; semplificazione algebrica con esempio.Algebra di Boole e porte logiche →). Ogni colore è un bit di una maschera: & con la maschera $m$ dà un valore non nullo se e solo se il bit corrispondente è acceso.

Esempio: per la lista 1, 2, 2, 4, 4, 4 countColors dà colors = [1, 2, 3] (un blu, due verdi, tre rossi): non uguali, verdi pari, quindi si applica il pattern 1, 2, 2.

Soluzione

#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;
}

Punti da notare

• 100 nel testo è binario. In C il letterale 100 è il numero decimale cento. Il rosso è 100 in binario, cioè $4$: va scritto 4, 1 << 2 o con una costante (ROSSO). Scrivere uniformColor(head, 100) imposterebbe il valore decimale cento (binario 1100100): nei conteggi apparirebbe come rosso (il bit del rosso è acceso), ma non è il valore $4$ atteso e un confronto del tipo color == ROSSO fallirebbe.
• & e non &&: node->color & VERDE isola il bit; un nodo con colore $3$ (011) conta sia come blu sia come verde, perché la rappresentazione a bit permette combinazioni.
• Il pattern si legge prima di modificare la lista: applyPattern riscrive anche i primi tre nodi, quindi i loro colori vanno copiati in pattern prima di chiamarla.
• Liste con meno di $3$ nodi: pattern è inizializzato a $0$ e il ciclo di lettura si ferma a NULL, quindi nessun accesso fuori dalla lista; applyPattern usa solo pattern[0..1].
• Lista vuota: i conteggi sono tutti $0$, quindi uguali: restituisce vero senza modificare nulla.
• Complessità: ogni funzione scorre la lista una volta: $\Theta(n)$ tempo, $\Theta(n)$ stack per le due ricorsive (profondità $n$; una lista di milioni di nodi potrebbe esaurire lo stack, per questo applyPattern è scritta con un ciclo: Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →, Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).
• Traccia di applyPattern con pattern = [1, 2, 2] su una lista di $6$ nodi: l'indice index vale $0,1,2,0,1,2$ ((index + 1) % 3), quindi i nodi ricevono $1,2,2,1,2,2$; il resto della divisione per $3$ fa "tornare a capo" l'indice (come nel buffer circolare di Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →).

Prove eseguite

Compilato con gcc -std=c99 -Wall -Wextra e provato su liste costruite a mano:

Errori comuni

• uniformColor(head, 100) con 100 decimale, invece di 4.
• Usare && o == al posto di & nel conteggio: color == VERDE non vede i colori combinati.
• Leggere il pattern dopo aver cominciato a riscrivere i nodi.
• Dimenticare il caso della lista con meno di $3$ nodi (deferenziare NULL).
• Prototipi modificati (il testo lo vieta).