martes, 21 de mayo de 2013

Mini-Reto JavaScript de TrackMaze

En http://trackmaze.blogspot.com/ nos anuncian un mini-reto javascript disponible en: http://resuelveme.tk/

Presentación del reto

 Básicamente teníamos que pasar una función de validación:

function verificarContra( respuesta )
{
    var conteo1 = 3, conteo2 = 5;
    var suma1 = 0, suma2 = 0;

    var listado = "CASH9";

    for( i = 0; i < respuesta.length; ++i ) { suma1 += ( respuesta.charCodeAt( i ) * conteo1 ); conteo1++; }
    for( i = 0; i < listado.length; ++i ) { suma2 += ( listado.charCodeAt( i ) * conteo2 ); conteo2++; }

    (suma1 == suma2&& respuesta.length==5) ? alert("Superado, sera redireccionado") : alert( "La respuesta es incorrecta, intentalo de nuevo" );
}

Vemos que se hacen dos sumas: suma1 se calcula desde respuesta usando conteo1 y suma2 se calcula desde listado usando conteo2.  Si las sumas dan iguales y la longitud de la respuesta es seis, pasamos la validación.

El las sumas lo que hacemos es tomar caracter a caracter de la cadena que nos interesa, calcular su representacion numerica con charCodeAt y a cada representación la multiplico por el conteo correspondiente.  Estos conteos incrementan caracter a caracter.

Para calcular el valor esperado use esto:

>>> sum( (i + 5) * ord(j) for i,j in enumerate('CASH9') )
2395

Donde calculo la suma de las multiplicaciones entre las representaciones de cada caracter y su posición contando desde cinco.   La suma esperada es 2395.

Nuestra respuesta tiene un comportamiento similar pero contando desde tres, no desde cinco.  Entonces, inicio con una cadena de cuatro caracteres como 'AAAA' y calculo la diferencia entre el valor esperado (2395) y la suma que llevo con estos cuatro caracteres

>>> 2395 - sum( (i + 3) * ord(j) for i,j in enumerate('AAAA') )
1225

Necesito un carácter cuya representación multiplicada por el factor correspondiente me de un resultado igual a 1225.

El factor correspondiente para el caracter en la posicion 5 es 7 (al que esta en la posicion 1 le sumo 3, al de la dos le sumo 4, y asi, entonces al de la poscion 5 le sumo 7).

Busco un carácter cuya representación multiplicada por 7 me de un resultado igual a 1225.

>>> 1225/7
175.0

Busco el caracter que tenga esta representación:

>>> chr(175)
'¯'

Entonces 'AAAA¯' cumple con la solución.

Reto superado

Siguiendo el mismo procedimiento puede verificarse que 'HACK¢' es otra solución. La mejor de todas :)

Sin embargo, es claro que no todas las cadenas iniciales de cuatro caracteres pueden generar una solución:

>>> 2395 - sum( (i + 3) * ord(j) for i,j in enumerate('BBBB') )
1207
>>> 1207/7
172.42857142857142

No tenemos un entero, entonces, no existe un caracter que complete la cadena 'BBBB' para generar una solución.

O incluso, podemos encontrar caracteres que si existen, pero no son imprimibles:

>>> 2395 - sum( (i + 3) * ord(j) for i,j in enumerate('RDMS') )
994
>>> 994/7
142.0
>>> chr(142)
'\x8e'

Pero es sencillo hacer un recorrido secuencial o una búsqueda aleatoria y encontrar múltiples soluciones.

from string import printable
from random import choice
esperado = sum((i + 5) * ord(j) for i,j in enumerate('CASH9'))
while True:
    candidato = ''.join(choice(printable) for x in range(4))
    control = esperado - sum( (i + 3) * ord(j) for i,j in enumerate(candidato) )
    if control % 7 == 0:
        complemento = chr( int ( control / 7 ) )
        if complemento in printable:
            print( candidato + complemento )

Aunque con este código solo genero soluciones ascii, igual se generan muchas soluciones válidas diferentes, como las siguientes:

