Over the last 9 weeks I've had the pleasure of being enrolled in the Discrete Optimization course at Coursera taught by Pascal Van Hentenryck. I had previously taken several of other massive open online courses (MOOCs), but this was the most challenging and rewarding. The key ingredients of this course were the unquestionable enthusiasm by its instructor and assistants, who created an excellent series of lectures and were personally involved at every step, as well as a game-like grading system, where the better your algorithm, the better your grade. It was rather intense! None of the programming assignments are issued with a well-defined strategy for creating a solution. Instead, the lectures cover various types of techniques and tools to be implemented and tinkered with by the students. Another interesting feature of the course is that all of the lectures and assignments are available from the first day. Most courses impose a schedule of lectures and assignments to be watched and completed on a week-by-week basis. The open structure of Discrete Optimization had me feeling a bit bewildered at first. They do provide a suggested study plan, so I (mostly) stuck with that and was able to make steady progress throughout the course.

One of the topics that resonated with many of the students, myself included, was that of Local Search. It's an idea that's easy to conceptualize and program, yet very powerful. I implemented a Local Search solution for the Traveling Salesmen Problem and, along the way, added some code to visualize some of the larger solutions. It looked pretty cool to see so many points connected together by a continuous route. I began experimenting with animating the algorithm as it finds a solution. Later, the professor's assistant (AKA graciously-answering-forum-questions-Carleton Coffrin) put out a call for the students to create visualizations of various heuristics that can be used to solve TSP. Here is my contribution – it displays Greedy algorithm, Local Search, and Simulated annealing strategies for a group of US cities.

I’ve seen some interest in knowing how this was created. Here are the steps:

• I wanted to use some "real" map data to help illustrate the problem.  From a list of cities from geonames.org, filtered by country and population to generate data sets
• Ran these through my TSP solver from the Discrete Optimization course assignment, collecting the intermediate routes as improvements are made
• Generated a metric ton of still images to illustrate the transitions between the routes - this involves:
• translating the points and lines onto a bitmap
• "tweening" many frames between each route to provide smooth transitions. I tried several different "easing functions" but ended up with something like "easeInOutQuad" shown on this Easing Functions page
• … also generate images for the distance and temperature
• Imported these as numbered frames into Adobe Premiere Elements - I don't use anything fancy, just the text, some cross-dissolve transitions, and alter the speed of the frames - the same could likely be done with open source editors ( VLMC?)
• The map of the US is a "flat" Mercator projection so that the latitude and longitude coordinates from the city list will show up in approximately the correct location - it's from here: Mercator Projection.svg
• ... and then a bunch of slicing and dicing and mixing and matching inside the video editor to "tell the story"

The code was done in .NET – here’s some pseudo-code used to generate the animation:

          minX, minY = points.Minimum(X), points.Minimum(Y) maxX, maxY = points.Maximum(X),
points.Maximum(Y) w = maxX - minX h = maxY - minY imgW = 720 imgH = 480 frame = 0
foreach routePair in routes.Pairwise() edgePairs = CalculateEdgePairs(routePair.Current,
route.Next) for tween in [0..30] tweenFactor = EaseInOut(tween) using (var bitmap
= new Bitmap(imgW, imgH)) using (var g = Graphics.FromImage(bitmap)) RenderPoints(g,
points, brush); RenderEdges(g, edgePairs, tweenFactor, pen); bitmap.Save(filename
+ frame++, ImageFormat.Png); RenderPoints(g, points, brush) foreach (var p in points)
point = Translate(p); g.FillEllipse(brush, point.X, point.Y, _pointSize); RenderEdges(g,
edgePairs, tweenFactor, pen) // interpolate the edge changes foreach (var edgePair
in edgePairs) point1Current = Translate(points[edgePair.Current.Point1]); point1Next
= Translate(points[edgePair.Next.Point1]); point2Current = Translate(points[edgePair.Current.Point2]);
point2Next = Translate(points[edgePair.Next.Point2]); g.DrawLine(pen, (point1Next.X
- point1Current.X)*tweenFactor + point1Current.X, (point1Next.Y - point1Current.Y)*tweenFactor
+ point1Current.Y, (point2Next.X - point2Current.X)*tweenFactor + point2Current.X,
(point2Next.Y - point2Current.Y)*tweenFactor + point2Current.Y); Translate(point)
new Point( X = (point.X - minX) / w * _imgW, Y = (point.Y - minY) / h * _imgH) EaseInOut(x)
(x*x)/(x*x + (1 - x)*(1 - x))
        

So intense. We've heard how HTML5's canvas element will provide device-independent in-browser graphics – and now I want a taste! After seeing some magnificentdemos, I started wondering what the plumbing looks like.  I haven't touched any graphical code since maybe 1994 in QBasic, so come along with me as I learn.

Also, I'm giving CoffeeScript a spin. I saw a presentation by Daniel Mohl at Codestock a few weeks ago and thought it was fantastic. You write in a terse-clean-"modern" language and get the functionally equivalent JavaScript out the other end.  So long to writing function(){...} every three lines! Much of the syntax is based on Ruby, so it's an easy language to read - I'll comment on any syntax that isn't immediately obvious.

But the important question is - what to draw?  I follow a few graphic design blogs and remember seeing some neat geometric patterns on veerle's blog done in Adobe Illustrator. These were inspired by the kaleidoscopic artwork of Andy Gilmore – check them out, some of the pieces are kind of hypnotic. The specific creation that motivated Veerle's tutorial can be seen here. It has a beautiful simplicity. As Veerle mentions - we don't want to make an exact replica, but instead use some of the patterns as a starting point of something original.

