Re: RETO I: Indetectables punto net
Publicado: 23 Jun 2016, 12:03
Esto sin código no vale pa'ná.sanko escribió:O poneis el codigo u os dejais de tonterias cabrones
Indetectables es una Comunidad de Hacking, Seguridad Informática, Impresión 3d y Desarrollo
./index.php
Esto sin código no vale pa'ná.sanko escribió:O poneis el codigo u os dejais de tonterias cabrones
Veo por donde vas, pero me ha llamado la atención donde dices 4*(4-1) = 12, la formula para calcular el numero de combinaciones deberia ser 4*3*2*1, es decir 4!, y de forma general n!, OJITO, para este caso, si pidiera formar palabras de longitud M, sería n!/(m-n)!, que seguiria siendo válida aqui puesto que 4!/(4-4)! = 24/0! = 24/1 = 24Atrypk escribió:Bueno! Como veo que no saco demasiado tiempo y no quiero demorarlo tampoco mucho, lo que voy a hacer es explicar la solución que quería llevar al lenguaje java.
Aviso! Lee bajo tu responsabilidad, como advertí en post anteriores mi cabeza es un jodi** locura
a,h = ['a','b','c'],set()
while len(h)!=factorial(len(a)): shuffle(a); h.add("".join(a))
print len(h),hdef backtracking(nivel):
if(nivel==n):
print sol
else:
for j in range(len(vLetras)):
if not marca[j]:
sol[nivel] = vLetras[j]
marca[j] = True
backtracking(nivel+1)
marca[j]= False
#Ejemeplo con abcdef
if "__main__":
vLetras = ['a', 'b', 'c', 'd', 'f']
n = len(vLetras)
marca = [False for x in range(n)]
sol = [0 for x in range(n)]
backtracking(0)def f(a,n,p):
s,x,A = [],[],__import__("Queue").PriorityQueue() ; A.put((1, []))
while not A.empty():
(score1, s) = A.get()
for sk in a:
s_prime = s + [sk]
if s_prime[-1] not in s_prime[:-1] and len(s_prime)>0: x.append(s_prime) if len(s_prime)==n else A.put((1, s_prime))
return x
f(["a","b","c","d","e"],5,0)Coño cabron! si sigues vivo!!!, deberias pasarte por el skype a saludarnos alguna vez jajaja.SuC escribió:Hola,
Me alegra un montón que siga habiendo estas iniciativas en el foro y la gente participe, esperemos que el RETO II llegue pronto!
Espero poder empezar a participar más a menudo en el foro y en temas como este.
Sanko, me alegra ver como avanzas, eres un ídolo crack!
Saludos,
Sanko hoy folla xDSuC escribió:
Sanko, me alegra ver como avanzas, eres un ídolo crack!
Saludos,
De tu enbidia nase mi famaSadFud escribió:Sanko hoy folla xDSuC escribió:
Sanko, me alegra ver como avanzas, eres un ídolo crack!
Saludos,
Increible, Gracias por dedicar tu tiempo a estas actividades del foro, todo el mundo sabe lo valioso que es el tiempo libresanko escribió:Bueno chicas, voy a dar por concluido este reto para dar pie a alguno más sencillito y que la gente se anime a hacerlo sin que se rompa demasiao la cabeza.
Que yo sepa, han participado 3 personas, aunque directamente en el post solo han participado 2, y solo una de ellas ha proporcionado código.
Luego vamos a darle el aplauso de 10 segundos a k0ws, el aplauso de 7segs a Atrypk y el aplauso de 5 segundos a anelyus.
Primero vamos a analizar la solución propuesta por Kows:
Esta es la que más se asemeja a la fuerza bruta, es una solución no determinista, esto quiere decir que realmente cuando se ejecuta el programa no sabes con certeza que vaya a haber una solución y de hecho cada vez que ejecutes el programa para una misma entrada, la salida será siempre diferente.
Básicamente lo que el hace es un bucle que mientras que el tamaño del vector solución no tenga el mismo valor que el número de combinaciones posibles sin repetición va a desordenar el vector original usando shuffle. No es una mala solución para cuando diversas estrategias no funcionen bien pero tampoco es la solución "más correcta".
Overx se ha tomao la molestia de reformular el problema puesto que es cierto que el código tiene mucho "relleno" de por medio, no era necesario el tener que convertir strings a vectores y generar los vectores solución como strings, ese tipo de relleno hace que sea menos entendible para el resto, de todas formas es solo por que tenga una mejor legibilidad:
a,h = ['a','b','c'],set() while len(h)!=factorial(len(a)): shuffle(a); h.add("".join(a)) print len(h),h
Pasamos con la solución de atry, el no ha aportado código pero su idea no iba para nada desencaminada.
El buscaba representar el problema en forma de matriz, cada fila o columna de la matriz exceptuando la primera sería un vector solución y la idea sería ir rotando filas/columnas de forma cíclica:
Ej: Cuando rote la primera esta tendra que rotar todas las que hay a continuación y así para cada vector.
Básicamente es la misma idea que la de anelyus pero esta es un poco más original por el hecho de representar el problema en forma de matriz, lo que quieras que no es más cómodo.
La solución de anelyus es básicamente la misma, la idea de anelyus era que para cada elemento del vector se usaran n bucles. Estas 2 soluciones tienen un problema y es que os podeís imaginar que es una solución ESPECIALMENTE lenta, la complejidad se dispararía tanto que creo que para un vector de longitud 6 ya tardaria la de su madre y más.
Y aqui es donde ya os voy a poner 2 soluciones, una hecha por over (ramifica y poda) y otra propuesta por mi (backtracking), ambas son soluciones buenas pero dependiendo de los requisitos del problema sería mas conveniente usar una en lugar de la otra, para este caso el backtracking nos sobra y nos basta porque el problema es muy sencillo.
Ámbas son soluciones deterministas.
Solución por backtracking:def backtracking(nivel): if(nivel==n): print sol else: for j in range(len(vLetras)): if not marca[j]: sol[nivel] = vLetras[j] marca[j] = True backtracking(nivel+1) marca[j]= False #Ejemeplo con abcdef if "__main__": vLetras = ['a', 'b', 'c', 'd', 'f'] n = len(vLetras) marca = [False for x in range(n)] sol = [0 for x in range(n)] backtracking(0)
El backtracking es una estrategia para encontrar soluciones a problemas con restricciones, la idea que es se hace un recorrido en profundidad con el objetivo de encontrar las soluciones por "fuerza bruta" para algún problema, recalco "fuerza bruta" entre comillas porque realmente no es así, de hecho coloquialmente lo que hace el backtracking es ir probando soluciones que satisfagan las restricciones y en el momento en que se toma una decisión que incumpla la restricción se deshace el/los movimientos, descartando así las soluciones inválidas.
El backtracking (os animo a leer más de ello por el guguel) se utiliza mucho sobretodo cuando se quieren encontrar TODAS las soluciones posibles para un problema, es decir, no es una estrategia para problemas de optimización.
La solución por ramifica y poda: (made by overx)El ramifica y poda es un variante del backtracking, que para ciertos problemas mejora al backtracking.def f(a,n,p): s,x,A = [],[],__import__("Queue").PriorityQueue() ; A.put((1, [])) while not A.empty(): (score1, s) = A.get() for sk in a: s_prime = s + [sk] if s_prime[-1] not in s_prime[:-1] and len(s_prime)>0: x.append(s_prime) if len(s_prime)==n else A.put((1, s_prime)) return x f(["a","b","c","d","e"],5,0)
¿Por qué?, en ramifica y poda, el recorrido se realiza en anchura, y normalmente se utilizan colas de prioridad sobre las que puedes aplicar distintos heurísticos para que ciertos nodos no lleguen a explorarse si no fuera necesario, ¿Quién necesita explorar un subarbol entero cuando se sabe que al llegar al final no va a ser una solución válida?, como podreis deducir se ahorra un montonazo de tiempo, puesto que los arboles se generan de forma exponencial, el tiempo que se ahorra es mucho.
Ramifica y poda suele usarse más para encontrar UNA solución, normalmente la mejor solución, en este caso como el problema no necesita heurístico pues la solución por ramifica no es la mejor opción, pero es bueno tenerla en consideración para que sepais que para otro tipo de problemas el ramifica y poda MEJORA sustancialmente al BACKTRACKING.
Si alguien quisiera apuntes sobre estos 2 temas que los pida sin miedo que tengo unos resumenes bastante buenos en PDF. (2 paginitas cada estrategia mas o menos)
Para más info: [Enlace externo eliminado para invitados] y [Enlace externo eliminado para invitados]
En este caso se nota a leguas que es determinista porque para una misma entrada SIEMPRE va a tener la misma salida.
Un saludo, espero que a partir de ahora cuando tengais problemas de tipo NP: [Enlace externo eliminado para invitados] tengais en consideración estas 2 estrategias.
Si alguno piensa que esto es una estupidez sin utilidad, sepais que juegos tan conocidos como SUDOKUS, NONOGRAMAS, VARIOS TIPOS DE PUZZLES, entre un sin fin de problemas son facilmente resueltos por estas estrategias.