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

Trackback URI | Comments RSS