25 October 2012

Triangle Finder

A few weeks ago there was an NPR Sunday Puzzle for counting all of the triangles in a particular shape. I thought it’d be fun to code up a solution using JavaScript and HTML5 canvas, so I did. Unfortunately, I caught the flu and finished it a couple days late.

The basic algorithm is:

  1. given all the explicit nodes and edges, find all of the implicit nodes and edges
  2. for every node, explore a path of length 3 that doesn't repeat the same slope between consecutive nodes and doesn’t repeat (except for connecting the last and first)
  3. dedupe any redundant paths, sort all the results by size, and print them out

In addition to getting the modeling and constraints right, I had to call on some basic algebra for computing lines and intersections, and I also had to deal with the inaccuracies of floating point arithmetic by rounding to the nearest thousandth only when I check for equality. The code is on my github.

I created some extra shapes for testing, click any of the shapes below to find more triangles.

    comments powered by Disqus

    Peter Coles

    Peter Coles

    is a software engineer who lives in NYC, works at Ringly, and blogs here.
    More about Peter »

    github · soundcloud · @lethys · rss

    It’s time to get big money out of politics. Join the kick-started campaign to put government back in the hands of the people. Pledge mayday.us now