The absolute first step is to draw a circle, just like it was in the Illustrator tutorial by Veerle. Well, part of a circle. I found it easiest to get the desired results using an "arc".  This is a term that simply means "a specific section along the side of the circle".  What this entails for the HTML5 canvas is specifying the center point of the circle, the radius, and the angles at the start and end the arc.  My trigonometry knowledge has deteriorated over the years (if it ever existed to begin with) – but this is pretty simple. The right-most point on the circle has an angle of 0π, travelling clockwise to the bottom-most point is .5π, the left-most has 1π, up to the top at 1.5π, and a full circle is (of course) 2π.  To draw a full circle, you'd type in context.arc(0,0,radius,0,Math.PI * 2).  Note: the angles I learned in school were oriented counterclockwise, yet most of the examples I've seen for HTML5 canvas are clockwise – most likely because the y-axis increases in a downward direction instead of up.  I'll keep it clockwise here.

Access the HTML5 Canvas using CoffeeScript

But what's this context, you ask? I might have lied about the first step – the super-absolute first step will be to set up the HTML5 canvas object so that we can draw on it.  Here's a complete example of a using CoffeeScript in a script tag with the in-browser compiler to accomplish this.

          <!DOCTYPE html> <html> <head> <title>Full on rainbow
Spirograph</title> <script src="scripts/jquery-1.7.2.min.js" type="text/javascript"></script>
<script type="text/coffeescript"> canvasSize = 300 # shortcut for jquery's document
ready jQuery -> # get the canvas element (using jquery) canvas = $('#myCanvas')[0]
# set the width and height of the canvas element canvas.width = canvas.height = canvasSize
# get the API object for drawing on the canvas ctx = canvas.getContext '2d' # make
a dark background ctx.fillStyle = '#002b36' ctx.fillRect(0,0,canvasSize,canvasSize)
# write some text ctx.font = '30px Arial' ctx.fillStyle = 'white' ctx.fillText("#myCanvas",
80, 150) </script> </head> <body> <canvas id="myCanvas"></canvas>
</body> <!-- download in-browser coffee-script compiler at --> <!--
https://github.com/jashkenas/coffee-script/raw/master/extras/coffee-script.js -->
<!-- coffee-script.js goes AFTER all the CoffeeScript. --> <script type="text/javascript"
src="scripts/coffee-script.js"></script> </html>
        

This generates a page containing a dark 300x300 rectangle with "#myCanvas" written in white. This is great for kicking the tires, but the script is getting compiled down to JavaScript each time the page loads.  It's preferable to compile it ahead of time.  With a little tooling this process becomes nearly transparent.  In Visual Studio a great option is the Web Workbench extension by Mindscape.  It automatically compiles your CoffeeScript (and Sass and LESS) scripts each time the file is saved. After making this change, the code now looks like...

          <!DOCTYPE html> <html>
<head> <title>Full on rainbow Spirograph</title> <script src="scripts/jquery-1.7.2.min.js"
type="text/javascript"></script> <script src="scripts/CoffeeScript_Compiled.js"
type="text/javascript"></script> </head> <body> <canvas id="myCanvas"></canvas>
</body> </html>
        

            # CoffeeScript_Compiled.coffee canvasSize
= 300 $ -> canvas = $('#myCanvas')[0] canvas.width = canvas.height = canvasSize
ctx = canvas.getContext '2d' ctx.fillStyle = '#002b36' ctx.fillRect(0,0,canvasSize,canvasSize)
ctx.font = '30px Arial' ctx.fillStyle = 'white' ctx.fillText("#myCanvas", 80, 150) 
          

            //
CoffeeScript_Compiled.js (function() { var canvasSize; canvasSize = 300; $(function()
{ var canvas, ctx; canvas = $('#myCanvas')[0]; canvas.width = canvas.height = canvasSize;
ctx = canvas.getContext('2d'); ctx.fillStyle = '#002b36'; ctx.fillRect(0, 0, canvasSize,
canvasSize); ctx.font = '30px Arial'; ctx.fillStyle = 'white'; return ctx.fillText("#myCanvas",
80, 150); }); }).call(this);
          

Circular

Now that the canvas is ready to draw on – let's get back to that arc. Like from the Illustrator tutorial, I'm aiming to make a leaf-like object that can be duplicated around a central axis.  First I'll create the right side of the leaf.

          # cache the math stuff pi = Math.PI cos = Math.cos sin = Math.sin $ ->
canvas = $('#spriospectrum-arc')[0] ctx = canvas.getContext '2d' # make center of
the canvas the (0,0) coordinate ctx.translate(size/2, size/2) # radius of the complete
circle radius = size / 4 # create the arc shape ctx.beginPath() ctx.arc(0, 0, radius,
1.7 * pi, .3 * pi, false) ctx.closePath() # fill it in with a color ctx.fillStyle
= '#fdf6e3' ctx.fill()
        

The first bits are again to set up the canvas context – I'll omit those from now on.  The first line of interest contains the translate function – this reorients the context to the specified point.  Anything drawn on the canvas afterwards will treat this point as the center.  Here I pass in size/2, size/2 - which makes the center of the canvas the 0,0 coordinate.

The next line computes a radius based off the size of the canvas – I simply did a fourth of the canvas dimensions so that it would fit with room to spare.

