SQL-Experiments: experimentando queries alternativas en SQL

Como ya sabréis, el lenguaje SQL permite procesar los datos contenidos en una BDD ya sea a la hora de consultarlos, insertarlos, borrarlos, o actualizarlos.
Si queremos hacer con ellos operaciones más complejas, lo habitual es, una vez obtenidos en SQL procesarlos en Java, PHP,...
Pero... ¿hasta que punto podemos ejecutar algoritmos dentro de la propia query SQL?
Recientemente he creado un nuevo respositorio en mi Github donde subir algunos experimentos.

Para inaugurar el repositorio, he subido una query recursiva que permite ejecutar el algoritmo dinámico de Longest common subsequence problem que tambien podeis encontrar en HackerRank bajo el nombre de Commond Child. La query final para SQLite me quedó así de bonica:

WITH
INPUTS(I1,I2) AS (
 SELECT 'HARRY','SALLY'
 UNION ALL SELECT 'AA','BB'
 UNION ALL SELECT 'SHINCHAN','NOHARAAA'
 UNION ALL SELECT 'ABCDEF','FBDAMN'
),
RESULTS(I1,I2,X,Y,A) AS (
 SELECT I1,I2,0,1,'0000'
 FROM INPUTS UNION ALL
 SELECT I1,I2,
  CASE WHEN X=LENGTH(I1) THEN 0 ELSE X+1 END,
  CASE WHEN X=LENGTH(I1) THEN Y+1 ELSE Y END,
  CASE WHEN X=LENGTH(I1) THEN '0000' ELSE
  SUBSTR('0000'||(
   CASE WHEN SUBSTR(I1,X+1,1) = SUBSTR(I2,Y,1)
   THEN 1 + CAST(SUBSTR(A,1+4*(LENGTH(I1)+1),4) AS INTEGER)
   ELSE MAX(CAST(SUBSTR(A,1+4*LENGTH(I1),4) AS INTEGER),CAST(SUBSTR(A,1,4) AS INTEGER)) END
  ),-4,4) END || A
 FROM RESULTS
 WHERE NOT (X=LENGTH(I1) AND Y=LENGTH(I2))
),
FRESULTS(I1,I2,R) AS (
 SELECT I1,I2,CAST(SUBSTR(A,1,4) AS INTEGER) FROM RESULTS WHERE X=LENGTH(I1) AND Y=LENGTH(I2)
)
SELECT * FROM FRESULTS;

Sí os perdeis, tambien teneis otra query más simple que os permite generar un triangulo de pascal como en otro problema de HackerRank. La query es así de bonica:

WITH P(N,ROW,IT,REM) AS (
SELECT '1',1,1,''
UNION ALL
SELECT CASE WHEN REM='' THEN '1' ELSE N||' '|| --FIRST VALUE ALWAYS 1
 CASE WHEN instr(REM, ' ')=0 THEN REM  --IF REM ONLY HAS A NUMBER(1) CONCAT N THIS VALUE
 ELSE substr(REM, 1, instr(REM, ' ')-1) + --ELSE CONCAT SUM OF FIRST 2 NUMBERS OF REM
  CASE WHEN instr(substr(REM, instr(REM, ' ')+1),' ')=0 THEN substr(REM, instr(REM, ' ')+1) ELSE
  substr( substr(REM, instr(REM, ' ')+1),1,instr( substr(REM, instr(REM, ' ')+1),' ')-1) END
 END
END,
CASE WHEN REM='' THEN ROW+1 ELSE ROW END,
CASE WHEN REM='' THEN 1 ELSE IT+1 END,
CASE WHEN REM='' THEN N WHEN instr(REM, ' ')=0 THEN '' ELSE substr(REM, instr(REM, ' ')+1) END --POP FIRST NUMBER FROM REM / SET IT TO PREVIOUS N
FROM P
WHERE ROW<=15
)
SELECT N FROM P WHERE ROW=IT;

Y el resultado de ejecutarla es así de bonico:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1

Os recomiendo ver los enlaces de los problemas y del repositorio donde se explica como están implementados. Ahora sí, esto es importante followers:

¡Sugeridme más experimentos SQL en los comentarios! ;)

