Winner of the minimum coin problem

I posted a puzzle about coins and change and promised a prize (a copy of The Geek Atlas) to one of the solutions picked by me. The following people provided solutions:

1. Matt

2. Michael Bauer

3. Asger Drewsen

4. vext01

5. Dubya

6. Josh

7. Anatoli Plotnikov

8. Matt Hickford

As that's a convenient 8 people I've chosen a winner by the roll of a d8.

 So the winner is #7, Anatoli Plotnikov.

The Four Power Days

Today, May 5 is written 5/12 in the US and 512 is a power of 2, it's \(2^9\). I tweeted that and received a rapid reply from Peter Inglesby that in UK-style dates it's 12/5 which is 125 which is \(5^3\). Which made me wonder whether there were other dates that had the same property in the US and UK on the same day.

Peter wrote a quick script:
and determined that there are four such dates:

March 24: US 3/24; \(324 = 18^2\). UK 24/3; \(243 = 3^5\)

May 12: US 5/12; \(512 = 2^9\). UK 12/5; \(125 = 5^3\)

June 25: US 6/25; \(625 = 5^4\). UK 25/6; \(256 = 2^8\)

December 5: US 12/5; \(125 = 5^3\). UK 5/12. \(512 = 2^9\)

Now I just need to think up a mystical significance to this, start a religion and retire on the proceeds.

A home made periodic table

One of my slow burn projects has been to make and display a periodic table of elements using element samples that I have been able to find or make myself. This is what it currently looks like:

The poster itself is actually a blown up version of the poster that comes with the quirky book Wonderful Life with the Elements: The Periodic Table Personified by Bunpei Yorifuji. Each element is represented by a person (or robot) and characteristics of the person reflect the element itself (such as its state at 'room temperature', its radioactivity, and when it was discovered).

Having got the poster enlarged I had a custom frame made using the cheapest online source I could find. To store each element I'm using 1/2 dram clear glass vials with black polypropylene caps that are lined with polyvinyl. This vial are very small (they are pictured here with my international object sizing tool) so that the overall periodic table is not too large.

It is possible to buy samples of the elements quite easily, but I wanted to obtain them from the world around me for the fun of learning more about them and to be cheap.

I extracted nitrogen from a can of Illy coffee where it is used to pack the coffee, hydrogen came by reacting a little NaOH with Al, oxygen via electrolysis of water, tungsten from a broken halogen light bulb, iron fillings I had lying around, lead came from my roof, copper from wire I had, germanium from an old diode, etc.

It's rather slow to build the table like this, but the original motivation came from reading Oliver Sacks' Uncle Tungsten and a desire to learn more about the elements themselves. For example, even simple old iron has lots of interesting things to know about such as its allotropes and the Curie temperature.

The two problems I had to solve in my Oxford interview

Back in the 1980s I went to Oxford University and studied Mathematics and Computation (this was almost the entire Mathematics course plus Computer Science added on; the degrees offered today are a little different).  Having sat the mathematics entrance exam and gone through all the mathematics interviews I had interviews in the Programming Research Group (now the Department of Computer Science). During those interviews two specific programming/algorithm design questions were posed. Here they are (I made up names for them).

The Z Machine

A computer is constructed with a simple memory layout. It has an unlimited amount of memory and each memory location is numbered so that a program can refer to it. Each memory location can store a single number or be uninitialized. In the following diagram memory locations that are blank are uninitialized some other memory locations have numbers in them.

The computer's CPU only has three instructions Z, I and J as follows:

Z. This instruction zeroes a memory location. For example, Z2 sets memory location 2 to 0, Z42 sets memory location 42 to 0.

I. This instruction adds one to the contents of a memory location. For example, I3 adds 1 to whatever is currently stored in location 3.

J. This instruction examines the contents of two memory locations and branches if the contents are different. For example J18,19 would compare the contents of memory locations 18 and 19, if they are the same the program continues with the next instruction, if different it branches. The branch destination is just specified by drawing an arrow to the instruction you want to go to.

When there are no more instructions the program stops.

For example, here's a loop that keeps adding one to memory location 4 until it equals memory location 20.

1. The operator of the machine places two numbers (one each) in memory locations 0 and 1. Here, for example, the operator has put 3 in location 0 and 4 in location 1. Write a program using the Z, I and J instructions to add those (arbitrary) numbers together and put the result in memory location 2.

2. Under what circumstances does this program fail?

The One-eyed Robot

