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

 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.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Software program solution | Comment 2 of 5 |
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 ?")
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...")
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

 Search: Search body:
Forums (0)