All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
The Conversing Club 3 (Posted on 2004-03-28) Difficulty: 5 of 5
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)

No Solution Yet Submitted by Gamer    
Rating: 4.5714 (14 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips my program | Comment 45 of 62 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information