Drawing Factorization Diagrams Programmatically

I recently saw a post on a blog called The Math Less Traveled about creating neat-looking factorization diagrams using Haskell and the Diagram library. In that light, I'd like to set the record straight right away: the entire idea of my blog post is lifted. The basic idea is that you can represent a number's factorization by creating diagrams like the following that make it easy to see what a number's prime factors are.

The author makes this comment at the end of the post:

I wish I knew how to make a website where you could enter a number and have it show you the factorization diagram… maybe eventually.

After I read that, I felt like I had to do it myself. I decided to ignore the Haskell code and just take a stab at implementing something using JavaScript and the <canvas> element.

I knew that I whatever I came up with would be unlikely to match the elegance of the Haskell version, but after whipping up a very primitive Diagram interface, I had some code that made it pretty simple to implement the kind of factor diagrams I wanted.

Instead of starting with the greatest factor and moving down, my version starts by filling the entire canvas space with a circle, which can be thought of as 1. It then loops through each factor, F, and each time it scales the current diagram down proportionately to F, and places copies of the scaled version at each vertex of an F-sided polygon filling the entire canvas space. If you're a programmer, it's probably easier to just read the code than to try and follow that explanation.

All in all, it actually works pretty well, although I would definitely need to expand my Diagram interface before it could be considered useful for doing much more than render these diagrams. For fun, here is an example of how to render the factor diagrams for the numbers 1-25 on a canvas element:

This is the output:

And since I claimed the whole point of this project was to create the interactive Web version, here it is:

• Factor Diagrams Online (tested in Chrome and Firefox, not in Internet Explorer)
• Complete source code

Solving Einstein's Puzzle with Haskell

I recently read Martin Erwig's interesting paper "Escape from Zurg: An Exercise in Logic Programming" [PDF]. It's a few years old, but still relevant, I think. The paper examines a homework assignment in a computer science course where the students were asked to solve a simple logic puzzle in the programming language of their choice. The paper goes on to compare a solution in Prolog with a solution in Haskell.

The solution in Haskell is actually fairly simple, as it just stores the solution space in a list and filters the list with a user-defined function which imposes the problem's invariants. Because Haskell is evaluated lazily, filtering the list ends up being equivalent to running a depth-first search with backtracking. It's pretty cool that the language gives this to the programmer for free.

I know "enough to be dangerous" with Haskell, and this paper got me thinking about solving other kinds of logic problems with Haskell. It seemed to me that the list monad (in conjunction with the MonadPlus instance for lists) could be used to model a simple constraint solver. I decided to see if I could model and solve Einstein's Puzzle.

Modeling the problem was not bad at all. I defined algebraic data types for each of the five main variables, and then defined a house as a 5-tuple containing each variable. I defined the street as a list of five houses. I then wrote functions for each of the problem's fifteen constraints. Each constraint function was of type [(Color, Nationality, Pet, Beverage, Cigarette)] -> Bool so that I could enforce the constraints with guard. Writing each constraint function was really easy due to Haskell's pattern-matching syntax. Here's one particularly nice example:

norwegianFirstHouse ((_, Norwegian, _, _, _):_) = True
norwegianFirstHouse _ = False

While writing the program, I noticed that the running time started to increase exponentially by the time I got to about the tenth constraint. I was more interested in solving the puzzle than optimizing my program (for the moment), so I decided to just plug in the rest of the constraints, compile with optimizations, and run the program and see what it would come up with.

Embarrassingly, the program took about two hours to complete. Although, considering the solution space includes close to 300 quadrillion possibilities, perhaps that's not too unreasonable for such a naïve solution (a well-written Prolog program could solve this problem orders of magnitude faster). I won't reveal the answer to the puzzle here, but my program did find the correct solution.

So my experiment was a partial success, I'd say. On the one hand, I solved Einstein's puzzle, and writing tho code was a breeze. On the other hand, my solution is hopelessly inefficient. I do believe that Haskell's list monad could be used as the foundation for a more efficient constraint solver, though. At this point, my only truly unresolved question is whether I qualify for Einstein's "2% of the population who can solve the puzzle." Unfortunately, Einstein seems to have been silent on the matter of those of us who can solve his puzzle by cheating.

Here is the complete code: