Visualizza il feed RSS

Titolo provvisorio...

C64 - A scuola in scooter... con COMAL!

Valuta questo inserimento
di pubblicato il 25-03-2020 alle 21:47 (212 Visite)
Abbiamo scelto un semplice problema logico, pubblicato come "2199ª prova d'intelligenza" sulla Settimana
Enigmistica, per proporre una completa soluzione in linguaggio COMAL 80 (versione 2.01 per C64). Approfittiamo
dell'occasione anche per un veloce ripasso su concetti e algoritmi fondamentali per la generazione di oggetti
combinatori elementari.

Il presente articolo si accoda, con qualche variazione, alla fortunata serie tratta da testi storici di puzzle e rompicapo logici per C64, che pare avere conquistato qualche apprezzamento tra i lettori più assidui. Il problema, in questa occasione, è preso direttamente dalla più nota e longeva rivista di enigmistica italiana: la soluzione vuole mettere alla prova il lettore grazie alle peculiarità del linguaggio COMAL, del quale recentemente abbiamo tracciato l'origine storica e l'evoluzione. Si esortano i lettori, come in passato, a proporre proprie soluzioni originali in BASIC V2 e in Assembly 6510.

Il testo originale del problema recita: «I quattro amici Aldo, Bruno, Carlo e Daniele abitano tutti nello stesso palazzo e ognuno di loro, dal lunedì al sabato, porta a scuola con lo scooter la propria sorella.
In una settimana un po' particolare succede che nessuno accompagni mai la propria sorella: ognuno porta infatti a scuola le sorelle dei tre amici, ciascuna per due volte. In nessuno dei sei giorni si ripete la medesima formazione di coppie di un altro giorno, e in nessun giorno succede che vi sia un ragazzo che accompagna la sorella dell'amico che accompagna la sua: ad esempio, nei due giorni in cui Aldo accompagna la sorella di Bruno, sullo scooter con Bruno non vi è la sorella di Aldo.
La sorella di Carlo va a scuola con Aldo mercoledì e sabato. Lunedì e giovedì Daniele ha con sé la sorella dell'amico che martedì accompagna sua sorella. Lunedì e sabato è con Carlo la ragazza che mercoledì è con Daniele.

In quali giorni Bruno accompagna a scuola la sorella di Carlo?»

Dal punto di vista strettamente combinatorico, la soluzione al problema è data da un particolare tipo di block design completo con ordinamento con 4 varietà e 6 blocchi. Si tratta di un oggetto combinatorio non comune e non propriamente elementare, la cui ampissima e ben studiata famiglia (che include tra gli altri BIBD, codici a correzione d'errore, lotto designs, schemi d'esperimento random, quadrati latini, matrici ortogonali, MOLS e molto altro) risulta fondamentale in innumerevoli settori: geometria finita, progetto e analisi di algoritmi e di reti, verifica esaustiva di software e hardware, reliability engineering, crittografia, tornei e lotterie, esperimenti incrociati sistematici di ogni genere nelle scienze dell'uomo e naturali, biologia molecolare, animale e vegetale, agronomia e molto altro. Data la vastità del campo applicativo e l'enorme importanza dell'argomento, l'autore confida che non mancherà occasione di approfondire questi multiformi e sofisticati oggetti combinatori, nonostante l'elevata complessità computazionale che medialmente caratterizza i relativi algoritmi generatori ed enumerativi, rendendone sovente proibitiva l'implementazione in ambito retrocomputing anche per dimensioni assai modeste dei problemi.

In questa sede, la volontà di mantenere l'approccio il più semplice e comprensibile possibile ci induce invece a fingere di chiudere un occhio sulla reale natura di tale oggetto matematico, scendendo ad un livello di astrazione minore e considerandone solo le componenti combinatorie elementari. Possiamo infatti riconsiderare i vincoli del problema sotto una nuova prospettiva semplificata e scolastica: si tratta di una particolare permutazione i cui elementi sono in realtà sei derangement ristretti da 4 simboli ciascuno. Sebbene esistano solo 6!=720 di tali permutazioni, un approccio bruteforce sarebbe ovviamente fuori discussione per lapalissiane ragioni didattiche e di principio.

Come da tradizione in questa serie di articoli, decidiamo di sfruttare alcune immediate deduzioni iniziali sui vincoli per semplificare la stesura del software, usandole in modo hardcoded per evitare ricerche esaustive o altri approcci. Se da un lato il ricorso al bruteforce sarebbe inutile e deleterio, non ci interessa neppure all'estremo opposto imbarcarci nella realizzazione di un risolutore generalizzabile, magari basato su ricorsione e backtracking, quanto piuttosto evidenziare la «traduzione» in COMAL dei vincoli e delle regole (quindi della specifica) restando focalizzati sull'istanza del problema-giocattolo proposto. La soluzione del nostro simpatico problemino è basata quasi interamente sullo sfruttamento delle proprietà combinatorie elementari degli oggetti interessati e sulla scelta di una opportuna coppia di strutture dati che congiuntamente consentono anche il reverse lookop e l'ordinamento in-place, senza scomodare algoritmi di ordinamento.

Se ardete dalla curiosità di sapere in quali giorni il buon Bruno accompagna a scuola in scooter la sorella di Carlo (messa così suona intenzionalmente come una interminabile telenovela adolescenziale... ), scaricate e leggete l'articolo completo in PDF. Per gli interessati è disponibile anche un'immagine disco .d64 contenente il sorgente COMAL e il relativo listato in formato sequenziale, tenendo presente che occorre comunque avere la cartridge COMAL 80 2.0 (o un equivalente, come la relativa immagine binaria caricata su emulatore o su una cartridge "universale") per poterlo caricare ed eseguire.

aggiornamento da 25-03-2020 a 21:54 di M.A.W. 1968

Categorie
Libri , Programmazione , Hardware