Sunday, July 23, 2017

Gary Cipolloni's Clock Puzzle

Gary Cipolloni, my computing teacher in eleventh or twelfth grade, was charismatic, and subtly counter-cultural. Equally comfortable in leather motorcycle gear or the polyester professional-wear of the time, Mr. C. would flit around the lab telling jokes and shelling pistachios, the snack he never stopped eating. The story people told was that in his student days, he'd broken new administrative ground at the University of Michigan's Dearborn campus by using FORTRAN to fulfill the foreign language requirement. (I doubt it.) I learned a great deal from him.

Mr. C. assigned us projects, but often he merely suggested them. One idea he floated was that the class might determine which of the little LED bars in a digital clock stayed lit the longest during a twelve-hour period. I don't think any of us ever found the answer.

I did try the clock LED problem, not in the PASCAL language we were studying in class, but using a BASIC program on my Commodore 128 at home. The 128 was a fantastic machine for its time, and it was a major upgrade from my old Commodore 64—itself practically a Cray compared to the machine I had started on, which was the revolutionary VIC-20.

BEHOLD! The VIC-20. Image from the VIC-20 article on Wikipedia. 

God, the hours I spent on that VIC-20! The machine had 3k of RAM. Until we added a tape drive the following year, whatever program I was writing would be permanently erased as soon as the computer was turned off. So I used to write down my programs in a notebook, and that way if I wanted to run an old program again, I just typed it line by line from the notebook. A couple of years later, I upgraded to the Commodore 64. Then came the Commodore 128, with a much more powerful BASIC language.

I don't remember the answer my program gave to the clock LED problem, but whatever it was, it was probably wrong. Not that the problem is especially hard, just that I remember that I wrote an overly complicated program to solve it and likely ended up with garbage as output.

Over the years I've often thought about Mr. C. and his clock puzzle. Finally this weekend I wrote a little program in Mathematica to solve the problem. The results are below, but first here is how to solve the problem without using a computer.

***

The clock design I worked with looks like this (these are home-made images):




Here are all the digits:


The clock display is of the form AB:CD:EF, where A stands for the hours tens-digit, B the hours ones-digit, C the minute tens-digit, D the minute ones-digit, E the seconds tens-digit, and F the seconds ones-digit. In each digit's place, there are seven LED bars, each turned on or off to form a specific digit. I number the seven LED positions from top to bottom, left to right, as follows:


So, some good quantities to calculate would be A1, …, A7, B1, …, B7, …, F7—where C4, for example, is the total number of seconds when the middle LED in the minutes tens-digit will be lit during the period from 12:00:00 to 11:59:59.

Here are a few examples of calculating these quantities:


  • C4. During the entire twelve-hour period, the minutes tens-digit will cycle a whole number of times through the values 0, 1, 2, 3, 4, 5, so that each digit gets an equal share of the time. Now when 0 and 1 are showing, the middle LED is dark; when 2, 3, 4, and 5 are showing, the middle LED is lit. So the middle LED is lit 4/6 = 2/3 of the time. We can write C4 = 2/3T, where T is twelve hours.

  • C5. When 1, 3, 4, and 5 are showing, the lower-left LED is dark; when 0 and 2 are showing, the lower-left LED is lit. So the lower-left LED is lit 2/6 = 1/3 of the time. Thus C5 = 1/3T.

  • B7. During the twelve-hour period, the hours ones-digit will progress through the values 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1. When 1, 4, 7 and 9 are showing, the bottom LED is dark; when 0, 2, 3, 5, 6, and 8 are showing, the bottom LED is lit. So the bottom LED is lit 7/12 of the time. Thus B7 = 7/12T.

  • A3. During the twelve-hour period, the hours tens-digit will show a 1 for three hours and will be blank for nine hours. When the digit is blank, the upper-right LED is dark; when 1 is showing, the upper-right LED is lit. So the upper-right LED is lit 3/12 = 1/4 of the time. Thus A3 = 1/4T.


A shortcut: once you calculate the Ei and Fi values, you've also calculated the Ci and Di values. The same events happen in the seconds display and the minutes display, and each event in the seconds display happens sixty times as often as its corresponding event in the minutes display, but it only lasts for a sixtieth of the time. So the aggregate time for a given event is the same in the seconds display as in the minutes display.

The largest fraction turns out to be 9/10, for D6 and F6. The final answer is therefore a tie between the lower-right LED in the seconds ones-digit and the lower-right LED in the minutes ones-digit, both of which are lit 90% of the time. The next-closest fraction is 5/6, which occurs for six different LEDs.

***

Here is the computer output, shown several ways.

The fractions:

A: 0, 0, 1/4, 0, 0, 1/4, 0
B: 2/3, 1/2, 5/6, 2/3, 5/12, 5/6, 7/12
C: 2/3, 1/2, 5/6, 2/3, 1/3, 5/6, 2/3
D: 7/10, 3/5, 4/5, 7/10, 2/5, 9/10, 3/5
E: 2/3, 1/2, 5/6, 2/3, 1/3, 5/6, 2/3
F: 7/10, 3/5, 4/5, 7/10, 2/5, 9/10, 3/5

A heat map. Pure blue corresponds to never being lit, and pure red corresponds to always being lit:


A 3-D plot, where the height of each prism corresponds to the total time the LED is lit:


Coding has changed a lot since my high school days. The old acronyms are no more, and the tools are vastly more powerful; but many of the principles I learned as a kid are still relevant. Thanks Mr. C. for all you taught me.

No comments: