Nov
17
2009
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
Possibly-related Articles:                                        
(auto-generated)
Sep
26
2009
#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:
Possibly-related Articles:                                        
(auto-generated)
Aug
17
2009
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.
Possibly-related Articles:                                        
(auto-generated)
Jul
21
2009
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).
Possibly-related Articles:                                        
(auto-generated)
Jul
15
2009
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.
Possibly-related Articles:                                        
(auto-generated)