Computer
Programming Tournament
January's
Contest: Our
first programming challenge ran for 48 hours from 5pm GMT on Sunday 23rd January and is outlined below:
Your
program will solve the classic 8-puzzle, where
numbers in a square 3x3 frame are slid one at a
time to adjacent squares. The solution is to form
a grid as follows:
from
any valid starting position. The program must
print out the tiles to move as a sequence of
numbers, and must calculate an optimal solution (shortest
number of moves).
Sample
data to run on your program:
|
The winner of the $500 First Prize awarded in the first contest was John Knoderer of
Sulphur Springs, AR in the United States of America,
pictured left. John is known as "The Maze Man" and justly proud
of his excellent and popular mazes
web site. As well as writing the best-scoring entry, John
investigated the problem further still, and his findings follow.
He wrote his program in two hours and seven minutes using Quick
Basic Extended QBX 7.1, and the 884-byte program ran in 1
minute and 52.98 seconds. His program found three correct solutions,
each of which involves 24 swaps: 657316573175678278241256, 657316573175628728741256 and 638218753687542175421458.
The program follows, with added comments:
|
DEFINT B-R
DEFSTR S-Z
a = TIMER 'a = starting time, in seconds
zz = "xxxxxxxxxxxxxxxxxxx" 'string: starting/current patterns
yy = zz 'format to hold the target pattern
DATA 4,7,5,8,3,6,2,1,0 : 'numbers for the starting position
FOR r = 1 TO 3
FOR c = 1 TO 3 'this set of nested
READ g 'FOR-NEXT loops inserts
j = (j + 1) MOD 9 'start #'s into 'zz',
MID$(yy, r * 4 + c) = CHR$(j + 48) 'and inserts target #'s
MID$(zz, r * 4 + c) = CHR$(g + 48) 'into 'zz'
NEXT
NEXT 'data files keep track of the patterns
CLS 'after each slide and moves to there.
OPEN "O", 1, "Slide-1" 'First file contains STARTING POSITION
PRINT #1, zz; ",," 'with zero moves in two move buffers.
d = 1 'd keeps track of if answer found yet?
d(0) = -4
d(1) = -1 'd(n) are the four directions you can
d(2) = 1 'slide a number.
d(3) = 4 'UP=-4, LEFT=-1, RIGHT=+1, DOWN=+5
1 l = l + 1 'l is the level currently working
PRINT l 'the number of slides to current place
CLOSE
OPEN "I", 1, "Slide" + STR$(-l) '1st file: all patterns
'that existed after L
'slides were taken.
OPEN "O", 2, "Slide" + STR$(-l - 1) '2nd file: all patterns
'that will exist after
'this slide.
WHILE NOT EOF(1)
INPUT #1, z, s, v 'read the next pattern out of file L.
k = INSTR(z, "0") 'look for the BLANK spot (zero)
FOR e = 0 TO 3 'see if the slide UP/LEFT/RIGHT/DOWN
p = k + d(e) 'is a valid move.
t = MID$(z, p, 1) 'if the value of that MID$ position
j = VAL(t) 'is positive, then it is valid slide.
IF j = 0 THEN 8 'if zero, it's invalid.
x = z 'x will contain pattern AFTER SLIDE
MID$(x, k, 1) = t 'these two MID$ statements reverse
MID$(x, p, 1) = "0" 'the numbers corresponding to slide
u = s + t 'these two strings keep track of all
w = t + v 'moves in forward and backward order
IF x = yy THEN
d = 0 'if answer has been found,
PRINT u; TIMER - a 'display it along with # seconds
GOTO 8 'd=0 remembers at least one found
END IF
FOR i = 1 TO l \ 2 'skip storing
IF RIGHT$(u, i) = MID$(w, 1 + i, i) THEN 8 'step if this
NEXT 'was backward
'slide.
PRINT #2, x; ","; u; ","; w 'store current pattern
8 NEXT
WEND
IF d THEN 1 'keep going until answers are found.
END
John reported that we didn't set the most difficult competition
of this type possible, and here are his investigations:
Just in case it is of interest to you,
These starting positions are 31 moves away from solution:
647X850X321 31 steps, 40 answers
867X254X301 31 steps, 40 answers
In other words, translating to squares, we get:
6 4 7 8 6 7
8 5 0 2 5 4
3 2 1 3 0 1
And these starting positions are 30 moves away from solution:
017X254X368 30 steps, 8 answers
017X354X628 30 steps, 16 answers
021X584X367 30 steps, 22 answers
021X654X387 30 steps, 4 answers
021X864X357 30 steps, 10 answers
027X354X681 30 steps, 18 answers
027X651X384 30 steps, 28 answers
027X684X351 30 steps, 20 answers
027X645X381 30 steps, 18 answers
027X658X341 30 steps, 20 answers
031X654X827 30 steps, 6 answers
032X654X871 30 steps, 16 answers
037X645X821 30 steps, 22 answers
037X652X841 30 steps, 18 answers
047X158X326 30 steps, 8 answers
047X258X361 30 steps, 16 answers
047X358X621 30 steps, 26 answers
047X586X123 30 steps, 22 answers
047X618X325 30 steps, 60 answers
047X652X381 30 steps, 20 answers
047X658X312 30 steps, 32 answers
047X658X123 30 steps, 8 answers
047X865X123 30 steps, 17 answers
051X264X387 30 steps, 22 answers
051X684X327 30 steps, 14 answers
051X824X367 30 steps, 17 answers
053X862X741 30 steps, 4 answers
054X867X231 30 steps, 16 answers
057X468X123 30 steps, 22 answers
057X624X381 30 steps, 20 answers
057X684X312 30 steps, 6 answers
057X681X324 30 steps, 10 answers
057X684X123 30 steps, 16 answers
057X846X123 30 steps, 10 answers
061X284X357 30 steps, 17 answers
061X524X387 30 steps, 10 answers
061X854X327 30 steps, 10 answers
062X854X371 30 steps, 28 answers
063X582X741 30 steps, 4 answers
063X854X721 30 steps, 16 answers
063X872X541 30 steps, 8 answers
064X587X231 30 steps, 16 answers
064X857X321 30 steps, 10 answers
065X874X321 30 steps, 24 answers
065X832X741 30 steps, 8 answers
067X485X123 30 steps, 10 answers
067X548X123 30 steps, 17 answers
067X834X521 30 steps, 24 answers
067X852X341 30 steps, 4 answers
067X814X325 30 steps, 8 answers
067X824X351 30 steps, 4 answers
067X845X321 30 steps, 4 answers
067X851X324 30 steps, 4 answers
067X854X312 30 steps, 4 answers
067X853X421 30 steps, 28 answers
067X854X123 30 steps, 10 answers
067X854X231 30 steps, 10 answers
078X154X326 30 steps, 16 answers
078X254X361 30 steps, 26 answers
078X456X321 30 steps, 18 answers
078X654X231 30 steps, 20 answers
078X652X341 30 steps, 20 answers
078X653X421 30 steps, 12 answers
081X254X367 30 steps, 8 answers
081X564X327 30 steps, 16 answers
081X624X357 30 steps, 12 answers
082X354X671 30 steps, 12 answers
083X652X741 30 steps, 8 answers
084X357X621 30 steps, 20 answers
084X627X351 30 steps, 20 answers
084X637X521 30 steps, 16 answers
084X657X231 30 steps, 8 answers
085X672X341 30 steps, 64 answers
085X674X231 30 steps, 16 answers
086X724X351 30 steps, 22 answers
086X753X421 30 steps, 16 answers
086X752X341 30 steps, 18 answers
086X754X123 30 steps, 6 answers
087X214X365 30 steps, 60 answers
087X256X341 30 steps, 20 answers
087X251X364 30 steps, 32 answers
087X352X641 30 steps, 20 answers
087X452X361 30 steps, 20 answers
087X426X351 30 steps, 18 answers
087X465X321 30 steps, 20 answers
087X456X123 30 steps, 4 answers
087X456X312 30 steps, 28 answers
087X546X321 30 steps, 20 answers
087X564X123 30 steps, 14 answers
087X564X312 30 steps, 10 answers
087X561X324 30 steps, 6 answers
087X632X541 30 steps, 64 answers
087X645X231 30 steps, 20 answers
087X645X123 30 steps, 12 answers
140X687X235 30 steps, 24 answers
147X208X365 30 steps, 30 answers
147X528X036 30 steps, 15 answers
147X658X320 30 steps, 30 answers
150X247X368 30 steps, 15 answers
184X267X035 30 steps, 24 answers
187X254X360 30 steps, 30 answers
247X651X380 30 steps, 32 answers
281X354X670 30 steps, 12 answers
281X354X067 30 steps, 6 answers
281X564X037 30 steps, 19 answers
310X654X827 30 steps, 10 answers
314X657X820 30 steps, 12 answers
317X654X028 30 steps, 33 answers
320X647X851 30 steps, 12 answers
321X684X570 30 steps, 13 answers
|
321X674X085 30 steps, 56 answers
321X674X850 30 steps, 13 answers
321X604X587 30 steps, 35 answers
327X654X081 30 steps, 10 answers
347X682X510 30 steps, 33 answers
351X624X870 30 steps, 18 answers
382X654X071 30 steps, 33 answers
450X687X123 30 steps, 19 answers
470X658X123 30 steps, 6 answers
478X653X120 30 steps, 12 answers
487X256X310 30 steps, 32 answers
521X384X067 30 steps, 15 answers
521X304X687 30 steps, 14 answers
521X634X087 30 steps, 26 answers
547X218X360 30 steps, 12 answers
547X382X061 30 steps, 33 answers
547X608X321 30 steps, 45 answers
563X802X741 30 steps, 14 answers
570X268X341 30 steps, 33 answers
570X342X681 30 steps, 37 answers
570X468X123 30 steps, 15 answers
578X326X041 30 steps, 37 answers
578X406X123 30 steps, 14 answers
580X476X123 30 steps, 26 answers
587X204X361 30 steps, 45 answers
587X642X310 30 steps, 9 answers
587X621X340 30 steps, 9 answers
610X524X387 30 steps, 12 answers
617X254X380 30 steps, 32 answers
617X804X325 30 steps, 29 answers
621X354X087 30 steps, 6 answers
621X584X037 30 steps, 12 answers
621X834X057 30 steps, 15 answers
627X345X081 30 steps, 20 answers
627X804X351 30 steps, 32 answers
630X582X741 30 steps, 15 answers
631X804X257 30 steps, 25 answers
631X854X027 30 steps, 6 answers
640X857X321 30 steps, 6 answers
647X281X350 30 steps, 10 answers
647X352X081 30 steps, 7 answers
647X508X123 30 steps, 19 answers
647X582X310 30 steps, 17 answers
647X832X051 30 steps, 33 answers
647X851X320 30 steps, 29 answers
647X825X310 30 steps, 17 answers
647X805X321 30 steps, 5 answers
647X835X120 30 steps, 33 answers
647X832X510 30 steps, 16 answers
650X784X123 30 steps, 19 answers
650X834X712 30 steps, 24 answers
654X321X870 30 steps, 10 answers
654X321X087 30 steps, 12 answers
657X324X081 30 steps, 11 answers
657X438X012 30 steps, 37 answers
657X804X312 30 steps, 13 answers
657X814X320 30 steps, 9 answers
657X801X324 30 steps, 14 answers
657X821X340 30 steps, 8 answers
657X842X310 30 steps, 8 answers
658X721X430 30 steps, 26 answers
670X485X123 30 steps, 12 answers
687X251X340 30 steps, 29 answers
780X154X326 30 steps, 33 answers
780X456X321 30 steps, 10 answers
780X436X125 30 steps, 56 answers
780X653X421 30 steps, 33 answers
785X261X340 30 steps, 33 answers
785X406X123 30 steps, 35 answers
785X463X120 30 steps, 13 answers
786X154X023 30 steps, 10 answers
786X154X230 30 steps, 12 answers
786X435X120 30 steps, 13 answers
786X425X031 30 steps, 12 answers
786X543X120 30 steps, 18 answers
820X571X364 30 steps, 37 answers
821X364X057 30 steps, 12 answers
831X564X027 30 steps, 19 answers
832X547X610 30 steps, 26 answers
847X156X320 30 steps, 32 answers
847X265X310 30 steps, 10 answers
847X652X310 30 steps, 29 answers
850X467X123 30 steps, 12 answers
851X204X367 30 steps, 19 answers
853X762X041 30 steps, 15 answers
857X146X023 30 steps, 12 answers
857X261X340 30 steps, 17 answers
860X275X341 30 steps, 33 answers
860X475X123 30 steps, 15 answers
860X754X123 30 steps, 6 answers
861X274X350 30 steps, 33 answers
863X571X024 30 steps, 24 answers
864X705X123 30 steps, 25 answers
865X271X340 30 steps, 16 answers
867X104X325 30 steps, 29 answers
867X204X351 30 steps, 5 answers
867X241X350 30 steps, 17 answers
867X254X310 30 steps, 29 answers
867X254X031 30 steps, 6 answers
867X405X321 30 steps, 32 answers
867X504X312 30 steps, 14 answers
867X514X320 30 steps, 9 answers
867X521X340 30 steps, 8 answers
867X542X310 30 steps, 8 answers
867X501X324 30 steps, 13 answers
870X256X341 30 steps, 7 answers
870X426X351 30 steps, 20 answers
870X456X123 30 steps, 6 answers
870X546X321 30 steps, 11 answers
870X546X213 30 steps, 12 answers
876X543X210 30 steps, 10 answers
|
I can give you starting positions for 29 down to 1 move away. I rewrote
yesterday's program this afternoon, working backward this time, starting with
the ending position and remembering every starting position that I reached.
It was fun.
I would have guessed that 876X543X210 would probably have had the
longest path to get to the starting position, so am surprised that
there are two longer sequences. It's also interesting to see how
some sequences have a vast number of different ways to go from the
start to the end while others can only be solved in a small number
of ways. Why should this be? I think there's material for a mathematical
research paper in there...
John then sent us his program which generates EVERY possible starting point,
and stores them in subdirectories along with every method that reaches to that
answer. Make sure the computer you use has at least 90 megabytes of space
free. When the program is done, you can delete the "slide-??." files, they
are the intermediate stages. The final results can be found by doing
directory searches.
DIR *.31 /S all patterns that can be solved after 31 moves
DIR *.30 /S etc.
DIR *.29 /S
Once you see the names of the files, you will be able to TYPE those files to
see all the ways to get from that starting pattern to the designated final pattern.
DEFINT B-R
DEFSTR S-Z
a = TIMER 'a = starting time, in seconds
zz = "xxxxxxxxxxxxxxxxxxx" 'string: starting/current patterns
yy = zz 'format to hold the target pattern
DATA 4,7,5,8,3,6,2,1,0 : 'numbers for the starting position
FOR r = 1 TO 3
FOR c = 1 TO 3 'this set of nested
READ g 'FOR-NEXT loops inserts
j = (j + 1) MOD 9 'start #'s into 'zz',
MID$(yy, r * 4 + c) = CHR$(j + 48) 'and inserts target #'s
MID$(zz, r * 4 + c) = CHR$(g + 48) 'into 'zz'
NEXT
NEXT 'data files keep track of the patterns
CLS 'after each slide and moves to there.
OPEN "O", 1, "Slide-1" 'First file contains STARTING POSITION
PRINT #1, zz; ",," 'with zero moves in two move buffers.
CLOSE
d = 1 'd keeps track of if answer found yet?
d(0) = -4
d(1) = -1 'd(n) are the four directions you can
d(2) = 1 'slide a number.
d(3) = 4 'UP=-4, LEFT=-1, RIGHT=+1, DOWN=+5
1 l = l + 1 'l is the level currently working
PRINT l 'the number of slides to current place
CLOSE
OPEN "I", 1, "Slide" + STR$(-l) '1st file: all patterns
'that existed after L
'slides were taken.
OPEN "O", 2, "Slide" + STR$(-l - 1) '2nd file: all patterns
'that will exist after
'this slide.
WHILE NOT EOF(1)
INPUT #1, z, s, v 'read the next pattern out of file L.
k = INSTR(z, "0") 'look for the BLANK spot (zero)
FOR e = 0 TO 3 'see if the slide UP/LEFT/RIGHT/DOWN
p = k + d(e) 'is a valid move.
t = MID$(z, p, 1) 'if the value of that MID$ position
j = VAL(t) 'is positive, then it is valid slide.
IF j = 0 THEN 8 'if zero, it's invalid.
x = z 'x will contain pattern AFTER SLIDE
MID$(x, k, 1) = t 'these two MID$ statements reverse
MID$(x, p, 1) = "0" 'the numbers corresponding to slide
u = s + t 'these two strings keep track of all
w = t + v 'moves in forward and backward order
IF x = yy THEN
d = 0 'if answer has been found,
PRINT u; TIMER - a 'display it along with # seconds
GOTO 8 'd=0 remembers at least one found
END IF
FOR i = 1 TO l \ 2 'skip storing
IF RIGHT$(u, i) = MID$(w, 1 + i, i) THEN 8 'step if this
NEXT 'was backward
'slide.
PRINT #2, x; ","; u; ","; w 'store current pattern
8 NEXT
CLOSE
KILL "Slide" + STR$(-l) 'delete temporary file when no
'longer needed.
WEND
IF d THEN 1 'keep going until answers are found.
END
Thanks for that, John! John won the competition on the speed
and quality of his entry, not because of this supplementary
work, but we were interested and intrigued by it - and glad that
he enjoyed taking part enough to take the investigation further.
Do you think you could do better? February's contest will be
bigger and better and has another $500 prize. A new set
of rules for February's contest will be released well in
advance of the contest, which will start at 5pm on Sunday,
February 13.
January Programming
Contest Rules
The
contest will set out a specific computing task.
Programmers will create a program to perform this
function using test data supplied by MSO. Once
you have completed your program, you must run
it on the test data,
note the elapsed time for the program run, and
enter this information on a form above. If your
program appears to be a winner, you may be
required to verify this on other sample data we
supply.
To
prevent cheating and possible later program
modifications or enhancements, all entries must
run the final executable version of their program
though an industry standard checksum program. MSO
will supply this program in both "C"
language and compiled form for MS-DOS computers HERE.
Entries
must be received by the time noted in the contest.
Late entries will not be accepted.
After
receiving all entries, judges will decide on a
possible winner, then require the possible
winning entries to send in the source and
compiled code so that it can be verified against
an internal set of inputs. Full instructions must
be supplied at this point if data entry is not
immediately obvious. Judges will use their best
means to verify the program is as described and
performs correctly. If the judges require it, the
programmer must be willing to run sample test
data through the program on his or her machine.
Winners
will be based on the entries which get the best
score (lowest number) using this formula:
Your programming time / fastest programming time
+ Your execution time / fastest execution time
+ Your program size / smallest program size
Program
size is of the object code. Only entries which
calculate the right answers will be judged.
Programming time is the time between when the
contest is begun and the time you submit your
entry.
Only
one entry is allowed per programmer per contest.
[ Back
to Top ]
|