Motor 3D para GameBoy Advance: Consiguiendo lo imposible

Versión 2:
Descarga ROM y código fuente aquí.
Esta versión ya se mueve fluida a 60fps y permite girar la cámara.
Cambios:
Aparte de las optimizaciones de la versión 1, he añadido mas optimizaciones, y he implementado la rotación de la camara.
-Todo el código es copiado a la RAM y se ejecuta desde ahí. Se usa código ARM en vez de Thumb.
-Para ganar mas velocidad utilizo el modo5, que baja un poco la resolución y permite tener dos framebuffer en la memoria de video evitando tener que usar la RAM para luego copiarla a la VRAM en cada frame. También uso las técnicas de escalado y desplazamiento de la GBA para crear un par de frames intermedios mientras se renderiza el siguiente frame final.

Para la rotación utilizo aproximaciones rápidas de lo que serían los auténticos cálculos de la rotación. Ademas, cada vez que se gira, desplazo la posición de referencia para evitar aun mas cálculos al transformar las coordenadas durante el dibujado.

Para evitar aun mas perdidas de velocidad, he replicado la función crítica Render para cada angulo posible, de forma que las transformaciones de coordenadas están hard-coodeadas dentro de las funciónes Render-n, evitando llamadas a funciones y comprobaciones de angulo cada vez que se procesa un pixel.

Versión 1:
Descarga ROM y código fuente aquí.
La GameBoy Advance fue una de las primeras videoconsolas portatiles que intentó en algunos de sus juegos simular el efecto 3D. Juegos como Driv3r, Asterix y Obelix XXL, o Craxy Taxi. No obstante en la mayoría de dichos juegos el efecto 3D era muy, muy básico. Es por eso que yo, como friki ingeniero informático que soy me puse a investigar de que manera se podría conseguir un motor 3D decente. Tras un día investigando y picando código...¡Este fue el resultado!

Como habréis comprobado, la calidad del efecto 3D casi no se puede comparar con la de ningún otro juego de GBA. El motor es de tipo voxel space y el video fue acelerado algo así como x200 ya que la demo en su versión original (la del vídeo) tardaba 11 segundos en generar cada frame. Esto es debido a la gran cantidad de multiplicaciones y divisiones que debía hacer el motor en cada frame. Para los que no sepáis muy bien como funciona un motor voxel space os lo explico de manera muy sencilla:

Tenemos una imagen de color y otra imagen de profundidad. Dibujamos el entorno desde el frente hacia atras aplicando perspectiva (podeis ver el triangulito con el campo de visión en el GIF), para ello trazamos en la pantalla lineas verticales del color proporcional al pixel horizontal de la pantalla y el pixel horizontal de la linea de campo de visión actual. Esta linea vertical empezará desde la ultima altura dibujada hasta un nuevo valor calculado a partir de la altura en el mapa de profundidad y la distancia con el punto de vista (Si el valor obtenido es menor, no se dibuja la linea).

Optimizando el código:

Pues seguramente la baja potencia del procesador de la GameBoy fue lo que hizo que no apareciera ningún juego usando este tipo de motor, las multiplicaciones y divisiones son muy lentas en su procesador. Estas operaciones son vitales tanto para calcular las posiciones horizontales del campo de vision y pantalla como las de las alturas. ¿Que solucion tenemos? ¡Crear una estructura de datos con estos valores precalculados! En el archivo comprimido podeis encontrar generarmatriz.c que puede ser compilado para PC y usando los datos de matrizalturas.h (compartido con el proyecto devkit) generar una estructura de datos con las alturas precalculadas matrizalturas.raw y posiciones horizontales matrizx.raw las cuales se añaden al ROM. También, para realizar otras divisiones y multiplicaciones con multiplos de 2, utilizo a ser posible las operaciones de desplazamiento << y >> las cuales son mas rápidas.

Ademas, calcularemos el campo de visión menos frecuentemente en posiciones alejadas y limitamos la distancia de dibujado a 512 pixeles.

Estos cambios, junto con otras cuantas optimizaciones de código, permiten tras un gran esfuerzo y sudor conseguir unos gloriosos...

¡5fps!

