En http://trackmaze.blogspot.com/ nos anuncian un mini-reto javascript disponible en: http://resuelveme.tk/
Básicamente teníamos que pasar una función de validación:
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:
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
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.
Busco el caracter que tenga esta representación:
Entonces 'AAAA¯' cumple con la solución.
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:
No tenemos un entero, entonces, no existe un caracter que complete la cadena 'BBBB' para generar una solución.
Pero es sencillo hacer un recorrido secuencial o una búsqueda aleatoria y encontrar múltiples soluciones.
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) '¯'
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
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'
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:
El conjunto de caracteres en el código puede reducirse desde 'printable' hasta 'ascii_letters', y aun asi se obtienen muchas soluciones.
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:
En este caso, "ascii_letters" tiene 681445 posibles soluciones, y podemos calcular entonces la densidad de las soluciones como:
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:
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.
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.
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?
yti[G T~_m ?~Del F+y}^ !yng\ 8~3kv KqnGj ([Ymt ay5zY IyiOc …
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 …
>>> 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).
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?
Comentarios
Publicar un comentario