I dropped in to Ernie's place a while back and he asked me to stay and help calibrate his new Drilling Device. It was an impressive looking machine consisting of a large raygun-like thing mounted on an x-y translation table. An electronic eye was supported above the table, and to one side was a box with two buttons, one red and one blue.
Ernie explained that he was sick of drilling countless holes in sheets of steel manually, so he had built this tool to do the job automatically. "The extraordinarily accurate x-y table has precisely 1000 mm x 1000 mm of travel, so I can cut holes anywhere within an area of one square meter - accurate to the nearest micron. The drill uses an incredibly powerful laser to drill the holes so it takes absolutely no time at all to make the hole. The translation stage has enormously powerful, but restrained, drive motors so it can move the drill between any two locations in the one metre square area at a speed of precisely 1 m/s."
"But how does it know where to drill the holes?", I asked.
"Ahh", Ernie replied, "I felt that an analogue approach was more desirable than a digital one for this job, so you just mark where you want to put the holes on the steel sheet with these two special pens. You draw a circle with the red pen and that is where the drill puts the first hole, and you add a series of crosses with the blue pen to tell the drill where to put the rest of the holes. The electro-mechanical brain works out what path to follow and when to drill"
It felt like a typical Ernie invention - weirdly simple in some ways, but bizarrely complicated in other ways. "Tell me more?", I asked, "what do the two buttons do?". And Ernie explained that each button followed a very exact algorithm.
If a red circle exists:
Move the drill, in a straight line, from its current position to the centre of the red circle.
Drill a hole.
While un-drilled blue crosses exist
Move the drill, in a straight line, to the centre of the nearest blue cross,
Drill a hole.
Ernie asked me to mark a plate so we could test the system. I marked the first plate with exactly one red circle and five blue crosses (the plate was a bit oversize so there was plenty of room to mark all the drill-points within the central 1000 mm x 1000 mm square that the drill could reach.). We mounted the plate and Ernie pressed the Red button - the drill moved until it was exactly over the red cross. Then he pressed the Blue button and simultaneously started a stop-watch. There were 6 bright flashes (and a little more flying molten steel than I had expected) as the drill made the holes in the plate. At the exact moment the sixth hole was made, Ernie stopped the watch.
"Hmmm", he exclaimed, and then very carefully measured the positions of the holes in the plate with a ruler. "You seem, quite by chance of course, to have chosen hole positions that maximize the time required for the drill to complete the Blue algorithm for six holes!".
This only happened a few weeks ago ago but Ernie never told me exactly how long it took the Blue algorithm to drill the six holes, or where (exactly) in the steel in the sheet I drew the red circle. Can you help me?
If that is all to easy, I plan to visit Ernie around Christmas and would love to play with his head by "quite by chance" marking out a seven hole plate which maximizes the Blue algorithm time, so knowing where to mark the red circle and six blue crosses would be useful. Ernie only uses his second-best stop-watch and ruler for this kind of job, so positions accurate to the nearest micron, and times to the nearest microsecond should be sufficient.