Tricky When You Least Expect It

Here's a problem: You've got a satellite dish that can be rotated to any absolute angle from 0 to 360 degrees. If you think of the dish as being attached to a pole sticking out of the ground, that's what the dish rotates around. Given a starting angle and a desired angle, how many degrees do you rotate the dish by?

An example should clarify this. If the initial angle is 0 degrees, and the goal is to be at 10 degrees, that's easy. You rotate by 10 degrees. If you're at 10 degrees and you want to end up at 8 degrees, then rotate -2 degrees. It looks at lot like all you have to do is subtract the starting angle from the ending angle, and that's that.

But if the starting angle is 10 and the ending angle is 350...hmmm. 350 - 10 = 340, but that's the long way around. No one would do that. It makes more sense to rotate by -20 degrees. With this in mind and some experimenting, here's a reasonable looking solution (in Erlang, but it could easily be any language):

angle_diff(Begin, End) ->
   D = End - Begin,
   DA = abs(D),
   case DA > 180 of
      true -> -(360 - DA);
      _ -> D
   end.

It seems to cover some quickie test cases, including those listed above. Now try angle_diff(270, 0). The expected answer is 90. But this function returns -90. Oops.

This is starting to sound like the introduction to a book by Dijkstra. He'd have called this problem solving method "guessing," and it's hard to disagree with that assessment. When I run into problems like this that look so simple, and I feel like I'm randomly poking at them to get the right answers, I'm always surprised. So many messy problems are solved as part of the core implementation or standard library in most modern languages, that it's unusual to run into something this subtle.

In Python or Erlang I never worry about sorting, hash functions, heap management, implementing regular expressions, fancy string comparison algorithms such as Boyer-Moore, and so on. Most of the time I write fairly straightforward code that's just basic logic and manipulation of simple data structures. Behind the scenes, that code is leaning heavily on technically difficult underpinnings, but that doesn't change how pleasant things are most of the time. Every once in a while, though, the illusion of all the hard problems being solved for me is shattered, and I run into something that initially seems trivial, yet it takes real effort to work out a correct solution.

Here's a version of the angle_diff function that handles the cases the previous version didn't:

angle_diff(Begin, End) ->
   D = End - Begin,
   DA = abs(D),
   case {DA > 180, D > 0} of
      {true, true} -> DA - 360;
      {true, _}    -> 360 - DA;
      _ -> D
   end.

Don't be surprised if it takes some thought to determine if this indeed handles all cases.

There's now a follow-up.

(If you liked this, you might like Let's Take a Trivial Problem and Make it Hard.)

permalink June 29, 2010

Tricky When You Least Expect It

previously

archives