yti[G
 T~_m
?~Del
F+y}^
!yng\
8~3kv
KqnGj
([Ymt
ay5zY
IyiOc

El conjunto de caracteres en el código puede reducirse desde 'printable' hasta 'ascii_letters', y aun asi se obtienen muchas soluciones.

kBroR
tObYe
UCuUo
QrxPX
aZoGm
pHnJo
XgUqX
TVecd
WbqaU
DzZiY

Solo por curiosidad puede uno lanzar algo como esto:

from string import ascii_letters as charset
from itertools import product
contador = 0
esperado = sum((i + 5) * ord(j) for i,j in enumerate('CASH9'))
for producto in product(charset,repeat=4):
    candidato = ''.join(producto)
    control = esperado - sum( (i + 3) * ord(j) for i,j in enumerate(candidato) )
    if control % 7 == 0:
        complemento = chr( int ( control / 7 ) )
        if complemento in charset:
            contador += 1
            # print( contador, candidato + complemento )
print(contador)

Si lo dejamos correr asi, tendremos el conteo de soluciones para el conjunto de caracteres seleccionado. O, si descomentamos la linea que dejo comentada tendremos en la salida todas las soluciones ordenadas, algo como:

1 aaajU
2 aaaqO
3 aaaxI
4 aaaGs
5 aaaNm
6 aaaUg
7 aabhV
8 aaboP
9 aabvJ
10 aabEt

En este caso, "ascii_letters" tiene 681445 posibles soluciones,  y podemos calcular entonces la densidad de las soluciones como:

>>> contador / len(ascii_letters) ** 5
0.0017923139752500047

Con lo que podemos concluir que en el conjunto de caracteres ascii_letters, la densidad de soluciones es casi de dos en mil.

Verifique también que no es posible resolver el problema solo con números, o solo con mayúsculas o solo con minúsculas, pero si es posible hacerlo solo con signos de puntuación.

Ademas, como curiosidad final, es posible resolverlo con solo dos caracteres diferentes.

En el caso del conjunto de caracteres de puntuación, solo hay dos soluciones que cumplen este criterio:

&{&{{
``_``

En el caso de "ascii_letters", encontre 67 soluciones:

bbWbb
ccScc
cOccc
ddddU
ddOdd
eeKee
eXeXe
ffGff
gggIg
ggCgg
ggXgX
gSSgg
gUgUg
iRiRi
jYYYj
kkkkC
kOkOk
mmOOm
mLmLm
mOmmO
mWWWm
oIoIo
pCCpp
pUUUp
qFqFq
rrrOO
ssKsK
sCsCs
sSSSs
sUUsU
vQQQv
xxAAx
xAxxA
yyVVV
yOOOy
Adddd
CppCp
CsssC
CCkkk
FqqqF
HkHkk
IoooI
KKKss
LmmmL
LyLLy
LLyyL
OkkkO
OyOyO
OOrOr
QvQvQ
RiiiR
SggSg
SsSsS
UgggU
UpUpU
UssUU
UUddd
VVVVy
Waaaa
WkWWk
WmWmW
WWkkW
XeeeX
XXXgg
YcYcc
YjYjY
ZZwZZ

Curiosamente solo hay dos soluciones en la que se usa la misma letra en mayúsculas y minúsculas.  Y las dos son con la misma letra, asi que 'sSSSs' y 'SsSsS' seran mis soluciones favoritas a este reto (al menos dentro de este charset limitado).

No hice pruebas con el charset "printable" (UPDATE: ya se hizo, esta al final).  Tampoco intente con el grupo de los UNICODE printables que es mucho mas extenso.  Dejo eso de tarea como un reto mas avanzado.

Reto superado

En ultimas, un reto sencillo pero entretenido.  Gracias a la gente de TrackMaze… Y gracias a http://markup.su/highlighter/ por el resaltado de sintaxis.

UPDATE (3 horas despues):
Corregi el código que estaba usando para la busqueda secuencial en "ascii_letters", pues desperdiciaba un generador para crear una lista, en lugar de usarlo directamente.  Asi, fue posible calcular la densidad para el rango "printable" sin excesivo uso de memoria.

from string import printable as charset
from itertools import product
contador = 0
esperado = sum((i + 5) * ord(j) for i,j in enumerate('CASH9'))
for producto in product(charset,repeat=4):
    candidato = ''.join(producto)
    control = esperado - sum( (i + 3) * ord(j) for i,j in enumerate(candidato) )
    if control % 7 == 0:
        complemento = chr( int ( control / 7 ) )
        if complemento in charset:
            contador += 1
            # print( contador, candidato + complemento )
print(contador)

Encuentra 4445918 soluciones de entre 100 ** 5 strings posibles (densidad = 0.0004445918).   En este charset hay 132 soluciones que incluyen solo dos caracteres diferentes.

Reto adicional: Que porcentaje de entre las 132 antes mencionadas son palindromos? En general, ¿que porcentaje de las soluciones es palindromo? ¿que porcentaje es simétrico (es decir, el inverso de una solución es también solución)?

Reto adicional: Considere el caso de los pares de soluciones ('|MMM|', 'M|M|M'),  ('[ccc[', 'c[c[c'), y ('jYYYj', 'YjYjY'), entre otros.  Desde estos pares de soluciones, puede pensarse que: si los caracteres de los extremos son iguales y los caracteres interiores son iguales entre si, es posible reordenandos para que los que antes eran extremos queden en las posiciones 2 y 4 y el resultado también es solución   ¿Se cumple esto para todos los pares de soluciones que cumplen esta condición  ¿Cuantos pares de soluciones se encuentran en el rango ascii printable?

No hay comentarios:

Publicar un comentario