perplexus.info :: General : The Conversing Club 4

The Conversing Club 4 (Posted on 2004-05-21)

The conversing club has lost more members as other problems came up such that now they only had 9 members. To help settle down the club, the club decided to get a series of 6 speakers to come in for 6 days of the week.

The chairs were arranged in 3 rows of 3, with space between each row, but less space between each chair in a row. The members wanted to talk to anyone to their immediate left or right during the performance, but felt it would be too rude to lean all the way forward or back to talk to anyone not on their immediate left or right. (Each day 6 people can talk to 1 person during the speech, and 3 people can talk to 2 people during the speech)

The schedule for where everyone would sit each day was created such that everyone would be able to talk to everyone once during the 6 days. The first day's schedule is as follows:

A B C D E F G H I
(So on the second day, B A E would be disallowed because A could talk to B again. DCB would not be allowed either, because B could talk to C again. ACF would be allowed because C would need to reach across B in order to talk to A, so C couldn't talk to A the first day. This means C could talk to A another day instead. DFB, BEI, CFG would be an allowed combinations, but GHA and FDE would not be allowed.)

What are schedules for all 6 days?

No Solution Yet Submitted by Gamer

Rating: 4.4000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

Software program solution

| Comment 2 of 7 |

Schedule:

A B C

D E F

G H I

E G A

I F C

H D B

F G C

E H B

I A D

D C I

E B G

H A F

B F H

D I G

C E A

G D F

A C H

E I B

Explanation:

The program listed below ran in less than 2 minutes, using 5,000 work tables. It produced the following output:

8 4 7 1 5 6 3 9 2

5 3 8 2 6 7 9 1 4

6 3 7 5 9 4 2 8 1

1 7 2 5 4 3 9 8 6

4 6 9 1 2 3 7 5 8

3 1 6 8 7 9 5 2 4

Then with letter substitution this becomes:

A B C D E F G H I

E G A I F C H D B

F G C E H B I A D

D C I E B G H A F

B F H D I G C E A

G D F A C H E I B

Which becomes the solution given with you break each line into three rows.

Here is the Visual Basic program that produced it:

Imports System
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
    Sub Main()
        Randomize()
        Dim intSchedules(0, 0, 0) As Integer
        Dim intPeople(0, 0, 0) As Integer
        Dim strGoodFlag As String
        Dim strEndFlag As String
        Dim strStartTime As String
        Dim dblCount1 As Double
        Dim dblCount2 As Double
        Dim intNumTables As Integer
        Dim intNumTabs As Integer
        Dim intGoodTable As Integer
        Dim intTableCounts(5) As Integer
        strStartTime = TimeOfDay
        dblCount1 = 0
        dblCount2 = 0
        For Index1 As Integer = 0 To 4
            intTableCounts(index1) = 0
        Next
        intNumTabs = 0
        While intNumTabs = 0
            Console.WriteLine("How many work tables " & _
            "should I use ?")
            intNumTabs = Int(Console.ReadLine())
        End While
        intNumTables = intNumTabs - 1
        ReDim intSchedules(intNumTabs, 6, 9)
        ReDim intPeople(intNumTabs, 9, 9)
        For Index1 As Integer = 0 To intNumTables
            For Index2 As Integer = 0 To 5
                For Index3 As Integer = 0 To 8
                    intSchedules(Index1, Index2, Index3) = 0
                Next
            Next
        Next
        For Index1 As Integer = 0 To intNumTables
            For Index2 As Integer = 0 To 8
                For Index3 As Integer = 0 To 8
                    If Index3 = 0 Then
                        intPeople(Index1, Index2, Index3) = Index2 + 1
                    Else
                        intPeople(Index1, Index2, Index3) = 0
                    End If
                Next
            Next
        Next
        strGoodFlag = "N"
        While strGoodFlag <> "Y"
            TryASchedule(intNumTables, _
            intSchedules, intPeople, strGoodFlag, _
            intGoodTable, _
            dblCount1, dblCount2, _
            intTableCounts)
            IntervalBreak(dblCount1, _
                dblCount2, _
                intNumTables, _
                intSchedules, _
                intPeople, _
                intTableCounts)
        End While
        Console.WriteLine("Success !!!!")
        DisplayGoodTableData(intGoodTable, intSchedules, _
        intPeople)
        Console.WriteLine("Program began execution at " & strStartTime)
        Console.WriteLine("and ended at " & TimeOfDay)
        strEndFlag = "?"
        While strEndFlag <> "X"
            Console.WriteLine("Please enter X to terminate program...")
            strEndFlag = UCase(Console.ReadLine())
        End While
    End Sub

    Sub TryASchedule(ByRef intNumTables, ByRef intSchedules, _
    ByRef intPeople, ByRef strGoodFlag, ByRef intGoodTable, _
        ByRef dblCount1, ByRef dblCount2, ByRef intTableCounts)
        Dim intConv1 As Integer
        Dim intConv2 As Integer
        Dim intConv3 As Integer
        Dim intSched(9) As Integer
        Dim strTableHit As String
        Dim intTable As Integer
        GetSchedule(intSched, dblCount2)
        strTableHit = "0"
        For Index1 As Integer = 0 To intNumTables
            IntervalBreak(dblCount1, _
                dblCount2, _
                intNumTables, _
                intSchedules, _
                intPeople, _
                intTableCounts)
            intTable = Index1
            PlaceInTable(intTable, intSched, _
              intSchedules, intPeople, strTableHit, _
               strGoodFlag, intGoodTable, _
                dblCount1, dblCount2, intNumTables, _
                intTableCounts)
            If strTableHit = "2" Then
                Exit For
            End If
        Next
    End Sub

    Sub PlaceInTable(ByRef intTable, ByRef intSched, _
        ByRef intSchedules, ByRef intPeople, ByRef strTableHit, _
        ByRef strGoodFlag, ByRef intGoodTable, _
        ByRef dblCount1, ByRef dblCount2, ByRef intNumTables, _
        ByRef intTableCounts)
        Dim intSubscr1 As Integer
        Dim strFlag1 As String
        Dim intConv1 As Integer
        Dim intConv2 As Integer
        Dim intConv3 As Integer
        Dim str1Match As String
        Dim strThere As String
        If intSchedules(intTable, 0, 0) = 0 Then
            If strTableHit = "1" Then
                strTableHit = "2"
                Exit Sub
            Else
                strTableHit = "2"
                For Index1 As Integer = 0 To 8
                    intSchedules(intTable, 0, Index1) = _
                    intSched(Index1)
                Next
                intTableCounts(0) += 1
                UpdatePeople(intTable, intSched, intPeople, _
                intSchedules, intTableCounts)
                Exit Sub
            End If
        End If
        str1Match = "1"
        For Index1 As Integer = 0 To 8
            If intSched(Index1) <> _
            intSchedules(intTable, 0, Index1) Then
                str1Match = "0"
            End If
        Next
        If str1Match = "1" Then
            If strTableHit = "0" Then
                strTableHit = "1"
            End If
        End If
        For Index1 As Integer = 0 To 8
            intConv1 = intSched(Index1)
            If Index1 Mod 3 = 0 Then
                intSubscr1 = Index1 + 1
                intConv2 = intSched(intSubscr1)
                intConv3 = intSched(intSubscr1)
            ElseIf Index1 Mod 3 = 1 Then
                intSubscr1 = Index1 - 1
                intConv2 = intSched(intSubscr1)
                intSubscr1 = Index1 + 1
                intConv3 = intSched(intSubscr1)
            Else
                intSubscr1 = Index1 - 1
                intConv2 = intSched(intSubscr1)
                intConv3 = intSched(intSubscr1)
            End If
            strThere = "0"
            FindConv(intConv1, intConv2, intConv3, _
               intTable, intPeople, strThere, _
               dblCount1, dblCount2, intNumTables, _
               intSchedules, intTableCounts)
            If strThere = "1" Then
                Exit Sub
            End If
        Next
        UpdatePeople(intTable, intSched, intPeople, _
        intSchedules, intTableCounts)
        For Index1 As Integer = 0 To 5
            If intSchedules(intTable, Index1, 0) = 0 Then
                If Index1 = 5 Then
                    strGoodFlag = "Y"
                    intGoodTable = intTable
                ElseIf Index1 = 4 Then
                    intTableCounts(4) += 1
                    intTableCounts(3) -= 1
                ElseIf Index1 = 3 Then
                    intTableCounts(3) += 1
                    intTableCounts(2) -= 1
                ElseIf Index1 = 2 Then
                    intTableCounts(2) += 1
                    intTableCounts(1) -= 1
                ElseIf Index1 = 1 Then
                    intTableCounts(1) += 1
                    intTableCounts(0) -= 1
                End If
                For Index2 As Integer = 0 To 8
                    IntervalBreak(dblCount1, _
                          dblCount2, _
                          intNumTables, _
                          intSchedules, _
                          intPeople, _
                          intTableCounts)
                    intSchedules(intTable, Index1, Index2) = _
                    intSched(Index2)
                Next
                Exit Sub
            End If
        Next
    End Sub

    Sub FindConv(ByRef intConv1, ByRef intConv2, ByRef intConv3, _
    ByRef intTable, ByRef intPeople, ByRef strThere, _
        ByRef dblCount1, ByRef dblCount2, ByRef intNumTables, _
        ByRef intSchedules, ByRef intTableCounts)
        For Index1 As Integer = 0 To 8
            If intPeople(intTable, Index1, 0) = intConv1 Then
                For Index2 As Integer = 1 To 8
                    IntervalBreak(dblCount1, _
                          dblCount2, _
                          intNumTables, _
                          intSchedules, _
                          intPeople, _
                          intTableCounts)
                    If intPeople(intTable, Index1, Index2) = intConv1 Or _
                    intPeople(intTable, Index1, Index2) = intConv2 Then
                        strThere = "1"
                        Exit Sub
                    End If
                Next
            End If
        Next
    End Sub

    Sub UpdatePeople(ByRef intTable, ByRef intSched, ByRef intPeople, _
    ByRef intSchedules, ByRef intTableCounts)
        Dim intConv1 As Integer
        Dim intConv2 As Integer
        Dim intConv3 As Integer
        Dim intSubscr1 As Integer
        For Index1 As Integer = 0 To 8
            intConv1 = intSched(Index1)
            If Index1 Mod 3 = 0 Then
                intSubscr1 = Index1 + 1
                intConv2 = intSched(intSubscr1)
                intConv3 = intSched(intSubscr1)
            ElseIf Index1 Mod 3 = 1 Then
                intSubscr1 = Index1 - 1
                intConv2 = intSched(intSubscr1)
                intSubscr1 = Index1 + 1
                intConv3 = intSched(intSubscr1)
            Else
                intSubscr1 = Index1 - 1
                intConv2 = intSched(intSubscr1)
                intConv3 = intSched(intSubscr1)
            End If
            For Index3 As Integer = 0 To 8
                If intConv2 <> 0 Then
                    If intPeople(intTable, intConv1 - 1, Index3) = 0 Then
                        intPeople(intTable, intConv1 - 1, Index3) = _
                                 intConv2
                        If intConv2 = intConv3 Then
                            intConv2 = 0
                            intConv3 = 0
                        Else
                            intConv2 = 0
                        End If
                    End If
                ElseIf intConv3 <> 0 Then
                    If intPeople(intTable, intConv1 - 1, Index3) = 0 Then
                        intPeople(intTable, intConv1 - 1, Index3) = _
                        intConv3
                        intConv3 = 0
                    End If
                End If
            Next
        Next
    End Sub

    Sub DisplayGoodTableData(ByRef intGoodTable, _
    ByRef intSchedules, ByRef intPeople)
        Console.WriteLine("Here are the good schedules:")
        For Index2 As Integer = 0 To 5
            Console.WriteLine( _
                  Str(intSchedules(intGoodTable, Index2, 0)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 1)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 2)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 3)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 4)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 5)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 6)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 7)) & " " & _
                  Str(intSchedules(intGoodTable, Index2, 8)))
        Next
        Console.WriteLine("Here are the people:")
        For Index2 As Integer = 0 To 8
            Console.WriteLine( _
                  Str(intPeople(intGoodTable, Index2, 0)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 1)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 2)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 3)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 4)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 5)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 6)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 7)) & " " & _
                  Str(intPeople(intGoodTable, Index2, 8)))
        Next
    End Sub

    Sub IntervalBreak(ByRef dblCount1, ByRef dblCount2, _
          ByRef intNumTables, ByRef intSchedules, ByRef intPeople, _
          ByRef intTableCounts)
        dblCount1 += 1
        If dblCount1 >= 999999 Then
            dblCount1 = 0
            Console.WriteLine("We have attempted " & _
            Str(dblCount2) & _
            " schedules...")
            If Str(intTableCounts(4)) <> 0 Then
                Console.WriteLine(Str(intTableCounts(4)) & _
                " tables have 5 rows.")
            End If
            If Str(intTableCounts(3)) <> 0 Then
                Console.WriteLine(Str(intTableCounts(3)) & _
                " tables have 4 rows.")
            End If
            If Str(intTableCounts(2)) <> 0 Then
                Console.WriteLine(Str(intTableCounts(2)) & _
                " tables have 3 rows.")
            End If
            If Str(intTableCounts(1)) <> 0 Then
                Console.WriteLine(Str(intTableCounts(1)) & _
                " tables have 2 rows.")
            End If
            If Str(intTableCounts(0)) <> 0 Then
                Console.WriteLine(Str(intTableCounts(0)) & _
                " tables have 1 row.")
            End If
        End If
    End Sub

    Sub GetSchedule(ByRef intSched, ByRef dblCount2)
        dblCount2 += 1
        intSched(0) = Int((9 - 1 + 1) * Rnd()) + 1
        For Index1 As Integer = 1 To 8
            intSched(Index1) = intSched(0)
        Next
        While (intSched(1) = intSched(0))
            intSched(1) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(2) = intSched(0) Or _
               intSched(2) = intSched(1))
            intSched(2) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(3) = intSched(0) Or _
               intSched(3) = intSched(1) Or _
               intSched(3) = intSched(2))
            intSched(3) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(4) = intSched(0) Or _
               intSched(4) = intSched(1) Or _
               intSched(4) = intSched(2) Or _
               intSched(4) = intSched(3))
            intSched(4) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(5) = intSched(0) Or _
               intSched(5) = intSched(1) Or _
               intSched(5) = intSched(2) Or _
               intSched(5) = intSched(3) Or _
               intSched(5) = intSched(4))
            intSched(5) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(6) = intSched(0) Or _
               intSched(6) = intSched(1) Or _
               intSched(6) = intSched(2) Or _
               intSched(6) = intSched(3) Or _
               intSched(6) = intSched(4) Or _
               intSched(6) = intSched(5))
            intSched(6) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(7) = intSched(0) Or _
               intSched(7) = intSched(1) Or _
               intSched(7) = intSched(2) Or _
               intSched(7) = intSched(3) Or _
               intSched(7) = intSched(4) Or _
               intSched(7) = intSched(5) Or _
               intSched(7) = intSched(6))
            intSched(7) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
        While (intSched(8) = intSched(0) Or _
               intSched(8) = intSched(1) Or _
               intSched(8) = intSched(2) Or _
               intSched(8) = intSched(3) Or _
               intSched(8) = intSched(4) Or _
               intSched(8) = intSched(5) Or _
               intSched(8) = intSched(6) Or _
               intSched(8) = intSched(7))
            intSched(8) = Int((9 - 1 + 1) * Rnd()) + 1
        End While
    End Sub
End Module

Edited on May 22, 2004, 5:26 pm

Posted by Penny on 2004-05-22 17:11:42

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:

blackjack

flooble's webmaster puzzle


perplexus dot info