El rincon de ex

Tetris clone in Unity

2011-10-09T14:18:00.002-05:00

I have been working with Unity lately and decided to use it for a a 3D version of my simple-tetris-clone.
Unity great strengths are the easiness to go from concept to implementation and its support for deployment in multiple platforms. It's not that easy, I can tell, after finishing a project with iOS and Android support but once you get it right, it works.

You can play it online if you have the Unity plugin installed.

The source is in my repository.

Right now this port is missing the HUD (and for a demo this size stock Unity GUI support would be somehow OK) but I better don't bother because the GUI system is one of the Unity weakest points and it really sucks big time. Due to performance issues is plainly unusable for mobile devices and it's pretty archaic and limited for everything else. You'll need to buy expensive third party plugins or use (and probably modify) the nice and free UIToolkit for sane and usable interfaces in your games, but even then you still will miss support for advanced containers and scrolling. Sight. The good news is that Unity 3.5 will have a brand new GUI system. I really really hope they fix it for then.
So please forgive my laziness but my fingers chucked and rebelled against me when I was trying to type OnGUI(), and using old fashioned GUIText is not my thing :D

Forgetting the GUI, Unity is an awesome and very fun engine to play with, and it's FREE.
Programming in C# with Visual Studio C# is also a pleasure.

Have fun.

Solving the Tic-Tac-Toe game, finally...

2011-02-09T22:51:00.007-05:00

The simple game that has been always after me laughing at my programming incompetence.

The very first time I tried to make a program that could play perfectly the game was in the university, after taking my very first course in Programming Languages (I learned Pascal). It was holidays and I was visiting my cousin and got the nice surprise of him getting a personal computer. It was a powerful 286 with a monochrome amber monitor. I couldn't find anything similar but for you to get the idea, games were played like this in those computers:

My cousin was the first lucky one in getting a computer in our family and he was learning Turbo Pascal by himself. We decided to celebrate our reunion programing the ultimate and invincible "Michi" (that is how the TicTacToe game is called over here). It was the morning and I had to return to my city at the afternoon, so we had only some hours to get it working. He was going to do the main menu and the game board, and I was going to implement the game logic. He started programming while I was writing on paper my part. This is just a bunch of ifs and a 3x3 matrix, How difficult can it be?. I thought. I recall he did a beautiful work, our graphics looked great (all in black and amber of course) but after typing my part the game really bombed, it played awfully, losing idiotically. Without more time to debug my program I had to leave with the bitter taste of defeat on my mouth.

The second time I tried to solve the game was after getting my programmable calculator Casio FX-7700, a powerful beast of 4K of memory. This calculator only accepted some kind of primitive BASIC but it gave me some moments of solace programming it. In every sense it was my first "computer", because before that I only could test my programs after getting laboratory time on my university laboratory, and that place was always full of people waiting, I had to awake early to sign-in the notebook for reserving a place. I remember using all the 4K of my calculator for my TicTacToe game, it draw the board not only with "X" and "O" but also with different icons that I had diligently drawn pixel by pixel. This time the game logic worked fine. Or that I thought. One of the reasons my first attempt failed so miserably was that I didn't want a "boring" adversary. I know this is ridiculous when the game is boring for starters, but it was very very boring if the computer always played in the center first, or in some corner first. I knew that the computer could play in any place if it was first and indeed had high chances of confusing the casual adversary playing that way, so my game logic must choose randomly from a valid set of possible movements. I have see some TicTacToe game solvers cutting corners starting always in the center or in some corner. My game seemed to play randomly and even so never to lose. Some day I needed the memory of my calculator for useful stuff, and I had to delete my TicTacToe program so I decided to play the little thing for the last time... and I found a bug I have never seen before! even worse, due to the randomness I couldn't reproduce it later. No time to debug, like the first time, TicTacToe laughing again at me.

This year I saw again the little monster thanks to a friend, and I decided to settle things once for all with it. This time I didn't want to use a greedy approach to the problem, like before. This time I would generate all the game tree once for all and decide the best move using the MiniMax algorithm. You can see the result below (flash):

Left click for doing a move, and clicking while pressing [shift] or [control] undo the last move. The valid moves for the next player are show in black. About the statistics printed on every cell: the first 3 numbers (from top to bottom) are the number of possible games that are won by any part or are drawn (in ascending order). Next is the total of games and finally comes the MiniMax score of that cell. That score is used by the program to show the best moves for the next player. Positive scores are a secure win for the "X" player, negative scores are a secure win for the "O" player, a zero score means a draw.
So TicTacToe in resume looks like this:

The area in blue is proportional to the possible games than "X" can win, the red area is proportional to the number of wins for "O" and the area in yellow are the draws. You can see that there are 255168 games with "X" wining 51% of them, "O" wins only 30% and the rest is a draw. Clearly "X" has an advantage. This is the distribution for the first move:

You can play in any cell (and like everybody knows) the best you can get is a draw (all the cells have zero for MiniMax score). Playing in the center gives you 60% chances of winning, in any corner a 52% percent of winning and playing in the side 48%. If you play in the corner, you'll get this:

Now the interesting bit is that for the "O" player there is only one valid possible answer for drawing (playing in the center) playing in any other place is a secure win for the "X" player. If "X" plays in the center first:

the only valid answers for "O" is playing in some corner, and if "X" plays in the side:

there are only 4 cells that are valid for the "O" player now (I really liked that opening).

Play with the flash thing and convince yourself that it's unbeatable. I hope I didn't do a mistake again! :D. Source code here.

Flasic: a very simple BASIC interpreter for Flash

2011-01-15T17:51:00.002-05:00

I just found this very little cute BASIC interpreter: Jasic and I decided to make a port to Flash in order to add basic graphics commands (just "setcolor" and "putpixel" actually) so I could see the little thing drawing a colored Mandelbrot fractal. It was very easy, thanks to the profusely commented code of the original author (Bob Nystrom). You can select the program demos from the drop-down menu and press the [Run] button to start the interpreter. So without further ado, Flasic:

It's not that slowly, but being a BASIC interpreter inside a Flex interpreter inside a Flash bytecode interpreter surely takes his toll, oh the irony... :D
The code is my repo, many thanks to the original author for releasing his original version, it was fun.

Solving the Princess in a Box Puzzle

2010-08-08T16:37:00.007-05:00