Next comes the definition of the arc's shape – or the path that the arc will make. The first step is a call to beginPath().  This is done so that the first point of the arc it is drawn as the beginning of the shape.  If I had drawn anything else on the canvas before this (which I actually have – more on that later), it would continue the previous path, drawing a line between that last piece and the arc.  I've found it's easier to explicitly begin and close the path rather than to assume it's a fresh canvas – especially when you start composing more complex drawings.

Finally – the actual call to arc! Since we've translated the canvas to center point we're passing in the 0,0 coordinate so that the circle gets drawn in the exact middle.  Next comes the radius variable which we've already defined. Now comes the tricky bit – the beginning and end angles of the arc. Going back to the circle schematic – I'm defining the beginning point slightly past the top (to the right), and the end point slightly before the bottom (to the left).  By "slightly", I mean by 0.2 for each side.  Multiply these values by π, and it's ready to be drawn! Oh – and the final parameter indicates that it should be drawn counter-clockwise. Completely assembled, the call looks like arc(0, 0, radius, 1.7 * pi, .3 * pi, false)

Finally, a fillStyle is specified as a color using hex RGB and the arc is drawn by calling fill(). Voila!

Well... that seems like a lot of work to draw something so trivial!  It'll get more interesting in a little bit...

Leafy

The first half of the leaf has been drawn – now for the other half.  There are a number of ways to go about this – I'll go over a few that I've found.  In this first pass, we'll simply draw another arc on the opposite side of the circle.

          ctx.beginPath() ctx.arc(0, 0, radius, 1.7 * pi, .3 * pi, false) ctx.arc(0,
0, radius, .7 * pi, 1.3 * pi, false) ctx.closePath()
        

Ok – not a bad start.  This time I draw the same arc on the right as before and then continue on with a second call to arc on the left side of the circle – arc(0, 0, radius, .7 * pi, 1.3 * pi, false).  The only differences are the start and end angle.  Going clockwise, the first arc goes from 1.7π to .3π, and then the second arc continues at .7π and ends at 1.3π.  Filling in this path produces the shape seen above.

The obvious problem is all that extra space in the middle of the circle – it's definitely not leafy so it's got to go! I'll start over with just the arc on the right side.  To allow us to easily figure out where the leaf will go, it'll be good to have an easy-to-spot anchor point. For this, I chose the bottom bottom-most point of the leaf which which will be located at 0,0. All that's needed is a bit of maths.

It's clear to see that the bottom-most point of the arc is below-and-right to the canvas center point.  To do this, we'll move the coordinates for the center of the circle up and to the left. But how much? To calculate, we'll use a little trig.  The coordinates on a circle can be calculated, given the angle θ, with x = cos(θ) and y = sin(θ). So, the offset for x will be -cos(.3π) * radius and for y will be -sin(.3π) * radius...

          ctx.arc( -cos(.3 * pi) * radius, -sin(.3 * pi) * radius, radius, 1.7 *
pi, .3 * pi, false)
        

Success!  Now the same process for the left-side...

          ctx.arc( -cos(.7 * pi) * radius, -sin(.7 * pi) * radius, radius, .7 * pi,
1.3 * pi, false)
        

Rotate

Another way to skin this cat is to use the rotate() function to spin the canvas around. Now I'll try drawing the first arc, flipping the context, and then drawing the exact same arc.

          drawArc = -> ctx.arc( -cos(.3 * pi) * radius, -sin(.3 * pi) * radius,
radius, 1.7 * pi, .3 * pi, false) ctx.beginPath() drawArc() ctx.rotate(pi) # rotate
by half a circle drawArc() ctx.closePath()
        

Kind of neat looking – but it obviously didn't turn out quite right.  It rotated around the center and ended up both vertically and horizontally on the opposite side.  This can be fixed with some additional translation...

          startAngle = 1.7 * pi endAngle = .3 * pi drawArc = -> ctx.arc(0, 0,
radius, startAngle, endAngle, false) ctx.beginPath() ctx.translate(-cos(endAngle)
* radius, -sin(endAngle) * radius) drawArc() ctx.rotate(pi) ctx.translate(-cos(endAngle)
* radius * 2, 0) drawArc() ctx.closePath()
        

This time I'm drawing the arc at 0,0 and doing a translate before the first arc, and a rotate and translate before the second arc.  It turns out to look the same the leaf before, but the code gets a bit more muddy.  I prefer the previous implementation if this is what it takes.  Also notice that I've added a few variables to capture the start and end angles – this will be important in just a little bit...

But first, you may have noticed that the height of the leaf, from bottom to top, is some length, but what exact length is not immediately obvious.  It'd be helpful to be able to define the leaf by a given height...

          height = size/2 arcDelta = .2 arcAngles = start: (1.5 + arcDelta) * pi,
end: (.5 - arcDelta) * pi # a little trig to base the leaf's radius on a desired height
radius = height / (sin(arcAngles.end) * 2) ctx.beginPath() ctx.arc( -cos(arcAngles.end)
* radius, -sin(arcAngles.end) * radius, radius, arcAngles.start, arcAngles.end, false)
ctx.rotate(pi) ctx.arc( -cos(arcAngles.start) * radius, -sin(arcAngles.start) * radius,
radius, arcAngles.start, arcAngles.end, false) ctx.closePath()
        

So, to compute the desired radius given for a given height, you can divide that height by the ratio between the center point and the leaf's bottom, sin(endPoint), multiplied by 2 to account for the top half:  radius = height / (sin(arcAngles.end) * 2)

