2008-10-30

Thankful for the Executor Framework

It is commonly said that a good framework makes common tasks easy to do, while keeping hard things possible. Today, I'm reminded that a good related property is to prevent common errors.

Whoops

My friend and fellow developer Jason posts today a chunk of hard-learned wisdom about spinning off worker threads to perform asynchronous tasks in an ASP.NET application. It seems that if an exception bubbles up to the top of the call stack, not only does the thread die (which is expected), but it takes down the entire ASP.NET application, forcing it to restart, leading to a loss of in-memory session state. OUCH, yes, and it's an easy bug to introduce.

Making easy errors hard to make

This is why I'm thankful for the general design Java's Executor Framework imposes on the developer, as it renders this sort of bug a bit harder to make.

Using an executor service with the Callable interface is pretty simple and it's generally easy to work with:

  • You create a task to offload, as an instance of a Callable, with a call() method that's allowed to throw any Exception it wants.

  • You submit your Callable to an executor service, which spins off a thread for it if required, and immediately returns you a Future instance, while the worker thread does its thing.

  • Later, using the handle of that Future instance, you can query the result of the computation from your main thread by calling get() on it. If the task you spun off threw an exception from call(), you get the exception only then (wrapped in an ExecutionException), on the main thread, where you're actually able to (and forced to) deal with it, since Future.get() declares itself as throwing ExecutionException.

2008-10-26

Postal codes on an iPhone

Canadian postal codes satisfy this regex: "[A-Z][0-9][A-Z] [0-9][A-Z][0-9]". Do you have any idea how annoying that is to type on an iPhone?

Secret Santa Protocols

Some friends and I are kicking off the holiday season early this year! Along with Jason Kealey and Etienne Tremblay of LavaBlast Software, as well as their better halves, I've arranged to rent a rather nice cottage in mid-December. We decided to hold a Secret Santa gift exchange over there, which brings us to this post.

Dinner

How do you arrange a randomly-assigned Secret Santa event when the participants are geographically distributed?

Assignment of giver/recipient pairs is usually handled by drawing strips of paper from a hat, an approach that obviously won't work here, when planning over email. So I started to think about how one could do this without relying on a trusted third-party. Is it possible for a group of peers, communicating only through email, to each choose a random recipient and guarantee uniqueness of picks, while ensuring picks are not revealed to others, and no one ends up picking themselves? [My father, over dinner the other day, helpfully pointed out that this is known as a derangement problem.]

The real-world pragmatic approach

We ended up going with the very pragmatic approach of relying on a trusted third-party (in this case a simple computer program). I wrote a Java program that took the list (L) of 5 email addresses, shuffled it (using Collections.shuffle()), then sent an email to address L[i] containing address L[(i+1) % 5], all without printing to the screen what it was doing, or logging anything. Once the program exited, there was no way for anyone to recover who got what address, and it guarantees that the final assignment is a derangement: no person in the initial list gets themselves.

Now, this is all well and good, but it's a boring solution because of its reliance on software. Is this doable with only five people talking over email? (Yes, it's a mostly academic exercise.) I've had some ideas that go in the right direction, but haven't solved the problem of ensuring the final mapping is a derangement, other than running the process for multiple rounds, until no one declares they received themselves as an assignment.

Primitive: mapping IDs to gift recipients

The first primitive our protocol needs is a method of mapping an abstract identifier (say, a number) to an actual name. This is because since participants need to pick one of the 5 identifiers unsupervised, they must not know in advance which person this identifier will represent.

This is the easy part: have everyone pick a unique value i from the pool of identifiers [0-4] (randomly or not) and remember it without disclosing it. Your assigned name is then L[(i+d) % 5], where d is the integer part of the TSX composite index at market close the following day. The offset value d is the same for everyone, is not known in advance, and when we all exchange gifts we can audit that no one cheated and changed their chosen ID after knowing d.

Independently choosing IDs

The above relies on everyone having independently picked a unique value for i, and this is where things get interesting.

  • There are 3125 [5^5] sets of picks when done independently with no knowledge of the others.
  • Of those, only 120 [5!] contain unique, unduplicated, choices, or 3.84%.
  • Of those, only 44 are derangements, where no one ends up with themselves (1.408% of the total)

First approach: anonymous broadcast

If a means of anonymously broadcasting a message to the whole list is available, we can rapidly constrain picks to the 120 cases where there are no duplicates. We'll then have a 36.7% chance [44/120] of having a derangement in each round, so we should be able to settle on a solution in very few rounds.

  • We declare the round started, and the pool of legal choices to be {0, 1, 2, 3, 4}.
  • Everyone picks a random delay d in [0; 3599] (with 5 participants, collisions are unlikely).
  • After d seconds, pick a value in the pool of legal choices, and anonymously broadcast "n has been picked", everyone removes n from the pool. (You can also just always choose the first available number, that works equally well.)

Second approach: no anonymous broadcast

OK, so you don't have an anonymous remailer. No problem!

I've devised a method to ensure the picks are independent, but it can take many rounds to work, as the expected success rate is only 120/3125. (And after that you still have the problem of restarting if you don't have a derangement.)

