El blog de Feregrino

Aprende ruso

De nuevo en época de vacaciones aproveché el tiempo y me puse a completar cursos en MVA, uno de ellos, llamado Designing Your XAML UI with Blend Jump Start me motivó a crear una aplicación un tanto diferente a las que ya había hecho, y es que esta es visualmente más atractiva.

La aplicación en cuestión se llama Aprende Ruso, y como su nombre lo indica, es una pequeña guía para los que apenas van iniciando en el aprendizaje de esa extraño idioma. La aplicación tiene cosas simples, como las letras, algunos números y frases comunes, la idea es que la iré extendiendo conforme aprenda más de el lenguaje.

Técnicamente la aplicación hace uso de algunos controles para Windows 8.1 y Windows Phone 8.1, además de que ambos proyectos comparten la misma lógica, bajo el concepto de las Universal Apps de Windows, es por ello que al momento de que descargas la app en una de esas dos plataformas tienes automáticamente disponible la descarga para la otra. Por cierto, tengo todo el código fuente en un repositorio de GitHub, por si le quieres echar un ojo, mejorarla o contribuir con el desarrollo.

Usa los enlaces para descargar la app para tu dispositivo:

¡Saludos!
@fferegrino :)

Extendiendo Construct 2 con C++

Últimamente me he dedicado de lleno a aprender sobre videojuegos, desde el diseño y planeación hasta el desarrollo y publicación. A la par he estado trabajando en un juego para Windows/Windows Phone 8.1 llamado Falling Dodge desarrollado casi por completo en Construct 2.

Y digo casi por completo porque hay algunas cosas que no es sencillo realizar dentro de C2 o bien, no entendemos de primera mano cómo se hace. Por ello decidí aprovechar los runtime components delegando cargas de trabajo pesado o complicado a C++. Con ello podemos aprovechar toda la facilidad de manejo de canvas, colisiones, sprites y otras tantas que nos otorga Construct 2 mientras que dejamos la carga pesada de operaciones matemáticas, algoritmos complejos, etc. al runtime component.

Como ya les había contado antes, podemos llamar a rutinas escritas en C++ mediante JavaScript y para llamarlas desde Construct 2 a nuestro juego debemos crear un plugin que haga uso de él. En el gráfico más abajo trato de explicar un poco mejor cómo es que se realiza. Podrá parecer bastante, pero lo que está rodeado con un borde amarillo es lo único que nos toca hacer a nosotros (bueno, eso y referenciar los proyectos manualmente).

A modo de ejemplo, me he creado un "juego" que nos pide colocar una cierta cantidad de árboles y luego los une formando el árbol de mínima expansión empleando el Algoritmo de Kruskal. He dejado todo el código necesario en GitHub dentro del repositorio kruskal-cpp2 o bien, descargar todo el proyecto en zip además de que ya saben que cualquier duda o comentario pueden dejarlo acá o escribirme y con gusto responderé.

¡Saludos!
@fferegrino :)

win-plus-c2, un plugin para Construct 2 y las Universal Apps

Hacía mucho que no le metía la mano a Construct 2 y ahora que lo volví a hacer, gracias a la unidad de aprendizaje Ingeniería de Software, me di cuenta que si bien es una herramienta extremadamente útil para realizar juegos y prototipos rápidos utilizando HTML5 tiene ciertas limitantes a la hora de querer realizar una aplicación preparada para cualquier tienda de apps.

La gran ventaja que nos presentan sus creadores es la posibilidad de extender nuestro juego a través del Construct 2 Javascript SDK y el empleo de plugins. Y es precisamente eso lo que tuvimos que ya que nuestra aplicación debía cumplir ciertos requisitos de diseño para contar como un proyecto de buena calificación.

El plugin se enfoca por completo en extender Construct 2 para el desarrollo de aplicaciones para Windows Store y más recientemente de la Windows Phone Store (aunque ahora estará centrado en las aplicaciones universales). El plugin nos ayuda a presentar mensajes en la pantalla, identificar cuando la aplicación pierde foco, cuando la pantalla es cambiada de tamaño, entre otras cosas.

El código está en GitHub win-plus-c2 junto con los archivos .c2addon listos para instalar y un poco de documentación. Desde luego, espero que quieran contribuir al desarrollo con código o sugerencias.

¡Saludos!
@fferegrino :)

Hora de formatear

