Are you surprised at how you sound when you listen to a recording of your voice? I always thought that we sound different to ourselves because your voice vibrates through your skull to your own eardrums, which gives you a unique experience of your voice. It’s kind of nice to think that every time you speak you’re giving yourself a private concert, but for effective communication you need to know how others hear you.

Vocal Coach Chris Beatty’s video shows one way to hear how you sound to others. He explains that part of the effect is due to sound travelling around your face to your ears. Blocking this sound lets you hear how your voice changes as it travels through the room. I gave it a try, and I was surprised at how well it works.

I have a deep voice, and people often have trouble understanding me. I’ve always wondered if I sound louder to myself than others, and if the distinct frequencies of my voice get muddled as they bounce around a room. When I used this technique and blocked my voice with some magazines, it sounded like my volume dropped to about 30%. I couldn’t believe it! I used to do theatre,¹ so I know I can speak loudly enough to be clearly heard across an auditorium. Because of this, I try to keep my volume down so that people don’t think I’m shouting, but I think I went too far. Now, using this technique to hear how I sound to others for feedback I’ll be able to adjust how I speak to be more clearly understood.

via LifeHacker

It would really help me out if you go rate Monstrosi Stacks on Newgrounds.

• 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.