Just a Little Impossible: Morris Counting

I'll often advise entrepreneurs I talk with that it's ideal if their Software Idea is just a little impossible. ProgrammingPraxis recently published a challenge / solution that fits this description well. It's quirky, but still instructive. Here's my own word-problem based description of the challenge:

Imagine you're given the task at counting entrants to the state fair (yum!). Your boss hands you one of those crowd counter devices and walks away. As you examine the counter you realize that it only counts up to 255. Once the 256th person walks in, your screwed. The counter won't work anymore.

What do you do? Pray that the state fair has 254 attendees? Flee for your life? If you're Robert Morris, you get creative and devise a new way of counting, one that solves this seemingly impossible problem.

Here's what you do: you borrow a coin from your fellow fair employees and you stand by the gate. The first time someone walks in, you click the counter. Now it reads one. The next time someone walks you, you look down at the counter and flip the coin however many times is shown on its face. If your coin comes up heads every time, then you click the button to increment the counter. And repeat.

So if the counter says 8, then you have to flip the coin 8 times in a row. And if you get heads 8 times (unlikely, but do it enough, and it'll happen), you increment the counter to 9.

When your boss comes by and asks how many people visited the fair you bust out your pocket calculator compute 2^x-1, where x is the number shown on the counter.

Of course, this won't be the exact number of people who visited the fair, but it will be in the ballpark. It'll certainly tell you if there were 10's, 100's or 1000's of visitors that day. And that's far better data than having nothing.

Here's some random executions of the this algorithm:

In some cases, the number is pretty accurate (524 was estimated at 511, 242 was estimated at 255). In other cases, it's pretty out there (2956 vs. 4095). But still, considering that you're making use of nothing more than a very limited counter and a single coin, the results are quite impressive.

The bigger lesson though is the recipe at play here: find a problem which others think is impossible, solve it, and you're on your way to changing the world. That's not too much to ask, is it?

Here's the code that implements the above algorithm:

;;
;; http://programmingpraxis.com/2015/02/20/morris-counting/
;;

(define (show . words)
 (for-each display words)
 (newline))

(define (heads? n)
 (let ((flip (= 1 (random-integer 2))))
  (cond ((not flip) #f)
        ((and flip (= n 1)) #t)
        (else (heads? (- n 1))))))
        
(define (int-count n)
 (+ 1 n))
 
(define (morris-count c)
 (cond ((= c 0) 1)
       ((heads? c) (int-count c))
       (else c)))
       
(define (morris-value c)
 (- (expt 2 c) 1))
  
(define (trial upper)
 (let loop ((n (random-integer upper))
            (i 0)
            (c 0))
  (cond ((= n 0)
         (show "actual=" i ", morris=" (morris-value c)))
        (else
         (loop (- n 1)
               (int-count i)
               (morris-count c))))))
               
(define (test)
 (for-each trial '(10 50 100 200 500 800 1000
                   1500 2000 5000 7000 10000)))