• The solution is one word.
• Post a comment with your answer. I will moderate comments so incorrect solutions will not appear.
• Feel free to put a link to your profile or contact information in the comment with your solution, so people that are impressed with your puzzle skillz can find you.
• Don’t submit more than one solution per day or you will be disqualified.
• If I get more than one solution within a few days, I will post them all.
• After a solution is posted, comments will be closed.

Okay. Now what?

As far as I can tell, this protest crystallized around anger directed at the people who got away with stealing billions from the rest of us. Lamenting the past is not the organizing principle for a political movement. This is a candlelight vigil for our economy.

What do we want?

If you think that getting mad as hell is all it takes to effect change, you need to go back and finish watching Network. Anger isn’t enough. We saw the same thing during the Mastercard hack in Dec. 2010. What did that achieve? Nothing. They had no demands and weren’t asking the public to help. If you don’t have a clear goal you’re not a protester, you’re a vandal. A protest that can effect change needs to have a stated, achievable goal, and a clear call to action.

A clear goal gives a protest a finish line, and it makes the opposition responsible for the costs. The message of a protest shouldn’t be, “We’re going to destroy your business,” but rather, “You can stop this by making a simple change.” A protest without a goal is just a public party, and the opposition has no choice but to wait it out.

At least they’re doing something?

Sure, maybe it’s not well organized, but at least they’re not just sitting on their butts doing nothing, right? Really? That’s the rock the vote argument, that every eligible person should vote regardless of how well they understand the issues. Just be heard; it doesn’t matter what you say.

This protest is going to be completely ineffective. This isn’t elementary school, there are no points for participation. This is going to demoralize people that might have participated in an effective civil action in the future. Worthless protests are a pressure release valve to prevent effective civil disobedience.

Don’t just do anything. Save your energy until you have a clear goal, and a real action that will put pressure on your opposition. Without those things you aren’t holding a protest. You’re just throwing a party.

The Graham scan algorithm finds the convex hull of a set of planar points in three steps. First, we find the lower-left point in the set (call it P). Second, we sort the set based on the angle each point makes with P and the x-axis. Third, we go through the sorted list and keep each point which makes a “left turn.”

Data Types

Even before we start, there are some obvious types we need. We’ll need a type to store points. This could just be a tuple, but I think the code will be easier to understand if the point type has accessors. I’ll define Point as

I parameterized the number type, so our algorithm can be as general as possible. I think we’ll want a type to represent the result of the turn calculation too, so define a turn data type:

Since I’m redefining Left and Right here, I have to hide Either with import Prelude hiding (Either(..)).

Stubs

I want to start capturing what I know about the Graham scan function in code. First, it will take a set of points and return the points of the convex hull, so

Next, the algorithm doesn’t work right if there are fewer than three points, so it will generate an error in that case. There are many ways to handle errors in Haskell. Some common methods include putting the function in the Error monad, returning an Either or Maybe, or returning an empty list. I’ll explore other methods in future articles, but since this function is for experimentation I’m going to just raise an error. I’m not even going to bother with a detailed error report, so the function will start like this.

Now that I know we have valid input, I can get to the meat of the algorithm. First we find the lower left point and sort the point list with it. I’m not sure how to find the lower left point, so I’ll just defer that to a function called findFirstPoint. I’ll use the functions compare and on with a new function angle to create a function that will compare points by their angle. This new comparator is handed to sortBy to sort the list. For now, I set findFirstPoint and angle to undefined so the code will compile. Compile early and often; it helps to keep mistakes from compounding and mutating.

The third step in the algorithm is a bit tricky. We need to look at the next three points in the set and decide whether or not to keep the second point, and the last two points have to be tested along with the first point. Since our input list is not circular, there has to be special handling for the end of the list.

Isn’t that lovely? Haskell is so expressive, the code basically reads like the English description: “Take the next three points in the list, and if they make a left turn keep the middle point. If there are only two points left, tack on the first point.” All that remains is to start the list with the first point and append the rest of the hull. Here is the complete body of the function.

Support

Now to define the helper functions I stubbed out before. The angle function is supposed to calculate the angle between ba and the x-axis, but it’s really calculating the cosine of that angle. Don’t tell anybody.

Now the compiler says that the type parameter in our Point has to be in the Floating class for sqrt. Add that to the type declaration of grahamScan.

The function turn is also simple. If the cross product of the two line segments is greater than zero then it is a left turn, while less than zero is a right turn. Equal to zero is colinear, which can go either way depending on what you want from your convex hull. I report ‘em all and let the caller sort it out.

I used compare here so I could use case instead of nested if statements, or a function with guards. I don’t know what the performance differences are, I just think the code is cleaner like this.

Since this function compares the values of the point coordinates, we’ll need to add the Ord class to the Point parameter. That goes on grahamScan, which now reads

The last function, firstPoint, is a little tricky. You could define it using two passes, like this:

However, I chose to do it in one pass by moving points from the input list to an output list. The lower-left point at each step is held back and prepended to the output at the end.

And that’s it for a working implementation. I also added a convenience function for converting tuples to Points: point = uncurry Point.

Refinement

Now we can test this out in ghci:

