Monday, February 23, 2015

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 2x-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)))

7 comments:

  1. Anonymous10:48 AM

    That's a lot of flipping.

    ReplyDelete
  2. True that.

    I suppose there's no such thing as a free lunch.

    ReplyDelete
  3. "find a problem which others think is impossible, solve it, and you're on your way to changing the world". That is doing science. Cool!

    ReplyDelete
  4. That is a great story. I would make the hand-help counter my base-256 counter, my first slot, and my right pocket would be the second slot. Every time I got to 256 I would rip off half of their ticket and keep it in my right pocket. Worst case, 8 full tickets would take minimal space and handle 4096 counts. The fund part about the story is abstraction and representation of numbers. Very fun.

    ReplyDelete
  5. > . Every time I got to 256 I would rip off half of their ticket and keep it in my right pocket. Worst case, 8 full tickets would take minimal space and handle 4096 counts

    Nice!

    ReplyDelete
  6. Those were the days of wooden computers and iron programmers; we current programmers truly stand on the shoulders of giants.

    ReplyDelete
  7. > Those were the days of wooden computers and iron programmers; we current programmers truly stand on the shoulders of giants.

    So true!

    ReplyDelete