# Javier Tordable

I also enjoy Mathematics,
Technology and Design.

# Javier Tordable

I also enjoy Mathematics,
Technology and Design.

## Blender

December 01, 2013

I haven't done any kind of 3D design in many years, but I was thinking last week that it would be fun to get back to it. And while I was looking at software available for Linux, I found Blender.

Blender has been around for quite some time but it seems that now it's features are up to par with some of the most popular 3D packages like 3DS Max or Alias.

Apart from the 3D design tools Blender has one very cool feature, a Python API! I will post another note after I have the chance to try it out.

Did you like this post? it on Google.

## A One-line primality test

November 09, 2013

A primality test in one line of Perl:

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]


Originally written by Abigail. Explained in detail by Neil Kandalgaonkar. Kudos to Pete Warden for the link.

Did you like this post? it on Google.

## Git Branching

September 22, 2013

I haven't had much time to write lately, work is keeping me busy. But today I wanted to share a site I found recently and I think is really interesting. It's essentially a git tutorial, but with a twist.

As most of you know git is a version control system. Essentially, a program to track and coordinate updates to a set of files, which is one of the most basic tasks in software engineering. Learn Git Branching helps beginners learn how to use git. But instead of simply explaining the git commands it's structured as a puzle game. The levels are git tree structures, and in order to solve the puzzles it's necessary to input the proper git commands.

The puzzles go from the very simple, to the fairly complex. So even if you already know git, it may be fun to play the most advanced levels.

Kudos to Petter Cottle for the tutorial. You can check out his Github profile here.

Did you like this post? it on Google.

## How Memories Look Like

June 22, 2013

A team from USC engineered microscopic markers that light up synapses in a living neuron in real time.

The fluorescent markers allow scientists to see live excitatory and inhibitory synapses for the first time and, importantly, how they change as new memories are formed.

Did you like this post? it on Google.

## Balloon Powered Internet

June 22, 2013

Project Loon is a network of balloons traveling on the edge of space, designed to connect people in rural and remote areas, help fill coverage gaps, and bring people back online after disasters.

Did you like this post? it on Google.

## Code Search with Regular Expressions

June 03, 2013

A few days ago I found out about codesearch. It's a group of command-line tools to index and search code using regular expressions. It was originally developed by fellow googler Russ Cox. It uses the same algorithms that were behind Google Code Search.

I played with it a little bit and I'm impressed by how fast it is. Also, it can be integrated easily with emacs. However, I think it would be even better with a simple web interface. For example, to show the content of the files and highlight matching expressions. Actually that would be a nice weekend project...

Did you like this post? it on Google.

## MIT Talk: Mathematics at Google

May 05, 2013

A few weeks ago I gave a small webinar for a group of students from MIT.

They told me it went quite well. About 40 people attended.

I basically covered the material in this presentation about Mathematics at Google which I published last year.

So I'll make use of the opportunity to put the link out there again, for any of you who didn't have the chance to take a look before. Comments and suggestions will be appreciated.

Did you like this post? it on Google.

## Atom movie

May 02, 2013

A stop-motion movie made with two-atom molecules.

IBM researchers used the scanning tunneling microscope to control a super-sharp needle along a copper surface to “feel” atoms. Only 1 nanometer away from the surface, which is a billionth of a meter in distance, the needle can physically attract atoms and molecules on the surface and thus pull them to a precisely specified location on the surface.

Did you like this post? it on Google.

## Tech Meetups

April 27, 2013

Over the last few months I have been going to a few technology meetups here in Seattle, and I enjoyed it very much. It's great to see all the cool technology that local companies are creating. Here are three of the most popular tech meetups in Seattle:

Seattle Tech Meetup

Hacker News Seattle Meetup

Seattle Scalability Meetup

Feel free to drop me a note if you are planning to go to any of these. And say hi if you see me there!

Did you like this post? it on Google.

## Card Games, Complete Subgraphs, Constant Weight Error Correcting Codes and Finite Projective Geometries

April 08, 2013

I was recently in a store buying a gift for a friend and found a card game that seemed interesting. The cards have small symbols which are arranged in a way such that between two cards there is always one symbol in common.