Terminando el ciclo escolar fue hora de formatear mi computadora personal, era necesario después de casi un año sin hacerlo. La novedad fue que ahora no tuve que respaldar nada de información en un disco externo gracias a OneDive, Dropbox y GitHub. Casi todos mis archivos escolares de este semestre estaban alojados en OneDrive, mientras que algunos otros estaban en Dropbox, para el código de los proyectos usé GitHub (hay un proyecto que inclusive está ahora en una tienda de apps).

Por primera vez el formateo fue más rápido de lo ya era. En menos de 15 minutos ya estaba con la computadora como nueva. Este es el software que le instalé:

SO: Windows 8.1 Pro
De IDEs: Microsoft Visual Studio Ultimate 2013 Update 2, Construct 2, NetBeans 8.0 y ADT Bundle
Navegadores: Internet Explorer y Google Chrome
Editores: Notepad++
Otros: Office Professional 2013, VirtualBox, GitHub for Windows, Paint.NET, WinMerge, Dropbox
Además de los compiladores libres de C y C++ que vienen con Cygwin.

No es mucho pero será suficiente para divertirme estas vacaciones con algunos de los proyectos que espero contar por acá más adelante.

¡Saludos!
@fferegrino :)

Puro AC, un nuevo blog

A pesar de mi poca experiencia en la solución de problemas de programación competitiva he decidido crear un blog para explicar algunos de los que vaya resolviendo de entre todas las plataformas que hay en línea tratando de explicar lo escencial del problema, detallar la solución, la complejidad de esta y el códdigo (o en su caso, pseudocódigo), siguendo la manera en que se escriben las editoriales de cada problema en Code Chef, como la entrada anterior a esta, mi editorial del problema Chef and Digits.

A esta iniciativa se sumará mi amigo y compañero de equipo Adrián Fernandez (@ferProgramming en Twitter), quien además propuso que en el blog también se explicaran además algunos algoritmos, estructuras y técnicas de programación que ambos estamos aprendiendo en el Club de Algoritmia, del que ya les había hablado antes.

En el blog he invertido algo de tiempo, dejándolo a punto con algunos extras y mejoras, como MathJax para que se vean mucho mejor las expresiones matemáticas, google-code-prettify para mejorar la apariencia del código escrito y el traductor de Google Translate, para traducir cualquier entrada a cualquier idioma disponible. Sin dejar de mencionar los plugins sociales para hacer que compartir una entrada en particular sea sencillo y a la vez descriptivo para quien lo lea.

Otro punto importante es que modifiqué la plantilla para que fuera adaptable a dispositivos móviles con un diseño responsivo. Además es posible imprimir la explicación ya que con el uso de @media queries pude crear una versión del blog que fuera amigable para imprimir (tamaño adecuado, colores en blanco y negro, etc...)

Sin más les dejo el enlace al blog, que hasta el momento cuenta con 3 entradas explicando soluciones a problemas, a la espera de que mi compañero publique algo más.

PuroAC

PD: Si te gustaría anexarte a la iniciativa, deja un mensaje en esta entrada o escríbeme por donde quieras. Entre más seamos, mejor.

¡Saludos!
@fferegrino :)

Chef and Digits (ADIGIT) - Editorial

Link al problema: ADIGIT (Practice)
Link al editorial en CodeChef: ADIGIT - Editorial

Dificultad: Fácil

Problema:

Dados $N$ ($N ≤ 10^5$) dígitos y $M$ ($M ≤ 10^5$) consultas que consisten en un entero $x$ ($1 ≤ x ≤ N$), que llamaremos step (paso), imprimir el resultado de $B1 - B2$, donde:

$B1$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b > 0$
$B2$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b < 0$

Solución:
Veamos el siguiente caso, con entrada a = 0123152397

Calculando los valores para todos los pasos tenemos lo siguiente:

En la tabla anterior he marcado dos casillas, para observar a detalle lo que sucede:

Para el paso 4 tenemos: $B1 = (3 -0) + (3 - 1) + (3 - 2) = 6$ y $B2 = 0$ lo cual nos da el valor de $6$
Para el paso 8 tenemos: $B1 = (3 - 0) + (3 - 1)+ (3 - 2) + (3 - 1) + (3 - 2) = 9$ y $B2 = (3 - 5) = - 2$, por lo tanto tenemos $B1 - B2 = 11$

Observando las ecuaciones anteriores, podemos notar que el paso 11 se compone del paso 3 en las sumas $(3 - 0) + (3 - 1)+ (3 - 2)$ más otras 3 sumas, así que ¿qué pasaría si los almacenamos para no volver a calcularlo todo? Basándonos en eso, almacenamos los resultados en otro arrelgo.