Also note that I'm trying the rotate again, except I'm just repositioning the center point of the second arc instead doing that messy translate.  This allows the leaf to be defined by only one set of start and end angles which get reused in the second arc.

Finally, I've added another variable, arcDelta, to capture the offset between the top and bottom angle.  So, rather than specifying 1.7π and .3π, now we only need .2 which will get added to 1.5π and subtracted from .5π.

Composing

Now to the fun stuff – the process to draw a leaf can now be encapsulated and we can start drawing neat patterns.  Let's make a class for the leaf.

          class Leaf constructor: (height, @fillStyle
= '#fdf6e3', arcDelta = .2) -> @arcAngles = start: (1.5 + arcDelta) * pi, end:
(.5 - arcDelta) * pi @radius = height / (sin(@arcAngles.end) * 2) draw: () -> #
saving now allows the context's state to be restored # when we're done drawing ctx.save()
ctx.beginPath() ctx.arc( -cos(@arcAngles.end) * @radius, -sin(@arcAngles.end) * @radius,
@radius, @arcAngles.start, @arcAngles.end, false) ctx.rotate(pi) ctx.arc( -cos(@arcAngles.start)
* @radius, -sin(@arcAngles.start) * @radius, @radius, @arcAngles.start, @arcAngles.end,
false) ctx.closePath() ctx.fillStyle = @fillStyle ctx.fill() ctx.restore()
        

           var
Leaf; Leaf = (function() { Leaf.name = 'Leaf'; function Leaf(height, fillStyle, arcDelta)
{ this.fillStyle = fillStyle != null ? fillStyle : '#fdf6e3'; if (arcDelta == null)
{ arcDelta = .2; } this.arcAngles = { start: (1.5 + arcDelta) * pi, end: (.5 - arcDelta)
* pi }; this.radius = height / (sin(this.arcAngles.end) * 2); } Leaf.prototype.draw
= function() { ctx.save(); ctx.beginPath(); ctx.arc(-cos(this.arcAngles.end) * this.radius,
-sin(this.arcAngles.end) * this.radius, this.radius, this.arcAngles.start, this.arcAngles.end,
false); ctx.rotate(pi); ctx.arc(-cos(this.arcAngles.start) * this.radius, -sin(this.arcAngles.start)
* this.radius, this.radius, this.arcAngles.start, this.arcAngles.end, false); ctx.closePath();
ctx.fillStyle = this.fillStyle; ctx.fill(); return ctx.restore(); }; return Leaf;
})();
        

I've added the compiled JavaScript for comparison to the right.  This is where CoffeeScript starts to spread its wings.  The class definition is much neater – the prototype functions are taken care of, the this repetitive-keystroke-injury-waiting-to-happen is replaced with @, you've got default values for arguments – and this is just scratching the surface.  So, now that we can easily draw some leaves...

          ctx.translate(size/2, size) #bottom center leaves = [ new Leaf(size, '#c3d5eb')
new Leaf(size/9 * 8, '#648dcf', .25) new Leaf(size/5 * 4, '#12204d', .3) new Leaf(size/2,
'white', .35) ] leaf.draw() for leaf in leaves
        

Now we're cooking with gas!  (badum-ching - I'll be here all week) The next step is to draw the spirograph from the Illustrator tutorial...

          class SpiroLeaves constructor: (leafCount, radius, arcDelta = 1/10) ->
@rotateAngle = (pi*2)/leafCount hsla = (i) -> "hsla(#{i/leafCount*360}, 100%, 50%,
.2)" @leaves = (new Leaf(radius, hsla(i), arcDelta) for i in [leafCount..0]) draw:
(ctx) -> ctx.save() for leaf in @leaves leaf.draw(ctx) ctx.rotate(@rotateAngle)
ctx.restore() ctx.globalCompositeOperation = "lighter" spiroLeaves = new SpiroLeaves(18,
size / 2) spiroLeaves.draw(ctx)
        

A few notes...

• The SpiroLeaves constructor takes...
  • leafCount – which is how many leaves you want to be drawn... it is used to calculate the angle to rotate between each leaf - @rotateAngle = (pi*2)/leafCount
  • radius – which is simply passed as the height for each leaf
  • arcDelta – which how "skinny" or "squat" the leaves will be. Can be values between 0 and .5, with the larger the value, the skinnier.
• The hue of each leaf is calculated this function - hsla = (i) -> "hsla(#{i/leafCount*360}, 100%, 50%, .2)". This produces a gradient hue between 0 and 360, with 100% saturation, 50% lightness, and an alpha value of .2.  Read more here at w3.org.
• Before drawing, the context is set to globalCompositeOperation = "lighter" so that the colors in overlapping leaves will reinforce each other.

Finally – let's do something really cool and animate this.  I'll draw two overlapping copies of the SpiroLeaves slowly rotating in opposite directions.

          spiroLeaves = new SpiroLeaves(18, size) i = 0 drawFrame = -> ctx.clearRect(0,0,size,
size) ctx.save() ctx.globalCompositeOperation = "darker" ctx.translate(size / 2 -
sin(i/200) * size/20, size / 2 - cos(i/200) * size/20) ctx.rotate(i/1000) spiroLeaves.draw(ctx)
ctx.restore() ctx.save() ctx.globalCompositeOperation = "lighter" ctx.translate(size
/ 2 + sin(i/100) * size/10, size / 2 + cos(i/100) * size/10) ctx.rotate(2-i/250) spiroLeaves.draw(ctx)
ctx.restore() i += 1 setInterval drawFrame, 25
        

