Julian's posterous

PCPlus 286: Cutting cloth

Come October 2009, it was time to write about some algorithm I knew nothing about. And so it was that I delved into two-dimensional bin packing; prompted by a reader question about how to cut cloth efficiently and aiming for the smallest waste possible.

It turns out that this is a fascinating area of research that has applications all over the place (a variant is the memory heap problem, or how to allocate memory such that you minimize the amount of wasted memory in between the allocated memory blocks). It turns out that the problem, like other bin-packing conundrums, is NP-complete, that is, there is no optimal solution that runs in polynomial time. So, algorithms to solve the problem tend to be optimization or goal-seeking solutions, where you “fiddle” with a solution to look for a better packing.

To make it easier (!) to analyze the 2D bin-packing problem, we assume that the pieces being cut from the cloth (or packed into the container) are rectangles.

The first algorithm I discuss is Sleator’s algorithm. This is important for (a) appearing in the the first paper that discusses the problem, and (b) being amenable to a bit of mathematical analysis that concludes that Sleator’s packing is within 2.5 times the optimal packing (what you might call God’s algorithm for bin-packing).

The next one is Jacob’s algorithm, which is a fun little algorithm because it works a bit like Tetris, at least a handicapped Tetris where you can’t rotate the pieces. You start at the upper right with a new rectangle, “slide” it down until you can’t go any further, slide it left until you can’t go any further, slide it down, left, etc, until the rectangle cannot be moved any further down or left. This was the first of the “Bottom-left” algorithms and Lui and Teng provided another variant that tried a slightly different strategy: prefer dropping down to moving left.

After those initial solutions, newer algorithms evolved into patented systems.

This article first appeared in issue 286, October 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

Now playing:
Thievery Corporation - Heaven's Gonna Burn Your Eyes
(from The Richest Man in Babylon)

PCPlus 285: Calculating Pi

With the September 2009 article, I decided to present a discussion of how the constant π (pi) was calculated in antiquity and over the ages, together with a layman’s rehash of an article I’d written a while ago on how to write a program to calculate it. The nice thing about writing code to calculate π is that it shows off Machin’s formula and writing a minimal “big number” library to perform the calculation.

I did come up with a fascinating fact to round off the article: it took 33 hours for a Ferranti Pegasus 1 computer to calculate 7,480 digits of π in 1957. Not only is this interesting to me because I was born in 1957, but, also because when I first started going out with my first wife in the very early 80s, she was the personal assistant to Sebastian de Ferranti, then Chairman of Ferranti Ltd. Ferranti Ltd no longer exists (it went into receivership in 1993 after a disastrous and fraudulent merger), but because of this association, and the fact that for a while Ferranti was the computer company in the UK, I have a special feeling for the name. (I even recall us being invited to the wedding of one of de Ferranti’s children: a huge do somewhere in Surrey, with the newly-weds being whisked off by helicopter.)

This article first appeared in issue 285, September 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

PCPlus 284: Solve computational geometry problems

For some reason, for August 2009’s article, I decided to take a bite out of computational geometry; what can only be described as a ruddy large subject. I mean, it’s huge. And it’s mathematical, to boot. I must have been delusional. Anyway, I touched on three fairly simple and well-known algorithms, well-known because they date from the very early days of computer science.

The first is the hoary chestnut: determining whether a point is inside a given polygon or not. This could be used to determine if a mouse click was inside a complex polygon on the screen (a click in a rectangle, like a button, say, is really easy to determine, provided the rectangle is oriented along the axes). The traditional answer is to draw a line off to infinity form the point, and then count the number of sides it intersects: odd, the point is inside; even the point is outside. This simple algorithm unfortunately leads to other problems, including how to tell if two lines drawn on the plane intersect or not, so I described a more modern version where you draw a horizontal line through the point and then cycle round the vertices of the polygon, checking to see if the sides thus described have their start/end points either side of the horizontal line. To do this, you just need to check the y coordinates. A little bit of logic later (an even number of intersections implies “inside”) and you have the answer.

The second is the convex hull of a set of points using the traditional method and a newer, faster one called Graham’s Scan (albeit from 1972).

The third is the “closest pair of points” problem. You’re given a set of points on the plane and you have to discover the pair that is closest together of all possible pairs. I discuss the brute-force method (a O(n²) solution) and then a more elegant and faster divide-and-conquer algorithm (essentially O(n.log n)).

This article first appeared in issue 284, August 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

My Volvo 1800S

I’ve been a bit remiss in posting these photos, but a friend reminded me yesterday that I’d promised to show off my “new” car.

Way back when I lived in England I owned a red 1969 Volvo 1800S, a rare B20B version (that is, a 2000cc, non-fuel-injected engine). Only 1693 were ever produced since Volvo brought out the 1800E pretty quickly with a fuel injection system added (E stands for einspritzung, the German for fuel injection, since the system used in the Volvos was produced by Bosch).

