Happy numbers again: spoilers

If you’ve tried the Happy numbers kata you may have noticed a couple of things about the algorithm. Firstly,

13 => 32 + 12 => 10 => 1

is the same as

31 => 12 + 32 => 10 => 1.

That is, happiness and unhappiness are preserved under all permutations of the digits. So if you have calculated the status of 134, you also know the status of 143, 314, 341, 413 and 431!

And secondly, zeroes have no effect on the outcome. So 103 is just as happy as 13; and similarly 1300, 1000300000 and 30010 are all happy.

In a sense, that means it is not meaningful to ask how many numbers can be examined in 5 seconds, say — because the answer is always infinite! So let’s redefine the kata:

Write a program to report the number of happy numbers in the range [1, n]. What is the largest n you can deal with in 5 seconds?

Some interesting questions now come to mind:

  • Where does the time go? Is it faster to calculate the happiness of a number than it is to create all permutations of its digits?
  • What is the best data structure for holding the results? Can a recursive or functional algorithm compete with a procedural approach?
  • What is the best way to deal with numbers containing zeroes?
  • Are the answers to these questions dependent on programming language?
  • Is this really an algorithm on the integers, or is it an algorithm on lists of digits?

Finally, something quite bizarre. The observations above regarding zeroes and digit permutations mean that we can acquire the answer to the challenge while examining fewer integers. How many fewer?

My rough calculations suggest that we only need to examine 54 of the integers below 100 in order to have complete information about every number in the range 1-100. Thats 54%. But we only need to examine 229 of the first 1000, which is 22.9%. To cover 1-10000 we only need to examine 714 numbers, and for 1-100000 we only need to examine 2002 numbers — ie. 2% of them! It would appear that this algorithm gets significantly faster as we move to larger and larger data sets. How much difference does this make to what your implementation can achieve?

The happy numbers kata

This weekend my 9 year old son was given the following homework:

Choose a two-digit number (eg. 23), square each digit and add them together. Keep repeating this until you reach 1 or the cycle carries on in a continuous loop. If you reach 1 then the number you started with is a “happy number”.

Can you find all the happy numbers between 1 and 100?

For example, 31 is happy because

31 => 32 + 12 => 10 => 12 + 02 => 1

But 4 is not happy because

4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4

and we have a cycle.

I thought this might make an interesting code kata, so while he beavered away with pencil and paper I set to writing a little program to do the job. Why not give it a try yourself?

  • What tests, if any, did you write? How many times did your stack overflow? What data structure(s) do you need?
  • Did you use recursion? Or loops? Or filters? Or something else?
  • Did you manage to eliminate all of the duplication? Can you eliminate all of the conditionals? Is any of this altered by your choice of programming language?
  • How long does it take to run? At what range size (eg. 1-100, 1-1000, 1-10000) does it take more than, say, 5 seconds to run? Does it run in linear time? Polynomial time? What mathematical tricks can you find to speed it up?
  • What will you do differently next time?

First time through, I wrote no tests. My stack overflowed three times. I used a dictionary to hold the results, with a simple array for cycle detection and a recursive algorithm. I made no attempt to eliminate either duplication or conditionals, and I used none of the arithmetic tricks that my son found while doing the exercise by hand.

Next time, however, will be different…

Supplementary (for the mathematicians among you):

Are there any numbers for which the series neither terminates at 1 nor eventually repeats forever?

On paperboys, newsagents and exceptions

A few days ago I asked whether an exception should be thrown when the customer cannot pay the paper-boy. The responses (thank you!) ranged widely across the spectrum between Yes and various shades of No, and are well worth taking a few minutes to read before we go any further. What follows is my take on the code…

TL;DR — replace the exception by giving the paper-boy a coping strategy

Let’s think about the real-world (domain) model for a minute:

Firstly, I note that I have been that customer on many occasions. I’m frequently not at home when the paper-boy or the Avon lady or the window-cleaner comes around (honest!). I would expect that non-payment is statistically likely to occur on pretty much every collection round.

