RIDUCI non serve solo a ridurre: costruire risultati iterativi in Excel
Il nome RIDUCI suggerisce un’operazione molto precisa: prendere molti valori e ricondurli a qualcosa di più piccolo. Una somma, un massimo, una concatenazione.
È certamente uno dei suoi utilizzi. Ma non è ciò che rende RIDUCI particolarmente interessante.
Il concetto centrale è l’accumulatore: a ogni iterazione la funzione riceve il risultato costruito fino a quel momento e può trasformarlo ulteriormente. Nulla impone che quel risultato diventi più piccolo. Può anche crescere.
Un accumulatore che costruisce
Immaginiamo di partire da una stringa vuota. Alla prima iterazione aggiungiamo un carattere, alla seconda un altro, poi un altro ancora:
"" → "╦" → "╦═" → "╦═╗" → ...
RIDUCI permette di esprimere proprio questa successione. Il valore restituito da un passaggio diventa l’ingresso del successivo.
Questo cambia il modo di guardare alla funzione: non soltanto aggregazione, ma costruzione progressiva di uno stato.
Un esempio meno convenzionale: costruire un labirinto
Un caso che rende evidente questo comportamento è la costruzione di una matrice composta da caratteri Unicode che rappresentano segmenti e incroci di un labirinto.
Disponiamo di una tabella T_Lab. Per ogni carattere sono indicate le connessioni disponibili nelle quattro direzioni: sinistra, sopra, destra e sotto. La tabella diventa quindi una piccola anagrafica delle tessere utilizzabili.
La matrice viene costruita da sinistra a destra e dall’alto verso il basso. Quando dobbiamo scegliere un nuovo carattere, conosciamo già due informazioni: ciò che si trova alla sua sinistra e ciò che si trova sopra.
Il nuovo elemento deve essere compatibile con entrambi.
Lo stato contiene già ciò che serve
Qui entra in gioco l’accumulatore. Invece di contenere un totale numerico, contiene tutti i caratteri scelti fino a quel momento.
Per ogni posizione k ricaviamo riga e colonna. Dall’accumulatore recuperiamo il carattere precedente, quando esiste, e quello posto una riga sopra. Attraverso T_Lab possiamo conoscere le rispettive aperture verso destra e verso il basso.
Queste diventano i vincoli per la tessera successiva.
=LET(
nR;numRighe;
nC;numColonne;
Tot;nR*nC;
str;
REDUCE(
"";
SEQUENZA(Tot);
LAMBDA(acc;k;
LET(
r;INT((k-1)/nC)+1;
c;RESTO(k-1;nC)+1;
chSx;SE(c=1;"";STRINGA.ESTRAI(acc;k-1;1));
chSp;SE(r=1;"";STRINGA.ESTRAI(acc;k-nC;1));
sx;SE(
c=1;
FALSO;
CERCA.X(
chSx;
T_Lab[Carattere UNI];
T_Lab[Destra];
FALSO
)
);
sp;SE(
r=1;
FALSO;
CERCA.X(
chSp;
T_Lab[Carattere UNI];
T_Lab[Sotto];
FALSO
)
);
chiusuraFinale;
SE(
E(r=nR;c=nC-1);
T_Lab[Destra]=
CERCA.X(
STRINGA.ESTRAI(acc;k-nC+1;1);
T_Lab[Carattere UNI];
T_Lab[Sotto];
FALSO
);
VERO
);
candidati;
FILTRO(
T_Lab[Carattere UNI];
(T_Lab[Sinistra]=sx)*
(T_Lab[Sopra]=sp)*
SE(c=nC;T_Lab[Destra]=FALSO;1)*
SE(r=nR;T_Lab[Sotto]=FALSO;1)*
chiusuraFinale*
(T_Lab[Controllo]=VERO)
);
scelto;
SE.ERRORE(
INDICE(
candidati;
CASUALE.TRA(1;RIGHE(candidati))
);
" "
);
acc&scelto
)
)
);
MAKEARRAY(
nR;
nC;
LAMBDA(rr;cc;
STRINGA.ESTRAI(
str;
(rr-1)*nC+cc;
1
)
)
)
)
Perché RIDUCI e non SCAN?
Una prima versione di questa formula utilizzava SCAN. Funzionava, ma conservava tutti gli stati intermedi della costruzione.
Alla fine era quindi necessario estrarre l’ultimo elemento prodotto, perché era l’unico che ci interessava realmente.
RIDUCI esprime meglio il problema: ogni stato serve per calcolare il successivo, ma ciò che vogliamo ottenere è soltanto lo stato finale.
La differenza non è soltanto sintattica. Scegliere tra SCAN e RIDUCI significa chiedersi se gli stati intermedi facciano parte del risultato oppure siano soltanto passaggi necessari per arrivarci.
Un dettaglio ai bordi che cambia il risultato
La prima versione aveva anche un difetto interessante.
Controllava la compatibilità con ciò che era già stato costruito, quindi sinistra e sopra, ma non imponeva che una tessera posta sull’ultima colonna fosse chiusa verso destra o che una tessera sull’ultima riga fosse chiusa verso il basso.
Il risultato poteva quindi essere localmente coerente e, allo stesso tempo, lasciare un percorso idealmente aperto oltre il bordo della matrice.
I due controlli aggiuntivi:
SE(c=nC;T_Lab[Destra]=FALSO;1)
SE(r=nR;T_Lab[Sotto]=FALSO;1)
risolvono quasi tutto, ma durante i test è emerso un caso più sottile: l’angolo in basso a destra può diventare impossibile da completare. Con le tessere utilizzate, quell’ultima posizione può chiudersi soltanto se riceve zero connessioni oppure due connessioni; una sola apertura proveniente da sinistra o dall’alto non ha una tessera terminale corrispondente.
La prima tentazione potrebbe essere introdurre un backtracking: tornare indietro e cambiare una scelta precedente. In questo caso, però, non serve.
La penultima scelta può garantire l’ultima
Quando arriviamo alla penultima cella dell’ultima riga, la cella sopra l’angolo finale è già stata costruita. Conosciamo quindi già se essa apre verso il basso.
Basta imporre che la penultima tessera apra verso destra esattamente nello stesso modo:
B[Destra] = A[Sotto]
La variabile chiusuraFinale esprime questo vincolo:
chiusuraFinale;
SE(
E(r=nR;c=nC-1);
T_Lab[Destra]=
CERCA.X(
STRINGA.ESTRAI(acc;k-nC+1;1);
T_Lab[Carattere UNI];
T_Lab[Sotto];
FALSO
);
VERO
);
Così l’ultima cella riceve necessariamente due stati uguali: FALSO/FALSO, che può diventare uno spazio, oppure VERO/VERO, che può diventare ╝. Non occorre tornare indietro: è sufficiente usare lo stato già costruito per rendere valida la scelta corrente.
Questo passaggio rende più preciso un concetto importante: l’accumulatore non contiene soltanto il risultato parziale. Può contenere anche le informazioni necessarie per garantire che la costruzione possa proseguire correttamente.
Anche il vuoto deve occupare una posizione
Un altro dettaglio emerso nei test riguarda la tessera senza connessioni. In T_Lab[Carattere UNI] non deve essere una cella realmente vuota, ma contenere un carattere spazio.
L’accumulatore è infatti una stringa nella quale ogni posizione della matrice deve corrispondere esattamente a un carattere. Se una tessera vuota aggiungesse zero caratteri, la lunghezza dell’accumulatore non coinciderebbe più con il numero di celle elaborate e i successivi STRINGA.ESTRAI leggerebbero i vicini sbagliati.
È un dettaglio tecnico, ma esprime bene una regola più generale: quando la posizione fa parte dello stato, anche l’assenza di contenuto deve avere una rappresentazione.
È davvero un labirinto?
Non necessariamente, almeno nel significato algoritmico più rigoroso del termine.
La formula costruisce una matrice di tessere compatibili. Non garantisce, da sola, che esista un percorso tra due punti, che tutte le zone siano raggiungibili o che tra due celle esista un solo cammino.
Chiamarlo “labirinto” descrive bene il risultato visivo, ma è utile distinguere l’aspetto grafico dalle proprietà che dovrebbe garantire un vero algoritmo di generazione di labirinti.
Anche questo limite rende l’esempio interessante: una formula può rispettare perfettamente tutte le regole locali senza garantire automaticamente una proprietà globale.
Il punto non è il labirinto
Il labirinto è soprattutto un modo visibile per osservare RIDUCI al lavoro.
Lo stesso schema compare ogni volta che il risultato di un passaggio deve diventare parte del contesto utilizzato dal passaggio successivo. L’accumulatore può essere un numero, un testo, un array o una struttura progressivamente più ricca.
È qui che RIDUCI diventa più interessante di quanto suggerisca il suo nome.
Non dobbiamo necessariamente chiederci: come riduco questi valori?
Possiamo chiederci invece: quale stato voglio costruire, passo dopo passo?