Il cubetto


Diversi anni fa — forse addirittura il secolo scorso — recuperai in non so più che fiera un piccolo puzzle costituito dalle sei facce del cubetto che vedete nell’immagine qui a fianco.
Dal punto di vista formale possiamo considerarlo come un cubo di lato 6. Su un solo lato di ogni faccia, di spessore 1, è impresso il nome dello sponsor. L’obiettivo del puzzle è incastrare le sei facce in modo da ricostruire il cubetto originale.

Lo tengo sempre vicino al monitor del pc di casa e per diverso tempo mi succedeva di risolverlo la sera per poi trovarlo la sera seguente, tornato
dall’ufficio, smontato nuovamente da qualche entità (moglie? figli? gatti? fantasmi? Questa informazione non è pertinente al problema e quindi non è dato conoscerla).

Una sera, in cui avevo meno sonno del solito, decisi di divertirmi scrivendo un programma che
risolvesse il puzzle e che mi togliesse anche un paio di altre curiosità (quante sono le soluzioni uniche a meno di rotazioni? C’è almeno una
soluzione con il nome dello sponsor impresso su tutte le facce esterne del cubo?).
A questo punto lancio una sfida: usando il linguaggio che preferite, sapete scrivere un programma che risolva il
puzzle? In quante righe di codice? In quanto tempo il vostro programma trova e stampa tutte le soluzioni?

Per definire un po’ meglio i dettagli del problema allego due file:

Non è necessario – ma non è nemmeno vietato – che il programma legga da un file la forma dei sei pezzi, anche se questo vuol dire sprecare preziose righe di codice.

Incidentalmente potrò così soddisfare un’altra mia curiosità: capire quale
possa essere il secondo miglior linguaggio del mondo dopo quello che ho usato io ;-)

Il vincitore, a insindacabile giudizio della redazione, avrà l’onore di
vedere il suo programma pubblicato su Stacktrace (sorry, per ora nessuna
assunzione a Google garantita :-) ).

About Marco Beri

Marco Beri si laurea in Scienze dell’Informazione nel 1990, periodo oramai definibile come la preistoria del settore. Il computer è prima di tutto un suo hobby e anche per questo si innamora di Python a prima vista nel lontano 1999, dopo aver sperimentato una ventina di altri linguaggi. Fa di tutto, riuscendoci, per portarlo nella sua azienda, la Link I.T. spa, dove dal 1997 occupa il ruolo di amministratore e responsabile dello sviluppo software. Riesce perfino a intrufolarsi come amministratore nella fondazione dell’associazione Python Italia. Incredibilmente pubblica anche diversi libri per Apogeo/Feltrinelli.

