domenica 2 ottobre 2016

Quesito con la Susi n. 936

Le precedenti puntate:

La (vecchia) Settimana Enigmistica che mi è capitata sotto gli occhi stamattina presenta il quesito 936°, che si può risolvere con la forza bruta (di nuovo).

Mi è venuto “spontaneo” farla in Python, che è anche quello che uso più spesso per i problemi di Project Euler che sto trascurando da un bel po', invero. A differenza dei problemi di Project Euler, con la Susi non dobbiamo temere di confermare che la soluzione peggiore (forza bruta) è appunto la peggiore, e non funzionerà in un problema successivo, simile ma “più grande”.

In questo problema abbiamo una matrice di 5×5 e la soluzione forza-bruta è ancora accettabile.

Il quesito sfronzolato è questo: data una matrice 5×5 (detta tabellone nel quesito), “togliere” cinque numeri in modo che la somma dei numeri in ogni riga e in ogni colonna sia uguale (se il vincolo fosse anche sulla diagonale, avremmo a che fare con un quadrato magico).

24   8  15  18   13
20   6  11  17    1
 7  21  12   2   14
22  19   3   9    4
 5  25  16  10   23

Il quesito chiede la somma dei cinque numeri “cancellati”.

La soluzione in Python ve la risparmio — cioè risparmio un gist: usando itertools genero delle permutazioni di lunghezza 5 di 25 simboli (i numeri da 0 a 24); un singolo “simbolo” diventa un indice di riga e colonna che uso per “cancellare” (metto 0 al posto del valore) il valore corrispondente del “tabellone”. Quindi ogni permutazione cancella 5 numeri. Fatto ciò non ci resta che verificare quanto fa la somma dei numeri in ciascuna riga e colonna. Quando sono tutti uguali la permutazione in esame identifica le 5 “coordinate” dei numeri cercati; le usiamo per “pescarli” e sommarli et voilà la soluzione.

Non c'è niente di nuovo (Python? già usato… Tentare tutte le possibili soluzioni e verificare ogni volta che quella in esame sia veramente la soluzione controllando direttamente se i vincoli sono violati o meno? già usato…); anche per questo risparmio il codice.

Anche l'implementazione fatta al volo non ha niente di interessante, specie per pythonisti incalliti (che anzi di sicuro troverebbero da dire e avrebbero già pronto un modo migliore di scrivere la stessa roba).

Quindi passiamo ad altro, ovvero al J. Non sono sufficientemente conoscitore di questo linguaggio per poterci fare qualcosa di “produttivo” (ehm), però ho perso 2 minuti con quel poco che ricordo di quel poco che ho visto, per cui…

   t =: 5 5 $ 24 8 15 18 13 20 6 11 17 1 7 21 12 2 14 22 19 3 9 4 5 25 16 10 23
   t
24  8 15 18 13
20  6 11 17  1
 7 21 12  2 14
22 19  3  9  4
 5 25 16 10 23
   +/t
78 79 57 56 55
   +/|:t
78 55 56 57 79

Avremmo potuto vedere quel che si vede con milioni (si fa per dire) di altri strumenti ben più semplici e meno potenti del J.

Con +/t abbiamo la somma di ciascuna colonna (24 + 20 + 7 + 22 + 5 = 78, 8 + 6 + 21 + 19 + 25 = 79, ecc.) e +/|:t di ciascuna riga (24 + 8 + 15 + 18 + 13 = 78, 20 + 6 + 11 + 17 + 1 = 55, ecc.)

Ovviamente “togliendo” l'elemento tij la somma della i-esima riga e quella della j-esima colonna diminuiscono proprio di tij; perciò possiamo trovare la soluzione a occhio dopo aver notato le somme uguali (prima riga e prima colonna, ultima riga e seconda colonna, ecc.).

Sommiamo gli elementi “tolti” a mano e otteniamo la soluzione (55).

Nessun commento:

Posta un commento

Sii educato, costruisci con cura le frasi, rifletti prima di pubblicare, evita parolacce e offese dirette, non uscire dal tema, cerca di non omettere la punteggiatura, evita errori ortografici, rileggi quel che hai scritto.