Now, presumably the paper-boy is on his round, calling on the newsagent’s customers. He may be only collecting money, or he may also be delivering papers. As he goes from house to house everything runs smoothly, in that every customer so far has paid their bill; he has a bulging bag of money, and has marked ‘Paid’ against every customer on the first page of his little Accounts book. But the next customer doesn’t have the funds to pay! The paper-boy hasn’t been told what to do, and wasn’t expecting this eventuality at all. He panics and runs screaming back to the newsagent.

The paper-boy runs into the arms of the newsagent, who sees that someone couldn’t pay. Thankfully the boy still has the money he has collected thus far. But he also has hold of the last customer’s wallet. And in his panic he is so incoherent that he can’t say which customer couldn’t pay [note that the exception has no constructor parameters]. At this point we have to make some assumptions about where the newsagent might be standing:

If he is back at the shop, then the paper-boy has run so far that his round must now be assumed to be abandoned; the newspapers (and the bills) of any remaining customers will need to be dealt with on another round. Alternatively, the newsagent might be accompanying the boy on his round, telling him which house to visit next; in this case he can simply calm the boy down, deal with the matter himself, and the pair can then proceed with the round.

Neither of these alternatives seems entirely satisfactory. In the first case, it seems unreasonable that neither the boy nor the newsagent would learn how to cope with non-payment (which must surely happen regularly). Even if the boy wasn’t told about the possibility before his first ever round, he wouldn’t continue behaving that way forever. And no sensible newsagent would be happy to have to re-start the boy’s rounds after each non-payment.

But in the second case, why have a dog and bark yourself? Why is the newsagent accompanying the boy, unless this is a training exercise? Again, not a scenario that is likely to be oft repeated.

I assume therefore that, in the real world, the boy is sent on the round because the newsagent wants to stay and mind the store. The newsagent wants to boy to collect his customers’ dues (and perhaps deliver papers too), without the newsagent having to break off his work (and potentially finish the round himself, or send another boy to do that later). It’s likely therefore that the boy will have been given instructions such as “If anyone isn’t at home, or can’t pay, just make a note in the book. We’ll see them next week, or send an invoice, but don’t you worry about that for now.” That is, the newsagent gives the boy a coping strategy. The boy’s responsibility is to mark ‘Paid’ or ‘Not paid’ against each customer, and to collect money where possible. The newsagent will reconcile these notes against his accounts later in the day and decide what to do, both with the money and with the non-payers.

So, back to the code. Throwing this exception forces some other part of our code (presumably the Newsagent) to cope with it; the catch clause will be an example of a “type 7″ conditional in my little catalogue. I don’t believe it models the domain at all faithfully. Alternatively, we could avoid the exception if the paper-boy returned a status code. But that seems to me to be pretty much the same as the scenario in which the newsagent accompanies the boy on his round (and it leaves the Newsagent having to implement a “type 1″ conditional too).

Instead, I agree with Paul D’Ambra: I think we should give the Paperboy a coping strategy: Equip him with code to call when the customer cannot pay. And in the interests of symmetry we might go further, having the boy update the accounts directly as he goes.

There are numerous ways to express this in code. For example, we could implement this using the Observer pattern, either with a directly coupled listener:

class Paperboy {
  private int collected_amount;
  private Newsagent newsagent;

  public void collect_money(Customer customer, int due_amount) {
    int amount_received = customer.payWhatYouCanAfford(due_amount);
    collected_amount += amount_received;
    newsagent.customerPaid(amount_received, customer);
  }
}

Or with a decoupled event notification mechanism:

class Paperboy
  def collect_money(customer, due_amount)
    amount_received = customer.pay_what_you_can_afford(due_amount)
    @collected_amount += amount_received
    EventBus.announce :customerPaid, amount: amount_received, customer: customer
  end
