Urinal Code Kata

While I was at CodeMash 2012, I had an idea for a programming Kata. I remembered an online “Urinal Quiz” that I had seen in the past. Basically, the idea is that for any given set of urinals, occupied and unoccupied, there is a single “best” one to pick. The rules for choosing the “correct” stall were simple enough to be memorized, but complicated enough to have some exceptions. This is similar to what we experience all the time at work as programmers. There’s a simple rule such as “Claims are processed the last Thursday of every month” and a bunch of exceptions “Unless the last Thursday is the last day of the month, in which case they are processed the week before”. It seems we’re always confronted with something that should have been very simple, but is made complicated by some set of arcane edge cases.

The rule set in this case is actually quite simple, so it makes for a good Kata. It also had the advantage of being somewhat humorous, and so I turned it into an entry in the Thursday night Pecha Kucha talks (20 slides * 20 seconds each). The video is available here (Codemash 2012 Urinal Code Kata)

There are a lot of ways to solve this particular problem. For instance, I considered assigning point values to different rules, and evaluating them for each position. I didn’t like this approach because it’s not the sort of thing you can do in your head easily. Instead, I decided to approach this using Linq as a sorting and ordering problem. This is closer to the way we think in our heads “Find the stall furthest from the door that has no neighbors”. The whole problem can be expressed with three very simple rules.

  1. Get as far away from the door as possible.
  2. Try not to stand next to another dude.
  3. Really try not to stand next to two other dudes.

The exceptions are not that complicated either. Rules 2 and 3 can be violated in one of two cases.

  1. There is a line
  2. Someone else has already broken that particular rule.

The first exception is simple to implement. The second one requires a bit of analysis of the existing data, and also some explanation. If someone else has already broken a rule, and you continue to follow it, you are unintentionally calling attention to their infraction, and that is clearly a violation of the Bro-code.

Like all good Katas, don’t try to over-analyze the problem up front. The rules can be further simplified, but that will happen as part of the Kata. The key with Katas is that you’re trying to train your mind to recognize patterns so that you can pick up on them when they happen in the real world.

I like to write tests for Katas in a style similar to many of the “Koans” you may have seen. It’s the opposite of “One assert per test”. In fact, there is only one test with many many assertions in it. This means that at any given time, running the unit tests will only tell you one thing that’s wrong with your code. Only when you have addressed that problem are you allowed to know the next one. It’s an approach that stops you from thinking ahead and trying to solve the whole puzzle at once.

So, lets see how the Kata progresses. First we’ll need a function to evaluate the scenario. I’ve refactored a little bit since the first presentation of the Kata during the CodeMash 2012 Pecha Kucha sessions. The function takes a boolean array representing whether the stalls are occupied or not, and returns a nullable integer representing the correct stall to choose. The array is taken to be in order of closest to farthest from the door. For instance, the array { false, false, true } represents three stalls, with the farthest one from the door being occupied. There’s an additional boolean parameter that indicates whether or not there is a line.

The function will first do some manipulation of the data, compiling neighbor counts and such, before proceeding to evaluate the rules. The version presented at CodeMash used the Neighbors method repeatedly during rule evaluation. Later, a coworker, Jeff Walker, suggested a way to move all the counting up-front so that it only happens once. It’s a good optimization, and makes the query much easier to understand.

The Method
  1. public class UrinalRules
  2. {
  3.     public static int? Solve(bool[] stalls, bool queued)
  4.     {
  5.         var positions = stalls
  6.             .Select((occupied, index) => new { index, occupied, neighbors = Neighbors(stalls, index) })
  7.             .ToList();
  8.         var result = (int?)null;
  9.         return result;
  10.     }
  11.     private static int Neighbors(bool[] stalls, int index)
  12.     {
  13.         return (index > 0 && stalls[index – 1] ? 1 : 0)
  14.             + (index + 1 < stalls.Length && stalls[index + 1] ? 1 : 0);
  15.     }
  16. }

Implementing Rule 1: “Get as far away from the door as possible”
It is imperative that you pick a position as far from the door as possible for a variety of reasons, not the least of which is reducing the amount of traffic passing behind you while you’re “occupied”. Call it a survival instinct. This is just a matter of adding a Linq query to select an unoccupied stall, and a simple ordering clause to pick the one furthest from the door.

