Many members of the club disliked the lack of variety and togetherness at the club. Although the club still had 12 members, some members were threatening to quit because each schedule was so short and there were so few people around each table.
To satisfy their request, the club decided to seat themselves around a big table and create a longer schedule. The twelve members of the club seated themselves in a schedule such that during each block of 55 days, no person was between the same pair of people. How was the schedule constructed?
(Based on The Round Table)
In case anyone cares, here is my program. Maybe someone with a faster computer can try it for 8. Or someone can play around with it until it morphs into a better version of itself? It basically tries every combination in alphabetical order backtracking letter by letter when it runs into a dead end. It only searches for positions 3 to totnum-1 in rows 2 to numdays The rest is defined in the beginning.
[start]
alpha$ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
input "How many people are in the club? "; totnum
if totnum = 0 then goto [quit]
print "I started searching for a schedule on ";date$();" at ";time$()
print
numdays = ((totnum-1)*(totnum-2))/2
dim TCC3$(totnum+1,numdays)
dim neigh$(totnum,numdays)
'define 1st day
for x = 1 to totnum
TCC3$(x,1) = mid$(alpha$,x,1)
next
TCC3$(totnum+1,1) = "A"
'define 1st & extra column
for y = 2 to numdays
TCC3$(1,y) = "A"
TCC3$(totnum+1,y) = "A"
next
'define 2nd column
a = 2
b = totnum-2
c = 1
for y = 2 to numdays
c = c+1
TCC3$(2,y) = mid$(alpha$,a,1)
neigh$(a,y) = "A "
if c=b then
a=a+1
b=b-1
c=0
end if
next
'define last column
a = totnum
b = 3
for y = 2 to numdays
a = a-1
TCC3$(totnum,y) = mid$(alpha$,a,1)
neigh$(totnum,y) = " A"
if a=b then
b=b+1
a=totnum+1
end if
next
'define neighbors
'1st column
for y = 1 to numdays
neigh$(1,y) = TCC3$(totnum,y) + TCC3$(2,y)
next
'1st row
for x = 2 to totnum
neigh$(x,1) = TCC3$(x-1,1) + TCC3$(x+1,1)
next
if totnum = 3 then goto [therest]
'start searching
for y = 2 to numdays
for x = 3 to totnum-1
abc = 2
[tryagain]
'pick letters that haven't been used yet in current row
a = 2
do
if mid$(alpha$,abc,1) <> TCC3$(a,y) then a = a + 1
if mid$(alpha$,abc,1) = TCC3$(a,y) then
abc = abc + 1
[do]
if abc > totnum then
x = x-1
if x = 2 then
y = y-1
x = totnum-1
abc = 1
do
abc = abc+1
loop until TCC3$(x,y) = mid$(alpha$,abc,1) or abc > totnum
neigh$(abc,y) = " "
TCC3$(x,y) = " "
z = 1
do
z = z+1
loop until TCC3$(x-1,y) = mid$(alpha$,z,1)
neigh$(z,y) = " "
abc = z+1
x = x-1
TCC3$(x,y) = " "
z = 1
do
z = z+1
loop until TCC3$(x-1,y) = mid$(alpha$,z,1)
neigh$(z,y) = " "
goto [tryagain]
end if
abc = 1
do
abc = abc+1
loop until TCC3$(x,y) = mid$(alpha$,abc,1)
neigh$(abc,y) = " "
TCC3$(x,y) = " "
z = 1
do
z = z+1
loop until TCC3$(x-1,y) = mid$(alpha$,z,1)
neigh$(z,y) = " "
abc = abc+1
goto [tryagain]
end if
a = 2
end if
loop until a >= totnum
if abc > totnum then goto [do]
TCC3$(x,y) = mid$(alpha$,abc,1)
'add letter to previous one's neighbor list
z = 1
do
z = z+1
loop until TCC3$(x-1,y) = mid$(alpha$,z,1)
neigh$(z,y) = TCC3$(x-2,y) + TCC3$(x,y)
mirror$ = TCC3$(x,y) + TCC3$(x-2,y)
'check to see if neighbors have already been used
c = 1
do
if neigh$(z,y) = neigh$(z,c) or mirror$ = neigh$(z,c) then goto [bad]
goto [good]
[bad]
TCC3$(x,y) = " "
neigh$(z,y) = " "
abc = abc + 1
if abc > totnum then goto [do]
goto [tryagain]
[good]
c = c+1
loop until c = y
'add last letter to 2nd to last letter's neighbor list and check above
if x <> totnum - 1 then goto [pass]
if abc > totnum then goto [therest]
neigh$(abc,y) = TCC3$(x-1,y) + TCC3$(x+1,y)
mirror$ = TCC3$(x+1,y) + TCC3$(x-1,y)
c = 1
do
if neigh$(abc,y) = neigh$(abc,c) or mirror$ = neigh$(abc,c) then goto [bad2]
goto [good2]
[bad2]
TCC3$(x,y) = " "
TCC3$(x-1,y) = " "
neigh$(z,y) = " "
neigh$(abc,y) = " "
x = x-1
abc = z + 1
if abc > totnum then
x = x-1
z = 1
do
z = z+1
loop until TCC3$(x,y) = mid$(alpha$,z,1) or z = totnum
abc = z
goto [bad]
end if
goto [tryagain]
[good2]
c = c + 1
loop until c = y
[pass]
next x
next y
'the rest of the neighbors
for y = 2 to numdays
for x = 2 to totnum
for a = 2 to totnum
if TCC3$(x,y) = mid$(alpha$,a,1) then
neigh$(a,y) = TCC3$(x-1,y) + TCC3$(x+1,y)
a = totnum
end if
next
next
next
'print schedule
for x = 1 to totnum+3
print " ";
next
for x = 1 to totnum
print TCC3$(x,1);
print " ";
next
print
for y = 1 to numdays
for x = 1 to totnum
print TCC3$(x,y);
next
print " ";
for x = 1 to totnum
print neigh$(x,y);
print " ";
next
print
next
print
print "I finished on ";date$();" at ";time$()
input dummy
cls
goto [start]
[quit]
|
|
Posted by Danny
on 2004-08-23 17:52:11 |
my program
