Friday 12 September 2008

Al Zimmermann's Programming Contests

Normally I don't participate in programming challenges, but something about the latest of Al Zimmermann's Programming Contests caught my attention.

The idea is to submit sets of numbers so their combination by addition and subtraction generates the most distinct primes.  There are 12 problems, for sets of 3 to 14 numbers.

A pen and paper should be sufficient to find the optimal solution for 3 numbers.  Don't be fooled however, the solutions for 4+ require a program to search through the possibilities.

4 yields easily to a computer search with at least three optimal solutions waiting to be discovered.  Despite writing a program which tests 280,000 potential solutions per second, I haven't found the top solution for 5.

Currently I'm restricting the search space to one odd number, one multiple of 6 and the remaining numbers all multiples of 30.  Maybe this is too restrictive?

Here's the program I'm using.  Any suggestions how I can improve the speed?
n1 equ 1
n2 equ 6
n3 equ 30
n4 equ 90
n5 equ 270

i1 equ 600
i2 equ 600

vprime equ 7000

numb equ 5

; *** generate list of primes

mov si,prime+4
mov bx,5
mov di,prime+2
mov ax,bx
xor dx,dx
div word[di]
or dx,dx
jz notpr
ja try
mov word[si],bx
inc bx
inc bx
cmp si,prime+vprime
jne nextpr

; *** fill prime table with zero

xchg ax,bx
mov di,tabl
xchg ax,cx
xor ax,ax
rep stosb

; *** update values to test

add word[xa],2
cmp word[xa],n1+i1+10
jc gogo
mov word[xa],n1

add word[xb],6
cmp word[xb],n2+i2+10
jc gogo
mov word[xb],n2

add word[xc],30
mov ax,word[xc]
cmp ax,word[xd]
jc gogo
mov word[xc],n3

add word[xd],30
mov ax,word[xd]
cmp ax,word[xe]
jc gogo
mov word[xd],n4

add word[xe],30

; *** mark primes in table

mov ax,word[xa]
add ax,word[xe]
add ax,word[xd]
add ax,word[xc]
add ax,word[xb]
xchg dx,ax
mov si,prime
cmp dx,ax
jc fini
add ax,tabl
xchg bx,ax
mov byte[bx],1
cmp si,prime+vprime
jne ptab

; *** test

xor bp,bp
mov ax,word[xa]
mov bx,word[xe]
mov cx,word[xd]
mov dx,word[xc]
mov di,word[xb]

call x2

; *** if there's a new top score...

xchg ax,bp
cmp ax,word[xhigh]
jl next

; *** ... display the winning numbers

mov word[xhigh],ax
call printdec

mov dl,' '
call printchar
mov dl,'-'
call printchar

mov cx,numb
lea si,word[xa]
mov dl,' '
call printchar
call printdec
loop disp

mov dl,0D
call printchar
mov dl,0A
call printchar

; *** and repeat

mov ah,1
int 016h
jz redo
int 020h
jmp testnew

push ax
add ax,bx
call x3
pop ax
push ax
sub ax,bx
call x3
pop ax

push ax
add ax,cx
call x4
pop ax
push ax
sub ax,cx
call x4
pop ax

push ax
add ax,dx
call x5
pop ax
push ax
sub ax,dx
call x5
pop ax

push ax
add ax,di
call x6
pop ax
push ax
sub ax,di
call x6
pop ax

neg ax
js xabs
add ax,tabl
xchg ax,si
cmp byte[si],0
je notprx
inc bp
mov byte[si],0
xchg ax,si

; *** print number in ax

push ax
push cx
push dx
mov cx,10
xor dx,dx
div cx
test ax,ax
je pdbye
call printdec
add dl,'0'
call printchar
pop dx
pop cx
pop ax

mov ah,2
int 021

xhigh:dw 0

xa:dw n1-2
xb:dw n2
xc:dw n3
xd:dw n4
xe:dw n5

dw 2
dw 3

tabl equ prime+vprime+10

No comments:

Post a Comment

Note: only a member of this blog may post a comment.