end

Another conditional avoided. (And a domain more faithfully modelled, in my opinion.)

Designing an error case

The other day I stumbled upon a seven year old blog post by @dan_menges called Misunderstanding the Law of Demeter. It’s a great post, and it includes a nice code sample for the classic “paperboy” example of Demeter violation:

class Wallet
  attr_accessor :cash
end

class Customer
  has_one :wallet
end

class Paperboy
  def collect_money(customer, due_amount)
    if customer.wallet.cash < due_ammount
      raise InsufficientFundsError
    else
      customer.wallet.cash -= due_amount
      @collected_amount += due_amount
    end
  end
end

I love examples like this, and I like Dan’s improved design later in the post (go read that now). The reason I like this example is because it contains more meat, and therefore more context, than the standard “isn’t customer.getWallet().getCash(amount) terrible!” examples we often see (I’m as guilty of that as anyone). And in that extra context lies an interesting design question…

First though, I’m going to translate Dan’s code from Ruby into Java, so that we can see past some of the syntactic sugar to what’s really happening:

class Wallet {
  public int cash;
}

class Customer {
  public Wallet wallet;
}

class Paperboy {
  private int collected_amount;

  public void collect_money(Customer customer, int due_amount) {
    if (customer.wallet.cash < due_amount)
      throw new InsufficientFundsError();
    customer.wallet.cash -= due_amount;
    collected_amount += due_amount;
  }
}

(This version isn’t identical to the Ruby, which has getter and setter methods for the cash field in the Wallet, but it’s close enough for our purposes.)

Anyway, back to the point. What interests me most about Dan’s code is the InsufficientFundsException. As soon as I saw that exception being thrown, I stopped to think about this code for a good few minutes. And so I have a question for you:

Would you throw that exception there?
If you would, why?
And if you wouldn’t, why not?

Feel free to answer in the comments here, or write your own post and link to it from the comments. I’ll post my thoughts in a few days.

Where is the database?

I have just watched an interesting conversation between Martin Fowler and Badri Janakiraman about #hexagonalrails, and in particular about the role of databases. The central question in the discussion is whether the database should be considered outside or inside the domain. While watching, I realised I had had similar thoughts in 2005!

In recent years I have considered databases to be always outside the domain. I can definitely see the attraction of an “always present” domain model, but I think it is conflating different points of view, and misunderstanding the point of Hexagonal Architecture. I was wrong in 2005 :)

The comments on the video are very interesting, particularly those by Alistair Cockburn. Specifically he makes two key points:

  1. [There is no] debate of whether the persistence is in or out in HA, it is out. So you should say you chose not to use that piece of HA, not that you used it but brought the db inside.
  2. the purpose of HA is the configurable link t0 db

By forcing ourselves to keep to database outside of the domain we respect the hexagonal symmetry , and this is the only way to guarantee complete separation of concerns. The choice of Active Record or Data Mapper then becomes a decision about how to implement the “configurable database” port/adapter.

Eliminate many conditionals with this one weird trick

Recently I attempted to classify the conditionals in software according to where in the code they originate. The first category of these was: Checking a value returned to me from code I own. A large proportion of these can be eliminated quite simply.

Imagine we want to begin reading a file at the last saved read position, which may be null if we haven’t read anything yet:

var readOffset = fileReader.GetSavedReadPosition();
if (readOffset == null)
  readOffset = new ReadPosition(fileReader, 0);

This code violates almost every rule in the book:

  • There is duplication, because both the caller and the callee have special code for the “no saved position” branch.
  • There is Connascence of Meaning, because both need a common understanding of what the special null value means.
  • We are violating the Tell, don’t Ask principle because we are making a decision on the basis of a value returned from a call to a different object.

All in all, this code has problems — and yet I see code like this everywhere I look. So, what to do?