We can solve the puzzle of my last post using a Breadth-first search (BFS) algorithm. The key idea is to realize than the problem is just a Shortest Path problem where the graph, even when it is not completely known at the beginning (because we don't have the graph's adjacency list or adjacency matrix), can be built joining the states the board takes after every movement. The image below can help to understand this. It shows some of the states the board cab take after some movements starting from the beginning.

So we are going to work over the graph of all the states the board can take by moving the pieces around. A nice thing is that the BFS algorithm assures us that if we reach our target we would reach it in the minimum number of steps, and if we can't reach our target the problem is indeed impossible to solve. BFS in seudocode looks like this:

But we'll need to modify some parts of this algorithm in order to solve our problem. See the highlighted lines below:

Lines 1-4 are no longer necessary (or possible) because we don't have the adjacency list or adjacency matrix. We don't even know the number of nodes our graph has!. Line 5 need to change because the above restriction forces us to attach the State property into our node, the same applies to lines 12-16. Line 11 and 18 would be ignored here because we don't need any special process after discovering a graph edge, there are other interesting problems with graphs that can be solved using these steps but not our problem at hand. So our algorithm ends like this:

In line 4 we have introduced a Discovered data structure, this object stores all the discovered nodes and can be a Set or Hash Table because we need to insert nodes and check their existence fast. This change is required because we don't know all the nodes at the beginning so we can't use a simple Array. As always everything is easy until you have to do it, and here the simple and innocent line 10 can give us a bit of trouble implementing it, but after a bit of code modifications we'll end with this:

This can solve the puzzle in less than 3 seconds (in my desktop with Windows7 and a Pentium D at 2.8 GHz) pretty nice if we are talking about Flash here, I have seen some native applications taking similar or longer times.
But some optimizations were required to obtain that speed. Also in order to don't freeze the browser I had to split the process along some frames, but that was easy because in a BFS process there is no recursion involved. It's a shame than Flash still doesn't have threading support despite the fact that HTML5 already got web workers.

The Princess in a Box puzzle

2010-07-29T23:38:00.005-05:00

Today was holidays here (national day) so I finally could finish the Professor Layton and the Curious Village cute little game. If you like puzzles there are no better games than the Professor Layton series. I really recommend them if you own a Nintendo DS. However I don't play games much, so take my advice with a bit of salt: the only games I ever finished were StarControl II, Starcraft and Jeanne d'Arc. That reminds me that the only time I went to Buenos Aires I brought with me a little box with a similar puzzle.

I totally forgot about it until I saw again a similar puzzle in the DS game.

This puzzle has been a long time around us as a member of the family of sliding puzzles and is better known as the Klotski puzzle, but I'm going to name it here The Princess in a Box puzzle because is the name that it has in the Professor Layton's game. I did this Flash demo if you want to play it:

The source code is in my repository, if you like that kind of things.
So that's it for now, have fun. I'll solve the puzzle in my next post.

My very own programming font

2010-04-11T23:43:00.009-05:00

I think fonts are the second best friends of programmers.

When I was a kid I used only Lucida Console, it was easy to find on every Windows installation and had a nice monospace feel. After some time I found the Proggy font family and I never looked back. Proggy was my only font for ages. It was very compact and it let me see more lines of code in those small CRT monitors of the time without losing clarity.

A good programming font makes easy for you to distinguish a zero '0' from a capital letter 'O'; a number '1' from a letter 'l'; and render all the operators and common programming symbols in a way that is very easy to distinguish one from another. (an exclamation '!' from a vertical bar '|', a parenthesis '(' from a bracket '[', etc) But even the good times come to an end.

And the end came with the advent of bigger monitors and bigger screen resolutions. The problem with Proggy was that it never looked good with sizes bigger than the default (11), and that was very small for me to see in the new resolutions. I did my best effort, but I already use heavy glasses to allow me the strain of small fonts all the day, it was overkill.

So I sadly had to look for a replacement. I surfed the web looking at all the other programming fonts ever created, nothing caught my attention. I tested many of them but all the time I found myself missing something. After a long time, and because I had to work, I ended with Consolas.

But it never was love. I had to said every time I started my editor 'I really like this font', I was making my best effort but deep root I knew it was only because I couldn't find anything better.

This night I changed again monitors and looking at some code of mine I finally realized that Consolas was definitively not my font, so I decided to create my very own font: Lucida Console Ex. Yes I'm returning to my origins, maybe I'm already old.

I'm not really sure if I would end liking this font, maybe creating a bigger Proggy font could be the only acceptable solution. And to clarify, I just modified the default Lucida Console font adding the things I missed the most.

Simple Tetris Clone (FLEX version)

2010-02-07T14:21:00.008-05:00

I added to my Tetris clone a FLEX branch, it only uses the compiler and not the FLEX class containers (unnecessary for this little game). The point is you can use the free API tools to make a simple game like this, without needing the Flash IDE at all.

