Brian J. Cardiff

Posted on

# A counting triangles story

Programming is a tool that can be used for a wide range of problems. Usually we code solutions for our clients, sometimes we build applications for ourselves. Programs don’t always need to be products at all, they can act as tiny pieces towards a larger objective.

It was back in May 2009 in Manas.Tech when Nico came with a simple question. How many triangles can you find in this figure?

Obviously `1-3-10`, `1-2-7` are triangles. For sure `7-9-2` is easy to depict. `2-4-6` is a bit small but definitely one to count and so on. Each of these triangles has another mirror image. After a little while, you realise there is also `1-2-6`, and `2-6-7` and –oh boy!– `1-2-9`. Most likely you will have lost count of how many triangles there are unless you are seriously organized.

Since we like having fun, either with arcades, drinks or whatever challenge comes to our daily life in Manas, we decided to tackle down this problem using our favorite tools.

In May 2009, some of us were nearing graduation, teaching assistants at college; school was another daily activity.

Most of us are programmers, and as such, we program. But each programmer has different preferences, backgrounds, areas of expertise, and this simple exercise was a perfect manifestation of that richness.

During the whole day a bunch of emails were sent with the proposed answers. Claims were made around 53, 54, 47, 63, 65. 47 was the most popular answer by far, yet, incorrect according to some sources.

The difference between the numbers is based on whether or not three aligned points shall be considered a triangle. And if `2-6-8` is equal to `2-8-10`... definitely not the important thing here.

## Different approaches

So the result was that we had lots of implementations, with completely different “mathematical” backgrounds to solve this riddle.

In chronological order we had the following solutions

• Santiago Palladino, with 62 lines of Python, he counted 3-segment cycles in a graph. Yep, he likes Python and Graph Theory (and Numerical Methods).

• Adrian Romero, with 35 lines of Python, he focused more on the lines than on the dots. He counted the intersections between pairs of lines that correspond to a triangle.

• Juan Wajnerman, with 41 lines of C# and heavy use of LINQ, he took a relational algebra approach (or SQL-ish if Algebra is not your cup of tea) to get a cross product and filter, achieving the same answer as the previous ones.

• Brian J. Cardiff (that’s me!), wrote a shameful and silly 30 lines of Prolog (could have been 20). Same answer! It was a Generate & Test algorithm that searched for three not aligned points that were aligned in pairs.

There were rounds of iteration along the day (we are agile developers after all) for fixing, discussing and discovering the different opinions around what is or isn’t a triangle. We relaxed the triangle criteria since we were not reaching the expected answer and we wanted to know why.

Adapting software is a big concern. If the inner functioning of the algorithm is not evident by reading the code, changing it is pretty hard. None of the above were too long or too cryptic, specially for the author himself. But, maybe because of my bias, Prolog was a clear winner here. Check the code!

But you know what? The solutions didn’t stop there.

• Ary Borenszweig codes a lot, seriously. Back then Crystal was not even a dream and he wrote 334 lines of Java. He even created a Graph class, tests and TrianglesCounter class. It’s Java’s way. The idea behind it was similar to Adrian’s, focused on the lines.

• Jonathan Kicillof (our graphic designer!) submitted his own. Although he knew ActionScript and today I am amazed about the Javascript plugins he is able to pull off, he submitted a PDF. Yeap, a well organized PDF that helped us point directly to the good, the bad and the ugly triangles.

• Ary Borenszweig, that guy that still codes a lot, submitted a total of 676 lines of Java. This time with a UI to draw and solve any triangle based problem.

Given that the input is fixed, the shortest program would be `echo 47` but that would have taken all the fun out of it.

And it’s nice to use your skills and the computer to solve a problem for yourself, by yourself. I happily remember when I already had lots of fun and challenges programming with nothing but a turtle.