That car was nice-looking enough that it was the October picture in the Classic Cars calendar of 1991. It was a fun day I had with the photographer, driving all over Rochester in Kent, trying to get the perfect picture. The one published was taken outside Eastgate House in Rochester High Street, although we drove up to the castle and down to the Medway as well. I’ll post a photo of that calendar page later.

Once I moved to the States in 1993, I had to sell it. I couldn’t afford the shipping to Colorado and the car needed to be driven and looked after otherwise it would just have rotted away. So in 1995 I finally found a buyer and sold it and silently regretted it.

Anyway, I’ve been looking for a reasonably-priced red 1800S for the past year or so, one that has already been restored. I finally found one in California in July, a 1964 version with a B18B engine, and bought it one of the weeks I was in the DevExpress offices in Glendale. I had it shipped to Colorado (no way was I going to drive an unknown car 1000 miles home, especially one that had only been driven some 200 miles in the last 5 years). This was it on the Friday it was delivered:

The very next Monday I took it to Concours Cars in Old Colorado City for them to thoroughly check it over and retune it for the altitude. And it was a good job I did too: the heater core had a leak and the car was losing coolant like there was no tomorrow. (Boy was I glad I hadn’t decided to drive it back from California.)

In the end, they kept it for nearly a month fixing various systems and bits and pieces and replacing oil, fluids, belts, etc. I’m going to guess that whoever restored it ran out of money after doing the bodywork and rebuilding the engine since there were quite a few minor problems, apart from the heater core leak. Egregious examples: the headlights weren’t connected to the switch; the cable for the flap for the defroster was missing (besides which the flap itself was broken); there was no windscreen washer system at all apart from the nozzles. They also decided that the carburetor needed to be replaced (whatever fuel additive the previous owner had used had rotted the jets while it was in storage). There’s still a few little things to fix (which they’ll be doing over the winter), but at least they made sure the car was drivable and legal to drive.

Here’s the front, showing the cowhorn bumpers and the aluminum “egg-crate” grill (and the crappy “VOLVO” plate that is screwed on with some security screws that will have to be drilled out):

And here’s the rear, showing that I still need to register it in Colorado. The plate reads “64SAINT”, because it’s a 1964 car and The Saint, played by Roger Moore in the TV series, used to drive one in the 60s. I might go for the same plate here, if it’s available.

(You can see my set of pictures of the car on Flickr. I’ll keep updating it as I take more photos.)

Let me just say that the car is just awesome. It’s great fun to drive around town, even without power steering (the steering wheel is huge though and my upper body strength is improving!). Now I know how the automatic choke works I can even start it from cold without cranking and cranking the starter. It gets a bit noisy on the interstate (besides which I don’t really go above 60mph in it until the rebuilt engine has had a chance to settle down) and turning the air conditioning on just makes it noisier still. And the wheels are too gaudy for my taste (going to go for some Panasports later). But... overall, it’s just brilliant.

Rubik’s Cube iPhone app

A couple of months ago I finished an article for PCPlus about algorithms for solving Rubik’s Cube. It’ll appear in issue 298 in September 2010.

As part of my research I came across this article and video on Wired about an iPhone app that helped you solve it and, more than that, solve it in a remarkably small number of moves (usually 20 or fewer) using Kociemba’s algorithm. The free app (called CubeCheater) was written by Eric Faller. Unfortunately it seems he didn’t request permission from Seven Towns (the current owners of the license to market Rubik’s Cube worldwide) and had to remove the app. (Aside: my editor at PCPlus, Alex Cox, obtained permission from them for me to write about Rubik’s Cube for the magazine before I ever put electronic pen to Microsoft Word paper.)

Bummer. I would have liked to try the app and written about it as well. But, no go, so I submitted the article and forgot about it.

Imagine my surprise when this weekend, I was perusing the App Store when I came across the official Rubik’s Cube iPhone app. Further imagine my surprise when I saw that said app had exactly the same solver function as CubeCheater. Not only that, but the same interface.

(Compare this to the interface shown in the video taken 18 months ago.) Interesting, no?

Anyway, I bought it ($4.99) to try it out. The only part of the app I was interested in was the Solver function where you input the state of a mixed-up cube and it solves it for you in as few moves as it can.

There is a cool feature where you input the faces using the camera rather than painting each cubelet with colors from the palette. You take a snapshot of the cube and the software works out the face’s grid and the colors in each cubelet.

For me and my particular cube this functionality is a complete and utter failure. The edge detection is pretty bad to begin with (hint: don’t try and fill the camera screen with the face like the image below, but make it occupy as much room as the image of the face above), but the color recognition just sucks. Here’s my white face (so called because it’s named after the center cubelet):