It's cool these days to bash anything Adobe related (and the bloated PDF reader or the security holes in the Flash player of course doesn't help). Just for the record this page can crash your browser (Click on it only if you feel lucky and don't have something to lose). That is a bug that has not been fixed since 2008, and there are many others out there (but with a less spectacular failure outcome). The sad truth is that anybody working (and I mean earning his bread) with Flash technology can tell you scary stories about classes refusing to compile, library assets getting mysteriously corrupted, different movie behavior under different player versions, etc. And if you are angry today I can assure you the bugs were a lot uglier in the AS2 times.

However, in all honesty, I don't dislike Flash technology, of course hitting a Flash bug makes you feel angry until you find the workaround, but you would learn from your experiences and you would start avoiding the things that don't work, after some time you would have earned an impressive list of best-practices and things to avoid, following that path, working with Flash can be actually a nice experience. I personally like their API design, at the very least they have invested a lot of time and thinking in that.

Playing with pure Javascript would be the other option (the canvas element seems very promising, I hope the 3D capability goes mainstream) but it's not an option for practical games right now (I mean this year). I have worked in big web game projects and I can't think of another tool that artists can use to recreate Flash animations, making them all sprite-based would make the game bigger in size while losing their vector appeal (easy scaling). Also there is nothing that can run at comparable speed in older browsers today. And don't let me start with the audio... So for making games (not your simple square and circle muted games) I suspect Flash is still going to survive for at least a couple of years. Even if it totally loses the video battle that has already started with the HTML5 video tag.

The Pascal's triangle

2010-02-01T23:59:00.001-05:00

It was already time to change the animation for this blog, (the little thing at the right, now with a chess board), so I would do a very short description of the previous one here:

This animation is just a Pascal's Triangle (reflected in the four quadrants) with different colors for cells accordingly to their modules with some random prime number that changes in every iteration. The triangle for the next iteration is drawn row by row, while the previous one is faded. Empty spaces are cells that are divisible by the selected prime number.

If you feel more interested, you could check the section 2.3 of the book Chaos and Fractals (Springer) that gave me the inspiration for this.
Browse the source code if you feel brave. That code has zero re-usability, I suspect. :P

Have a nice night!

Simulator for a basic computer

2010-01-07T15:45:00.003-05:00

This is simple simulator for the basic computer described in the book of Morris Mano "Computer System Architecture". Here professor Hyunsoo Yoo maintains a succinct but complete description of this computer, check it if you can't find the book. In special look for the lectures 5 (Basic Computer Organization and Design) and 6 (Programming the Basic Computer) that this simulator uses as foundation.

This basic computer is built from these components:

Component	Bits	Functionality
DR	16	Data Register
AR	12	Address Register
AC	16	Accumulator
IR	16	Instruction Register
PC	12	Program Counter
TR	16	Temporary Register
INPR	8	Input Register
OUTR	8	Output Register
MEMORY	16	Memory 4096 x 16
FGI	1	Input Flag
FGO	1	Output Flag
IEN	1	Interrupt Enabled Status
R	1	Interruption Status
I	1	Decode Bit
S	1	Halt Status
E	1	Carry Bit
SC	3	Sequence Counter

And the table of instructions it supports is:

	Symbol	Hexcode		Description
	Symbol	I = 0	I = 1	Description
M E M O R Y	AND	0xxx	8xxx	AND memory word to AC
	ADD	1xxx	9xxx	Add memory word to AC
	LDA	2xxx	Axxx	Load AC from memory
	STA	3xxx	Bxxx	Store content of AC into memory
	BUN	4xxx	Cxxx	Branch unconditionally
	BSA	5xxx	Dxxx	Branch and save return address
	ISZ	6xxx	Exxx	Increment and skip if zero
R E G I S T E R	CLA	7800		Clear AC
	CLE	7400		Clear E
	CMA	7200		Complement AC
	CME	7100		Complement E
	CIR	7080		Circulate right AC and E
	CIL	7040		Circulate left AC and E
	INC	7020		Increment AC
	SPA	7010		Skip next instruction if AC is positive
	SNA	7008		Skip next instruction if AC is negative
	SZA	7004		Skip next instruction if AC is zero
	SZE	7002		Skip next instruction if E is zero
	HLT	7001		Halt computer
I/O	INP	F800		Input character to AC
	OUT	F400		Output character from AC
	SKI	F200		Skip on input flag
	SKO	F100		Skip on output flag
	ION	F080		Interrupt on
	IOF	F040		Interrupt off

The assembler is a bit different than the book, it supports labels of any size and uses the character (:) instead of (,) also I added the LBL pseudo instruction that can help in some cases:

ORG	N	Hexadecimal number N is the memory location
		for the instruction or operand listed in the following line
DEC	N	Signed decimal number N to be converted to the binary
HEX	N	Hexadecimal number N to be converted to the binary
LBL	L	Address of label L to be converted to the binary
END		End of symbolic program

There are 3 sample programs to select, or you can enter your own. After your program is ready press the [Assemble] button, if the program is correct you will need to load the binary codes of the program into memory, you can do this pressing the [Load] button. Now you are ready to run the whole program with [Run] or just go cycle by cycle with [Next].

The source is available under the MIT license in:
http://code.google.com/p/basic-computer-simulator/

Have fun!

Very very simple interpreter in Flex

2009-08-02T11:29:00.002-05:00

This weekend I've been playing with making a very very simple interpreter in Flash, mostly for drawing functions of the form: z = f(x, y).
This is based in the part 4 of the famous Lets build a Compiler! tutorial by Jack Crenshaw.

I'm planning to do a step by step tutorial when I have time.

Solving simple International Mathematical Olympiad problems.

2009-07-11T13:56:00.004-05:00

Solving simple International Mathematical Olympiad problems by programming is a sadistic stress reliever. They were originally thought to be solved using only paper, pencil and lots of young and smart neurons. Let's amuse ourselves solving them with a bit of code. Afterall, Why not to use the nukes? :D

Follow the links for the solutions in AS3, but if you felt tempted give them first a try, some of these problems can even make a nice programming interview exercise (if the position at hand requires minimal mathematical skills from your candidates).

IMO 1960 Problem 01

Determine all three-digit numbers N having the property
that N is divisible by 11, and N/11 is equal to the sum
of the squares of the digits of N.

It's a simple loop with known limits. I guess the average programmer can solve this quickly.

IMO 1962 Problem 01

Find the smallest natural number n which has the following
properties:

(a) Its decimal representation has 6 as the last digit.
(b) If the last digit 6 is erased and placed in front of the
remaining digits, the resulting number is four times as
large as the original number n.

A bit involved, because now your loop doesn't have a limit:

IMO 1963 Problem 06

Five students, A,B,C,D,E, took part in a contest.
One prediction was that the contestants would finish in the
order ABCDE. This prediction was very poor. In fact no
contestant finished in the position predicted, and no two
contestants predicted to finish  consecutively actually did so.
A second prediction had the contestants finishing in the
order DAECB. This prediction was  better. Exactly two of the
contestants finished in the places predicted, and two disjoint
pairs of students predicted to finish consecutively actually
did so. Determine the order in which the contestants finished.

Now we are talking.... Raise your hand if you know what a permutation is. Ok. Now every one of you have to code a working version in five minutes. Counting! :D
I couldn't do it. As always the optimized permutation generator slips through the holes in my mind. So I had to resort to my simple but inefficient recursive generator, it has the advantage that if I forget it, I can deduce it again. Here my ruby version:

Once you have a working generator of permutations the rest is just loop through all the possible outcomes and checking if the conditions are satisfied.
Hmm... pretty boring for human minds, even if there are only 5! = 120 possibilities. It's no wonder that the solution for this problem in my book is a one liner without explanation. I guess this problem deserves the nukes!

Take care!

IMO 1959 Problem 04

2009-07-05T18:17:00.002-05:00

The year is 1959. The place: Braşov, Romania, where the first International Mathematical Olympiad is being held. The problem is short, simple and sweet:

Construct a right-angled triangle whose hypotenuse c is given if 
it is known that the median from the right angle equals the 
geometric mean of the remaining two sides of the triangle.

You can solve it like every high-schooler can do:

Or you can brute force it! :D

Cheers.

Particiones enteras

2009-07-03T02:00:00.003-05:00

Celebrando el hecho de que ya termino con mi primer ciclo de la maestría, y que ademas he conseguido el titulo de experto en ProjectEuler haré un post acerca de un problema que me parece interesante. El enunciado es bien simple:

Dado un numero entero "n" ¿De cuantas maneras diferentes se puede descomponer "n" en números enteros positivos?.

La solución aunque simple no es evidente.
Por ejemplo, sea n = 4.
4 puede descomponerse en: ( 1 + 1 + 1 + 1 ), ( 1 + 2 + 1 ), ( 3 + 1 ), ( 2 + 2 ) y ( 4 ). Cada una de estas sumas es una partición entera de 4. Como buscamos solo particiones diferentes hay algunas que no se consideran, por ejemplo, no se esta considerando ( 2 + 1 + 1 ) porque es lo mismo que ( 1 + 1 + 2 ) si ignoramos el orden.
Es fácil entender de donde viene el nombre de partición entera, lo que estamos haciendo es "partir" el numero 4 en agrupaciones diferentes:
Vemos que el numero de formas diferentes en que se puede descomponer 4 es 5.

La función que devuelve el numero total de particiones diferentes de un numero "n" se denota como p(n), entonces: p(4) = 5. ¿Como hacemos para calcular p(n) para un "n" cualquiera? Antes de resolver este problema resolveremos el problema mas general:

Dado un numero entero "n", listar todas las particiones enteras diferentes de "n".
La clave para resolver este problema es considerar particiones ascendentes y ordenadas de menor a mayor.
Una partición ascendente (que abreviaremos: PA) es aquella en la cual se cumple que cada termino es igual o mayor que el termino a su izquierda; así ( 1 + 1 + 2 ) es una PA, pero ( 1 + 2 + 1 ) no lo es.

Una partición es mayor que otra partición si su n-ésimo termino es mayor que el n-ésimo termino de la otra partición (cuando se lee de izquierda a derecha), siendo todos los términos anteriores al n-ésimo iguales (si existen). De aquí que ( 1 + 3 ) sea mayor que ( 1 + 1 + 2 ) porque su segundo termino es mayor que el segundo termino de la otra.

Ordenando las particiones ascendentes para n = 4:

pa1 = 1 + 1 + 1 + 1
pa2 = 1 + 1 + 2
pa3 = 1 + 3
pa4 = 2 + 2
pa5 = 4

Iterativamente no se cómo se pueda generar esta secuencia así que iremos por el camino recursivo. De la lista de arriba podemos ver que las particiones ascendentes de 4 son:

PA de 4 = (pa1 + pa2 + pa3) + (pa4) + (pa5)

o dicho de otra manera:

PA de 4 = (PA de 4 que empiezan con 1) + (PA de 4 que empiezan con 2) + (PA de 4 que empiezan con 4)

Sea f una función recursiva que devuelva particiones ascendentes. Si esta función recibiera como primer parámetro una partición ascendente con la que queremos que empiecen todas las particiones ascendentes devueltas por esta función, podríamos escribir la igualdad anterior como:

PA de 4 = f({1}, ...) + f({2}, ...) + f({4}, ...) -- (1)

Donde usamos las llaves { } para indicar los términos de una partición. Estamos considerando que f puede recibir otros parámetros (que aun no hemos descubierto) y por eso le agregamos los puntos consecutivos como segundo parámetro.

Para resolver este problema es vital darse cuenta que todas las particiones de 4 pueden a su vez ser generadas por la misma función pero enviándole como primer parámetro una partición vacía:

PA de 4 = f({}, ...) -- (2)

Examinando la ecuación (1) vemos que falta el termino f({3}, ...) que correspondería a las particiones ascendentes de 4 que empiezan con 3. De nuestra lista de particiones (al inicio) vemos que no existe ninguna, pero razonemos porque; si existiera alguna PA esta sería de la forma: ( 3 + ... ), ya que 3 es menor que 4 entonces aun tenemos que agregarle mas términos, pero los únicos valores que podemos agregar como siguientes términos serian números iguales o mayores que 3 (porque tiene que ser una PA) entonces la lista de posibles particiones seria: ( 3 + 3 ), ( 3 + 4 ), etc. Todas ellas con sumas mayores que 4, lo que no puede ser, de aquí que:

f({3}, ...) = ∅ (conjunto vacío)

Agregando esto a (1):

PA de 4 = f({1}, ...) + f({2}, ...) + f({3}, ...) + f({4}, ...) -- (3)

Remplazando (2) en (3):

f({}, ...) = f({1}, ...) + f({2}, ...) + f({3}, ...) + f({4}, ...) -- (4)

Nos falta una forma de pasar la información del número de quien estamos generando particiones (en nuestro ejemplo de 4). Para esto podemos pasar como segundo parámetro el valor que queremos que sumen los términos que se agreguen a la PA que pasamos como primer parámetro, agregando esto a (4):

f({}, 4, ...) = f({1}, 3, ...) + f({2}, 2, ...) + f({3}, 1, ...) + f({4}, 0, ...) -- (5)

en donde:

f({1}, 3, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 ), ( 1 + 3 )
f({2}, 2, ...) = ( 2 + 2 )
f({3}, 1, ...) = ∅ (conjunto vacío)
f({4}, 0, ...) = ( 4 )

Aquí f({1}, ...) se ha convertido en f({1}, 3, ...) porque si cada PA empieza con 1 (y buscamos las PA de 4), solo necesitamos agregar términos hasta que sumen 3:

PA de 4 que empiezan con 1 = f({1}, 3, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 ), ( 1 + 3 )

Ya estamos preparados para investigar el comportamiento recursivo de f, vemos que:

f({1}, 3, ...) = [( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 )], [ ∅ ], [( 1 + 3 )]

o en palabras:

PA de 4 que empiezan con {1} = (PA de 4 que empiezan con {1, 1}) + (PA de 4 que empiezan con {1, 2}) + (PA de 4 que empiezan con {1, 3})

en donde:

f({1, 1}, 2, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 )
f({1, 2}, 1, ...) = ∅ (conjunto vacio)
f({1, 3}, 0, ...) = ( 1 + 3 )

o en términos de f :

f({1}, 3, ...) = f({1, 1}, 2, ...) + f({1, 2}, 1, ...) + f({1, 3}, 0, ...) -- (6)

De (5) y (6) podemos obtener pistas de como terminar la recursion, observemos que:

f({4}, 0, ...) = ( 4 )
f({1, 3}, 0, ...) = ( 1 + 3 )

Es simple deducir de estos ejemplos que si nos pasan como segundo parámetro cero, significa que no necesitamos agregar nada a la lista que nos pasaron como primer parámetro (pues ya suma lo que estábamos buscando), y solo debemos retornar esa lista como respuesta y terminar la recursión, entonces:

f(pa, 0, ...) = pa -- (7)

en donde:

pa = alguna partición ascendente

Además de:

f({3}, 1, ...) = ∅ (conjunto vacio)
f({1, 2}, 1, ...) = ∅ (conjunto vacio)

se puede deducir que si el segundo parámetro es un numero menor que el último termino de la PA pasada como primer parámetro, entonces la función debe retornar nada y terminar:

f(pa, m, ...) = ∅ (conjunto vacío) Si (m < z) ∧ (m > 0) -- (8)

en donde:

z = último termino de pa.

Es fácil demostrar esto ya que los únicos elementos que podemos agregar a pa = {a, b, ... , z} son números iguales o mayores que z, y como m > 0 aún tenemos que agregar términos a pa (pues no esta completa), pero agregando cualquiera de los términos válidos nos dará una suma mayor que m (porque los términos validos son por lo menos iguales a z y z > m) lo que no se quiere.

De (5) y (6):

f({}, 4, ...) = f({1}, 3, ...) + f({2}, 2, ...) + f({3}, 1, ...) + f({4}, 0, ...)
f({1}, 3, ...) = f({1, 1}, 2, ...) + f({1, 2}, 1, ...) + f({1, 3}, 0, ...)

Es posible deducir que:

f(pa, m, ...) = f({pa, z}, m - z, ...) + f({pa, z + 1}, m - z - 1, ...) + ... + f({pa, m}, 0, ...) -- (9)

en donde:

pa = alguna partición ascendente
z = último termino de pa, o 1 si pa esta vacía.
m > 0 ∧ m ≥ z

La ecuación (9) dice que todas las PA que empiezan con pa (y a las que hay que agregar términos hasta que sumen m) son iguales a la sumatoria de todas las PA que empiezan con pa mas un termino (que va desde z hasta m, donde z es el ultimo termino de pa) en donde se resta el nuevo termino a la suma a la que deben llegar los nuevos términos de las nuevas particiones. Como vemos pa crece en tamaño y m disminuye en valor, siendo evidente por (7) y (8) que este proceso recursivo debe llegar a un fin.

Ademas de (7), (8) y (9) vemos que ya no serán necesarios mas parámetros para esta función pues ya hemos establecido su proceso iterativo y condiciones para detener la recursión.

Resumiendo:

f(pa, m) = f({pa, z}, m - z) + f({pa, z + 1}, m - z - 1) + ... + f({pa, m}, 0) Si (m ≥ z) ∧ (m > 0)
f(pa, m) = ∅ Si (m < z) ∧ (m > 0)
f(pa, m) = pa Si (m = 0)

en donde:

pa = alguna partición ascendente
z = máximo termino de pa, o 1 si pa esta vacía.

La relación recursiva puede escribirse en forma compacta:

Listo!, ya tenemos todo lo necesario para programar.
Usaremos arreglos para representar las particiones e iremos imprimiendo las particiones que vayamos encontrando (no las devolveremos). En código simplificado:

void f(pa, m) {
    // Determinar valor de [z].
    z = (pa.longitud() > 0)? pa.ultimo() : 1 

    // Proceso recursivo
    for (k = z; k <= m; ++k) {
        // Crear nueva particion temporal [pt] agregando 
        // elemento [k] a la particion [pa].
        pt = pa.agregarAlFinal(k)
        
        if (m == k) {
            // Si (m - k == 0) imprimir [pt]
            imprimir(pt) 
        }
        else {
            // Continuar recursion
            f(pt, m - k)
        }
    }
}

Puedes revisar la implementación online en AS3 aquí, los comentarios están en ingles, pero son similares a los comentarios de arriba.

Lamentablemente la solución que he implementado es bastante lenta para valores de n grandes. Los métodos de optimización serán motivo de otro post, incluyendo la historia de como ese genio entre genios llamado Euler encontró una respuesta genial a esta pregunta... después de buscarla por 11 años!

Cuídense.

Chess problems in your phone

2008-03-22T19:57:00.001-05:00

This little thing can make you waste serious time if you like chess problems :)
It has been only tested in my SonyEricsson W810i, but I hope it could run in most of the phones with MIDP 2.0 + CLDC 1.1 support. It requires a phone with at least 176x176 pixels in screen resolution.
It supports UNDO and REDO and has the first move of the solution as a hint (if you feel impatient).