These are the rules, from the store page:

Some people can spot a 90% off designer dress in a pile of discounted rubbish. They make out street signs from superhero distances. And they can identify the rarest of rare birds without even trying. You can be one of those people after a few quick rounds of Spot It! This smart game contains 55 illustrated cards with eight symbols each. There is always one, and only one, matching symbol between any two cards. All you need is a sharp eye and quick hands to take home the title of “Spot It! Master of the Visual Universe.” Win or lose, every player gets killer visual perception skills as a parting gift.

You can see an example of the relationship between cards here:

As I was leaving the store I though maybe there is something more to this game than meets the eye.

## Card Games

First of all, how many symbols are there? And are they repeated or not? Let's start with the most simple approach. We have 55 cards, and we know that there is always a symbol in common between two cards. Given 55 cards we have a maximum of $$\left(\begin{array}{c} 55\\ 2\end{array}\right)=\frac{55\cdot54}{2}=1485$$ pairs of cards. Now, that seems a large number of symbols, more than one would imagine by looking at the card images. But the real problem with this approach is that each card would need 54 symbols, instead of just 8.

Let's think about it the other way around. We have 55 cards, with 8 symbols each, and each symbol is repeated at least twice. That makes $$\frac{55\cdot8}{2}=220$$ symbols. Obviously the problem here is that we can't guarantee that between any two cards there is always a symbol in common.

Now, if we think for a moment about the second question, what if the symbols were not repeated across more than 2 cards? Let $$C_{1}$$ be one card from the deck, it has 8 symbols, $$C_{1}=\left\{ s_{1},\ldots,s_{8}\right\}$$ which are shared by at most eight other cards $$C_{2},\ldots,C_{9}\,|\, C_{1}\cap C_{2}=\left\{ s_{1}\right\} \ldots C_{1}\cap C_{9}=\left\{ s_{8}\right\}$$ what happens when we consider yet another one, $$C_{10}$$. Then it has to be $$C_{1}\cap C_{10}\in\left\{ s_{1},\ldots,s_{8}\right\} \Rightarrow\exists i\in\left\{ 1,\ldots,8\right\} \,|\, C_{1}\cap C_{10}\cap C_{i}\neq\emptyset$$ Or in another words. With 8 symbols the card 1 could only be connected to 8 other cards, but not the remaining 46, arriving to a contradiction. As a matter of fact, if one looks carefully at the images of the deck and the video, it's possible to spot 4 cards that share the same symbol.

## Complete Subgraphs

The combinatorial approach didn't get me very far. Let's go back to the original problem and try to model it as a graph. We have 55 nodes, for each of the 55 cards. And each pair of nodes is connected through a symbol. So we have the complete graph of 55 nodes $$K_{55}$$, which has 1485 edges. Now we could think that each edge has a color, and that would reduce our problem, to the problem of finding a coloring of the dual graph of $$K_{55}$$. However that doesn't seem to work. In a coloring problem we are interested in assigning colors to nodes such that two asjacent nodes have different colors. In our case we can perfectly have two adjacent edges with the same color, corresponding to one card sharing a symbol with two other cards. In any case, the theory of graph coloring is very rich so there may be another less obvious approach that works.

Going back to our original graph $$K_{55}$$, realize that we can have edges coming from the same node that have the same color, for instance $$n_{1},n_{2},n_{3}\in V\left(K_{55}\right),\left(n_{1},n_{2}\right),\left(n_{1},n_{3}\right)\in E\left(K_{55}\right)$$ such that $$\left(n_{1},n_{2}\right),\left(n_{1},n_{3}\right)$$ have the same color. But this imposes the additional condition that $$\left(n_{2},n_{3}\right)$$ has the same color as the other two. Or in other words, taking all the edges that have the same color and the corresponding nodes should give us a complete subgraph. Going back to cards and symbols, this makes obvious sense. If we have 8 cards that share a particular symbol, then any two pairs of cards out of those 8 are connected through that same symbol. We know from the problem definition that there is no other symbol that can be shared among any pair of those 8 cards.

