Post by Alessio Severi

Primo progetto di gruppo del Common Core di 42 Roma Luiss: push_swap, realizzato insieme a James Gonzales Il problema è semplice da enunciare — ordinare una sequenza di interi usando solo due stack e undici operazioni, nel minor numero di mosse possibile — ma diventa interessante quando lo si affronta come un problema di progettazione algoritmica e di analisi della complessità, non solo come ‘trovare un algoritmo che funzioni’. È stato anche il progetto in cui ho dedicato più tempo alla progettazione, all’analisi matematica delle scelte algoritmiche e alla loro verifica sperimentale, oltre che all’implementazione. Un’esperienza che ha confermato quanto progettazione, matematica e sperimentazione siano inseparabili nell’ottimizzazione di un algoritmo. Sono state implementate quattro strategie distinte, ciascuna pensata per una classe di complessità diversa (O(n²), O(n√n), O(n log n)), più una strategia adattiva che sceglie tra queste a runtime in base al disorder misurato sull'input: → Simple: Longest Increasing Subsequence, con reinserimento guidato da un costo di rotazione calcolato dinamicamente, non un ordine fisso. → Medium: bucket sort con una struttura annidata (ogni bucket avvolge il precedente) e un meccanismo di "parcheggio" per ricostruire lo stack. → Complex: radix sort ricorsivo in base 3, con una ricodifica mediante una trasformazione affine dei rank a ogni ricorsione,  inclusa una codifica personalizzata applicata immediatamente prima degli ultimi blocchi, calibrata su come il risolutore BFS li elabora; il caso base della ricorsione — blocchi di 5 elementi o meno — viene risolto con una BFS che garantisce la soluzione ottima. → Sotto i 5 elementi, tutte le strategie convergono sulla stessa BFS ottimale, con gli stati codificati in tempo costante tramite codice di Lehmer e notazione factoradic. Dopo che una strategia produce la sua sequenza di mosse, un peephole optimizer la riscrive individuando sottosequenze equivalenti a versioni più corte: 179 pattern di riscrittura, ciascuno con la propria condizione di equivalenza dimostrata. A completare il progetto, James Gonzales Oyolo ha progettato e scritto il checker: il programma bonus che rilegge la sequenza di mosse prodotta da push_swap e ne verifica indipendentemente la correttezza. Risultato: con disorder vicino a 0.5 (il caso naturale di un input casuale), il complex impiega in media ~3900 operazioni su 500 elementi — contro una soglia di 5500 che il subject definisce come "eccellente". Il medium, nella stessa fascia di disorder, si ferma a ~489 operazioni su 100 elementi, contro una soglia "eccellente" di 700. Il progetto è disponibile su GitHub, con un README che documenta le scelte progettuali e i benchmark completi delle quattro strategie, anche al variare del disorder dell’input, e commenti nel codice che riportano le dimostrazioni matematiche delle scelte più tecniche. https://lnkd.in/efv36UFg #42network #algorithms #C 42 Roma Luiss 42 ELIS