Gracias, Ernő Rubik

Erno RubikHungría le ha dado al mundo notables matemáticos, como Jon Von Neumann y Paul Erdos. También grandes novelistas como Ferenc Molnar, autor de “Los muchachos de la calle Pal“, un clásico de la literatura juvenil que leí unas 150 veces durante mi infancia. Sin desmerecer a estas y otras luminarias húngaras de las ciencias y las artes, debe reconocerse que Ernő Rubik (foto) ha eclipsado a todas ellas. El creador del célebre “Cubo de Rubik” es inventor, arquitecto, escultor y profesor. Desde su vocación docente, Rubik creó el “Cubo Mágico” en 1974 como un experimento para explicar geometría tridimensional.cubo_magico A lo largo de sus casi 40 años de vida, el cubo fue tomando cada vez más protagonismo, llegando a niveles que ni el buen Ernő soñó en sus más salvajes pesadillas. No sólo es el puzzle más famoso de todos los tiempos, sino también el producto más vendido de la historia. Se calcula que 1/5 de la población mundial ha intentado resolverlo. Incluso se ha formado un movimiento llamado “Rubikcubismo“, que consiste en usar cubos para crear formas de arte. Desde 2003 se han celebrado regularmente campeonatos mundiales, donde speedcubers expertos se miden en diferentes disciplinas como como “velocidad”,  “a ciegas” o “con los pies” (no es chiste). En 2007, el francés Thibaut Jacquinot logró batir la marca de los 10 segundos. El récord actual de velocidad fue marcado en 2013 y es de nada menos que 5,55 segundos:

Sufriendo el mismo destino que el Ajedrez, hoy las máquinas resuelven el cubo más rápido que los seres humanos. Este Lego Robot lo logra en 5,35 segundos:

Métodos de resolución

El método más fácil requiere conocer sólo 7 algoritmos. Con unas pocas horas de práctica, el “Beginner’s Method” permite resolver el cubo en algunos minutos. El mayor problema de este sencillo y vergonzante mecanismo es que resuelve una sola capa por fase. La legendaria Jessica Fridrich desarrolló un set de algoritmos llamado F2L (First 2 Layers) que resuelve las dos primeras capas simultáneamente. Luego de F2L, el procedimiento más conocido para terminar el cubo se divide en dos fases: OLL (Orientation of the Last Layer) y PLL (Permutation of the Last Layer). En suma, para ser el alma de una fiesta de ñoños, es necesario conocer 78 algoritmos. Este es el mejor video que encontré sobre F2L:

El cubo en mi vida

Estudié a fondo el cubo durante los 15 días posteriores al nacimiento de mi hija, período en el cual mis deberes escatológicos dejaban baches de tiempo ideales para tal fin. Hasta que no logré bajar los 60 segundos, estuve obsesionado con el tema. Me recuerda la historia de un querido amigo, quien hace poco me contó que cuando se embarcaba en la Marina, tomaba todas las guardias de sentina (nadie las quiere porque implica pasar horas encerrado) para estudiar el adictivo cubo. Por suerte mi grado de obsesión cedió, lo que me permitió volver a mi vida profesional y social. No obstante, gracias a esta belleza de 3x3x3, nunca más me voy a aburrir en un lugar sin nada para hacer. ¡Gracias, Ernő Rubik!

Daniel Rabinovich

The Kid and the Beast

At Reykjavik Chess Tournament of 2004, a “kid vs beast” match took place. A 13-year-old player faced Garry Kasparov, the greatest chess player in the history of the game. At move #30, Kasparov had to defend himself with serious risk of loosing the match. He was lucky to escape with a draw. Full report here.

Eight years later, “the kid” became “the beast”. Magnus Carlsen is now the #1 chess player in the world, with the second highest ranking in history (after Kasparov).

Yesterday the “new beast” played an interesting game with a “new kid”. Carlsen played ten simultaneous games with randomly selected players from the Marshall Chess Club. To everyone’s surprise, after easily defeating nine of them, the only player still fighting was an 8-year-old named Daniel Levkov.

He (Carlsen) checkmated his first opponent in around 15 moves, with a surprising move that left the man dumbfounded. Some players kept playing when they had no chance of winning. But not Levkov, who stayed near equal in piece count until the end game. (Source: Business Insider)

With his full concentration on the board, the best player in the world crushed the 8-year-old in the endgame:

I love when little kids show extraordinary talent and achieve little miracles like this one. If some day I read in the papers that Daniel Levkov became the next #1, I’d smile and remember this episode. And if he decides to quit chess and become a musician, I’d also enjoy the idea of him telling his friends: “My dad taught me to play chess. When I was a kid, I forced the best chess player in the world to try his best to beat me”.