And here’s what the app thought it was:

There’s another problem which the app doesn’t address. For some unknown reason — perhaps because my cube is so old (I purchased it in 1979 before Ideal Toys got the original license to market the puzzle worldwide in 1980) — my cube center cubelets don’t follow the current standard positioning. I have red on the opposite side to white, not yellow. In fact, yellow and red are reversed on my cube, so, even if the camera input method worked, I’d have to fiddle with the colors anyway (wherever the app talks yellow, I have to think red, and vice versa).

OK, so given that for my physical cube I have to remember to switch yellow and red, does it work? Does it calculate a solution with a small number of moves? The answer is yes. It’s quite magical if you look at the cube after each move and see the colors slowly coming together.

I don’t particularly want to rate the app officially (after all, I haven’t tried the other parts of the app: solving a virtual cube on the screen with flicks of the finger, or the tutorial section), but I will admit to being very disappointed in the camera interface. Unlike this Sudoku Grab app, the AI in the Rubik’s Cube iPhone app is not that good at all.

PCPlus 283: Learning the ropes

For July 2009, I managed to snuff out something about ropes, a kind of heavier programming type than string. Apart from the pun/joke, it was an interesting article to research. I have no recollection any more about how I came across the rope type; presumably it was through a late night surfing session, fueled with some microbrew.

Ropes are like strings in that they store text, but unlike strings in that the bytes making up the text are no longer contiguous in memory. A rope will split up the text into nodes and build up a tree with them. The original text can be recovered by reading the nodes in an in-order traversal.

Why would anyone do such a thing? Well it’s great for building up a string through lots of insertions/deletions — in effect it’s the same performance argument as inserting into/deleting from an array versus a linked list — and it’s good for really long strings. The final benefit is all about heap memory usage: long strings (or any large allocations) in run-times like .NET tend to stick around after disposal since the garbage collector is tuned more to small allocations rather than large ones.

Of course, these benefits come at a cost: for smaller pieces of text, the effort in manipulating them (reading the nth character, copying them, etc) tends to have high overhead, both in terms of memory and in terms of performance. So, not for every situation, by all means.

I couldn’t find a reference implementation of ropes in C# or .NET, but there is one for Java as part of this discussion here. Personally speaking, I’d have to say that the StringBuilder class in .NET would suffice in many scenarios and the effort of creating an implementation of a rope class probably not worth the effort.

This article first appeared in issue 283, July 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

Counting knuckles for the days in each month

Just to show you that algorithms can come from the most bizarre places...