Rule 1
  1. public static int? Solve(bool[] stalls, bool queued)
  2. {
  3.     var positions = stalls
  4.         .Select((occupied, index) => new { index, occupied, neighbors = Neighbors(stalls, index) })
  5.         .ToList();
  6.     var result = positions
  7.         .Where(x => !x.occupied)
  8.         .OrderByDescending(x => x.index)
  9.         .Select(x => x.index)
  10.         .FirstOrDefault();
  11.     return result;
  12. }

Rule 2: “Never stand next to another dude”
I’ll just highlight the differences in the query from this point forward. All we need for this rule is another condition in the where clause to limit the choices to positions with no neighbors.

Rule 2
  1. var result = positions
  2.     .Where(x => !x.occupied && x.neighbors == 0)
  3.     .OrderByDescending(x => x.index)
  4.     .Select(x => x.index)
  5.     .FirstOrDefault();

Rule 2, Exception 1: There is a line at the door
Now we start getting into the exceptions, and things start getting more interesting. If there’s a line at the door, you must take a stall. You still want to be as far from the door as possible, though. That part does not change.

Rule 2, Exception 1
  1. var result = positions
  2.     .Where(x => !x.occupied && x.neighbors == 0
  3.         || (queued && x.neighbors == 1))
  4.     .OrderByDescending(x => x.index)
  5.     .Select(x => x.index)
  6.     .FirstOrDefault();

Rule 2, Exception 2: Someone else has already broken Rule 2
This gets into complex social behavior that’s harder to explain, but suffice to say that continuing to uphold a rule when someone else has already violated it would be “calling them out”, a clear-cut violation of the bro-code. So, if someone already has a neighbor, then it’s okay to have one too. We’ll just expand the exception to encompass both of the conditions. We’ll also need another OrderBy clause because, while it’s now acceptable to have a neighbor, it is still to be avoided if at all possible.

Rule 2, Exception 2
  1. var result = positions
  2.     .Where(x => !x.occupied && (x.neighbors == 0
  3.         || (x.neighbors == 1 && (queued || positions.Any(y => y.occupied && y.neighbors == 1)))
  4.         ))
  5.     .OrderBy(x => x.neighbors)
  6.     .ThenByDescending(x => x.index)
  7.     .Select(x => (int?)x.index)
  8.     .FirstOrDefault();

Rule 3: Never stand next to two other dudes
This is kind of like Rule 2, except more important. If having one neighbor is bad, then it goes without saying that having two neighbors is even worse. This rule has similar exceptions to Rule 2 (There’s a line, or someone already broke the rule), so I’ll include them here as well.

Rule 3
  1. var result = positions
  2.     .Where(x => !x.occupied && (x.neighbors == 0
  3.         || (x.neighbors == 1 && (queued || positions.Any(y => y.occupied && y.neighbors == 1)))
  4.         || (x.neighbors == 2 && (queued || positions.Any(y => y.occupied && y.neighbors == 2)))))
  5.     .OrderBy(x => x.neighbors)
  6.     .ThenByDescending(x => x.index)
  7.     .Select(x => (int?)x.index)
  8.     .FirstOrDefault();

By now, a pattern should be apparent. I can’t have a neighbor if no-one else does. I can have exactly one neighbor if someone else does. I can have two neighbors if somebody else does, as well. What we’re really saying is that you should never have more neighbors than anyone else. Of course, if you can get away with fewer neighbors than everyone else then you win.

To refactor the query, we’ll use Linq’s Max extension method to select the highest neighbor count from all the occupied positions. Unfortunately, in the case that none of the stalls are occupied, this result set would be empty, and Max will throw an exception. We can work around this by changing the type of the Neighbors method to be nullable, and coalescing the result of Max with 0. It’s kind of a cheat, but it works. For more information on this particular problem, see http://www.interact-sw.co.uk/iangblog/2007/09/10/linq-aggregates.

The final version of the class looks like this:

