Portada
mis comunidades
otras secciones
![Un solucionador de sudokus de realidad aumentada hecho en WebAssembly [eng]](https://cdn.mnmstatic.net/cache/34/8b/media_thumb_2x-link-3443638.jpeg?1610928366)
#1:
Para quien prefiera leerlo en español, un artículo sobre lo mismo:
https://gotec.io/es/novedad/inteligencia-artificial-ia/ar-sudoku-solver-utiliza-el-aprendizaje-por-maquina-para-resolver-puzles-instantaneamente
https://gotec.io/es/novedad/inteligencia-artificial-ia/ar-sudoku-solver-utiliza-el-aprendizaje-por-maquina-para-resolver-puzles-instantaneamente
#2:
Supongo que no resolverá el sudoku en cada "frame". Es más eficiente conservar el resultado y mientras la imagen "input" siga conteniendo los mismos números, ofrecer la misma solución que en el frame anterior.
Ya se que la "chicha" de este artículo es el reconocimiento y la generación de imágenes en tiempo real, y no la resolución del sudoku; pero si no lo digo reviento. Me crié en una época en la que había que ahorrar ciclos de procesador.
Ya se que la "chicha" de este artículo es el reconocimiento y la generación de imágenes en tiempo real, y no la resolución del sudoku; pero si no lo digo reviento. Me crié en una época en la que había que ahorrar ciclos de procesador.
Comentarios
Para quien prefiera leerlo en español, un artículo sobre lo mismo:
https://gotec.io/es/novedad/inteligencia-artificial-ia/ar-sudoku-solver-utiliza-el-aprendizaje-por-maquina-para-resolver-puzles-instantaneamente
#1 La cuadrícula se resuelve entonces usando un módulo basado en el óxido
#73 Madre mía, sí, confieso que no he leído el otro artículo, era por si ayudaba, pero ya ves...
Supongo que no resolverá el sudoku en cada "frame". Es más eficiente conservar el resultado y mientras la imagen "input" siga conteniendo los mismos números, ofrecer la misma solución que en el frame anterior.
Ya se que la "chicha" de este artículo es el reconocimiento y la generación de imágenes en tiempo real, y no la resolución del sudoku; pero si no lo digo reviento. Me crié en una época en la que había que ahorrar ciclos de procesador.
#2 Mi práctica de la asignatura fundamentos de la programación fue hacer un programa que resolviera sudokus.
#4 Estabas en la UOC no? Yo me saque unas perras haciendosela a un conocido
#12 No, estaba en la UAH, pero vamos, que creo que el sudoku estaba muy de moda entonces.
#15 #12 es un problema sencillo de hacer entender, con un codigo desde sencillito a complicado y hacer que puede llevar el uso de varios algoritmos chulos que entiendo que es perfecto para una práctica
#26 Lo normal es que en estas practicas pongan juegos con un conjunto que tenga pocas reglas sencillas y que el alumno ya conozca y pueda resolver a mano y que sean estimulantes.
Es más, puede que al alumno ya tenga sudokus resueltos a su alcance, habida cuenta de que en pleno auge de la prensa gratuita en papel que había entonces venían pasatiempos que incluían sudoku.
#4 En una asignatura teníamos que hacer un programa que resolviera 80 sudokus lo más rápido posible.
).
La nota se basaba en lo siguiente:
- Si resolvías uno mal, suspendo.
- No resolver ninguno en 1min, también suspenso (no creo que se diera el caso).
- Si resolvías entre 1 y 80 tenías entre un 5 y 7, según cuantos resolvieras. El alumno que más resolviera tenía un 7, el que menos un 5 y los demás según la cantidad resuelta proporcionalmente.
- Si resolvías los 80 en menos de 1min tenías entre un 7 y un 9. El que más rápido los resolviera tenía un 9, el que menos un 7 y los demás según el tiempo proporcionalmente.
El punto restante iba en la documentación (¡porque documentar es importante!
Los sudokus estaban hecho a mala idea para un programa. Resolverlos a mano es imposible casi, y por fuerza bruta estaban pensado para que te encajara todo bien hasta que tenías casi todo resuelto. Entonces fallaba algo y tenías que deshacer todo.
(saque un 10)
#2 bueno resolver el sudoku es trivial modo dios,sobre todo comparado con el resto del curro, pero si supongo que hicieron esa comprobacion comparar sudoku de este frame con el ultimo resuelto si es el mismo utilizar ultimo resultado.
#2 es posible que sí lo haga por frame. El tiempo de resolución de un sudoku de este estilo puede rondar la centésima de segundo.
#7 #2 el proceso de reconocer la imagen debe de ser 50 o 100 veces mayor, así que es una optimización innecesaria.
#10 ole tus huevos, asi que como hace algo mas complicado eso no hace falta optimizarlo? jaja teniendo en cuenta que la optimizacion lleva dos lineas y ahorra cientos de veces minimo tiempo de ejecución de esas dos lineas....
#13 Es mucho más productivo dedicar el tiempo a optimizar el código que ocupa el 90% del proceso.
Es lo que aprendes cuando tienes una deadline. Lo más valioso es el tiempo de desarrollo, no el tiempo de proceso.
Pero si nos ponemos así, este servidor en sus tiempo contaba los ciclos de proceso y bloqueaba la caché con el código del bucle principal.
#16 Vamos no me vendas la moto de que contabas ciclos y me suelte la burrada esa de que como otra tarea es enorme eso no hace falta... estoy de acuerdo que si nos podemos a optimizar podemos no acabar nunca y hay momentos que ya no interesa... lo que me deja alucionado es tu criterio de oye que esto ya no lo optimizo que como va con algo mas grande pa que!! se optimiza siempre que el trabajo de hacer la optimización y el resultado merezca la pena vaya acompañado de tareas mega grandes o tareas mega pequeñas.
Estamos hablando de una optimización mega trivial!! tener en memoria el ultimo sudoko escaneado y el ultimo resultado, comparar el nuevo sudoku escaneado, si por ejempo usa strings de 81 caracteres es hacer:
if ultimosudoku=nuevosudoku then resultado=ultimoresultado. // una misera linea!!!!!!!!!!!!!
Ten encuenta que hablamos de webassembly no es codigo que corre directamente en cpu sino que se "desvirtualiza" primero. Ten en cuenta tb que la idea es que esto corra incluso en dispositivos moviles cuya potencia y autonomia de bateria depende de que tu codigo no consuma mas de lo necesario.
BTW Ponte como quieras yo comparaba los ciclos de ejecucion contra espacio de la instrución de ensamblador para hacer demos gráficas de sólo 4 kilobytes.
#16 Hombre, entre una optimización que ya tienes hecha (son 2 líneas) y otra que tienes que dedicarle mucho tiempo a ver si encuentras algo (y puede ser que no lo encuentres).
Aquello del pájaro en mano...
#31 #35 Este el el principal error humano de la programación, que lleva a las dos primeras regla de la ingeniería de proyectos:
1. Todas las estimaciones de tiempo y esfuerzo están infravaloradas.
2. Están infravaloradas POR MUCHO.
La broma es que toda estimación de tiempo se convierte en el doble de la siguiente escala. Es decir, dos días acaban siendo cuatro semanas.
Veinticinco años con proyectos. No ha fallado una sola vez.
#41 bla bla bla es un if con una condicion booleana que ahorra tocho de codigo, el tiempo de saber que ese if te lo ahorra es de 30 segundos de un programador medio decente.
#43 ¿Pero tu te crees que si fuera tan fácil no lo habría hecho ya el programador a la primera?
#45 para empezar de donde sacas que no esta hecho? Sé que es asi de fácil se trata de comparar dos arrays de 81 numeros enteros y si son todos iguales no ejecutar algo ES DE PRIMERO DE PARVULOS DE PROGRAMACIÓN
#46 No, sigue siendo un pensamiento equivocado.
1. Has gastado tiempo en pensar cómo podrías ahorrarte esos ciclos en el bucle. Si lo has pensado aquí, es algo que piensas asiduamente. Tiees un hábito nocivo de invertir tiempo en pensar cómo ahorrar bucles en un if cuando tu máquina está gastando el 99% del tiempo en analizar una imagen.
2. Para ahorrarte unos bucles has escrito una función, que es más código. Si tienes un pelín de experiencia, has hecho un código unitario para protegerte de errores. Lo que es aún más tiempo de desarrollo.
3. El código tiene un if que quizás no sea entendible. Corres el pequeño riesgo de hacer el código menos legible; algo que es crítico e importa mil veces más que cualquier ahorro de bucles que puedas sacar.
La gente que vive en el punto 1 o son muy novatos o son programadores no adaptados a un entorno empresarial en donde se exigen resultados. Yo era el primero que ponía ++i en vez de i++ en C++ porque ahorraba un pelín. Pero hacía el cóigo menos legible, que es infinitamente más importante. Era novato e hice novatadas.
#49
vaya sarta de burradas me estas troleando? por que sino es imposible ...
Tu no habras programado cyberpunk 2077 por que tiene toda la pinta de que eres su master
#51 1. Te devuelvo los negativos. Que los disfrutes.
2. i++ es más lento que ++i en la mayoría de ocasiones. Si bien en compiladores "más nuevos", la última década, el compilado seguramente esté optimizado en ambos casos por lo que no es una solución actual; sí que lo era cuando yo lo usaba y, como te he explicado, la ganancia era ridícula.
https://stackoverflow.com/questions/24886/is-there-a-performance-difference-between-i-and-i-in-c
No esperes más respuesta por mi parte a ningún mensaje más de esta noticia. Solo vienes a insultar y a molestar.
#55 tu eres el que me esas vacilando, tengo a mis compañeros de trabajo (programadores) por los suelos de la risa con tus afirmaciones.
++i e i++ no son lo mismo por lo que escoger entre uno u otro no es cuestion de gustos o velocidades depende del codigo no puedes usar uno u otro sin cambiar el resultado, por eso pense que me vacilabas añadido al resto....
++i es igual o mas rapido por que se convierte en una única instrución de ensamblador, en cambio i++ depende...
#60 No te iba responder más, pero no me puedo aguantar.
++i e i++ no son lo mismo (...) no puedes usar uno u otro sin cambiar el resultado
Madre del amor hermoso...
#75 #60 yo si sé que no estamos hablando de lo mismo por eso digo "depende del codigo".
Poca gente sabe por que existe el i++ esta hecho para convertilo a pelo en ensamblador a la instrucion INC por los compiladores de hace años eso de i=i+1 pues lo compilaban a 3 instruciones de ensamblador cargar de memoria a registro sumar a registro,1 y almacenar registro en memoria asi usado solo por eso usado sólo ++i o i++ que es cuando se puede cambiar se pasa al mismo ensamblador a inc[posiciondememoriadevariablei] (https://c9x.me/x86/html/file_module_x86_id_140.html). La diferencia en ciclos de ejecucion entre un INC y lo otro es abismal por eso exise el ++.
Es decir que lo que propone este sabiendo es usar ++i o i++ cuando es una linea única para ganar velocidad es INCORRECTO a mas no poder por que siempre el compilador generara en ensamblador: inc[posiciondememoriadevariablei] (pudiera ser un in INC registro si la variable esta ya en el registro antes)
En cambio cuando i++ o ++i forma parte de una linea mas larga y entonces el compilador puede hacer una conversión muy diferente ya que la optimizacion para la que fue pensada el i++ pierde parte de su utilidad y depende del compilador y la situacion ++i o i++ pero en todo caso en ese tipo de lineas y es donde se contraadice pues si decides usar ++i para ganar ejecucion tienes que platear toda la linea de otra manera ...
Por eso que lo dicho ni idea tiene
#51 A ver quién va a ser el troll
El preincremento ahorra unos ciclos de reloj respecto al postincremento al compilar.
https://stackoverflow.com/questions/24886/is-there-a-performance-difference-between-i-and-i-in-c
#56 Mira, hemos puesto el mismo enlace.
#45 #2 https://github.com/ColinEberhardt/wasm-sudoku-solver/blob/master/src/steps/solver.js
de hecho lo ha hecho incluso parece que tiene una cache de mas de un resultado:
#49 aprende!!
#52 Exactamente eso es lo que te decia, que seguramente ya lo habría hecho en la primera pasada.
#53 me estas troleando... no has dicho eso nunca.
#54 Es lo que quería decir y lo he dicho también en #42
#52 Ese código no pasa PR en mi equipo de desarrollo.
https://en.wikipedia.org/wiki/Magic_number_(programming)
#57 tu tienes un equipo de rugbi
#41 Una optimización trivial, como interrumpir un ciclo cuando es evidente que lo tienes que interrumpir, no se discute en ninguna parte, si sabes donde lo tienes que interrumpir es absurdo pararse a hacer cálculos de rendimiento porque vas a tardar infinitamente más haciendo cálculos que en interrumpirlo y no interrumpir un bucle no afectará significativamente al rendimiento, pero los miles que forman generalmente un programa lo más seguro es que sí.
Resumiendo: que cuando es evidente que tienes que interumpir un bucle tan absurdo es no interrumpirlo como ponerse a hacer cálculos de rendimiento para ver si merece la pena hacerlo, lo interrumpes y ahorras tiempo de programación y tiempo de ejecución. Es lo mejor de lo mejor.
#16 Si, y más productivo aún es no optimizar nada. Total si así se vende bien ¿para qué "perder el tiempo"?
#13 Sí, así es como funciona el mundo real. #10 Tiene razón. Tu pensamiento es poco práctico y poco profesional
Mucha gente se equivoca optimizando bucles chorras y gestión de memoria cuando hay otras secciones críticas que usan mil veces esos recursos y es donde hay que poner el esfuerzo.
#32 estamos hablando de poner un if y evitar un monton de bucles for. No me digas que en la vida real tu trabajo no consiste en evitar un monton de bucles poniendo un misero if por que si dices eso es no sabes tampoco programar....
Lo que tu y el otro #10 pretendeis decir es que optimizar por optimizar es de locos y estoy de acuerdo pero estoy hablando de poner un if para evitar una ejecucion mucho mas compleja....
Segun vosotros:
for i=0 to 1000000 do wahtever
no tiene sentido optimizarlo a:
if esnecesario then for i=0 to 1000000 do wahtever
no me jorobes!!
el trabajo de programador consiste en saber donde con un if ahorras una ejecucion pesada.... que yo no estoy hablando de inventar un nuevo metodo de ordenacion basado en tecnología cuantica para evitar usar una busqueda binaria de libro... estamos hablando de poner un if que ahrorra ejecutar un monton de for.... en una aplicacion de tiempo real ademassss....
#35 Posíblemente todo eso ya esté en el código original, y todo sea "un pelín" más complejo de como se ve por fuera.
#42 un if en cualquier codigo incluso en ensamblador es trivial modo dios.... no cuela
#38 gracias de verdad que pensaba que estaba en la dimension oculta... por que #32 va y le da la razón...
#40 Es que yo tengo mis años en esto. Soy de la época en que había que adaptarse al hardware.
Actualmente el programador tiene como objetivo terminar cuanto antes. No importa si quedan errores y mucho menos importa optimizar el código. Si el programa va lento el usuario ya se las arreglará comprando un ordenador más potente.
Hoy en día la gente piensa que si un software es pesado y requiere un equipo más rápido es porque debe ser bueno y hacer muchas cosas importantes.
#13 Tienes razón.@sillicon está listo para trabajar en Microsoft.
¿Para qué escribir 2 líneas más si puedes evitarlo?
#13 En general se optimiza el tiempo del programador, que suele ser mucho más caro.
https://github.com/ColinEberhardt/wasm-sudoku-solver/blob/master/src/steps/solver.js
#64 en general pero no en este caso razones:
- es un aplicación que busca hacer un monton de cosas en tiempo real cualquier mejora en el tiempo de ejecución merece la pena ver si es "rentable"
- si ya sin optimizar los tiempos son buenos quizas no merezca la pena mirar nada (si miras el video los fotogramas se saltan van justos)
- es webassemlby la idea es ejecutarlo incluso en moviles se ahorraria bateria si se sonsume menos cpu
- la optimización es mega trivial un programador medio que la ve y la escribe instintivamente en 30 segundos. (coste zero)
pero vamos que una aplicacion que realiza en tiempo real 3 tareas a b y c de pesos 1000 100 y 900 decir que si hay opcion super sencilla a reducir la de 100 a 1 no aplica por que total ya hay tareas de 1000 es....demencial..
#2 #7 me respondo: https://github.com/sunjay/sudoku 0.644 seconds to solve 95 "hard" puzzles
#2 Y digo yo, no sería mas facil hacer un reconocimiento de los numeros ingresarlos en una matriz y procesarlo como lo que son números y no imágenes. Luego ya si eso los pintas para que haga bonito. Yo también soy de esa generacion que buscaba la optimización del código, ahora da igual, es mas barato que se compren una maquina mas potente y listo que meter horas en optimizar código. Hay que vender.
#19 ¿no sería mas facil hacer un reconocimiento de los numeros ingresarlos en una matriz y procesarlo como lo que son números y no imágenes?
Eso es exactamente lo que se está haciendo.
#28 #21 Teneis razon no lo habia leido bien.
#19 100% que primero hace un OCR y luego resuelve con datos y luego pinta en tiempo real en las cooordenadas.
#2 Resuelve una vez, proyecta virtualmente muchas. Si acaso escaneará para comprobar que el sudoku no ha variado cada cierto tiempo (imagino que mientras se mantenga a la vista lo tomará por el mismo objeto, cuando lo pierda y lo recupere, lo recalculará).
Webassembly, el futuro de la web
#3 #8 #9 ¿Sabéis si Webassembly tiene una librería que sea capaz de pintarte bien en realidad aumentada datos de una matriz GPS?
Hice un estudio hace un par de años pero no encontré nada bueno que no necesitara una API externa. Apunté hasta dónde llegué y aparqué el proyecto, ahora veo esto y me gustaría indagar de nuevo. Gracias.
https://gitlab.com/CommonsVisualization/augmented-cultural-experience/-/issues/57
#c-47" class="content-link" style="color: rgb(227, 86, 20)" data-toggle="popover" data-popover-type="comment" data-popover-url="/tooltip/comment/3443638/order/47">#47 Yo la verdad es que sólo conozco la implementación para c# Blazor. Si hay alguna librería para .Net que haga lo que necesitas, debería funcionar igual en webassembly que en cualquier aplicación de servidor.
Muy interesante #0 Gracias
Hubo cierta revolución en la web con la aparción de ajax, igual esta es la siguiente revolución
Y si no te atrapa un villano y para salir de la mazmorra tienes que resolver sudokus, ¿esto para que sirve?
¿Solo para comprobar el resultado? Porque la cosa de los sudokus es hacerlos tú, no que una máquina los haga por ti.
Deduzco entonces que esto lo han hecho "porque pueden" y aparte de que se pueda implementar en otras cosas más prácticas no tiene utilidad alguna.
#8 trata de demostrar lo potente que es webassembly, una tecnologia reciente que permite darle a los navegadores la posibilidad de ejecutar codigo a velocidad de aplicacion de escritorio, lo cual abre muchas posibilidades para el futuro de la web.
#17 la posibilidad de ejecutar codigo a velocidad de aplicacion de escritorio
El código javascript ya se ejecuta a velocidad de escritorio. Es tu procesador quien lo está ejecutando (no el servidor).
Lo interesante de Webassembly es poder programar en el lenguaje que quieras. Resumiendo: olvidarnos de la basura de javascript.
#22
ಠ_ಠ, el codigo javascript no se ejecuta a la misma velocidad que una aplicación nativa, por mucho JIT que le metas a la JSVM sigue siendo un 70% de la velocidad que conseguirias con codigo nativo compilado a ASM. No hace falta ponerse puntillosos, que se te va con la pedanteria.
Por la misma regla de tres lo que dices tu tambien estas equivocado porque lo que dices ya se podia hacer antes con emscripten y ASM.js, o usando transpiladores como Babel (vease programar en typescript o coffeescript)
#27 el codigo javascript no se ejecuta a la misma velocidad que una aplicación nativa
Estás comparando peras con manzanas. ¿A la misma velocidad qué con qué? El código de una aplicación nativa, ¿en qué lenguaje respecto a qué lenguaje? ¿qué librerías de un framework respecto a qué librerías de otro framework? Porque aquí puede influir mil variables. ¿Estamos hablando de cosas que ejecuten una suma? ¿Leer un fichero?
Mmmm, perdona por ser puntilloso, pero las ventajas de Webassembly no van por el tema de la velocidad (o no exclusivamente si quieres). Van por el tema de crear un estándar más interoperable entre tecnologías para el desarrollo web.
#29 tienes razón en que una de las ventajas es poder usar otros lenguajes, pero la ganancia de velocidad es un factor MUY importante.
https://www.smashingmagazine.com/2019/04/webassembly-speed-web-app/
#25 #18 #17 #34 entiendo. Gracias a todos por las aclaraciones.
#33 👍
#8 Por supuesto que lo han hecho "porque pueden", el sudoku es solamente un MacGuffin, la gracia está en todo lo demás.
(Dicho de otra forma: Si crees que esto va de resolver sudokus entonces tal vez no lo estás enfocando de la forma adecuada).
#8 dedo, luna
#8 Es una prueba de concepto. De mostrar la potencia de un lenguaje ejecutado en un browser de cliente. De mostrar que los navegadores hoy en día son ordenadores en sí mismos.
Esta muy bien pero esto creo que ya lo hacia Google Goggles desde 2010.
#5 Lo revolucionario es que esta hecho con webassembly. La gracia es que todo ese código se está ejecutando en el navegador (cliente).
Te contesta #9
#9 Y ha quedado superlimpio
Usando DFS y un minimo de heuristicos eso se resuelve en javascript en pocos milisegundos. Fue una practica de la uni (en java en mi caso), e incluso subiendo a sudokus gigantes con un numero minimo de valores de partida era practicamente instantaneo
Eh... disculpad... pero en JavaScript normal, un sudoku lo resuelve en 1ms...
Que no digo que no sea interessante, pero como test... flojito.
#66 Lo que dices ya lo han comentado antes y se le ha respondido. Yo te diré que el hecho de resolver el sudoku es el 0,1% de lo interesante del envío.
#67 Si, lo entiendo, pero no lo venden así.
ahora me diras que:
printf(++i);
printf(i++);
es lo mismo no? que sale lo mismo en pantalla por que ya sólo te falta eso.
ahora me diras que
a= i++;
a= ++i;
"a" acaba teniendo el mismo valor no? es eso? ves como no se puede cambiar los i++ por ++i libremente que depende de donde y como se este usando?
#71 Creo que estáis hablando de cosas distintas y por eso no os estáis entendiendo. No creo que nadie esté diciendo en serio que ++i e i++ sean lo mismo (todos sabemos la diferencia, en un caso se incrementa y luego se usa el valor y en el otro caso es al revés).
Lo único que se está diciendo es que si le quieres sumar 1 a la variable y no haces nada más (es decir, no usas el valor), entonces un compilador moderno probablemente producirá el mismo código en los dos casos, y por ese motivo (repito, cuando sumarle 1 sea lo único que quieres hacer) la cosa acaba siendo más una cuestión de estilo que de eficiencia.