I think the following should work, but YMMV, I haven't proven it:

  • We publish the list of 5 participants. Their order is unimportant.

  • We publish 5 IDs. Let's use 5 prime numbers {3, 5, 7, 11, 13}. I don't think they need to be prime, but they must be picked to ensure that their product, known by all (in this case, P=15015) can only be achieved if you pick EXACTLY one of each number, and this is easy to ensure if you take primes [I think].

  • Everyone independently picks an ID i from the list, keeping it secret.

  • I'm first on the list. I choose a random large integer s. I compute P' = i * s * P.

  • I hand off this product (P') to the second person on the list. The number she receives from me is evenly divisible by 3, 5, 7, 11, 13 and P, so she has no way of knowing what my chosen i is, or what value of s I picked (there are 5 equiprobable possible values for s, which tells her nothing).

  • She multiplies P' by her own chosen i, and gives that to the third person on the list, and so on.

  • The list wraps around and I'm sent a value from the 5th person on the list. If everyone picked a unique value for i, I get s * i0 * i1 * i2 * i3 * i4 * P or, succinctly, s * P2. If I get anything else, then I know there's a duplicate.

  • I announce whether or not there was a duplicate. (I, or anyone else, can always lie, but then when gifts are exchanged we'd know someone lied - in the spirit of the holidays, the participants in this protocol are honest.)

Phew. Each round has a 1.408% chance of working, so it could take a while. I have yet to find a much better approach, so I think our little 30-line Java program was appropriate in this situation.

2008-10-21

This Week in Food

Will Ron Eade wake up with a head of lettuce in his bed?

First up is Ron Eade's column from Ottawa Citizen blogs, where he heaps some well-deserved praise on Kevin Mathieson (of Art-Is-In Bakery) for his bread. Eade says it's better than ACE bread (n.d.a.: no shit), and I for one am glad to note that the supply problems I was hurting from a year ago seem to be a thing of the past: whereas last year, getting your hands on Art-Is-In bread required much haste in returning home from the office, this year I find that retailers aren't consistently running out by late afternoon.

Eade calls New York Times' Mark Bittman's bread recipe a good replica of Art-Is-In's, which I have to humbly disagree with. Bittman's recipe is good, it's my go-to recipe for homemade bread, but I hardly think it's close to equal to Mathieson's.

I think it's awesome that he can get away with saying:


I'm not kidding when I say you need a six- to eight-quart heavy cast-iron Dutch oven with lid. Every kitchen should have one.


Yes, every kitchen should have one - but when I say anything like that, people roll their eyes at me. If you're a newspaper columnist though...


Amate

Amate in Wellington Village

Got around to trying Amate (link goes to ottawafoodies.com) for some quick Mexican take-out. I came in a few minutes before they decided to shut down for the night, and ordered a tostada with some puerco pibil. Unfortunately, I only got a tiny spoonful, maybe 40g, of pork but hey, what I tasted was good. I think they're still going through opening pains and are a bit disorganized, so it's not fair to say more at this time - let's give them a few more months.

I'll probably try my hand at making puerco pibil myself (in more generous quantities) when I get a free afternoon.

Malak Pastry

Tasty Baclava

I've lived in Westboro for over a year and had never tried Malak Pastry, despite it being right at Carling/Broadview - shame! It's a bakery offering up a range of baklawa (which I'll admit I know little about). I asked for the shopkeeper's recommendations and got a few samples to try before buying, and was incredibly impressed. Delicious! They weren't yet listed on OttawaFoodies, so I'm adding them presently.

foods++;

Finally, I've tried sauerkraut (at a corporate event at the office, no less), bringing my 100 Food countdown (previously blogged about) to 57% completion. Moving up 1% in two months is a rather pathetic pace, so I'm going to make a bigger effort.


2008-10-18

Sure, but what year?

Sure, but what year?

That's what I call optimistic.

I really, really, wish I could afford one of those condos, the artist's renderings I've seen look pretty sweet. Also, expensive.

2008-10-16

Coffee Shop Technology

I'm sitting in the Westboro Bridgehead, working on a presentation on my MacBook Pro.
Observations from the coffee shop:
  • A 50 year-old looking woman is texting. She's typing pretty fast, too.
  • No one is wearing iPod headphones. Everyone is here to enjoy the atmosphere, I like that.
  • Among the people typing away on laptops, the Mac market share is 100%. ONE HUNDRED. Way to go Apple.

2008-10-08

A bit of free money from ING Direct

ING Direct is trying to beat the fray of banks that will be offering TFSAs in January 2009. Even though, to the best of my knowledge, the federal government hasn't yet published the full TFSA rules and details, based on the details available now, banks are starting to jump in.

Here's the announcement they made on October 7th:

Earn special Bonus Interest between October 4th, 2008 and December 31st, 2008 and get saving tax-free earlier!

Because we just couldn’t wait until January 1, 2009 – we’ll cover your taxes!

Bonus Interest!

While we can’t help you avoid taxes in 2008, we can pay you more than enough bonus interest to cover those taxes! Effective January 1, 2009, funds deposited in the promotional Tax-Free Investment Savings Account opened between October 4 and December 31 will be transferred to a new Tax-Free Savings Account so you won’t miss a minute of Tax-Free interest.

Open an ING DIRECT promotional tax-free Investment Savings Account today and on December 31st we will double your interest payment. This should be enough to cover any tax you’ll need to pay on interest earned and will help you get a head start for tax-free saving in January.

Tax-Free

With the new Tax-Free Savings Account, any interest earned in an ING DIRECT Tax-Free Savings Account will not be taxed.


It seems this account is identical to their regular savings account, except it automatically gets registered as a TFSA on 1 January 2009, and on 31 December 2008, it gets a bonus interest payment equal to all the interest paid in the last 11 weeks of the year (from now until 31 December). They're marketing the bonus payment as a way to offset taxes paid on the regular portion of the interest in 2008, since TFSAs don't yet exist.

I'm not normally a fan of trivial quarter-point rate chasing between banks, but assuming you've got a savings account at ING Direct already (I keep my emergency cash at ING), I see absolutely no downside to getting in on this.

It took me about 2 minutes to login, create an anticipated TFSA, and transfer 5000$ from regular savings to the new account. At the current 3% rate, with monthly compounding, the expected interest on 5000$ between now and December 31st is around 35$, so they're giving away 35$ for two minutes of work.