The problems belong to the books:

J. W. Abbott: 121 Chess Problems (1887)
F. Healey: 200 Chess Problems (1866)
[link]

I must thank to the guy who converted those PDF files to PGN files, without that I would have spent more time translating the positions to FEN, I only needed to prune off the bad problems and add the hints, the original PGN files can be found here:
[link]

You can choose from 4 different sets of pieces, every set has been composed by me, so every one of those pixels belong to me!! :D
To say the truth, the "Da Vinci" set was inspired in this article:
[link]

However I guess I couldn't capture the spirit and interchanged the knight by the bishop.

DOWNLOAD:
chessProblems.jar
chessProblems.jad

Have a nice day!

Update 2010: I'm going to port this to the Android soon, also planing to opening the source code if someone is interested.

Futuro movil

2008-03-02T08:26:00.001-05:00

Me parece que el futuro será móvil.

La epoca de las grandes y ruidosas PC de escritorio esta llegando a su fin :D. Y no me refiero a las costosas y pesadas laptops de ahora sino mi idea va mas por el lado de los celulares de ultima generación que están saliendo al mercado.

Ya estamos viendo laptops cada vez mas pequeñas con discos de estado solido y Linux como SO:

$400: Asus EEE

$200 OLPC (solo puedes comprarlo por millares)