Final Version
  1. public class UrinalRules
  2. {
  3.     public static int? Solve(bool[] stalls, bool queued)
  4.     {
  5.         var positions = stalls
  6.             .Select((occupied, index) => new { index, occupied, neighbors = Neighbors(stalls, index) })
  7.             .ToList();
  8.         var result = positions
  9.             .Where(x => !x.occupied
  10.                 && (queued || x.neighbors <= (positions.Where(y => y.occupied).Max(y => y.neighbors) ?? 0)))
  11.             .OrderBy(x => x.neighbors)
  12.             .ThenByDescending(x => x.index)
  13.             .Select(x => (int?)x.index)
  14.             .FirstOrDefault();
  15.         return result;
  16.     }
  17.     private static int? Neighbors(bool[] stalls, int index)
  18.     {
  19.         return (index > 0 && stalls[index – 1] ? 1 : 0)
  20.             + (index + 1 < stalls.Length && stalls[index + 1] ? 1 : 0);
  21.     }
  22. }

From here, you can explore some of the more esoteric rules on your own. The example I gave as extra credit in the Pecha Kucha talk was the “No Pairing” rule which states that it is preferable to join a pre-existing pair of neighbors than to start a new “couple” with a singleton “loner”. I haven’t given this one much thought, myself, and it was only included in the talk as a kind of punch line, since it’s so odd and obscure that no-one would guess it corectly.

You could also explore the simpler problem of what to do with the short, or “kids” stall. The ruling on this is actually very straightforward. The short stall is ignored by everybody until it is the last stall left to choose from, and even then it’s only used if there is a line.

If you want to work through this particular Kata yourself, here are the tests to exercise the rules presented above. They are presented in MsTest format simply because it’s built into Visual Studio and makes for a good lowest common denominator.

Unit Tests
  1. [TestClass]
  2. public class UrinalRulesTests
  3. {
  4.     [TestMethod]
  5.     public void UrinalRules_Test()
  6.     {
  7.         Assert.IsNull(UrinalRules.Solve(new[] { true, true, true, true, true }, false), “All stalls are occupied. You should return a null (Stalemate).”);
  8.         Assert.AreEqual(4, UrinalRules.Solve(new[] { false, false, false, false, false }, false), “Rule 1: Get as far away from the door as possible.”);
  9.         Assert.AreEqual(2, UrinalRules.Solve(new[] { true, false, false, false, true }, false), “Rule 2: Avoid standing next to another dude.”);
  10.         Assert.IsNull(UrinalRules.Solve(new[] { true, false, true, false, true }, false), “Rule 2: Avoid standing next to another dude.”);
  11.         Assert.AreEqual(4, UrinalRules.Solve(new[] { false, true, false, true, false }, true), “Rule 2, Exception 1: You can have a neighbor if there is a line.”);
  12.         Assert.AreEqual(3, UrinalRules.Solve(new[] { true, true, false, false, true }, false), “Rule 2, Exception 2: You can have a neighbor if someone else already does.”);
  13.         Assert.IsNull(UrinalRules.Solve(new[] { true, false, true, false, true }, false), “Rule 3: Really avoid standing next to TWO other dudes.” );
  14.         Assert.AreEqual(3, UrinalRules.Solve(new[] { true, false, true, false, true }, true), “Rule 3, Exception 1: You can have two neighbors if there is a line.”);
  15.         Assert.AreEqual(3, UrinalRules.Solve(new[] { true, true, true, false, true }, false), “Rule 3, Exception 1: You can have two neighbors if someone else already does.”);
  16.     }
  17. }

So, what started as a funny idea, and turned into an impromptu talk, has quickly evolved into a useful coding Kata. It is representative of real-world business code, which always seems to have nearly as many arcane exceptions as rules. It also gives us an opportunity for a simple refactoring, and to exercise some Linq goodness. The Linq part may not help the Java folks much, but as I said at the beginning of this post. There are many ways to solve this particular puzzle. Even the .Net folks should try doing it without using Linq. You could attack it by writing your own sort, or by assigning point values to different rules.

Remember… Stick to the code.

About these ads
This entry was posted in Computers and Internet. Bookmark the permalink.

2 Responses to Urinal Code Kata

  1. Pingback: Our ComponentOne | Blog | CodeMash 2012 Recap

  2. Nick says:

    Very hilarious …… I was wondering why I always break the code, then I figured you left out the urgency factor….. How full is the bladder, how much time do I have …..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s