This seems closely related, but not quite the same as the problem of finding cliques in the graph. In our subgraphs each of the nodes is also connected to nodes outside of the subgraph. All other nodes, as a matter of fact. Nevertheless, considering that the clique cover problem is NP-complete, that doesn't augur an easily computable solution to our deck problem.

For the sake of example, let's try to find a solution in case we had 6 cards. We can start taking the complete subgraph with the first 5 nodes. All with the same color, or symbol a. And then the remaining node, with 5 edges to the previous 5. Each one with a different color b,c,d,e,f. We can't take the same color for all because the destination nodes are not connected within the subgraph. The 6 cards would be: $$\begin{eqnarray*} C_{1} & = & \left\{ a,b\right\} \\ C_{2} & = & \left\{ a,c\right\} \\ C_{3} & = & \left\{ a,d\right\} \\ C_{4} & = & \left\{ a,e\right\} \\ C_{5} & = & \left\{ a,f\right\} \\ C_{6} & = & \left\{ b,c,d,e,f\right\} \end{eqnarray*}$$ These verify that between each pair of cards there is only one symbol in common. However they don't satisfy the condition that each card have the same number of symbols. In order to satisfy that condition as well, we would need to make sure that each node is contained in the same number of subgraphs. With a little bit more work we can find a solution for $$K_{6}$$, which is as follows

Giving the cards: $$\begin{eqnarray*} C_{1} & = & \left\{ a,b,e\right\} \\ C_{2} & = & \left\{ a,d,f\right\} \\ C_{3} & = & \left\{ b,d,g\right\} \\ C_{4} & = & \left\{ c,d,e\right\} \\ C_{5} & = & \left\{ b,c,f\right\} \\ C_{6} & = & \left\{ a,c,g\right\} \end{eqnarray*}$$ Again, it's easy to verify that between each pair of cards there is only one symbol in common. But now each card has only 3 symbols. In any case, following this approach it doesn't seem obvious how to manually scale the process to 55 cards.

## Constant Weight Error Correcting Codes

Here is another insight: we can write a matrix that has one row for each card, and one column for each symbol. This reminds to the incidence matrix for the graph, but is clearly different. The matrix is: $$\begin{array}{c} \begin{array}{ccccccc} a & b & c & d & e & f & g\end{array}\\ \left(\begin{array}{ccccccc} 1 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 1\end{array}\right)\end{array}$$ And what we have here is a set of binary words, such that the Hamming distance between each pair of words is 4. Between each of the words there is one symbol in common, there are two symbols which appear only in the first word, two more that appear only in the second word, and the remaining symbols don't appear in any of them. This is precisely what makes an error correcting code valuable. In our particular case we are interested in codes with constant weight, because each of the words should have the same number of symbols.

With this, the problem is reduced to finding an error correcting code. We have 55 words, corresponding to the 55 cards in the game. The weight of each word is 8, because each card has 8 symbols, and the distance between words is 14, because for each pair of cards there is one symbol in common, 7 appear only in the first card, 7 in the second one, and the rest don't appear in any of them.

Three questions arise, first, is it possible to build a code like this? second, how many symbols do we need? and third, how do we actually go about building this code?

Fortunately, there are complete tables that indicate the bounds for binary constant weight codes. Formally, $$A\left(n,d,w\right)$$ is the maximum number of words in a binary code with word length n, distance d and constant weight w. In our case d=14, w=8 and we are looking for the minimum n such that $$A\left(n,d,w\right)\geq55$$. By looking at the tables we can see that $$A\left(n,14,8\right)<55$$ for all $$n<55$$, and $$A\left(56,14,8\right)=49$$ and $$A\left(57,14,8\right)=57$$. And this answers the first two questions. If we take 57 symbols then we can build a code with 57 words which verifies our constraints. If you look back at the tables you will see a note which indicates that the maximum is reached by taking $$PG\left(2,7\right)$$.

## Finite Projective Geometries

$$PG\left(2,7\right)$$ is a finite projective geometry of dimension 2 and order 7. The order is one less than the number of points in a line. In particular, this is the projective plane built on top of the finite field $$\mathbb{F}_{7}$$.