Nice! I've made a jsfiddle with this code setup – feel free to tinker and make something of your own.  Here's the link.  Also, if you'd like to bring your CPU to its knees, make the canvas full screen.

This is my first foray into both HTM5 Canvas and CoffeeScript and I'm simply sharing what I've learned.  So, please feel free to make any corrections and/or suggestions.

HTML5 Canvas resources: HTML5 Canvas Tutorials, HTML5 Canvas Cheat Sheet

CoffeeScript resources:  CoffeeScript.org, CoffeeScript Cookbook, The Little Book of CoffeeScript

P.S. – I had mentioned that I had already drawn something on the canvas before the leaves.  This would be the grid pattern – here's the code:

          # draws a nice grid on the canvas drawGrid = (ctx, styles) -> line =
(x1,y1,x2,y2) -> ctx.beginPath() ctx.moveTo(x1,y1) ctx.lineTo(x2,y2) ctx.closePath()
ctx.stroke() divideAndStroke = (styles, divisions = 2) -> if (styles.length >
1) divideAndStroke(styles[1..], divisions * 2) ctx.strokeStyle = styles[0] for i in
[0..size] by (size/divisions) line(i,0,i,size) line(0,i,size,i) ctx.save() ctx.lineWidth
= 1; divideAndStroke styles ctx.restore() $ -> # draw all the grids $('canvas').each
-> this.width = size this.height = size ctx = this.getContext '2d' ctx.fillStyle
= '#002b36' ctx.fillRect(0,0,size,size) drawGrid(ctx, ['#657b83','#29434C','#073642','#073642'])
        

I’ve been slowly making my way through the first 100 Project Euler problems while learning F# in an attempt to be more pragmatic - and to try and prevent my grey matter from getting too stale.  After many hours of keyboard-head-banging, I’m now getting to the point where I don’t flail uselessly when beginning to type in some F# code – the pattern matching, automatic generalization and higher-order functions now feel like useful tools rather than strange curiosities.  Since I’ve primarily coded in C# for many years, I’ve been using the book “Real World Functional Programming” by Tomas Petricek as a starting point – it’s been a pretty good read. So, for this post the code will be in F#, but it’ll be secondary to the more general topic of problem solving for puzzle-type scenarios commonly found on Project Euler.

I found this particular problem, #98, a bit more challenging than usual - and kind of fun to work through.  It involves matching anagrams with square numbers using character replacement – here’s the full description:

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt, a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

This is what I’d consider a pretty good puzzle – the elements (a word list and square numbers) are easy enough to grasp, the way they’re related together is unique for this scenario, and an effective solution does not immediately pop into mind.  Well, it didn’t pop into my mind, at least.  So – where to begin?

Many of the problems (at least the ones I’ve solved so far) on Project Euler involve a few common steps to reach a solution:

• Generate a set of input values for the problem – usually this will be a large set of potential values, such as all the prime numbers below 10,000,000, or in this case, 16K of words and a bunch of square numbers.
• Given these inputs, build an algorithm that can test for the solution.
• Add constraints to reduce the size of the input set so that the solution can quickly be found.  On modern hardware, this is usually under 1 second – but anything under a minute is considered kosher.

Input Values

The input values are easy here – they’ve provided the word list, and a sequence of square numbers should be trivial.  First, reading the word list.  Instead of placing the words each on a new line, the file instead contains a single line formatted like:

"A","ABILITY","ABLE","ABOUT","ABOVE","ABSENCE"...

Ok – so it’ll take a little parsing.  No problem.

          let words = System.IO.File.ReadAllLines(@"words.txt") |> Array.collect
(fun line -> line.Split(',')) |> Array.map (fun w -> w.Replace("\"", "").ToLower())
        

This loads the line from the file, splits the words by commas, and removes the quotations… and I threw in making the words lowercase – since I hate having my puzzles constantly shouting at me.  A little aside for the language particulars: the |> is the magical-looking-but-actually-quite-simple pipeline operator – it passes the output from the function on the left to be input for the function on the right. And the fun –> is F# syntax for lambda expressions.  At the end of the pipeline comes a simple array containing the parsed words.

So for the rest of the input - the square numbers.  F# has the means to generate an infinite sequence which can then be sliced and diced to get at the bits that are needed.  The perfect squares can be generated with:

          let allSquares = 


Seq.unfold(fun (square,odd) -> Some(square, (square+odd, odd+2))) (0,1)
        

The square numbers are “unfolded” – that is, each element is calculated based on the result from the previous element, like you’d do with.  Square numbers have a property where they can be generated by as the sum of a list of successive odd numbers. The tuple of (0,1) on the far right is fed in as an initial value, with 0 being the first “square” number and 1 being the first odd number.  At each step of the unfold, the odd number is increased by 2, and the square number is calculated by the adding the previous odd number. So, the (square,odd) tuples being computed will look like:(0,1),(1,3),(4,5),(9,7),(16,9), with only the squares being captured as output.  Works for me!

As with most simple-yet-effective bits of code, this one went through a couple of refinements before nailing it.  The first pass looked like this:

          Seq.unfold(fun i -> Some(i, i + 1)) 0 |> Seq.map (fun i ->
i*i)
        