Let’s look at this code from the Connascence point of view. The problem is the null value representing the special “not saved” case: both the caller and the callee have to agree to use null to mean that (hence “Connascence of Meaning”). Now, connascence becomes stronger with increasing distance. Our example smells strongly because the two connascent code fragments are in different classes; thus we could weaken it if we can bring the endpoints closer together.

Currently, the fileReader decides what to return when it has no saved read position, and the client code has to cope with that decision. What if, instead, the client code decides what it would like to get back in that case; what if it could simply tell the method what to return if it can’t do the thing we’re asking:

var readOffset = fileReader.GetSavedReadPosition(0);

Now the connascence has disappeared, and the conditional has disappeared with it. It’s as simple as that.

Many frameworks and APIs offer this kind of default return value parameter. For example, the standard Ruby Hash class provides this feature via the fetch method.

But what if there’s no sensible default value that we can pass into the called method? For example, consider the following case:

var username = auth.GetPrincipal();
if (username == null)
  throw new UsernameNotFound();
auth.SetPassword(username, password);

We still have Connascence of Meaning due to the null return case; and we don’t want to push the error handling (or whatever) down into the authentication object, because different callers may want to handle the situation differently. But we can take a leaf from the default parameter book, and have the authentication object execute code for us:

var throwIfNotFound = () => throw new UsernameNotFound();
var username = auth.GetPrincipal(throwIfNotFound);
auth.SetPassword(username, password);

Again, the null value has disappeared, and so has the Connascence and the conditional. For the sake of symmetry we can often also dispense with the return value altogether and pass in both code branches to the callee:

auth.WithPrincipal(
  (username) => auth.SetPassword(username, password),
  () => throw new UsernameNotFound());

Pretty much every modern language supports this kind of code now:

  • Functional languages allow us to pass in functions to do the job; likewise Javascript;
  • C and C++ let us pass function pointers;
  • C# lets us use lambdas via Linq; Ruby lets us pass in lambdas, and even C++ (thanks @mmeijeri) and Java 8 now allow lambdas.

Some even let us use named parameters to make the options a little clearer; for example, we might write the above example in Ruby thus:

auth.withPrincipal(
  if_known: lambda {|username| auth.set_pass(username, passwd)},
  if_unknown: lambda {raise UsernameNotFound.new})

It’s as simple as that. By adopting these approaches it is possible to simplify a lot of code, effectively removing the connascence and the duplicated conditionals from the caller and the callee.

Where do conditionals come from?

Given that we want to reduce the number of conditional branches in our code, I wonder whether it is possible to catalogue all of the reasons they exist, so that we might then in turn list a few ways to eliminate each category.