Por otro lado los celulares de ahora son cada vez mas potentes.

Consideremos el iPhone por ejemplo, fue el primero que me demostró que un celular podía ser utilizado para navegar internet. Antes de eso seguro que muchos celulares tenían web browsers, pero la calidad de navegación era deprimente o incómoda, pantallas muy pequeñas, dificultad para mover la pagina, etc. Súmale a eso la tarifa de la llamada y no era muy tentadora la idea tampoco. Tenia que ser Apple quien demostrara que el tema de la web en tu celular es posible y práctico.

El futuro parece converger en un híbrido de las laptops actuales y tu celular. Con el dispositivo ideal:

Puedes comunicarte fácilmente con tus amigos.

Puedes guardar tu agenda, revisar tu correo, responder tu correo.

Puedes escuchar música, ver videos.

Puedes jugar juegos.

Puedes escribir reportes (o programar) en el camino.

Todo eso es posible en las laptops actuales, pero no en los celulares, actualmente no existe siquiera un celular que sirva realmente para jugar, al menos que yo sepa. Trata de jugar cualquier juego de acción en tu celular y veras que es bastante difícil, e incómodo, los botones son pequeños y duros o están muy cerca uno del otro y el pad de dirección esta en un lugar donde no es fácil de usar.

Necesito un gameboy-celular!! Aunque nada impide soñar que algún día tendremos un iGameBoy.