Ahora, ¿cómo es que sabemos que tenemos un valor ya calculado?, esto es sencillo de encontrar y ocurre cuando los números $a_x$ y $a_y$ son iguales. Si los calculamos de manera secuencial, es decir de 1 hasta N, estaremos garantizando que para cada paso los pasos previos ya estarían precalculados, como solo hay 10 dígitos distintos, en el peor de los casos terminaremos sumando 10 veces. Al terminar el precálculo, para cada consulta que nos hagan la respuesta será obtenida en tiempo constante

Complejidad: $O(10 * N) + O(M)$

Código (C++):
Definiremos un arreglo A, donde A[i] es es valor de paso i-ésimo del problema y s, un arreglo de char, donde s[j] es la posición del dígito j-esimo.

void precalc(){
 int t = 0;
 for(int step = 0; step < n; step++){
  int ans = 0;
  for(int i = step-1; i >= 0; i--){
   t = (s[step] - '0') - (s[i] - '0');
   if(t == 0){
    ans += A[i];
    A[step] = ans;
    break;
   }
   ans += abs(t);
   A[step] = ans;
  }
 }
}

Haciendo que para responder a las consultas q, solo será necesario imprimir el valor almacenado en A[q-1]

int main(){
 scanf("%d%d",&n,&m);
 scanf("%s",s);
 precalc();
 while(m--){
  scanf("%d",&q);
  printf("%d\n",A[q-1]);
 }
 return 0;
}

¡Saludos!
@fferegrino :)

Leyendo de la entrada estándar con scanf y fgets

Hace tiempo, les contaba que me inicié en la programación competitiva, en la cual, la mayoría de problemas nos piden leer información de la entrada estándar o stdin seguramente me lo van a creer... yo no sabía cómo hacerlo de una manera "correcta" (._. ), en especial cuando de cadenas se trataba. En este post trataré de explicar cómo es que lo hago (y he aprendido que lo hacen) en C o C++.

La función scanf

Esta función mágica llega a nosotros gracias a la librería <stdio.h> en C o <cstdio> en C++, resulta la manera básica de recuperar valores. Nos sirve para todo tipo de entradas y si no tienes algo muy complicado de leer, esta es tu mejor opción, recuerda que esta función trata de leer el tipo de dato que le especifiques hasta que encuentra un salto de línea o un espacio en blanco. El uso de esta función depende de los especificadores de formato para recuperar los valores que deseas.

Por ejemplo, supongamos que tenemos la siguiente entrada

10 3161565164181
aab baa aba

y este código para leerlo

int a;
long long int b;
char cadena[15];
scanf("%d %lld", &a, &b); 
scanf("%s", cadena); // 'cadena' es ya una referencia a memoria

Una vez que se ejecute, en a tendremos 10, en b tendremos 3161565164181 y cadena será "aab" (¡porque solo lee hasta el espacio en blanco!).

La función fgets

Pero, qué pasa si la entrada es un poco más complicada, como la del problema Wetlands of Florida en la que vienen secuencias de caracteres seguidas inmediatamente por un par de números enteros:

// ...
LLLLLLLLL
3 2
// ...

Para ello se ocupa la función fgets (que es parecida a gets, solo que más segura), en combinación con sscanf que funciona de manera similar a scanf solo que esta "lee" de una secuencia de caracteres y no de stdin. En cuanto a fgets, sus parámetros son: la dirección de memoria, la cantidad de caracteres que esperamos leer como máximo, y el flujo del que los vamos a extraer, de tal manera que tenemos algo así:

int i, j;
char entrada[10];
fgets(entrada,10,stdin);
// Procesamos 'entrada', que contiene la siguiente secuencia de caracteres: 
// 'L','W','W','W', 'L', 'L', 'L', 'L', 'W' y '\n' <= ¡Sí! el salto de línea
// Recuperamos los enteros:
fgets(entrada,10,stdin);
sscanf(entrada,"%d %d",&i,&j);

Ya para finalizar es necesario remarcar esto: fgets recupera hasta que encuentra el salto de línea. Repito: fgets recupera hasta que encuentra el salto de línea por lo que es necesario eliminarlo "a manita" con '\0' si es que no es lo que deseamos de él.

Espero que les sirva como a mi me ha servido, ya que hay que recordar que una parte importante de resolver los problemas es saber interpretar de manera adecuada la entrada que nos dan, así como saber introducirla dentro de nuestra probable solución a este.

¡Saludos!
@fferegrino :)