Programmer’s Diary

I’m taking part in Al Zimmermann’s latest programming contest, Son of Darts. The idea of the contest is to select values for the regions on a dartboard. The aim is for a number of darts to make as many consecutive values as possible.

For example with 6 darts and two regions with values 1 and 5, it’s possible to make any value from 1 to 18, but not 19.

Being a lazy programmer, I’ve coded a dumb brute force attack rather than taking the time to come up with a fancy algorithm. So far I’ve found the optimal solution for 1 to 6 regions and I’m reached rank 130 in the standings!

Here’s the program I’m using, written in BASIC. Unfortunately it’s incredibly slow Can you see any obvious improvements?:

10 regions=3
20 high=0
30 dim r(regions+1)
40 max=5000
50 dim s(max)

60 for a=1 to regions+1
70 r(a)=a-1
80 next a

90 for a=1 to max
100 s(a)=0
110 next a

120 for c=1 to regions+1
130 for d=c to regions+1
140 for e=d to regions+1
150 for f=e to regions+1
160 for g=f to regions+1
170 for h=g to regions+1
180 s(r(c)+r(d)+r(e)+r(f)+r(g)+r(h))=1
190 next h
200 next g
210 next f
220 next e
230 next d
240 next c

250 best=0
260 best=best+1
270 if s(best)=1 and best<max then goto 260
280 if best<high then goto 350

290 high=best
300 print best,
310 for a=2 to regions+1
320 print r(a);
330 next a
340 print

350 ptr=regions+1
360 r(ptr)=r(ptr)+1
370 if r(ptr)>best then goto 390
380 if r(ptr)<1000 then goto 90
390 r(ptr)=r(ptr-1)+2
400 ptr=ptr-1
410 if ptr<>2 then goto 360
420 stop

#songsincode is a trend which started on Twitter a few weeks ago. The idea is to express the title or lyrics of a song as a computer program. Here’s an example by Roy van Rijn:

for(Leaf leaf:leafs)
{leaf.setColor(new Color(139,69,19));}
sky.setColor(Color.GRAY);

This is California Dreamin’ by the Mamas and Papas, “All the leaves are brown and the sky is gray”. If #songsincode is of interest, here are some of the best collections I’ve found:

• #songsincode - Lyrics for Programmers - a countdown of the finest #songsincode
• songs in code at wee doors banging - a selection of #songsincode by John Girvin
• Songs in Code at Juixe Techknow - an early collection of about 60 #songsincode
• #songsincode on redcode.nl - a selection of #songsincode by Roy van Rijn
• Songs in Code Database - automatically updated with the latest tweets

I’ve just rediscovered a project I started in 1997 and have always intended to go back and complete one day. The project is a small operating system suitable for microcontrollers.

The OS will provide the following functionality, similar to a MicroKernel:

• memory management (done)
• preemptive task switching (done)
• process management (done)
• inter process communication

Memory Management

Memory is divided into variable size block, each preceded by a small memory control stucture. The structure contains the following:

• link to previous block
• link to next block
• link to owner of block
• length of block
• in use flag: is this block available?
• ready flag: is process ready to execute?
• stack pointer: sp saved when not active

Functions to allocate / free memory are provided. Have I missed anything important?

Task Switcher

The task switcher is called by the timer interrupt and switches to the next available task. Switching is disabled while memory is being allocated / freed.

Process Management

Functions are provided to create new processes, kill processes, mark a process as available or blocked. Switching is disabled while processes are being manipulated.

Inter Process Communication

Semaphores and message passing will be implemented. Unfortunately, I stumbled across a problem. How do I get two processes to agree which semaphore / message to use?

Should they be numbered, named or referred to by an address in memory? Should a semaphore / message buffer be allocated to each process or block of memory? If named, how should I handle name collisions?

Any advice on implementing IPC would be appreciated.

At the moment I have two major projects on the go, but so far this week I’ve only written seven lines of code! Despite this I’ve managed to either read or skim through a variety of papers / articles about programming (listed below).

It’s got to stage where I need to tell myself the same thing most recreational programmers need to be told from time to time:

Stop reading about programming and get some actual programming done.

Here are the papers I’ve read, all unrelated to either of the projects I’m working on!

• On µ-Kernel Construction, Jochen Liedtke, 1995. On the design and implementation of micro kernels.
• The Nucleus of a Multiprogramming System, P Brinch Hansen, 1970. A early paper describing a micro kernel.
• Updating the Forth Virtual Machine, Stephen Pelc, 2008. Explores some changes to Forth, notably address registers.
• Bubble Sort: An Archaeological Algorithmic Analysis, Owen Astrachan, 2003. Investigates the history of Bubble Sort.
• Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey), Paul Vitányi, 2003. In depth.
• A Fast Easy Sort, Stephen Lacey and Richard Box, 1991. Describes Comb Sort (also known as Dobosiewicz Sort).

Implementing my own Forth interpreter is taking a little longer than anticipated. Each Forth word is almost like a puzzle. What’s the smallest number of words each can be written in? What’s the most efficient implementation? For an example, take a look at Implementing MIN in Forth without Conditional Code. The smallest version of MIN is 2 words shorter than eForth’s MIN.

Even words with a trivial implementation can pose an interesting problem. For example which of the following is most efficient:

Jones Forth TUCK (Corrected)

: TUCK DUP -ROT ;

Alternative TUCK

: TUCK SWAP OVER ;

If DUP, -ROT, SWAP and OVER are all primative, the alternative implementation will execute two fewer instructions on an 80×86 Forth. However, -ROT is often implemented in Forth which would cause the Jones Forth TUCK to be substantially slower. Here’s a typical implementation of -ROT:

: -ROT SWAP >R SWAP R> ;

Note: there’s an error in Jones Forth. The implementation of ROT and -ROT are reversed.

If you can think of an alternative two word implementation of TUCK or four word implementation of -ROT, please let me know.