So to that end I’ve listed out those origins of conditionals that I could think of. Is this a fool’s errand? Possibly, but let’s give it a try anyway. Please comment if you can spot any that I have missed, and let’s see if we can grow a “complete” list…

  1. Checking a value returned to me from code I own
    This is the essence of the Null Check smell, and more generally Connascence of Meaning. For example, see this (intentionally bad) code from William C. Wake’s Refactoring Workbook:

    public class Report {
      public static void report(Writer out, List<Machine> machines, Robot robot) throws IOException
      {
        //...
    
        out.write("Robot");
        if (robot.location() != null)
          out.write(" location=" + robot.location().name());
    
        if (robot.bin() != null)
          out.write(" bin=" + robot.bin());
    
        //...
      }
    }
    
  2. Checking a value returned to me from code I do not own
    For example, in Rails projects we often see code of this kind:

    if User.exists?(:user_id => current_user.id)
      # ...
    else
      # ...
    end
    
  3. Checking a parameter passed to me by code I own
    Whenever I write a method that accepts a Boolean parameter, I open myself up to the Control Couple smell. Here’s an example from Piotr Solnica’s blog:

    def say(sentence, loud = false)
      if loud
        puts sentence.upcase
      else
        puts sentence
      end
    end
    
  4. Checking a parameter passed to me by code I do not own
    Here’s an example from the jQuery documentation:

    <script>
    var xTriggered = 0;
    $( "#target" ).keypress(function( event ) {
      if ( event.which == 13 ) {
         event.preventDefault();
      }
      xTriggered++;
      var msg = "Handler for .keypress() called " + xTriggered + " time(s).";
      $.print( msg, "html" );
      $.print( event );
    });
    </script>
    
  5. Checking my own state or attributes
    Here’s an (intentionally bad) example from Martin Fowler’s Refactoring:

    class Employee {
      private int _type;
      static final int ENGINEER = 0;
      static final int SALESMAN = 1;
      static final int MANAGER = 2;
    
      Employee (int type) {
        _type = type;
      }
    
      int payAmount() {
        switch (_type) {
          case ENGINEER:
            return _monthlySalary;
          case SALESMAN:
            return _monthlySalary + _commission;
          case MANAGER:
            return _monthlySalary + _bonus;
          default:
            throw new RuntimeException("Incorrect Employee");
        }
      }
    }
    
  6. Checking a value I set previously in this method
    For example:

    public String format(List<String> items) {
      StringBuffer s = new StringBuffer();
      boolean first = true;
      for (String item : items) {
        if (first)
          first = false;
        else
          s.append(", ");
        s.append(item);
      }
      return s.toString();
    }
    
  7. Checking the type of an exception thrown by code I own
    Here’s an example from the PHP language documentation:

    <?php
    function inverse($x) {
        if (!$x) {
            throw new Exception('Division by zero.');
        }
        return 1/$x;
    }
    
    try {
        echo inverse(5) . "\n";
        echo inverse(0) . "\n";
    } catch (Exception $e) {
        echo 'Caught exception: ',  $e->getMessage(), "\n";
    }
    
    // Continue execution
    echo "Hello World\n";
    ?>
    
  8. Checking the type of an exception thrown by code I do not own
    We often find code such as this in Rails controllers:

    def delete
      schedule_id = params[:scheduleId]
      begin
        Schedules.delete(schedule_id)
      rescue ActiveRecord::RecordNotFound
        render :json => "record not found"
      rescue ActiveRecord::ActiveRecordError
        # handle other ActiveRecord errors
      rescue # StandardError
        # handle most other errors
      rescue Exception
        # handle everything else
      end
      render :json => "ok"
    end
    

Is this list anything like complete? Can it ever be?

I wonder if a useful next step might be to write down some general strategies for removing each of these kinds of conditonal…?

A problem with Primitive Obsession

By an odd coincidence, a number of the teams I work with have been looking at the Primitive Obsession code smell recently as part of the software habitability and craftsmanship training programmes I am currently running. As we have explored legacy code looking for examples of the smell, I’ve noticed a tendency to enthusiastically label every primitive in any method signature as smelly. This certainly demonstrates Primitive Obsession, but mostly on the part of the reader of the code, rather than in the code itself.

I so wish Fowler and Beck hadn’t used this particular name, because it seems to spread as much confusion as enlightenment. In my book I tried renaming it to Open Secret, but that was a very small voice lost in the noise. So hear my plea: please, please stop using the term Primitive Obsession — let’s talk about Connascence of Meaning instead.

I think it is important to recognise that not every primitive in a method signature represents (bad) Connascence of Meaning: Firstly, the problem is significantly weaker when the method is private (ie. it can only be called from inside the same object). That’s because connascence becomes stronger with distance. Inside a single class we expect a lot of connascence, because otherwise the class is probably not a cohesive unit of responsibility. It’s a fairly weak smell when two methods in a class both know how to interpret the meaning of a primitive.

And secondly, recall that this smell is mostly about the way domain concepts are represented and understood. If the primitive is passed straight through our code without being parsed in any way, again the smell is much weaker because we are not attempting to intuit any Meaning for ourselves. For example, if you’re working in a domain in which time is always given to you as a long, and you never do anything with it except store it or pass it on, then there is certainly Connascence of Meaning between the libraries you’re using, but I would argue that there’s probably none in your own code.

