¿Alguien conoce una web con retos de programación medianamente complicados? Hay veces que me apetece programar algo medianamente corto, y un reto de programación sería lo ideal, la cuestión es que no encuentro por Google.
resolver un sudoku, hacer un snake con números, mostrar por pantalla exactamente el mismo código que usas para realizar ese programa, etc
Te vas a hartar de programar, te lo garantizo xD
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8
Salu2 
PD: respecto a lo que comenta #2 de sacar el código fuente del programa mismo (cosa que a priori puede parecer imposible sin hacer "trampas"...) -> http://es.wikipedia.org/wiki/Quine_(programa)
PD2: se me olvidaba, los enunciados de los problemas están en inglés.
Pero coño, esto no son retos normales...
Interviene IA en altos grados, algebra, metodos de resolucion determinísticos, etc...
Eso no son retos, eso son problemas! xDD
Ais el "vicio del programador"... que extraño como nos cala a algunos eh? Dicen que con el tiempo se pasa...
Por cierto, dicen "se considera que abrir el cpp, leerlo y mostrarlo es trampa". Y van y se dedican a crear un char que contiene basicamente el codigo y lo imprimen... MUY BIEEEN! xD
Lo curioso del tema, es no caer en una recursividad infinita. Revisando algunos de ellos, creo que sencillamente cambian el contenido de la cadena por el simbolo cadena...
Bueno, como me aburría he hecho caso a #2 y he hecho un solucionador de Sudokus por fuerza bruta que me ha ocupado poquísimo. Desde aquí animo a la gente a que hagan su propio solucionador, y luego los publicamos a ver cuál se curra el más corto/más rápido/más ingenioso.
Vamos, si os apetece... xD
De momento al mío creo que le voy a añadir algunos algoritmos heurísticos para que no sea solo fuerza bruta 
Aunque bueno, me tira más la web de #3/#4, voy a ver si hay algún problema interesante. ¿Hay que tener cuidado de no acabar con \n el output y cosas de esas?
Sudoku es un problema NP (además, completo).
Por reducciones se demuestra.
Sabes lo que es un SAT Solver?
MiniSat... que recuerdos...
Mira, un screen del programa que hice:
Le dabas un sudoku, y hacia maravillas!
Ademas, al final como resultado te daba el sudoku sin resolver y el sudoku resuelto por satsolver.
Que gran programa!
Puse el sudoku nuevo y solucionado uno al lado del otro, para que se puedieran imprimir i plegar, y así ibas con las solucion debajo, mientras los hacias. xD
ImageMagick usé para hacer el sudoku visual y todo! xD
#5 intenta hacerlo tu solo sin copiar el de la wikipedia y verás como no puedes xDD.
Piensa que al hacer el printf("") ese propio printf con toda la cadena que metes dentro, es también parte del programa y entonces tienes que imprimir también la función que gastas para imprimir.
#9 por fuerza bruta he usado un algoritmo recursivo muy simplito, no sé si eso es backtracking. Te lo subo a pastebin para que lo veas. http://pastebin.com/f291f65ea
Hay que tener en cuenta que se te dispara el tiempo de cálculo como te descuides, aunque de momento los sudokus que le he metido los resuelve rápido (Pero se le va la pinza con Sudokus con muchas soluciones.)
Backtracking es llegar a una solución, ver que no puedes continuar por ahi y volver a la anterior y probar con otra combinación a ver si es mejor. Si pudieras pegarmelo y asi lo veo para hacerme una idea de como lo has hecho, porque me pica la curiosidad. Se que hay un modelo matemático para resolver sudokus, pero nunca lo he aplicado xD
Perdona se me había olvidado poner el link, ahí lo tienes xD Creo que sí, que lo que hago es backtracking por lo que explicas.
Te dejo 2 problemas que supongo que los habras hecho ya, pero bueno:
El problema de las 8 reinas. Disponemos de un tablero de ajedrez de tamaño 8x8, y se trata de colocar en él ocho reinas de manera que no se amenacen según las normas del ajedrez, es decir, que no se encuentren dos reinas ni en la misma fila, ni en la misma columna, ni en la misma diagonal. Sacar todas las soluciones posibles.
El problema del caballo de ajedrez. En un tablero de ajedrez y saliendo de la casilla que uno quiera, hay que mover un caballo de manera que pase por cada una de las casillas una sola vez. Implemente un algoritmo recursivo basado en la vuelta atrás para resolver este problema.
En cuanto pueda le hecho un vistazo con mas tranquilidad.
NinjaEdit: Fack! Te imprime todas las soluciones en un fichero txt... La verdad es que el programita esta currado.
En la FIB de la UPC hay una ALE que se llama "Reptes de Programació", (Retos de Programación) para los de la LOGSE. Esta asignatura esta pensada de cara a un concurso de programación que se celebra cada año en la universidad. Yo ahora estoy bastante desconectado pero era bastante interesante. Cuando yo la hice, consisitia en resolver 12 "retos de programación". Solucionando los 12 obtenias el 10, con 6 problemas solucionados sacabas un 5. Aún así el principal obejetivo era inducir a la gente a participar en el concurso final, el cual premia a los mejores participantes con invitaciones a concursos a nivel Europeo y Mundial.
De esta ALE ha salido gente muy buena que ha ganado premios a nivel mundial. En la página salen sus logros.
Esta es la página web, por desgracia solo la encontrado en catalan (si alguno tiene algun problema con la traducción que postee y traduciré gustosamente)
He hecho una pequeña modificación al código del Sudoku que mejora y mucho la eficiencia. Ahora sólo prueba los candidatos que de verdad valgan.
775.140 segundos tardaba antes frente a los 335.383 que tarda ahora con el sudoku que puso bLaKnI. Supongo que a él le tardaría mucho menos siendo un SAT solver en lugar de usar backtracking (De hecho probablemente lo resuelva al instante.)
Ahora que lo pienso, debería haber hecho otra matriz en la cuál se guarde no sólo el sudoku sino un mapa de bits de los candidatos cambiando sólo en cada paso lo que tenga que cambiar, pero me he aburrido y no me apetece seguir xD Aparte de que creo que con el "approach" que he seguido tendría que rediseñar bastante. De momento con esto me sobra, así que voy a pasar a otros problemas.
Si a alguien le apetece seguir optimizando a lo mejor me animo a seguir yo también... De momento pondría una función que antes de generar nada del Sudoku lo sanease, es decir, que lo que se pueda hacer sin prueba y error lo haga. Me parece que sólo con esto ganaría en velocidad muchísimo.
EDIT: http://pastebin.com/f139a9857 Tras unas pequeñas modificaciones, ahora tarda 46 segundos con el Sudoku de bLaKnI. No está mal Poner el vector sudoku como global en lugar de pasarlo por referencia ahorra 2 decimas, inapreciable, así que lo dejo como está.
Según he estado viendo, el primero que hicistes hacia todas las soluciones posibles, independientemente de que estuvieran bien o mal, y luego las miraba una por una y descartaba las malas, no??? Hay otra manera, y es que cada linea, columna y cuadrante tiene que sumar 45 y que no se pueden repetir números, es otra manera.
Tal y como está ahora mismo sólo prueba los números que no hayan sido usados en la fila, columna o cuadrante correspondiente. Echa un vistazo a la función generaPosibles()
EDIT: Añadida lógica básica al programa. Menos de un segundo en resolver el sudoku de bLaKnI, habrá que probar con sudokus más difíciles que requieran métodos lógicos más complejos. http://pastebin.com/ff8b17d5
Qué mamón 
, te iba a poner una ligera optimización que le había hecho a tu penúltima versión que le recortaba unos 15 segundos en el de blanki pero luego me meto y veo que en la última has metido heurística ("sencilla" pero heurística al fin y al cabo). Menudo owned jojojojo Buen trabajo, va como un tiro
Ya postearé la mia (cuando le meta "truquis", porque la de bactracking va a pedales comparada con la tuya última). A ver si termino los exámenes arggg ¬¬...
Salu2
ElKaoD, por curiosidad, que es lo que estudias??
Yo te pongo uno facilito, entro en mi examen de MTP de este año:
Mr. Scrooge ha cobrado una antigua deuda, recibiendo una bolsa con n monedas
de oro. Su olfato de usurero le asegura que una de ellas es falsa, pero lo único
que la distingue de las demás es su peso, aunque no sabe si éste es mayor o
menor que el de las otras. Para descubrir cuál es falsa, Mr. Scrooge dispone de
una balanza con dos platillos para comparar el peso de una o varias monedas. En
cada pesada lo único que puede observar es si la balanza está equilibrada, pesan
más los objetos del platillo de la derecha o pesan más los de la izquierda.
a) Diseñar un algoritmo para resolver el problema de Mr. Scrooge (encontrar la
moneda falsa y decidir si pesa más o menos que las auténticas). Estudiar la
complejidad del algoritmo.
La idea es currarse un algoritmo que te lo resuelva en un tiempo eficiente.
LOc0, ¿Cuál era la optimización? 15 segundos de optimización es un cojón y si te soy sincero ya no veía cómo optimizar más la búsqueda por fuerza bruta. Espero ansioso que subas código
Gan, ahora mismo en 2º de bachillerato. Supongo que se nota por la forma en que programo xD Sobre el problema que propones, ¿Eso no era un problema de lógica? Me suena que hay una forma de hacer que en dos pesadas o así (Hablo de memoria, me parece que las n monedas eran... ¿3? Ni me acuerdo) se sepa... o a lo mejor no y era sólo un problema parecido y recuerdo mal xD
Pues para estar en 2º de bachillerato tienes un nivel de programación que ya la quisieran muchos que estudian ingenieria informática, creeme.
Para el problema que propongo hay varias soluciones, desde pesar una a una para encontrar la moneda hasta pesar en grupos, el tema es encontrar un método eficiente, porque como tengas muchas monedas la complejidad se dispara. El truco es hacerlo por divisiones con divide y vencerás, ir dividiendo las monedas en grupos de 3 y comparandolas entre si, como ves tampoco es nada dificil.
Es lo que había pensado, ir dividiendo las monedas en subgrupos de monedas/3 elementos, comparar esos grupos de dos en dos (Sólo G1-G3 y G2-G3) y si son iguales descartarlos y tomar como número grupo de monedas las que no entraban en la pesada. Si en la pesada no son iguales, hacer de esas monedas de nuevo subgrupos de monedas/9 elementos y así sucesivamente hasta que haya un grupo de 3 elementos. Si hay monedas sobrantes y los tres grupos son iguales simplemente se crea un nuevo grupo con esos sobrantes y una moneda cualquiera. pero Sospecho que ésta no es la solución óptima.
Luego he pensado que si tienes por ejemplo 4/5 monedas lo óptimo sería hacer grupos de 2 (Ya que puedes), es decir, maximizar el tamaño de los grupos teniendo en cuenta que sólo se usan 2 de esos grupos (No sé si me explico bien xD) para tener un menor número de pesadas. En el caso de 5 monedas, con monedas/3 como número de elementos, saldrían 3 grupos de 1 y dos monedas sueltas, mientras que se puede hacer simplemente un grupo con 2 monedas, otro con otras dos y otro grupo con una moneda cualquiera que haya dado como igual (Si no ha dado como igual la primera pesada, el grupo ni se neceista, total, no vale de nada...)
Ésto no importa en casos con pocas monedas, pero en casos con un montón de monedas seguro que ahorra pesadas.
PD: Supongo que eras GaN2vsKirbys en HR, ¿Verdad? ¿O es sólo casualidad?
Si, soy el mismo xD
El metodo que vas a seguir esta bien, de hecho es el que yo use en el examen y creo que me lo puso bien, pero creo que hay uno aun más facil y que no hace falta preocuparse cuando los grupos no sean divisibles en 3.
No se me ocurre otro método que no sea dividiendo en grupos de tres. De todas formas, pensando un poco mejor el segundo razonamiento (El de que si hay monedas sobrantes se repitan), creo que es casi correcto, pero quizá es mejor hacerlo de otra forma. Lo pongo en forma de ejemplo. Si tenemos 99 monedas, se hacen grupos de 33 elementos. Si tenemos 98 monedas se hacen grupos de 33 elementos, estando uno de esos elementos presente en los dos grupos (Sólo se repite una moneda.) Sin embargo si tenemos 100 monedas, ¿No sería correcto hacer también grupos de 33 elementos? Así, si las dos pesadas en las que se comparan los grupos son iguales, sabemos que la moneda distina es la que queda suelta y además nos ahorramos que si hay dos monedas sueltas y alguna de esas dos es la distinta (El peor caso de todos), haya que iterar hasta el final.
Luego simplemente habría que programar resolver cuando se ha reducido a los casos n=3 o n=4 (Para n=4 con lo que estoy comentando, el numero de monedas por subgrupo es 1, lo cuál me hace pensar que está mal mi razomiento porque en ese caso lo óptimo es que el número de monedas por subgrupo sea 2.)
O eso o me estoy montando ya pajas mentales. El problema éste me resulta más interesante pensar cómo sería la solución mínima que programarlo xD
elkaoD -> http://www.hackvalue.org/fuentes/coloreator.php?fichero=medio_sudoku.c
Un 30% más rápido con este por ejemplo (el de blanki lo hacen los dos follados porque no necesita apenas backtracking):
001|004|000
000|060|305
000|900|000
---+---+---
800|000|703
000|000|028
500|070|600
---+---+---
300|080|006
009|200|000
040|001|000
Formato de "ristra":
..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1...
Hala, ahora vas y lo cascas
Salu2
PD: ya me hubiera gustado programar (y "algoritmizar") como tú con tu edad...
PD2: como verás, la mejora de velocidad se consigue sacrificando algo de memoria así que ¬¬...
Editado: Le he metido unas pequeñas estadísticas de uso.
Editado2: Modificada la forma de leer el sudoku para que se pueda introducir de la forma que se quiera. Ahora ignora cualquier caracter distinto de los numéricos y el que representa el "hueco" (que por defecto es el '.' aunque se puede meter como parámetro opcional otro distinto).
No te lo vas a creer, he arreglado una tontería y ahora por fuerza bruta ese sudoku se resuelve en la mitad de tiempo con tu programa. De todas formas, que conste que es sólo casualidad xD
Me explico. Al leer el sudoku y al imprimirlo estaba poniendo los valores de la x en la y, y los valores de la y en la x (sudoku[casilla/9][casilla%9] debería haber sido sudoku[casilla%9][casilla/9]) Funcionaba todo bien, pero las filas se consideraban columnas y al revés. Ahora tarda la mitad por fuerza bruta porque da la casualidad de que llega antes a la solución de ese sudoku haciendo la fuerza bruta columna por columna, y al estar ahora el sudoku bien guardado en memoria, empieza columna por columna (Antes sólo parecía que iba por columnas, pero en realidad iba por filas al estar volteado el sudoku en memoria.)
Si pones el simétrico de ese sudoku como entrada, vuelve a tardar más que con tu algoritmo sin usar el sudoku simétrico. El caso es que si a ambos algortimos les das el sudoku simétrico, el tuyo sigue mejorando (Más o menos la mitad de tiempo) respecto al mío, por lo que creo que arrastramos el mismo error (O tu algoritmo va por filas mientras que el mío va por columnas.)
En definitiva, que tu algoritmo sigue siendo más eficiente que el mío.
A ver si saco tiempo y le echo un vistazo a tu código que ahora mismo no puedo, y no sé exactamente qué optimizaciones tiene.
Resulta que el problema que plantee antes lo tenia bien en el examen xD A ver si me lo manda un compañero mio (la solución) y la posteo, porque no me acuerdo como lo hice xD
99 problemas para programadores de Lisp o Scheme
http://www.ic.unicamp.br/meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html
Y mi favorito, el Proyecto Euler...
hay problemas de todo tipo, lógicos, matemáticos... algunos realmente interesantes
en particular intento resolverlos todos en SharpScheme, creo que es una gran forma
de aprendizaje.
http://projecteuler.net/