Daniel Rabinovich

Guinea pigs and cognitive biases

Some time ago, a friend asked for my help with a puzzle:

There are 1,000 buckets, one of them contains poison, the rest of them are filled with water. They all look the same. If a pig drinks that poison, it will die within 30 minutes. What is the minimum number of pigs do you need to figure out which bucket contains the poison within one hour?

Since I was familiar with similar problems, I quickly replied: the answer you’re looking for is 32 (the rounded square root of 1000). The procedure looks like this: the first half hour, split all 1000 buckets in 32 groups of 32 buckets. Have the first pig drink a drop from every bucket from group #1, and so on. Half an our later one pig will die, so we’re left with 32 candidate buckets (and 31 pigs) for the second half hour. Then, have all pigs drink from one bucket. This should find the poison (if none of them perish, the poison is in bucket #32). Proud at my problem solving skills, quickly rested my case and focused my attention in something else.

A few weeks later, I realized that I was wrong. 1000 buckets can be binary encoded with 10 bits (log 2, 1000) = 9,96 -> 10 pigs will suffice. The procedure is explained below for 8 buckets and 3 pigs (10 pigs solve 1024 buckets).

          Pig1   Pig 2   Pig 3
Bucket 1:  0       0      0
Bucket 2:  1       0      0
Bucket 3:  0       1      0
Bucket 4:  1       1      0
Bucket 5:  0       0      1
Bucket 6:  1       0      1
Bucket 7:  0       1      1
Bucket 8:  1       1      1 

There was a disturbing fact though: the procedure solves the problem in half an hour, and we have an entire hour to use. However, after finding a a solution to a similar problem in the comments section of the original post, I ignored this annoying fact and quickly jumped into the conclusion that the solution was actually 10.

Long story short, I was wrong, again. There are 2 better solutions:

Solution with 9 pigs: binary encoding, but in two “rounds” of 512 buckets.

Solution with 7 pigs: use ternary encoding instead of binary. The “trits” (as opposed to bits) represent 3 states: “dead in the first half hour”, “dead in the second half hour” and “survivor”. Using this technique, 7 pigs can solve up to 2187 buckets (3^7).

A dangerous cognitive bias

This sequence of failures have a common denominator: I tried to match the problem with the most similar pattern I knew, and quickly jumped into conclusions. As Daniel Kahneman says in his marvelous book Thinking Fast and Slow:

“A failure to check is remarkable because the cost of checking is so low”

In my case, I only had to check the comments section of the page! I almost answered by intuition. Since everything “looked right” the lazy left side of the brain failed to ring the alarm… 4 times.

To illustrate this point, Kahneman gives the following example. Don’t try to solve it but listen to your intuition:

A bat and ball cost $1.10
The bat costs one dollar more than the ball
How much does the ball cost?

They tested this simple puzzle on thousands of university students. More than 50% of students at Harvard, MIT and Princeton gave the intuitive -incorrect- answer: 10¢. The right answer is $1.05 and 5¢.

“A few seconds of mental work, with slightly tensed muscles and dilated pupils, could avoid an embarrassing mistake.”

This cognitive bias “force a situation into a known pattern and quickly jump into conclusions” is quite dangerous in a Technology team. Often the size of the inefficiency of a suboptimal solution is in the range of “32 vs 7 pigs”. In a large system, this cost could be huge, both financial and in terms of User Experience.

My first hand encounter with this dangerous bias made me tweak the “left side alarms” and strive to minimize the negative effects. After a while, it’s paying off. Hope you find it useful too.

Daniel Rabinovich

Relative color

I’m amazed at how many people think that colors are absolute, meaning the same RGB value will be perceived as the same color in every condition. It’s definitely not like that. Lighting conditions and the proximity of other colors and shapes greatly affect our perception, and our brain performs an enormous amount of corrections.

Consider this optical illusion:

Despite squares A and B are the exact same color, they are perceived as black or white in the proximity of other colors. In Color Theory, this is called “color context”.

Lighting conditions are another source of relativity. When using our eyes, our brain learned what lighting conditions we’re on and automatically adjust perceived colors. Digital Cameras have a tough time understanding what our brain is automatically correcting. That’s why we’re asked to adjust white balance when taking pictures. The following pictures show the same object in the assumption of three different lighting conditions (tungsten, fluorescent, and sun):

Why is this relevant to an e-commerce company like MercadoLibre? Because we need to extract product colors from user-uploaded pictures with unknown lighting conditions and therefore, unknown colors. This is a non-deterministic, complex, and beautiful problem to deal with. We’ll keep you posted.

Daniel Rabinovich