In general I’m finding that connascence is better than code smells as a tool for discussing coupling. And in particular, it seems to me that Primitive Obsession creates the wrong impression and makes the concept harder to learn.

On boolean externalities

This week @avdi wrote a really interesting blog post in which he expounds the woe induced by trying to debug a stack of methods that return booleans to each other. I couldn’t get Disqus to load on the post itself, so my response is below. Go ahead and read Avdi’s article now; take your time, and think about what you would change in his code; I’ll wait here until you’re ready.

A lot of the comments on That Twitter suggest that this can be “fixed” by returning things that are more complex than simple booleans, including switching to a different language to make that easier. I think most of them are missing the point. I think this is a representation problem. Let me explain.

The code as it stands uses several booleans — I counted around six, and I suspect there are more in the code branches we weren’t shown. In order to figure out whether the user is allowed to view an episode, the code effectively rummages through the user’s past, looking for a confluence of events that combine together to give the user that permission. And so when the code doesn’t do what was expected, poor Avdi then has to do the same, only using the debugger or logging statements. The problem therefore, it seems to me, is that the current state of the user is only represented indirectly.

It seems to me that this code breaks the second rule of Simple Design, in that the domain is not represented faithfully by these booleans. I would be willing to bet that not every one of the 2n possible combinations of values of these booleans is possible. Indeed, it seems likely that there are only a handful of states in the lifecycle of a user. So to use a group of booleans to represent these states is to misrepresent the structure of the domain: The representation permits many more possibilities than can actually occur, and leaves the job of figuring out the current state to a bunch of other methods scattered through a couple of different objects. Another way to express this might be to say that the code shows Connascence of Meaning (or Algorithm), because numerous methods need to know something about how the user’s state is represented.

So my solution would be to create an explicit state transition model for users, and then to represent that in the code using a state field on the user. It would then be possible to produce errors such as “User X cannot do Y because s/he is in state Z”. It also opens up the possibility of using the State pattern, so that the user would hold a reference to an object representing its current state. Such an object might know how and when the user arrived in this state, and have code that validates the user’s state changes. It might even provide the valid onward transitions as, say, Command objects.

So that’s my approach, and I’ve been finding it more and more useful recently to solve modelling problems such as this. The question is: is this applicable in Avdi’s case; does the code we haven’t seen support this design…?

Sinatra/Heroku microservices

I spent some of this weekend working on a side project. It began as a monolithic Sinatra app, then became two apps, and then finally the design settled on five microservices. At some point in this evolutionary journey I had a separate git repository for each microservice. But some of them wanted to share code, so I also had yet another git repository for each shared library, with the shared code included via git submodules.

This was a nightmare to work with, particularly as all of these git repositories were evolving simultaneously. So I wondered whether I could have a single git repository containing the code for all five microservices. But then how could I deploy them as separate Heroku apps? The answer lies in this Heroku article about managing multiple environments:

For simplicity, imagine we have a single git repository containing two Sinatra apps, stored in app_a.rb and app_b.rb. First, create a heroku app for each:

$ heroku create --remote app_a
...
$ heroku create --remote app_b
...

Now set an environment variable in each, telling it which of the two apps it is:

$ heroku config:set WHICH_APP=app_a --remote app_a
$ heroku config:set WHICH_APP=app_b --remote app_b

And finally in config.ru I configure Rack to start the app that matches the environment variable in each instance:

require 'rubygems'

service = ENV['WHICH_APP']

if ['app_a', 'app_b'].include?(service)
  require File.join(File.dirname(__FILE__), service
  run Sinatra::Application
else
  abort &quot;Unknown microservice '#{service}'&quot;
end

Now, when I push to Heroku:

$ git push app_a master
$ git push app_b master

each Heroku app will launch a different Sinatra app.