In $$PG\left(2,7\right)$$ we have $$7^{2}+7+1=57$$ points, 57 lines, 7+1=8 points on each line, and 8 lines through each point. As such, if we model the cards in our deck as lines, and the symbols as points, we can build explicitly our deck:

Points: $$\begin{array}{c} \left(\underline{0},\underline{0},\underline{1}\right),\\ \left(\underline{0},\underline{1},\underline{0}\right),\left(\underline{0},\underline{1},\underline{1}\right),\left(\underline{0},\underline{1},\underline{2}\right),\left(\underline{0},\underline{1},\underline{3}\right),\left(\underline{0},\underline{1},\underline{4}\right),\left(\underline{0},\underline{1},\underline{5}\right),\left(\underline{0},\underline{1},\underline{6}\right),\\ \left(\underline{1},\underline{0},\underline{0}\right),\left(\underline{1},\underline{0},\underline{1}\right),\left(\underline{1},\underline{0},\underline{2}\right),\left(\underline{1},\underline{0},\underline{3}\right),\left(\underline{1},\underline{0},\underline{4}\right),\left(\underline{1},\underline{0},\underline{5}\right),\left(\underline{1},\underline{0},\underline{6}\right),\\ \left(\underline{1},\underline{1},\underline{0}\right),\left(\underline{1},\underline{1},\underline{1}\right),\left(\underline{1},\underline{1},\underline{2}\right),\left(\underline{1},\underline{1},\underline{3}\right),\left(\underline{1},\underline{1},\underline{4}\right),\left(\underline{1},\underline{1},\underline{5}\right),\left(\underline{1},\underline{1},\underline{6}\right),\\ \left(\underline{1},\underline{2},\underline{0}\right),\left(\underline{1},\underline{2},\underline{1}\right),\left(\underline{1},\underline{2},\underline{2}\right),\left(\underline{1},\underline{2},\underline{3}\right),\left(\underline{1},\underline{2},\underline{4}\right),\left(\underline{1},\underline{2},\underline{5}\right),\left(\underline{1},\underline{2},\underline{6}\right),\\ \left(\underline{1},\underline{3},\underline{0}\right),\left(\underline{1},\underline{3},\underline{1}\right),\left(\underline{1},\underline{3},\underline{2}\right),\left(\underline{1},\underline{3},\underline{3}\right),\left(\underline{1},\underline{3},\underline{4}\right),\left(\underline{1},\underline{3},\underline{5}\right),\left(\underline{1},\underline{3},\underline{6}\right),\\ \left(\underline{1},\underline{4},\underline{0}\right),\left(\underline{1},\underline{4},\underline{1}\right),\left(\underline{1},\underline{4},\underline{2}\right),\left(\underline{1},\underline{4},\underline{3}\right),\left(\underline{1},\underline{4},\underline{4}\right),\left(\underline{1},\underline{4},\underline{5}\right),\left(\underline{1},\underline{4},\underline{6}\right),\\ \left(\underline{1},\underline{5},\underline{0}\right),\left(\underline{1},\underline{5},\underline{1}\right),\left(\underline{1},\underline{5},\underline{2}\right),\left(\underline{1},\underline{5},\underline{3}\right),\left(\underline{1},\underline{5},\underline{4}\right),\left(\underline{1},\underline{5},\underline{5}\right),\left(\underline{1},\underline{5},\underline{6}\right),\\ \left(\underline{1},\underline{6},\underline{0}\right),\left(\underline{1},\underline{6},\underline{1}\right),\left(\underline{1},\underline{6},\underline{2}\right),\left(\underline{1},\underline{6},\underline{3}\right),\left(\underline{1},\underline{6},\underline{4}\right),\left(\underline{1},\underline{6},\underline{5}\right),\left(\underline{1},\underline{6},\underline{6}\right)\end{array}$$

Lines:

Feel free to check my computations. I wrote the table above manually. I included it as an image to make the formula rendering easier on the browser, but I can share the orginal $$\LaTeX$$ code on request. I don't have the game with me, so I can't check if this is exactly how it's made, remember that the game has 55 cards instead of the 57 available. This leaves another question open, what other ways are there to build a deck like this, possibly with more symbols and less words?

Did you like this post? it on Google.