En cuanto a herramientas de desarrollo, J2ME es lento. Concuerdo plenamente con John Carmack (padre de Doom). El dice que no entiende como un celular con hardware suficiente para ser mejor que un GameBoy Advance con Java se convierte en un CPU con el poder de una IBM PC de 4.77 MHz y encima con controles que apestan!

Google mismo se ha dado cuenta de esto y le ha lanzado una artera puñalada a Sun con su Android. Android hasta ahora es solo una copia del J2ME, claro, sin todas las restricciones del consorcio J2ME y open source, pero sigue siendo Java (aunque usando una máquina virtual completamente diferente). Aun falta algo que permita acceder al procesador directamente, algo tan importante para desarrollar juegos de acción. Google ha dicho que esta en sus planes. Esperemos pues.

Un tercer contendor seria: FlashLite.

Aunque Flash ya tiene en su récord haber desaparecido (para efectos practicos) los applets de la web, su incursion en el mercado de celulares es aun muy limitada y aunque mejora el hecho de la compatibilidad (por el mismo hecho de que solo corre en pocos equipos) los primeros reportes no indican un aumento en el desempeño gráfico importante.
El tiempo dirá, de todos modos el tiempo corre a favor de FlashLite y en contra de J2ME.

Y bueno esta semana decidi portar mis problemas de ajedrez de la semana pasada de AS3 a J2ME como un ejercicio y este es el resultado:

JAR
JAD

Demás esta decir que tuve que experimentar en carne propia el ya famoso "write once, run everywhere", que para efectos prácticos se convierte en "compila en windows, falla donde sea". En mi caso habían dos errores que en el emulador no se notaban pero si en mi celular. Claro que los dos errores eran mi culpa (en este caso), pero se de otros que se han jalado los cabellos por errores esotéricos en la implementación del fabricante. De nuevo, no es culpa de Java tampoco, pero eso les pasa a los chicos de Sun por crear un lema tan pegajoso :).

Solo lo he probado en mi celular W810i y supuestamente debería correr en cualquier dispositivo con soporte CLDC 1.1 y MIDP 2.0.

Notas finales:

- No quiero hacer juegos de accion para celulares, pero puzzles esta bien.
- Java sera por fin WORE? O sera desplazado de nuevo por Flash?
- Microsoft existira en el futuro? Creo que ninguno de esos celulares corre Windows ni IE.... :D
- Cuando sale mi iGameBoy????

Hasta la proxima!

Perl

2007-11-04T11:36:00.001-05:00

Recuerdo el día que se rompió la burbuja C/C++ que aprisionaba mi cabeza. Fue por la noche, estaba molesto, pues tenía que aceptar, nuevamente, que aquel simple programita que me había querido hacer seguiría demorándose n-dias mas porque ya estaba cansado de escribir tanto código aburrido, para hacer hacer algo que no era ni tan interesante, ni tan urgente como para seguir frente a una computadora, después de haber estado todo el día frente a otra en mi trabajo, tal ves podría dormir temprano por alguna vez, y tratar de llegar temprano mañana, para variar.

"Debe haber algo mejor", me decía, no puede ser que para abrir un archivo tenga que escribir:

HANDLE hArchivoFuente = NULL;
hArchivoFuente = CreateFile (m_strSource,
    GENERIC_READ,      //Para lectura
    0,                 //No se permite compartir
    NULL,              //No seguridad
    OPEN_EXISTING,     //Falla si no existe
    FILE_ATTRIBUTE_NORMAL,
    NULL);

if (hArchivoFuente == INVALID_HANDLE_VALUE) {
  ::MessageBox (NULL,
      "No se pudo abrir el archivo de origen.",
      NULL, MB_OK | MB_ICONERROR);
  return;
}

Y eso que ni siquiera estaba programando usando el API Win32 puro, debido a que me estaba tomando mucho tiempo, había terminado usando MFC, denigrándome en mi auto conferido titulo de "verdadero programador". Que iba a saber yo entonces que los "verdaderos programadores" solo programan en ensamblador :)-

Para entonces seguro que ya me habría hecho el programita en VisualBasic en un dos por tres, pero a mis cándidos ojos de flamante internauta, crédulos y asombrados, le era evidente que en el mundo de los "verdaderos programadores", los que programaban en VisualBasic o eran unos retardados o lo hacían porque no tenían ninguna otra opción. Y claro esta que yo no quería parecer retardado ante semejantes luminarias.

Asi pues, por ese entonces, para mis proyectos personales o era C/C++ o era nada. Aunque por ahi rondara un triste engendro mio hecho en VB, cuyo único punto que lo salvaba del anonimato era que tenia un control programado en C++ usando ATL.

Pero ya estaba harto. Programar en C/C++ era lento, tanto que aveces me aburría del proyecto y comenzaba con otro.