At lunchtime I was flipping through the Oxford Dictionary of Nursery Rhymes (don't ask), when I came across the nursery rhyme -- or, more accurately, the mnemonic -- that describes the numbers of days in each month:

Thirty days hath September,
April, June, and November;
All the rest have thirty-one,
Excepting February alone,
And that has twenty-eight days clear
And twenty-nine in each leap year.

The entry went on to talk about the derivation of this particular mnemonic, and quoted a remarkable French ditty from the 13th century which might be the ancestor of the rhyme. The last sentence of the entry caught my eye though: "Another juvenile way of discovering the number of days is along the knuckles of the hand." It gave no explanation apart from that, but I had never heard of this method or algorithm before. So I did some research.

You might already know this, but it's a fun one. Form a fist with your left hand and position it so you can see the knuckles easily. Using the index finger of your right hand and starting at the leftmost knuckle, tap the knuckles and the dips between the knuckles as you recite the month names: January, February, March, etc. When you get to July and the last knuckle, start over from the leftmost knuckle again with August. The months that are on the knuckles have 31 days (they're 'taller'). The months in the dips have 30 days (they're 'shorter'), and you just have to remember that February actually has 28/29 days.

By the way, the reason for February having this weird arrangement, and not, say, December, is that the Romans started their year with March and so February was at the end of their year. (Hence September, October, November, and December being derived from the Latin for seventh, eighth, ninth, and tenth.) It was easier to add or take away days from the last month, and indeed this is what Augustus did to August: he ordained that August should have 31 days, not 30, and took it away from February. August was "his" month, you see, and it couldn't be shorter than Julius Caesar's month, July. Thank heavens he didn't make it 32 days in length instead to be one better.

Anyway, there you are: your algorithm for the day.

Testing Writerous

Scott Lovegrove (@scottisafool on Twitter) is a Windows Live Writer fan and he's been working on a plug-in for it called Writerous that will publish a blog post to Posterous. He's got it ready for beta, and since I also am a Live Writer fan and have a blog on Posterous, I begged him for a spot on his beta team. Several used fivers changed hands, and I'm in. Since Posterous requires you to email a post to get it published, I'm interested to see how Writerous gets around it.

This is my first post using this new plug-in, and so I'd better check a few things...

First, a gratuitous photo of fields in Muker, North Yorkshire, this June:

And now some gratuitous C# code using my own personal code plug-in for WLW. This'll make the whole system sweat:

private void AddCalendarBody(StringBuilder sb) {
      sb.AppendLine("<tbody>");

      // a month calendar has a maximum of 6 rows, 42 cells
      string[] days = new string[42];

      int firstEntry = (int)new DateTime(year, month, 1).DayOfWeek;
      int lastDay = DateTime.DaysInMonth(year, month);
      int day = 1;
      for (int i = firstEntry; i < firstEntry + lastDay; i++) {
        string dayLink = OnGenerateDayLink(day);
        if (string.IsNullOrEmpty(dayLink))
          dayLink = DayNumbers[day];
        days[i] = dayLink;
        day++;
      }

      // there will always be at least 4 rows
      int cdn = 0;
      for (int i = 0; i < 4; i++) {
        cdn = AddCalendarRow(sb, days, cdn);
      }
      // rows 5 and 6 may or may not be there
      if (!string.IsNullOrEmpty(days[cdn])) {
        cdn = AddCalendarRow(sb, days, cdn);
        if (!string.IsNullOrEmpty(days[cdn])) {
          cdn = AddCalendarRow(sb, days, cdn);
        }
      }

      sb.AppendLine("</tbody>");
    }

I shall also add a category (posterous) and a couple of tags (writerous, plug-in). We'll see what happens to them. OK, ready? Here goes... <clicks Publish>

Entrenched developers

Something I've been pondering on given a couple of articles I read recently: I find I dislike (and have done for a while) developers who get entrenched in what they know and thereby deem everything else as being wrong. It's the worst kind of rut. They become immune to new ideas, new developments, new methodologies.

The first article was a paper published in the Communications of the ACM called A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World by Bessey et al that talks about how Coverity built and marketed their static code analysis tool. The whole paper is fascinating to read, but it's completely hilarious when the authors talk about the discussions they had with developers regarding the bugs they found. Here's a sample:

For this use-after-free

[Developer said] "No, that's OK; there is no malloc call between the free and use."

As a final example, a buffer overflow checker flagged a bunch of errors of the form

[Developer said] "No, ANSI lets you write 1 past the end of the array." After heated argument, the programmer said, "We'll have to agree to disagree."

The second article is by Ted Neward, Don't Fear the dynamic/VARIANT/Reaper..., as a robust counter-argument to a commenter on one of Scott Hanselman's blog posts. Here we have Rob dissing dynamic in C# 4 (and, in passing, the Variant type of yore in VB and anybody who would dare to use them). A better example of developer entrenchment I have yet to see, complete with all the carefully chosen adjectives: horrible, ridiculous, loosey-goosey, etc. The kicker is the final paragraph:

I'm just saying, it's a shame that popular "nerd celebrities" like you (and I mean zero offense by that!) - endorse all this loosey-goosey typing. I say that becuase [sic] I've never seen a single case where weak typing or late binding: A) made a design better or B) where it didn't make the component or application worse, because it was a looser design.

How to survive on three passwords

Some time ago, I read in some issue of Women's Health, a magazine my wife subscribes to, that you can survive in the modern always-connected online world on just three passwords. One password for your financial institutions, one password for the less important sites (say, your social sites, or your shopping sites), and one password for everything which you don't consider important or particularly care about or is essence a one off.

Bloody nonsense, was how I put it to myself at the time and took the mag for recycling.

Incredible bloody nonsense, is how I put it now. One reason? Well, you may have heard that Twitter had some issues today. They sent out password reset emails to a bunch of users due to some anomalous behavior with their accounts, The reason? Well, it seems that these users had been using the same password on some compromised sites as they had on Twitter. Bad guys do some harvesting of userid/password combinations on the compromised sites, try them out on Twitter (and I dare say on other sites too), and make hay with those logins that work. Holy crap.

And on top of all that, about a month ago, an interview with a Facebook employee was published about the "master" password that was (is still?) used internally to provide full permissions to anyone's Facebook page and user details. Think about it: a rogue employee who could harvest logins from the company they work for, resign, and then use those logins willy-nilly.

Look, it's not difficult. Use a good password database program. There are free ones out there (Password Safe being by Bruce Schneier, the crypto guru), or you can purchase them. I use one called SplashID, mainly because you can sync the database between an app on your PC and one on your iPhone. There are very few sites I remember my password to any more, really only my banks, my network logins, and my PCs because I use them every day. These password programs even come with password generators to avoid having to use ordinary words (a dictionary attack, even with 1337 character substitutions, will discover a single word passwords in less than half a second). The answer to the question posed by the post title should be "it can't be done, not without exposing yourself to some possible bad things happening". You should have a unique password for each site.

No excuse.