Per le strade di Manhattan

Siamo in autunno, cala la libido, fa freddo e cadono le foglie, il pozzo freatico della mia immaginazione è quasi a secco. Non mi resta che il trucco delle citazioni e delle connessioni e delle auto-citazioni per tenere in vita questo blog. E in questo mi è d’aiuto la lettura di un arido manuale di programmazione in LISP. Se vi capita di smarrire la strada, di perdervi da qualche parte, ad esempio in un bosco in un tardo pomeriggio d’autunno, ricordatevi di non guardare le cime degli alberi e le nuvole nel cielo per non cadere in un fisiologico esistenzialismo, piuttosto osservate attentamente il terreno, non la sua natura geologica ma la conformazione pedologica, vale a dire il terreno è in pendenza? Se sì, allora siete a cavallo, anche se siete a piedi, che comunque sono il cavallo di San Francesco; ma la vostra strada è attraversata da un drammatico dilemma, da un vero e proprio aut-aut: scendere o salire? Se volete potete tirare a sorte, lanciate in aria una monetina da un centesimo, ce l'avete vero una monetina? (quando ci si perde per boschi si deve sempre avere in tasca una monetina da un centesimo, semmai dimenticate a casa bussola e telefonino).
Testa, ascenderemo fino alla cima del monte. Croce, scenderemo giù fino a valle. Se la sorte deciderà per l’ascensione, allora forza e coraggio, puntare i piedi e salire come capre di montagna, ché quelle di pianura non servono allo scopo; afferrando radici terragne e muschiosi tronchi d’albero, prima o poi sarete sulla vetta, sul crinale di un monte che forse un tempo fu percorso dai nostri più agili antenati ominidi (punto indicato come A), e di lassù, guardando tutt’attorno, giacché vi siete persi in un bosco mediterraneo, senz’altro noterete qualche ondivago pennacchio di fumo che si dipana neghittoso nel terso cielo grigio-azzurro, o febbrili torri elettriche di babele, oppure un pittoresco campanile di una chiesetta fatiscente di campagna. Tracciata mentalmente la strada, che unisce A al pigro pennacchio o al rudere medioevale (punto B), lesti e balzelloni scenderete giù a valle, senza deviare il cammino di un solo centimetro, frenando ogni tanto e riprendendo l’abbrivo della corsa per non rischiare l’inciampo in qualche radice marcita o rimbalzare come una palla di gomma nel muschioso tronco di una quercia, o in un duro castagno. Ma tutta questa fatica e tutto 'sto sudore perso per strada, ora, se ci pensiamo bene, è stato superfluo, inutile e vano, ché in ogni modo scendere a valle si doveva, e allora, la prossima volta, lasciamo la monetina in tasca e rispondiamo al nostro aut-aut che senz’altro sì, noi scenderemo a valle. E che alla fine sì, noi troveremo un sentiero, e lo seguiremo non nel verso che scema ma in quello che declina, oppure finiremo dentro un gelido torrente e ci lasceremo trascinare dalla corrente a valle, come in un tranquillo week-end di paura, ovvero metteremo la suola destra (sinistra se siamo mancini) dello scarponcino infangato, ma di marca, sul materno catrame di una strada provinciale. Tutto bene. Noi seguiremo la strada... ok, ma se la strada è in piano? Niente panico. Ecco che parte in testa un secondo aut-aut: destra o sinistra? Non vi consiglio di seguire inclinazioni politiche o fedi religiose ma di lanciare in aria la monetina. E se questo smarrimento ci afferra come il virus dell’influenza, una notte d’inverno, tra i padiglioni di un grande ospedale? Chi si è smarrito in quel labirinto piano e oscuro ha provato veramente l’incubo e l’angoscia di non arrivare. Eppure nonostante l’angoscia in cuore, esiste sempre un punto B nello spazio, esiste una meta, una persona cara da visitare, perché nessun visitatore si perde la notte tra i padiglioni di un grande ospedale solo per andare a visitare un letto vuoto.
Ma come fare ad arrivare al punto B se la strada è in piano? La domanda mi spinge ad una riflessione filosofica che è anche un’auto-citazione (da LISP Trek, 2007):


La fig. 1 rappresenta in modo schematico un quartiere simile a Manhattan, le cui strade sono tutte ortogonali (con una unica eccezione). Si ipotizza che ogni tratto di strada tra un incrocio e quello successivo, sia in direzione da nord a sud che in direzione da ovest ad est, abbia una lunghezza di 100 metri. L'obiettivo è andare a piedi dall'isolato A (ed in particolare dall'incrocio in basso a destra dell'isolato A) all'isolato B (e in particolare all'incrocio in alto a sinistra dell'isolato B). Se B dista da A x isolati in direzione ovest-est e y isolati in direzione nord-sud, dobbiamo percorrere x+y tratti di strada. Quante alternative abbiamo per spostarci da A a B lungo uno dei percorsi più brevi? Con x = y = 0 restiamo dove siamo. Con x = 0 (a) o y = 0 (b) l'unico percorso più breve è una linea retta da nord a sud (ipotesi a) o da ovest a est (ipotesi b). Rimane da esaminare il caso con x e y maggiori di 0, e il problema non cambia se A e B sono molto vicini, come si vede nella seconda figura.


I percorsi più corti sono solo due: xXy e yYx; non esiste un terzo percorso breve che attraversa sia l'incrocio X sia l'incrocio Y. Se ora ricollochiamo A dove stava in origine si vede che comunque ogni percorso breve che porta a B deve passare o dall’incrocio X o dall’incrocio Y ma non da entrambi. La soluzione sta quindi nel sommare il numero di percorsi brevi che passano dall’incrocio X e il numero di percorsi brevi che attraversano l’incrocio Y. Il numero di percorsi brevi da A a X è lo stesso problema con x e y-1 (a). Il numero di percorsi brevi da A a Y è lo stesso problema con x-1 e y (b). Infatti nel caso della fig. 2 (a) è x = 1, y = 0 e (b) x = 0, y = 1.

; manh.lsp * 17 febbraio 2004
; © 2004 Claudio Piccini
(defun nPercorsi (e c)
(if (or (= e 0)(= c 0))
(setq np 1)
(setq np (+ (nPercorsi e (- c 1))(nPercorsi (- e 1) c))))
)
(defun c:manh ()
(initget (+ 1 4)) ; non nullo, non negativo
(setq e (getint "\nInserire numero isolati in direzione OVEST-EST: "))
(initget (+ 1 4)) ; non nullo, non negativo
(setq c (getint "\nInserire numero isolati in direzione NORD-SUD: "))
(princ (strcat "\nLe alternative sono " (itoa (nPercorsi e c))))
(princ)
)
;;; eof