Uh oh, there’s a bug. The convex hull in the last test should have included (1, 1) but not (0.5, 0.5). The problem is that they are colinear with the lowest point (0, 0), so they have the same angle. They will be sorted in an arbitrary order, but whichever one ends up first will be rejected. To fix this, we’ll need to add the distance to the lower-left point in the angle comparison. If two points have the same angle, the point that is closer should come first in the list. That way, it will be rejected.

To do this, I’ll change angle to return a tuple with the angle and the length. When comparing tuples, the elements n are only compared if the elements n-1 are equal, which is exactly what we want. So, with the subdefinitions the same, angle becomes:

When I did this, I realized that I could use a tuple in the findFirstPoint comparison too. The expression:

is equivalent to

I think the second is easier to read, and due to laziness the x-coordinates aren’t even calculated unless the y-coordinates are equal.

Final Thoughts

So that’s it really. You can get the final source here. I would be interested to see someone tune the performance on this. It scales about linearly,¹ which is expected since the algorithm is O(n log n), but I think that there’s plenty of room for improvement. If you have some suggestions, fork the repository at Github and show me what you can do.

Haskell’s expressive power made the implementation of this algorithm fairly easy. There are several different ways to do it, and I’ll explore some of the options in future articles.

I’ve been playing around with some of the new features in HTML5, particularly to see how the canvas stacks up to Flash. One of the things I wanted to test was javascript performance, so I ported this Flash toy I wrote a few years ago. It’s a physical simulation of a double pendulum system. It’s interactive, and it can export the line drawing it produces as a PNG.

How did canvas+JS do? The export was a lot easier: I had to write a PNG encoder in Actionscript for the original version! Pretty much everything else was harder. Canvas has features similar to Flash 5, and I missed modern Flash’s rich standard library. CSS layout is still somewhat inferior to Flex for GUI design, as the layout options are less flexible.

One of the appeals of canvas is mobile support, but I was disappointed by the performance on my Motorola Droid. Just clearing the background on a canvas larger than 500×200 took the frame rate to single digits, and I couldn’t find a reliable way to make the canvas fill the screen if other elements were present (I didn’t look too hard, since a canvas that large was unusable). The javascript performance was fine, it was just the drawing that caused problems. Let me know if you get better results on different hardware, I’d love to know that this can work better.

Overall, canvas shows promise, but I don’t think it’s ready to replace Flash for complex graphical applications.

Windows vs. Unix File System Semantics – Conifer Systems.

Practical Haskell: scripting with types « Control.Monad.Writer.

To simplify the game mechanic functions, we’ll carry the game state around in a State monad called GameStateM.

This is created by the input functions that we’ll see later.

The first thing we want is a high-level function that can be used to move a piece. This is easy to describe in plain English: if the move from space A to space B is valid, move the piece on the board and remove any piece that was jumped, then it’s the next player’s turn. It is almost as easy to write in Haskell:

We’ll look at isMoveValid soon. When the move is valid, this gets the board from the current state, makes a new board with the pieces moved, then puts the new board back in the state. The function gets board maps the projection board into the state, so it is equivalent to get >>= return . board. We put the new board back into the state with modify, which takes a function that modifies the current state. So modify f is equivalent to get >>= put . f. We’ll look at switchPlayer and selectPosition in the part about input.

Now, let’s define move and jumpPiece.

In move we first try to get the moving piece from the board. If it existed, we return the board with the piece moved. To do that, we delete the piece from the old position and insert it at the new one.

Next, we take a leap.

Notice that these are partial functions. If the position that was jumped is Nothing, i.e. no jump, then don’t modify the board. Otherwise, delete the piece that was jumped.

Now the hard part: checking if the move is valid. We have a number of things to check here, so let’s break it down. A move is valid if:

• The destination is on the board
• The destination space is empty
• If the piece that is moving is a goose, then it must move forward
• The spaces have to be adjacent or a jump
• A jump can only occur if the destination is two spaces away from the start along a line, and the moving piece is a fox, and the space jumped had a goose, and the first two rules still apply

Whew, that’s a lot to check. Let’s start.

We’ll need to know what piece is moving in a few places, so get it here. It also helps to get what we need from the state here, so we can define helper functions which aren’t in the state monad. Next, we check if the destination is empty with Map.member. Remember, we don’t store empty spaces in the map. We use a couple of helper functions to check if the move is a jump, then we combine all of our rules in a call to and. Finally, the result of the function is if the move is valid and which space was jumped, if any.

Let’s dive into these helper functions.

These are all very simple definitions. We need dx and dy in a lot of places, so they’re defined here. onBoard and isAdjacent use two definitions from part 1. The function isGoose checks if a jumped space has a goose. How do we calculate the jumped space? We know that it has to be either two positions up, down, or sideways, and if (x + y) is even then we can go diagonally also.

If the jumping piece isn’t a fox, or the move isn’t a jump, return Nothing.

This is the bare minimum of mechanics for a working fox and geese game. It’s actually not complete, because we don’t allow multiple jumps, and we don’t force a player to take a jump if he can. I will add those later and write a new post.

Next time, we’ll see how to make our game interact with the world, with input and drawing. The source code is available on GitHub, so please fork it and make it better.