Comments

  1. Mi sa che questo post non ha avuto molto successo..

    Perchè non proponete lo sviluppo di un applicazione opensource sponsorizzata da starkrace piuttosto?

  2. Michele Simionato says:

    Veramente il giorno in cui questo articoletto e’ stato pubblicato abbiamo avuto ~250 contatti in piu’, qualcuno che l’ha letto ci sara’ stato ;)

  3. Io ci sto pensando su come farlo :) solo che ho gia’ cambiato idea un paio di volte e per via dello studio ci dedico solo poco tempo ogni giorno…
    Bella idea, pero’.

  4. Che cosa magnifica, cercherò di lavorarci nel tempo libero… però voi così mi rovinate, devo studiare causa esame imminente…!

  5. Andrea Laforgia says:

    sto scrivendo un programmino in C per la soluzione del problema, però leggendo la prima soluzione del tuo programma, vedo che il pezzo più a sinistra è in realtà l’inverso – e non una rotazione – del secondo pezzo elencato nella lista. Essendo richiesto che il nome del produttore sia sul TUTTE le facce esterne, incastrarlo a quel modo non invaliderebbe le cose?

  6. @Andrea: ti chiedo scusa se mi sono spiegato male. Tutti i pezzi possono essere usati per un verso o per l’altro, quindi mostrando o meno la faccia dello sponsor. Nello specifico caso della soluzione che ho postato, solo cinque pezzi mostrano la faccia dello sponsor verso l’esterno. Inoltre, se giri tutti i pezzi, hai una soluzione simmetrica e speculare in cui solo una faccia mostra lo sponsor verso l’esterno e le altre cinque no.
    Le domande che ho posto sono:
    1) quante soluzioni uniche? (a meno di riflessioni e/o rotazioni come questa)
    2) esiste una soluzione con tutte le facce che mostrano uno sponsor?
    E` chiaro che ho dovuto postare come esempio una soluzione che non rispondesse implicitamente alla seconda domanda.

  7. Mi associo a quelli che vogliono dilettarsi nel farlo (ma hanno gli esami a spaccare i maroni).
    I detrattori si divertano pure con l’ennesima applicazione web.

  8. Andrea Laforgia says:

    Ahimè, è anche questione di tempo… purtroppo il lavoro non lascia spazio a queste divagazioni che, almeno nel mio caso, sono pur sempre necessarie per non farsi ammorbare da quel brutto male chiamato Java… :-)

  9. Ho scoperto proprio oggi questo sito (complimenti!), e stamattina ho letto il problema e mi sono incuriosito.

    IMHO non esiste un linguaggio “migliore” in assoluto: per ogni problema c’è un linguaggio più adatto a scrivere un programma per risolverlo, sta poi al programmatore conoscere vari linguaggi e scegliere quello più adatto.

    Per risolvere questo genere di problemi, il linguaggio più adatto che conosco è il Prolog: si basa sul paradigma della “PROgrammazione LOGica”, in questo modo non devo preoccuparmi troppo dell’algoritmo da usare per risolvere il quesito: basta definire i dati iniziali, definire le trasformazioni ammesse, applicare alcune trasformazioni e controllare se ho ottenuto il risultato. Funziona grazie al backtracing: dopo aver applicato alcune trasformazioni, se non ho ottenuto il risultato “torna indietro” per provare un’altra trasformazione e controllarla, fino ad arrivare ad una soluzione o, una volta provate tutte le possibili trasformazioni, dichiarare l’impossibilità. Con questo linguaggio è facile scrivere programmi per risolvere problemi logici (ci ho scritto un risolutore del Sudoku), ed è usato anche in programmi di “intelligenza artificiale”.

    Il programma che ho scritto è lungo circa 200 righe (un centinaio per trovare la soluzione e un centinaio per scrivere l’output in ascii art come nell’esempio), ma è una soluzione “quick and dirty”, che non ho ottimizzato per accorciare il codice.

    Non ho usato particolari metodi per ottimizzare la velocità, però ordinando in un certo modo i comandi riesce a scartare velocemente alcune soluzioni non valide, ottenendo un tempo di esecuzione di 20 millisecondi.

    Per evitare soluzioni ripetute, ho fissato la faccia al centro della “croce” scegliendo il primo pezzo ruotato di 180 gradi (come nell’esempio), ottenendo 6 soluzioni valide tra cui quella data come esempio. Tutte le soluzioni hanno alcune facce ribaltate.

    Volete il sorgente? Come ve lo mando? Non me la sento di inserirlo in un semplice commento, mi sa che viene fuori una schifezza…

  10. unwiredbrain says:

    Fabio Fabbri: phpfi.com

    Aggiungi una clausola di copyright nel codice, non si sa mai :P

  11. In quel sito non c’è il supporto del Prolog… Allora ho usato l’opzione di KWrite per esportare come HTML il codice evidenziato e l’ho messo sul mio sito:
    http://stasera.altervista.org/pub/prolog/cubetti.pl.html

    L’ho testato sia su SWI-Prolog (www.swi-prolog.org) che su GNU Prolog (www.gprolog.org), ma dovrebbe funzionare anche su altri interpreti, magari con qualche modifica (ci sono anche alcuni interpreti on-line scritti in java, ma non li conosco bene e provandone alcuni non andava…)

    Per trovare tutte le soluzioni bisogna lanciare “risolvi_all.”

  12. @Fabio: inviami pure la lista delle soluzioni (nel Chi Siamo ci sono i nostri indirizzi di email) perché a seconda dell’interpretazione possono essere 3, 4, 6 o 8. A breve scriverò un addendum citando la tua e l’altra soluzione che ho ricevuto. Se qualcun altro ha intenzione di inviarcela deve farlo in questi giorni :-D

  13. Finalmente ho trovato il tempo di risolvere il problemino! Di soluzioni ne ho trovate solo 6, con l’ipotesi che il primo pezzo è fissato…

    Qua il codice, un po’ alla buona:
    http://code.google.com/p/naufraghi/source/browse/trunk/sandbox/cubetto.py

  14. @Matteo: sei arrivato sul podio! :-)
    Per curiosità, quanto ci mette il tuo programma a trovare le sei soluzioni?

  15. @marcob: Ci stiamo larghi sul podio! Quanto tempo? Meno del tempo di stampare a console…

    real 0m0.221s
    user 0m0.204s
    sys 0m0.015s

  16. unwiredbrain says:

    Qualcosa mi dice che avete seri problemi di spam… :(

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.