…where the squares are generated in two steps instead of one. The first bit unfolds all the natural numbers from 0 to infinity (or more likely, maxint), and the second part maps these each by squaring them.  It produces the same result, but is less elegant because it uses more moving pieces.

That’s all the input this problem should require – next, to design the…

Success Algorithm

A useful bit of the Project Euler problem descriptions is that they usually include an example which can be used as a test case for a solution algorithm. Here they’ve provided:

care, race // <- anagrams map to

1296, 9216 // <- squares

…with a replacement dictionary of (c,1),(a,2),(r,9),(e,6).  It’s important to note that the anagrams and squares might be symmetric, where the numbers can be swapped (i.e. (c,9),(a,2),(r,1),(e,6) works as well), but there are cases (such as the final answer) where this doesn’t hold.

To devise an algorithm to test for an answer, the first step is to think it over before doing any typing.  It’s better to have some notion of a strategy than to rush in with the codes.  I struggle with adhering to this – it’s just too easy to think “I’m so good, I’ll just figure it out as I program.”  I’ve found it’s more productive to get away - get a pen and some paper and start sketching ideas, take a walk, etc.  There’ll be plenty of time to work through all the details in code, but it’s best to go in with a plan – a vague or even an incorrect strategy is better than none at all.

For this problem, I started with the idea of comparing each letter of the first word with the first square number, building a replacement dictionary while iterating through them.  If a valid replacement dictionary for the first set is found, it would then be tested against the second word-square-number pair. Writing in algorithm in F# meant I could treat the words as lists and iterate them using a common combination of recursive function calls and pattern matching.

          let rec getReplacementDictionary (sToT, tToS) (source, target) = match