Lo cual supone aproximadamente un speedup del 3000% y seguiría siendo insuficiente para cualquier juego en condiciones, pero al menos se mueve decentemente.

Se podría decir que la optimización es del 95% ya que los limites técnicos de la consola están ahí. Estas son algunas otras optimizaciones menores posibles que ni me he molestado en hacer:

• Alinear matrizx.raw a 256 bytes cada linea para asi a la hora de leer sus datos podamos cambiar SCREEN_WIDTH*(step-minstep) por (step-minstep)<<8 aunque esto nos hará desperdiciar 16 bytes de memoria en la estructura de datos en la ROM por cada linea.
• Dibujar las lineas verticales una por una, de forma que si una alcanza el valor maximo se haga un break y se pase a la siguiente sin seguir avanzando en profundidad. Solo habría aceleración en los casos que el mapa alcanzase la parte de arriba de la pantalla y la aceleración sería irregular. Habría que almacenar los valores de step en una estructura de datos.
• Si se os ocurriese alguna mas, ¡comentad!

Curiosidad:

Uso de memoria en la demo:

Elemento	Espacio (KB)	Porcentaje	Notas
Código	9.79	0.18%	El corasón de la demo. La parte que controla todo el funcionamiento.
Imagen Background	39.1	0.72%	La imagen del cielo tan bonica para la mitad superior de la pantalla (240x80) a 16 bit bgr555
Mapa colores	2048	38.07%	1024x1024 a 16 bit bgr555
Mapa profundidad	1024	19.03%	1024x1024 a 8 bit (valores 0-255)
Matriz x	238	4.42%	Valores para cada pixel horizontal (1-240) en cada profundidad (8-512) de la posición horizontal del campo de visión (valores de 16 bit)
Matriz Alturas	2021	37.57%	Valores de altura en la pantalla de 8 bit para cada altura del mapa (0-255) en cada profundidad (8-512) para distintas alturas de camara posibles (16)
Total	5379.89	100%

Bots: resolviendo los re-capchas: human-tunnel by Juanmv94

Antes cuando los captchas eran simples textos deformados con lineas pintadas por encima no era demasiado complicado mediante OCR obtener una determinada tasa de acierto resolviendo los catchas en los bots.

Ahora con la tecnología re-captcha de Google, implementada en muchísimos sitios esta tarea es casi imposible, ya que las técnicas de visión artificial aunque han avanzado mucho estos últimos años, siguen siendo insuficientes para la complejidad que este tipo de capchas presentan.

Nos podríamos calentar la cabeza haciendo unos algoritmos de visión artificial super avanzados... O podríamos resolver este problema de una forma sencilla, eficiente, y que nadie se esperaba. Como dijo Bill Gates: “Siempre escojeré a un vago para hacer un trabajo difícil… porque, encontrará una manera sencilla de hacerlo”


Pues bien: tenemos un servicio (pagina) web con usuarios que pueden registrarse, loguearse, interactuar,... Y aparte tenemos nuestro bot encargado de hacer alguna función repetitiva (buscar en Google, registrar cuentas, publicar comentarios,...) que puede estar o no relacionada con nuestra web.

Cuando a nuestro bot le aparezca un captcha, solo tendremos que enviar ese captcha a la primera persona de nuestra web que vaya a hacer algo, ya sea registrarse, loguearse, o cualquier otra actividad (esta decisión dependerá de la cantidad de actividad de nuestra web en proporcion con la del bot). ¡Esa persona lo resolverá por nosotros! Aparte le daremos mayor seguridad a nuestra web de una forma gratuita.

La forma de hacerlo sería algo así: 
-Nuestro servidor establece una conexion HTTPS con re-capcha y le mostramos al usuario ese mismo re-capcha desde nuestra web, (normalmente tambien desde HTTPS) creando una conexion parecida a un proxy en la que nuestro servidor hace un man-in-the-middle.
-Cuando el usuario resuelva correctamente el captcha (A veces puede darse el caso de que lo fallase) nuestro servidor que intercepta la comunicación lo sabrá, permitiendole acceso al usuario, y continuando la ejecución del bot.

De momento es solo un concepto, que no debería ser muy dificil de implementar.
Comentad cualquier duda que tengáis, comentario, o agradecimiento.