(If you've studied computer science you may recognize this problem)

On the ground along Keble Road there are a line of n buckets, in each bucket is a single ball. The balls are red, green and blue. A robot is to be programming to sort the balls so that there's one ball in each bucket still but the colours are now in the order red, green, blue. So, working from left to right an observer will see all the red balls in buckets, then all the green balls in buckets, and finally all the blue balls.

The robot is only allowed to examine one ball at a time by peering into its bucket and is only allowed to examine each ball once. When it looks at a ball it must decide what to do with it. The robot has two arms and the only ball manipulation it can do is swap the balls in two buckets.

1. Program the robot to sort the balls.

2. Write out a proof that the proposed algorithm works.

Note

Of course, a whole load of other questions were asked about program running time, correctness and what I later realized was the lambda calculus. But these were the two main 'programming' tasks.

From the ground up (or how to encourage a school boy)

Following on from my popular blog post about coding by hand in 1985 I dug into my pile of old stuff to look at how myself and another boy at school reverse engineered the Research Machines CHAIN network and built everything from networking protocols to a network management system in assembly language.

In 1982 Research Machines in the UK launched the LINK 480Z Z80 based machine that had an optional 800kbps proprietary network called CHAIN. My upper school got a small network of them linked to a file server running MP/M. The 480Z's would boot from the file server across the network.

Unfortunately, the entire network protocol was undocumented by Research Machines and unpublished. Myself and another boy, P, decided to reverse engineer because we wanted boot control and we wanted network access. Disassembling the running operating system (often using its front panel, which was on screen and not via flashing lights) we were able to determine that the Z80 RST 8 instruction was used to send/receive packets on the network.

The CHAIN network supported up to 255 machines (each machine had an 8-bit DIP switch to set its address) and was similar in operation to Ethernet in that packets could be lost when collisions occurred. The built in operating system provided access to files on the file server; we wanted much more. Specifically, we wanted reliable remote control of any machine on the network.

Once we had decoded how RST 8 worked we quickly realized that (a) we could see every packet on the network and so could build a protocol analyzer (we built that and called it NETSCOOP) and then built a program just to watch file system access by all other users and see what files they were reading/writing and grab their contents.

But that was just passive so we went a bit further. P came up with the idea of building a reliable protocol on top of the unreliable CHAIN network. His idea was to send a sequence number in each packet and then acknowledge the packet (I don't recall whether he read about this idea or came up with it alone). If we didn't get the acknowledgement then after a delay we'd resend. He wrote up some Pascal pseudocode and I coded what we called 'safe network transactions' in assembly language:

Once we'd got that coded we were able to start building up a network OS of sorts. The first step was to build something we called NMBOS which gave us basic functions across the network to any machine running it.

The most interesting feature of that is that it operated using what we called 'worms': executable code sent directly to the machine and executed in the packet buffer. We had all this working in 1984, but it appears I added nice comments to the code and printed everything out in 1986.

The word 'worm' is interesting because this all precedes the famous Morris Worm by a few years and I'm pretty sure we got the name from John Brunner's Shockwave Rider.

This worked by simply assembling some function you wanted executed and then sticking it in the send buffer and reliably sending it to the remote machine which would simply execute it. By using self-modifying code we could prepare routines to be executed remotely and modify them before a send. Here's the actual receive handler. In the middle you can see the call into the packet buffer. We only had (if memory serves) about 128 bytes of receive space, but it was plenty.

Having built that we created the NMIOS which used the worm functionality to provide slightly higher level function (such as writing characters to the screen, insert characters into the keyboard buffer, and even reading and writing arbitrary memory locations on the remote machine!). The NMIOS could also be called from Pascal or assembler.

From there we were able to build the manager system called NETCON which allowed the teacher to control all the machines simultaneously and included a 'virtual blackboard' mode where they could write to the screens of all machines. Other functions allows them to freeze machines (to get the pupils to pay attention). After that we went on to write two-way chat programs, peer-to-peer file transfer and a nice program that linked two CHAIN networks together of a 1200 baud modem (essentially a router).

We also hacked the boot mechanism for the entire network so that our NMIOS was included in the boot image and even added password protection on top (P did that work managing to stuff the whole thing into a 'space' in the boot image). We had different levels of password protection for pupils, teachers and ourselves.

During 1984 I wrote to Research Machines and asked them for assistance. I was hoping they'd give me documentation to RST 8 so that I could have the official information not what we'd reverse engineered. I received the most wonderful reply.

That's the spirit! And very encouraging to a school boy.