Asi fue como comenzé a buscar algún otro lenguaje y me tope con Perl, lo que mas me gusto fue que podía programar iterativamente, lanzaba el programa desde mi editor con una tecla y asi sucesivamente iba refinando mi programa. A mis manos cayo un librito de como "Aprender Perl en 24 dias" o era horas? no recuerdo bien y casi como jugando empecé a usarlo para todas esa cosas aburridas y tediosas que necesitaban ser automatizadas. Gracias a Perl pude agregar comandos a mi editor para compilar C/C++, Java, C#, Haskell, Ocaml y hasta HLA, pude mandar correos con una tecla, hacer backups de la empresa mientras leía cosas mas interesantes, administrar el repositorio SVN, crear instaladores y no se cuanta cosa mas. Mi computadora (y la de mi trabajo) esta llena de pequeños y útiles archivos pl, tanto asi que Perl es la segunda cosa que instalo cada vez que tengo que formatear mi computadora.

De eso ya hace tiempo, puedo decir que he aprendido lo suficiente de Perl como para encontrarle cosas que no me gustan. Por el tiempo que decidí aprender Perl, ya existía Python y Ruby. Pero debido a que todos esos nombres me sonaban raros decidí usar el primer lenguaje que me funcionó, así que se puede decir que mi elección por Perl fue accidental, y no fríamente calculada. A pesar de ello, no me arrepiento de haberlo aprendido, aunque ahora ya no lo use tanto. De haber llegado a mis manos "Aprenda Lisp en 24 horas" tal vez otra seria mi historia :)

# Fill parameter values
if (/(\S+)/) {
  if ($arrayOpen) {
    if (/\}/) {
      $arrayOpen = 0;
    }
    chomp($_);
    @{$test[$indexTest]}[$indexParam] .= $_;
    $_ .= "\n";
  }
  else {
    if (( /\{/ ) && !( /\}/)) {
      $arrayOpen = 1;
    }
    chomp($_);
    @{$test[$indexTest]}[$indexParam] = $_;
    $_ .= "\n";
  }
}

El código de arriba es parte del script mas grande que tengo en Perl, crea una solución completa para VisualStudio 2005, interpreta un problema, y crea todos los archivos necesarios con formato y casos de prueba. En el colmo de la ironía: para poder resolver problemas en C++. En Perl es un poco mas de 600 lineas, no quiero imaginar cuantas lineas sería en C++, aun usando Boost. Pero seguro que son mas de las que me molestaría en programar para algo así. El punto es: el código de arriba trata de ser legible, aun asi: ¿Cuantos pueden adivinar que esta pasando ahi?.

Hace tiempo Larry Wall (el creador de Perl) estaba hablando de las irracionalidades que comenten los que crean lenguajes de programación, aquí algunos extractos, algunos bastante graciosos (tristemente con algo de verdad) :

- "Tenemos que comenzar todo desde el principio!" (casi cualquier lenguaje académico que encuentres)
- "Frases en ingles" (eso es Cobol)
- "El procesamiento de texto no importa mucho" (Fortran)
- "Lenguajes simples producen soluciones simples" (C)
- "Se me ha ocurrido un modo de hacerlo asi que debe de estar bien" (PHP)
- "Puedes construir todo con puertas NAND" (cualquier lenguaje inventado por un electrónico)
- "Este es un lenguaje de muy alto nivel, ¿A quien le importan los bits?" (lenguajes 4G)
- "A los usuarios les importa la elegancia" (Eiffel)
- "La especificación es suficientemente buena" (Ada)
- "Hagamos esto fácil para la computadora!" (Lisp)
- "Todo es un objeto" (Smalltalk y Ruby)
- "Todo es una hipótesis" (Prolog)
- "Todo es una función" (Haskell)
- "Los programadores no deberían tener nunca libre albedrío" (Python)

Pero Larry se olvido de criticar Perl, yo diría:

- "Hagamos esto críptico!" (Perl) :p

Hasta al proxima!

De como encontré programadores que no podían programar la serie de Fibonacci

2007-11-01T17:00:00.001-05:00

Es difícil encontrar buenos programadores y es mucho mas difícil decidir en unos cuantos minutos cual es la capacidad de cada candidato para resolver problemas de un nivel de dificultad no trivial. No quiero equivocarme, es muy costoso para la empresa contratar un candidato que no pueda ajustarse a las exigencias del puesto, es frustrante para dicha persona y negativo para el equipo en general. Lamentablemente ya me ha pasado. Asi que en la duda prefiero rechazar que aceptar.

Ahora bien si nosotros estuviéramos mas enfocados en búsquedas en tablas y presentación de resultados (y no hay nada de malo en ello) obviamente me centraría mas en saber cual es la experiencia con SQL, herramientas de reportes, creación de interfaces, etc. del candidato. Lamentablemente lo que yo busco es un candidato con la capacidad de resolver problemas que probablemente ni el ni yo hemos visto, además de poder hacer todas esas cosas mundanas que la gente de TI hacemos.

Encontrar este tipo de programadores es bastante difícil, encontrar buenos programadores en general es difícil. Por ello el proceso completo de selección de un programador con experiencia (no junior) envuelve: revisión de su CV, un examen online y finalmente un examen escrito con entrevista personal.

El CV básicamente solo descarta aquellas personas que mencionan su experiencia con lenguajes de programación como Word, PowerPoint o Internet Explorer (y no es haciendo macros o JavaScript). Es decir: tienes que tener un CV tan pero tan malo para que sea rechazado en esta fase.

El examen online me ayuda a separar a los que dicen tener años de experiencia en C/C++, de los que realmente tienen algo de experiencia. Las preguntas no son triviales, aunque ciertas pistas y respuestas se pueden encontrar buscando en la web. Casi todas las preguntas se pueden responder con menos de 100 lineas. Y debido a que se pueden elegir las preguntas a resolver casi siempre se eligen las preguntas mas simples. El candidato tiene un tiempo máximo de una semana para entregarlo después de contactar con el. Esto debido a que puede estar trabajando y solo podría resolver el examen en su tiempo libre. Que lo entregue lo mas pronto posible es por cierto considerado como un punto a favor. Solo un 5% pasa esta etapa, quizás menos. Lo que es bueno porque me evita el trabajo de descartar a los que solo han hecho cosas triviales en C/C++, (como copiar de la pizarra en su clase de Lenguajes de Programación I, hace varios años dicho sea de paso, eso señores no cuenta como años de experiencia en ningún lenguaje de programación excepto quizás VisualBasic), asi como a los que realmente no están muy interesados en el puesto y piensan que es un fastidio continuar con tan horrendo examen.

