Alguns tenim una irresistible atracció pels enigmes.
Un dels que més m’agraden és trobar-me un paper meu antic, ple de símbols, números, diagrames o línies de programa i mirar d’esbrinar de què es tractava.
Fa uns dies vaig trobar un paper d’aquests. Però vaig recordar ràpidament que era: un programa escrit fa quasi 20 anys, en una mena de basic estructurat, amb el que vaig guanyar un concurs d’una revista britànica de l’època.
Era més aviat un concurs d’antiprogramació que de programació, ja que l’objectiu era minimitzar el nombre de línies del programa per damunt de qualsevol altra consideració. El límit era de 20 i en aquell llenguatge, només s’hi podia posar una instrucció per línia, amb un límit de 255 caracters.
Encara que m’ho han comentat, tot això no té a veure gens amb ofuscar o ocultar el codi, és una qüestió d’algorísmica amb alguna martingala per reduir el nombre de línies.
Si us agraden els enigmes aquí va aquest:
Què fa aquest programa i per què funciona?Notes:
Separo les línies del programa amb una línia en blanc a efectes de legibilitat.
El llenguatge emprava algunes expressions no gaire standard, en comento algunes a continuació:
RAND(N) : retorna un enter aleatori entre 0 i N-1
RND : retorna un real aleatori entre 0 y 1
SPACE$(N) : crea una cadena de caràcters amb N espais
TEXT X,Y,Z$ : Escriu el text Z$ a las coordinades (X,Y) de la pantalla
SWAP X,Y : intercanvia les variables X i Y
MIN(X,Y) : retorna el menor de X i Y
Les expresions lògiques tipus (A<B) retornen 0 si són falses, i -1 si són certes
X\Y : divisió entera de X entre Y
A la primera línia entre les corrues d’uns hi ha quatre espais (caracter ascii 32), no espais durs com he escrit en aquest post, ja que si fossin normals, dels quatre sols se’n visualitzaria un. (I el programa no aniria, clar)
===== INICI DEL PROGRAMA =======
a$=SPACE$(26)+"11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111+SPACE$(26)+"!#,0DHQS"
p=27+RAND(8)+12*RAND(8)
MID$(a$,p)=" "
FOR i=1 TO 63
d=8
FOR z=0 to 7
q=p+ASC(MID$(a$,145+z))-58
c=RND-("1"=MID$(a$,ABS(q-25),1))-("1"=MID$(a$,ABS(q-23),1))-("1"=MID$(a$,ABS(q-14),1))-("1"=MID$(a$,ABS(q-10),1))-("1"=MID$(a$,ABS(q+10),1))-("1"=MID$(a$,ABS(q+14),1))-("1"=MID$(a$,ABS(q+23),1))-("1"=MID$(a$,ABS(q+25),1))-9*(MID$(a$,q,1)=" ")
r=-q*(c<d)-r*(c>d)
d=MIN(c,d)
NEXT z
DRAW 80+48*((p-26) MOD 12),32+48*((p-27)12) TO 80+48*((r-26) MOD 12),32+48*((r-27)12)
TEXT 72+48*((p-26) MOD 12)-4*(i<10),38+48*((p-27)\12),STR$(i)
SWAP p,r
MID$(a$,p)=" "
NEXT i
TEXT 72+48*((p-26) MOD 12),38+48*((p-27)\12),STR$(i)
===== FI DEL PROGRAMA =======
Arxivat a [Mataneurones]
| Tags: [programacio ] | [ 
]
Comparteix:
[ 
| 
]
Demano el comodí del públic!!
En condicions normals, en lloc de fer servir una cadena de
caràcters a$ per fer de tauler, hagués emprat un array
d’enters de dues dimensions. Concretament de dimensions
(12,12). Els darrers caracters, de fet són vuit constants
amagades.
Però el programa quedava més llarg…
Per ara em trobo bastant perdut pero trobo molt interessant que el num. hi aparegui tant:
A a$ tenim 8 grups de 8 \"bits\" (8 bytes). També les 8 \"constants amagades\" que comentes. Després al crear la variable \"p\" els dos RAND són de 0 a 7, un altre cop 8 bits amb un d\’ells \"activat\" (el que retorni el RAND) i els altres \"desactivats\". O al revès?
Després al primer FOR fem 64 iteracions (8 bytes) i al segon bucle FOR fem 8 iteracions (!!).
Parles d\’un tauler de 12×12. Aquí és on hem desconcerto perquè tot indica que el programa dibuixa \"a memòria\" una posició d\’una partida d\’algun joc com escacs o dames i al sortir de l\’ultim bucle el dibuixa a pantalla amb la funció TEXT (el tauler es dibuixa dins dels bucles).
També he suposat que les 8 constants son les diferents fitxes:
Rei
Reina
Peó
Alfil (caselles negres)
Alfil (caselles blanques)
Torre
Cavall
Però em surten 7 fitxes! Si no distingeixo entre Alfils em quedo amb 6. No puc descartar tampoc aquesta teoria perquè les altres 2 constants poden ser algo que s\’em passi… Un Peó transformat en Reina o coses similars (un Rei amenaçat o amb escac-mat). També pot ser que una de les constants indiqui una casella buida
El que \"sembla clar\" (sempre fent suposicions) és el dibuix d\’un tauler amb les caselles numerades del 0 al 63 (STR$(i)?).
M\’hi acosto potser?
Volia dir \"què el num. 8 (vuit) aparegui tant\".
Per cert, m\’he oblidat de trobar explicació convincent pel que comentes de que el tauler seria una array de 12×12 :-\\
Alguna relació amb els escacs té, peró sols amb una de les seves
peces.
El fer el tauler de 12×12 és un recures usaual a molts jocs de
tauler per evitar d\’haver de mirar a cada moment si ens sortim
dels límits.
Penso que el millor per esbrinar el que fa un pugrama és
reproduir-lo en un llenguatge que dominem.
De fet, la primera implementació que vaig fer d\’aquest algorisme
(sense la part gràfica, clar, ja que la sortida eren tan sols
números) va ser sobre la calculadora HP41, amb un llenguatge
similar al forth. Tal com està ara, escriu els números en la
posició adequada.
Les constants amagades no són fitxes, podríem dir que són vuit
vectors…
No sé què vols dir amb \"que el num. hi aparegui tant\"
En un fórum sobre jocs i trencaclosques, fa uns mesos els hi vaig
posar aquest problema. El va resoldre un que havia estat
professor d\’algorísmica, que em va dir que sens veure-ho,
hagués dit que un programa que fes el que fa aquest, pel cap
baix hauria de tenir una cinquantena de línies. Però amb un
algorisme adequat es poden escurçar molt les coses.
Salutacions enigmístiques
Per cert, la numeració és entre 1 i 64.
Amb lo de \"0 a 63\" se m\’havia anat el cap, però de totes maneres el bucle fa desde 1 a 63, encara que suposo que la variable \"i\" no s\’incrementa fins que no ha fet la primera iteració amb lo que tenim 64 iteracions.
La pista sobre \"te a veure amb una sola peça\" m\’ha donat una altre idea sobre lo que pot fer però el cas és que anar dient cada X minuts \"fa això? fa allò?\" és una mica \"la cuenta de la vieja\"
De totes maneres te l\’envio en privat i ja em comentaràs
T\’ho he enviat amb el sistema d\’enviament de correu de Eines!. Espero que hi arrivi
Com en Mystix va esbrinar, el programa va d\’escacs,
concretament de dibuixar el recorregut d\’un cavall per les 64
caselles del tauler.
Primer comento el programa i després l\’algorisme.
L\’string que representa el tauler, el podem visualitzar millor així:
(Copieu-ho tot hi poseu-hi una lletra monoespaiada, courier, per
exemple. No ho poso en html perquè hi hauria problemes am els
símbols \"<\")
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
A més al final hi tenim els caràcters ASCII: 33 35 44 48 68 72 81 83
\"p\" apunta al atzar a qualsevol dels \"1\" .Serà la casella per on
anem passant.
A la posició \"p\" hi col·loquem un espai per marcar que ja està
usada.
Ara repetim el procés 63 vegades amb índex \"i\"
Per a \"z\" de o a 7, l\’expressió \"ASC(MID$(a$,145+z))-58\" ens
retorna successivament: -25, -23, -14, -10, 10, 14, 23, 25
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· X 1 X 1 1 1 1 1 1 · ·
X · 1 1 X 1 1 1 1 1 · ·
· · P 1 1 1 1 1 1 1 · ·
X · 1 1 X 1 1 1 1 1 · ·
· X 1 X 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · 1 1 1 1 1 1 1 1 · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
Si som a la posició marcada amb \"P\", els valor de les vuit \"q\" que
resulten del bucle menat per \"z\", estan marcades amb una \"X\"
(Hagués pogut fer el tauler de 12×10 sense problemes que el
cavall entrés per l\’altra banda, però el programa quedava més
fàcilment escalable escrit d\’aquesta manera)
Ara ve la línia crítica de l\’algorisme, recordem que \"q\" són les
posicions, marcades amb \"X\" al segon diagrama, a les que es pot
saltar des de \"p\", estiguin ocupades o no.
MID$(a$,ABS(q-25),1) ens torna el valor de la casella a la que es
pot arribat des de \"q\" amb un salt de valor -25, o amb dos salts
des de \"p\", el primer indicat per l\’índex \"z\" i el segon en aquest
cas pel \"25\". Si resulta que la casella és lliure ens torna -1 i si
està ocupada 0.
I resulta que fem això per als vuit possibles salts, a partir de \"p\"
passant per \"q\". Estem comptant quants segons possibles salts hi
ha des de cadascun dels salts que es poden fer des de \"p\"
Però no ens hem aturar a considerar els salts impossibles des de
\"p\" per estar ocupada la casella \"q\" corresponent. D\’això se
n\’encarrega la formula: \"9*(MID$(a$,q,1)=\" \")\". Si la casella \"q\"
estava ocupada el resultat \"c\" augmenta en 9 unitats. Cal veure
que per la primera part de la fórmula el màxim seria 8.
I el RND del començament? És un valor entre zero i un a l\’atzar.
Fa que si per a dues \"q\" corresponents a dues \"z\" el valor \"c\"
(sense el RND) fos igual, es desfés l\’empat sense alterar la seva
part entera.
Les dues següents línies actuen en cas de ser \"c\" inferior a \"d\".
En aquest cas \"r\" serà la casella on apunti el salt corresponen a
la \"z\" que estem considerant i el valor de \"d\" minvarà fins a \"c\".
Amb una estructura IF no hagués estat possible fer-ho amb dues
línies, que és el que es tractava de minimitzar en aquest
programa.
En definitiva, hem esbrinat dels possibles salts que es poden fer
des de \"p\" quin és el que té MENYS possibles segons salts. I en
cas d\’empat, n\’hem escollit un a l\’atzar. el resultat queda a \"r\" i
una vegada escrita la sortida gràfica passarà a \"p\".
Naturalment, si el primer salt no era possible la part de la
fórmula \"…9*(MID…\" se n\’encarrega de que \"c\" sigui sempre
superior a \"d\" i no pugui se escollit.
La resta del programa és trivial.
L\’algorisme.
La idea \"canònica\" de com resoldre aquest programa seria un
algorisme de prova i error: vaig saltant, i si no puc més, tiro
enrera i agafo un altre camí.
Lògicament, seria un algorisme recursiu que pugés un nivell per
avançar casella i en retrocedís un en trobar-se sense sortida.
Però hi ha un problema, si als primers salts bloquejem una
casella, és possible que no ens trobem amb la impossibilitat de
saltar fins a la fi del recorregut, i la pila de recursió que hauria
de mantenir el programa seria monstruosa.
Per evitar-ho poden haver-hi diverses estratègies: dividir el
tauler en zones que s\’han d\’omplir successivament, fer una llista
de \"multisalts\" per avançar vàries caselles a cada nivell, esbrinar
unes regles heurístiques que avaluïn quin possible salt és el
millor a partir d\’una posició concreta, fer que el programa eviti
carrerons sense sortida…
Va ser amb aquesta darrera idea que vaig veure el següent: Si
des de la casella \"a\" puc saltar per exemple a \"b\", \"c\", \"d\" i \"e\" i
resulta que des de \"d\" sols tinc una sortida (un sol possible
segon salt), he d\’agafar el camí de \"d\" necessàriament, ja que en
cas contrari \"d\" es convertiria en un cul de sac, dit d\’una altra
manera, una casella que si hi anem a parar ja no en podrem
sortir.
D\’això en surt una primera regla empírica \"si des d\’un lloc pots
saltar a una casella des de la qual sols es pot saltar a una altra,
has de fer precisament aquest moviment\"
I si podem anar a una casella des de la que no es pot fer cap
altra salt? Si és la darrera serà el normal, hem de saltar a ella a la
força. Si no ho és, és que estem en un carreró sense sortida.
D\’agafar el camí que té una sola (o cap) sortida a agafar el que
en té menys hi ha un petit pas. No sé si fàcil o difícil, però ho
vaig provar. Amb un programa força més llarg, clar. I resulta que
partint d\’una casella a l\’atzar i escollint aleatòriament en cas
d\’empat, el problema té solució en més del 98% dels cassos.
Es pot afinar l\’algorisme perquè funcioni sempre, però la
complicació i la velocitat no compensen el haver de repetir el
procés un 2% dels cops.
De fet, els algorismes paradoxals de mínims són freqüents. Si feu
jugar dos programes d\’othello, un que a cada jugada miri de girar
el màxim possible de peces i un altre que miri de girar-ne el
mínim, guanya sempre el del mínim.
Caram, caram…
Ha estat genial tot plegat! bastant complicat però suposo que això és lo
que aporta el factor \"repte\"