source, target with // have already seen this exact mapping -> skip it | s::ss,
t::tt when Map.containsKey s sToT && (Map.find s sToT) = t -> getReplacementDictionary
(sToT, tToS) (ss, tt) // have a mapping for the source, but it's not the target ->
failure | s::_, _ when Map.containsKey s sToT -> None // have a mapping for the
target, but it's not the source -> failure | _::_, t::_ when Map.containsKey t
tToS -> None // never before seen mapping -> add it | s::ss, t::tt -> getReplacementDictionary
(Map.add s t sToT, Map.add t s tToS) (ss, tt) // end of the line - a successful translation!
| [], [] -> Some(sToT, tToS) | _ -> raise(System.ArgumentException("words not
equal length")) 
        

I’ve named the variables “source” and “target” – they’ll get passed the word and the number, respectively.  They are “matched” against conditions using the patterns seen on each line following the pipe “|” character.  The easiest of these to grasp is near the end – “| [], [] –> Some(sToT, tToS)“ which matches two empty lists, indicating that the words have been completely checked and that there is a valid dictionary.  For the dictionary itself, I found that it was necessary to keep tabs on both the source-to-target values (sToT) as well as the target-to-source (tToS) values.  A bi-directional mapping structure would be ideal, but it would have been more effort to construct that than to fudge it with an extra variable.  If there is a better way to handle this, I’d be interested to hear it… 

At any rate, the result of this function will either be a failure - with the None value - or with the completed dictionary(s) – the Some(sToT, tToS).  Testing it against “care” and “1296” produces the expect result:

          > getReplacementDictionary (Map.empty, Map.empty) ("care" |>
List.ofSeq, "1296" |> List.ofSeq);; val it : (Map<char,char> * Map<char,char>)
option = Some (map [('a', '2'); ('c', '1'); ('e', '6'); ('r', '9')], map [('1', 'c');
('2', 'a'); ('6', 'e'); ('9', 'r')])
        

…and changing a digit in the number to one of the already mapped digits results (I’m using 1292 which repeats the 2) in a failure:

          > getReplacementDictionary (Map.empty, Map.empty) ("care" |>
List.ofSeq, "1292" |> List.ofSeq);; val it : (Map<char,char> * Map<char,char>)
option = None
        

To test this dictionary against the second group, “race” and “9216”, the original function may be reused because all of the character mappings will have been seen in the first group and they will simply be verified via the first pattern. 

          let dict = getReplacementDictionary (Map.empty, Map.empty) ("care"
|> List.ofSeq, "1296" |> List.ofSeq) getReplacementDictionary dict.Value ("race"
|> List.ofSeq, "9216" |> List.ofSeq);; val dict : (Map<char,char> * Map<char,char>)
option = Some (map [('a', '2'); ('c', '1'); ('e', '6'); ('r', '9')], map [('1', 'c');
('2', 'a'); ('6', 'e'); ('9', 'r')])
        

This is making an assumption that the input words are anagrams of each other – this is an OK assumption to make for now.  Indeed, it can be even assumed that the input data may be filtered for anagrams – I’ll cover that in the next section.

I noticed that this could be further streamlined by simply appending the words and the numbers together, since that is more-or-less what is occurring when calling it twice.  And in that case, the function no longer needs to return the mapping dictionary – just a simple boolean indicating if a valid dictionary can be applied to the input.   So, the function can be modified as follows, making sure to rename it:

          let rec hasReplacementDictionary (sToT, tToS) (source, target) = match
source, target with | s::ss, t::tt when Map.containsKey s sToT && (Map.find
s sToT) = t -> hasReplacementDictionary (sToT, tToS) (ss, tt) | s::_, _ when Map.containsKey
s sToT -> false | _::_, t::_ when Map.containsKey t tToS -> false | s::ss, t::tt
-> hasReplacementDictionary (Map.add s t sToT, Map.add t s tToS) (ss, tt) | [],
[] -> true | _ -> raise(System.ArgumentException("words not equal length"))
        

and run a test:

          > let los = List.ofSeq let s = List.append (List.ofSeq "care") (List.ofSeq
"race") let t = List.append (List.ofSeq "1296") (List.ofSeq "9216");; > hasReplacementDictionary
(Map.empty, Map.empty) (s, t);; val it : bool = true
        

Success!  Now, having all the necessary input and a valid algorithm, it would be possible to test every possibly combination of inputs to find the correct answer. 

Input Constraints

Project Euler problems are usually infeasible to answer without a computer.  (There’s sometimes really smart math folks in the forums who will find clever ways around this, but for the rest of us…) 

How many combinations of the input data could there be, anyway?  There’s a total of 1,786 words ranging in length from 1 to 14 characters, which leads to ~3.2 million combinations of just the words.  My script to calculate the count of all square numbers under 14 digits ran out of memory, but it turns out only up to 9 digit squares are needed.  There are 31,623 of those.  The number of combinations would be 1,786² × 31,623² ≈ 3.2E15.  That’s several thousand billion – got to keep filtering or it’ll take a year!

The next obvious step is to pair up the anagrams and discard the rest of the words.  A simple way to do this is to alphabetically sort each character in each word and group together the ones that are exactly the same.  For example “care” and “race” will both map to “acer” – neat trick!  Here’s the code

          let groupAnagrams ws = ws // sort by characters in each string and then
glue them back together |> Seq.groupBy (Array.ofSeq >> Array.sort >>
(fun cs -> new string(cs))) // take only the anagrams - where the number of words
is greater than one |> Seq.map snd |> Seq.filter (Seq.length >> ((<)
1))
        

This is a great first step – but it’s not quite enough.  I want all the pairs of anagrams and there are cases where there are more than 2 words that all have the same letters.  For example, “post”, “spot” and “stop” will all group together.  What I need is combinations of all the pairs – so I’ll end up with (“post”, “spot”), (“spot”, stop”), and (“post”, “stop”).  Fortunately, I had already borrowed/stolen a generic combination function that Tomas had posted on Stack Overflow.

          let combinations size set = let rec combinations acc size set = seq { match
size, set with | n, x::xs -> if n > 0 then yield! combinations (x::acc) (n -
1) xs if n >= 0 then yield! combinations acc n xs | 0, [] -> yield acc | _,
[] -> () } combinations [] size (set |> List.ofSeq)
        

Now I can run all the whole list of anagram groups through the combinations algorithm and produce a single list of anagram pairs:

          let pairwiseTuples = Seq.collect ( combinations 2 >> Seq.map (fun
l -> l.[0], l.[1]) ) 
        

And indeed – it does its job:

[|("cat", "act"); ... ("race", "care");
  ...
  ("spot", "post"); ("stop", "post"); ("stop", "spot"); 
  ...|]

Running the words through this results in 44 pairs of anagrams with the lengthiest pair being 9 letters long ("reduction", "introduce"). This is starting to sound reasonable to process – and it’s where I got stuck for a bit.  Looping through all of the squares for each pair still seems computationally prohibitive. 

I walked away from it for the day and in the shower the next morning – “duh, the square numbers can be bundled up as anagrams as well!"  These are the ah-ha moments that make it all worthwhile.  A few examples – (“1024”, “2401”), (“14400”, “10404”).  There turned out to still be quite a few for the larger digit counts (for example, there are 70052 anagram pairs for square numbers with 9 digits), but since there are so few words in the list that are above 5 characters long, it turned out to be OK.

All was left was to write a few more lines to run all the equal-length anagram pairs through the success function and find the result.  It ran in about a second on my hardware, so that is an acceptable solution in my mind.  There are undoubtedly numerous additional optimizations that could be applied – and perhaps even a way to word it out on paper (I doubt it for this one) – so I’d be eager to hear any comments.

In Jon Galloway’sSplitting Camel Case with RegEx blog post, he introduced a simple regular expression replacement which can split “ThisIsInPascalCase” into “This Is In Pascal Case”.  Here’s the original code:

          output = System.Text.RegularExpressions.Regex.Replace( input, "([A-Z])",
" $1", System.Text.RegularExpressions.RegexOptions.Compiled).Trim(); 
        

Simple and effective.  Matches any capital letters and inserts a space before them.  But there’s room for improvement.  First, the call to String.Trim() to remove any spaces potentially added if the first letter is uppercase – this can be handled with a “Match if prefix is absent” group containing the “beginning of line” character ^.  This prevents any matches from occurring on the first character, which eliminates the need for the String.Trim() call.  The formal name for this grouping construct is “Zero-width negative lookbehind assertion”, but just think of it as “if you see what’s in here, don’t match the next thing”.

           (?<!^)([A-Z])
        

Next - there’s a potential issue with how acronyms get handled with this.  Given this fictional book title: “WCFForNoobs” – the split will occur on each uppercase letter resulting in “W C F For Noobs”.  The fix is simple, though – require that uppercase letters be followed by a lowercase:

           (?<!^)([A-Z][a-z]) 
        

…Now it’ll result in “WCF For Noobs” (aren’t we all!).  But now it won’t add a space before the acronym – for “LearnWCFInSixEasyMonths”, the result will be “LearnWCF In Six Easy Months”.  No problem – add an alternate match for a lowercase letter coming before the uppercase letter.  The replace pattern makes this more difficult – we don’t want the space to go before the lowercase letter, we want it between the lowercase and the first capital letter of the acronym.  RegEx can handle this with another lookbehind match group – “Match prefix but exclude it” - (?<=).  This allows the match to occur on the lowercase-uppercase pair, but only the uppercase portion will get matched, so when it comes time to run the replacement, the space will get inserted between the two letters.  By itself, that’ll look like this:

           ((?<=[a-z])[A-Z]) 
        

Great!  But this needs to be combined with previous expression.  Easy accomplished with an either/or match using the vertical bar “or” construct:

           (?<!^)([A-Z][a-z]|(?<=[a-z])[A-Z]) 
        

The example “LearnWCFInSixEasyMonths” will now be split into “Learn WCF In Six Easy Months”.  These same techniques can be used for additional splits – perhaps on numbers or underscores.  More generally, lookbehind and lookahead are great tools to have in your RegEx toolbelt.

With tongue implementation injected dynamically into cheek object …

ReSharper is my shepherd,
I shall not want;
He lets me apply quick refactors.
He leads me to errors before compile;
He cleans up my code.
He navigates me in paths of inheritance
for each namespace.

Even though I strive to remove cruft
of the brownfield app,
I fear no error;
for You are in my IDE;
Your red and Your green unit tests, they comfort me.

Surely correctness and maintainability shall follow me
all the deployments of my app;
and I shall dwell favorably in the thoughts of my
Users forever.

Sum(23)

This last week I gave two presentations at CodeStock 2010.  Thanks to everyone attended my sessions, hope you got something out of them, and thanks to the CodeStock organizers for all your hard work.  Here’s some content from the presentations:

Digging around in some code circa 6 months ago I discovered a method that I had scrounged from the web and, in my apparent haste at the time, had not build any unit tests.  It was less than 20 lines of code doing some simple array manipulation – and it was from a pretty decent site, so it seemed pretty safe.  It’s the weekend so I thought, hey, time to plug that gap!  I started with some simple cases and soon realized that one of the execution paths was just … well, plain wrong.

Luckily, that behavior wasn’t being used anywhere in my project (yet!), but still, it was essentially a land mine waiting for someone to trip it.  My first reaction was “shame on them for posting that without testing it!”  Of course, this code didn’t end up in my project because of the author.  It was I who blindly accepted and given it the “it’s from the internet!”-stamp-of-approval.

Lessons learned today:

• Trust is earned, not given.
• Source code becomes trusted by-way-of thorough unit and functional testing.
• Do not trust untested code from the internet.
• Do not trust untested code from your own keyboard even more so – at least on the internet it’s likely that someone else has reviewed it.

I’ve written the author a friendly note with a simple fix – it’s better to diffuse that bomb than let it get somebody else!

I’m feeling a bit guilty about some code I wrote:

          using (new OperationTimer("MyOperation", this)) { // ... complete operation
}
        

This innocent looking C# snippet is hiding a tricky secret - the using statement is being misused (no pun intended).  The documentation defines the intended usage clearly:

using Statement

Defines a scope, outside of which an object or objects will be disposed.

The problem?  The notion of “object disposal” is being hijacked!  In your garden variety IDisposable implementation, you’d be dealing with an external resource that needs to be released before the object can be removed from memory.  Instead, I’m using it to time a block of code like so:

          class OperationTimer : IDisposable { private readonly string _operationName;
private readonly ITimable _obj; private readonly Stopwatch _stopwatch; public OperationTimer(string
operationName, ITimable obj) { _operationName = operationName; _obj = obj; _stopwatch
= new Stopwatch(); _stopwatch.Start(); } public void Dispose() { _stopwatch.Stop();
_obj.OnOperationCompleted(_operationName, _stopwatch.Elapsed); } }
        

The constructor starts a timer and the Dispose() method stops it and reports the elapsed time.  (aside: if you’re interested in how I’m using the timer, check out my previous article Simplified Performance Counters) There are certainly other ways to accomplish this same behavior, but they lack the elegance of a neatly scoped code block.  It’s arguably an acceptable way to repurpose the language.  In fact, the ASP.NET MVC authors saw fit to use it in a similar fashion with the BeginForm helper.  The only “resource” it disposes of is to render a closing </form> tag.

My question is: When does repurposing language constructs turn from “acceptable language use” to a “dirty trick”, or worse, “illegible line noise”?

It seems like a slippery slope.  One instance that I don’t care for is controlling execution flow by-way-of logical operator precedence in most C-like languages:

          expression1 && expression2 || expression3
        

Which is equivalent to:

          if (expression1) expression2 else expression3
        

This takes advantage of the order of evaluation in a logical statement – it is assumed (correctly) that expression2 will never be evaluated if expression1 is evaluated as false, and instead, expression3 will get to run.  Likewise, if the first two evaluate to true, the truth value is known for the statement and expression3 is never evaluated. This is clearly not the intended usage which the language designers had in mind, but it works, and it saves any keywords from being written.

Some truly beautiful code has been written by way of hijacking the language.  For instance, here’s a program that will calculate the value of pi using an ascii circle.  Truly neat - but also completely useless from a software development standpoint.

What do you think?  Should I just get over my guilt about repurposing IDisposable?  Or, should I be true to the original intent of the language and find another way?

I just posted an article on CodeProject about a generalized code block which can be used in a common scenario for simple performance benchmarking.  Check out "Simplified Performance Counters for Timed Operations" here…