Ahora viene la parte difícil, decidir de entre los que enviaron el examen a los que realmente me gustaría contratar de los que no. Una primer vistazo al código es suficiente para descartar muchos, solo un 20% logra aprobar el examen, y no hablo de formato de código, o eficiencia de la implementación, hablo que muchos programas se cuelgan o dan soluciones equivocadas.

Entonces me queda un 1% del total por evaluar. Para comenzar debo aclarar que cualquiera que haya resuelto y aprobado ese examen por su cuenta es capaz de realizar cualquier trabajo medianamente complejo en C/C++. Y de tener recursos ilimitados por gastar contrataría directamente a dicha persona. Pero no los tengo, asi que mi inquietud es medir con cuanta ayuda resolvió el candidato ese examen online y cuanto tiempo real le tomaría hacerlo todo de nuevo bajo mi supervisión. Ahora que lo pienso esa seria una buena solución. Esto de escribir blogs es bueno. De hecho bastaría sentarme con el media hora para darme cuenta de que se encontró la solución por algún lado y la copio o que realmente se tomo un mes para resolver el examen antes de enviar su CV. Ahora, el hecho que lo haya podido hacer tiene su lado bueno, el restante 95% de candidatos no pudo hacerlo. Por otro lado no quiero contratar una persona deshonesta.

La solución actual implica pedirle al candidato venir para una entrevista personal y un examen psicológico y de programación. El examen psicológico es un test de IQ estándar, no hemos tenido sorpresas aqui, casi todos hacen entre 8 y 10 de 13 (lo que esta dentro del rango normal), donde si he tenido sorpresas es en el examen de programación. Este examen es bastante simple, o me parecía bastante simple, al principio pensé que seria ridículamente simple y esperaba ver cierta cara de mofa en los candidatos ante tales preguntas, todo sea por verificar la capacidad de cada candidato me decía. Si tu dices saber teoría de números y yo te pongo una pregunta donde debes multiplicar 13x14, lo que se espera es que puedas resolver eso sin ninguna dificultad. Casi como respirar.

Dicho examen puede ser resuelto en C/C++ o pseudocódigo, importa poco si te equivocas por allí en cerrar una llave o un paréntesis si la idea se entiende. Vamos yo me equivoco varias veces en ese tipo de cosas todos los dias, seria tonto decirte que no sabes programar porque no pusiste un punto y coma al final de una sentencia, ese tipo de cosas suelen pasar y mas si estas bajo presión y escribiendo en papel. Además, y aqui voy a dejar tema para otro post: yo creo que un lenguaje que te obliga a poner un punto y coma al final de cada sentencia es un fastidio, por decir lo menos. Y ya esta, que empiecen a llover los vilipendios. Pero desde que mi lenguaje favorito dejo de ser C/C++ y ahora es Ruby no voy a cambiar de opinión (si ya se que que Ruby es lento, por eso aun uso C/C++), pero bueno, a lo que iba.

Espero que un candidato con experiencia resuelva ese examen sin mucho problema: OK lo ideal seria darle un compilador por media hora pero el examen también tiene preguntas de concepto y diseño, no creo que una PC le ayude mucho en ello, además estamos partiendo del precepto de que el candidato sabe programar y bastante bien. Entonces llegamos a la pregunta maldita:

Implementar una función que devuelva el termino n-esimo de la serie de Fibonacci: 1,1,2,3,5,8,... ¿En cuanto tiempo calculará su función el valor de fibonacci(75)?

Tan simple como eso, la segunda parte es un hint para que el candidato implemente una solución iterativa, pues la solución recursiva demora demasiado y me sirve perfectamente para verificar si el candidato ha implementado alguna vez en su vida este ejercicio básico.

Y aqui viene la parte desagradable y el motivo de este post, pues he tenido que rechazar candidatos que en el papel tenían amplios conocimientos y certificados, cuyo examen online estaba dentro del promedio de calidad que acepto (sin llegar a ser brillante) pero cuya respuesta a esta pregunta hizo que sonaran muchas campanas de alerta en mi interior.

Hubo un candidato que tenia en su CV una maestría en una universidad del extranjero en ciencias de la computación, había implementado como tesis de bachiller un complejo algoritmo de optimización y que sin embargo falló en todas las preguntas simples que le hice. Siendo esta la de Fibonnacci la que ya no pude soportar. Cuando le pregunte el porqué me respondió: "Que era algo que había visto en la universidad hace mucho tiempo y no se recordaba bien pero tenia que hacerse con recursión."

El que no se recordara de Fibonacci no importaba, de hecho que nunca haya visto el problema seria lo ideal pues el candidato trataría de resolverlo solo con su ingenio, la serie esta ahí, ¿Quizás no pudo recordar como se formaba la serie? Difícilmente pues el mismo está admitiendo haberla visto algún tiempo y no es una serie como esta: 1, 11, 21, 1211, 111221, 312211,... Esa si es una serie que te hará doler la cabeza. El hecho es que para mi el candidato solo conocía la programación desde un punto de vista teórico, y eso hasta puede estar bien, Dijkstra mismo pensaba que había algo mas abstracto en las ciencias de la computación que mera programación. Algo en lo cual yo creo totalmente. "Las computadoras no son mas, a las ciencias de la computación, de lo que los telescopios son a la astronomía". Absolutamente cierto, pero yo estoy buscando un programador practico, y todos los programadores buenos y prácticos que conozco, aquellos que logran hacer cosas, pueden resolver este problema sin pensarlo mucho, quizás sin usar un tipo de dato que te permita calcular fibonacci(75), quizás sin emplear solo dos variables, quizás sin usar la formula cerrada o usando matrices, quizás sin emplear librerías especiales de números para calcular valores grandes, etc. Solo pon algunas variables y un contador dentro de un sucio for o while y punto. Siguiente problema.

Por eso escribo este post, quizás haya algún buen programador ahí afuera, realmente bueno, que lo lea y que tampoco sepa como programar la serie de fibonacci y que me convenza que alguien que no puede hacerlo en 10 minutos puede aún resolver problemas mas complejos pero practicos(?).