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

Home > General
Dinner and Dialogue (Posted on 2005-11-02) Difficulty: 4 of 5
The Dinner and Dialogue Club has planned a series of small meetings. Each meeting would consist of two or three members enjoying friendly conversation with each other while eating food from different places all over the world. Each member is scheduled to meet exactly four times. No pair of members will meet twice, but some pairs might not meet at all.

The first thing the club did was schedule and arrange the meetings so that each member knew whom to meet and when. When it came to choosing restaurants, someone suggested that each member eat at two restaurants with eastern food, and two with western food (each restaurant is either one or the other). They liked the idea, but to their dismay, the idea was not possible without rearranging at least some of the meetings.

What possible meeting schedule might cause this to happen? How many members are there in this club, at the least?

See The Solution Submitted by Tristan    
Rating: 3.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(2): Least number of members ? Comment 9 of 9 |
(In reply to re: Least number of members ? by Tristan)

Thanks, Tristan.

Here is my program (parts of it are summarized)

Imports System
Imports System.IO
Imports System.Text
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
    Dim number As Integer
    Dim size0 As Integer
    Dim loop0 As Integer
    Dim pairs(0, 0) As Integer
    Dim size1 As Integer
    Dim loop1 As Integer
    Dim meetings(0, 0) As Integer
    Dim members(0) As Integer
    Dim size2 As Integer
    Dim loop2 As Integer
    Dim loop3 As Integer
    Dim population(0) As Integer
    Dim restaurants(0, 0) As Integer
    Dim loop4 As Integer
    Dim loop5 As Integer
    Dim sub1 As Integer
    Dim sub2 As Integer
    Dim random1 As Integer
    Dim random2 As Integer
    Dim flag_good_bad As String
    Dim flag0 As String
    Dim flag1 As String
    Dim flag2 As String
    Dim flagx As String
    Dim work1 As Integer
    Dim work2 As Integer
    Dim work3 As Integer
    Dim work4 As String
    Dim work5 As Integer
    Dim counter As Integer
    Dim here As Integer
' ------------------------------------------------------
    Sub Main()
        Randomize()
        number = 0
        While number < 3
            Console.WriteLine("Enter number of club members, >= 3")
            number = Int(Console.ReadLine())
        End While
        flag_good_bad = "?"
        While flag_good_bad <> "g" And flag_good_bad <> "b"
            Console.WriteLine( _
            "Do you want a good schedule or a bad one ? (g/b)")
            flag_good_bad = LCase(Console.ReadLine())
        End While
        size0 = (number * (number - 1)) / 2
        ReDim pairs(size0, 2)
        loop0 = size0 - 1
        size1 = number * 4
        ReDim meetings(size1, 4)
        loop1 = size1 - 1
        size2 = number
        ReDim members(size2)
        ReDim population(size2)
        ReDim restaurants(size2, 2)
        loop5 = number - 1
        initdata()
        flag0 = "?"
        While 100 > 0
            get_the_meetings()
            If flag_good_bad = "b" Then
                If flag0 = "y" Then
                    Exit While
                End If
            Else
                If flag0 = "n" Then
                    Exit While
                End If
            End If
        End While
        If flag_good_bad = "b" Then
            write_badfile()
        Else
            write_goodfile()
        End If
    End Sub
' ------------------------------------------------------
    Sub initdata()
        counter = 0
        loop2 = size2 - 1
        loop4 = size2 - 1
        For index0 As Integer = 0 To loop0
            For index00 As Integer = 0 To 1
                pairs(index0, index00) = -999
            Next
        Next
        For index1 As Integer = 0 To loop1
            For index11 As Integer = 0 To 3
                meetings(index1, index11) = -999
            Next
        Next
        For index2 As Integer = 0 To loop2
            members(index2) = 0
        Next
        For index4 As Integer = 0 To loop4
            population(index4) = index4
        Next
        sub1 = -1
    End Sub
' ------------------------------------------------------
    Sub get_the_meetings()
        Dim work94 As String
        flag1 = "n"
        initdata()
        While flag1 = "n"
            gen_meeting()
            If counter > 999 Then
                initdata()
            End If
        End While
        If sub1 > 100 Then
            Console.WriteLine(sub1 & " size too big !!")
            Exit Sub
        End If
        flag2 = "n"
        For index9 As Integer = 0 To 1
            meetings(0, 3) = index9
            vary_meeting_0()
        Next
        If flag2 = "n" Then
            flag0 = "y"
        Else
            flag0 = "n"
        End If
    End Sub
' ------------------------------------------------------
    Sub gen_meeting()
        Dim work8 As String
        Dim option0 As Integer
        Dim max0 As Integer
        Dim min0 As Integer
        loop3 = Int((2 - 1 + 1) * Rnd() + 1)
        sub1 += 1
        For index1 As Integer = 0 To loop3
            While 100 > 0
                counter += 1
                If counter > 999 Then
                    flag1 = "n"
                    Exit Sub
                End If
                random1 = Int((loop4 - 0 + 1) * Rnd() + 0)
                random2 = population(random1)
                check_a()
                If flagx = "n" Then
                    GoTo nextwhile
                End If
                check_b()
                If flagx = "n" Then
                    GoTo nextwhile
                End If
                meetings(sub1, index1) = random2
                If meetings(sub1, 3) = 2 Then
                    Console.WriteLine("sub1 index1 " & Str(sub1) & Str(index1))
                    Console.ReadLine()
                End If
                Exit While
nextwhile:
            End While
        Next
        For index1 As Integer = 0 To loop3 - 1
            For index2 As Integer = index1 + 1 To loop3
                For index3 As Integer = 0 To loop0
                    If pairs(index3, 0) < 0 Then
                        pairs(index3, 0) = meetings(sub1, index1)
                        pairs(index3, 1) = meetings(sub1, index2)
                        GoTo nextnext
                    End If
                Next
nextnext:
            Next
        Next
        For index1 As Integer = 0 To loop3
            members(meetings(sub1, index1)) += 1
            If members(meetings(sub1, index1)) > 3 Then
                work2 = meetings(sub1, index1)
                For index2 As Integer = 0 To loop4
                    If population(index2) = work2 Then
                        work3 = index2
                        Exit For
                    End If
                Next
                If work3 < loop4 Then
                    For index3 As Integer = work3 To loop4 - 1
                        population(index3) = population(index3 + 1)
                    Next
                End If
                loop4 -= 1
            End If
        Next
        flag1 = "y"
        For index1 As Integer = 0 To loop2
            If members(index1) < 4 Then
                flag1 = "n"
                Exit For
            End If
        Next
    End Sub
' ------------------------------------------------------
    Sub check_a()
        flagx = "y"
        For index1 As Integer = 0 To 2
            If random2 = meetings(sub1, index1) Then
                flagx = "n"
            End If
        Next
    End Sub
' ------------------------------------------------------
    Sub check_b()
        flagx = "y"
        For index1 As Integer = 0 To 2
            If meetings(sub1, index1) >= 0 Then
                work1 = meetings(sub1, index1)
                For index2 As Integer = 0 To loop0
                    If pairs(index2, 0) = random2 And _
                    pairs(index2, 1) = work1 Then
                        flagx = "n"
                        Exit Sub
                    End If
                    If pairs(index2, 1) = random2 And _
                    pairs(index2, 0) = work1 Then
                        flagx = "n"
                        Exit Sub
                    End If
                Next
            End If
        Next
    End Sub
' ------------------------------------------------------
    Sub vary_meeting_0()
        Dim constant As Integer = 0
        here = constant
        If sub1 < constant Then
            Exit Sub
        End If
        check_meetings()
        If flagx = "n" Then
            Exit Sub
        End If
        If flag2 = "y" Then
            Exit Sub
        End If
        If sub1 > constant Then
            For index9 As Integer = 0 To 1
                meetings(1, 3) = index9
                vary_meeting_1()
                If flag2 = "y" Then
                    Exit For
                End If
            Next
        End If
    End Sub
' ------------------------------------------------------
Etc...Etc......
vary_meeting_1()
thru        
vary_meeting_99()
' ------------------------------------------------------
    Sub vary_meeting_100()
        Dim constant As Integer = 100
        here = constant
        If sub1 < constant Then
            Exit Sub
        End If
        check_meetings()
        If flagx = "n" Then
            Exit Sub
        End If
        If flag2 = "y" Then
            Exit Sub
        End If
    End Sub
' ------------------------------------------------------
    Sub check_meetings()
        Dim sub6 As Integer
        If flag2 = "y" Then
            Exit Sub
        End If
        For index0 As Integer = 0 To loop2
            For index1 As Integer = 0 To 1
                restaurants(index0, index1) = 0
            Next
        Next
        For index0 As Integer = 0 To here
            For index1 As Integer = 0 To 2
                If meetings(index0, index1) >= 0 Then
                    sub6 = meetings(index0, index1)
                    If meetings(index0, 3) = 0 Then
                        restaurants(sub6, 0) += 1
                    ElseIf meetings(index0, 3) = 1 Then
                        restaurants(sub6, 1) += 1
                    End If
                End If
            Next
        Next
        flagx = "y"
        For index0 As Integer = 0 To loop2
            For index1 As Integer = 0 To 1
                If restaurants(index0, index1) > 2 Then
                    flagx = "n"
                End If
            Next
        Next
        If here = sub1 Then
            flag2 = "y"
            If flagx = "n" Then
                flag2 = "n"
            End If
        End If
    End Sub
' ------------------------------------------------------
    Sub write_goodfile()
        Dim objStreamWriter As StreamWriter
        Dim string0 As String
        Console.WriteLine("Writing good schedule...")
        objStreamWriter = _
        New StreamWriter("C:VB.GOOD.DINNER.DIALOGUE")
        For index1 As Integer = 0 To sub1
            string0 = "Meeting " & Str(index1 + 1) & ": "
            Select Case meetings(index1, 3)
                Case 0
                    string0 &= "(Eastern food) {"
                Case 1
                    string0 &= "(Western food) {"
                Case Else
                    string0 = "(??????      ) {"
            End Select
            For index2 As Integer = 0 To 2
                If meetings(index1, index2) >= 0 Then
                    string0 &= Str(meetings(index1, index2) + 1)
                End If
            Next
            string0 &= "}"
            objStreamWriter.WriteLine(string0)
        Next
        objStreamWriter.Close()
        Console.WriteLine("Done.")
    End Sub
' ------------------------------------------------------
    Sub write_badfile()
        Dim objStreamWriter As StreamWriter
        Dim string0 As String
        Console.WriteLine("Writing bad schedule...")
        objStreamWriter = _
        New StreamWriter("C:VB.TWO.BAD.DINNER.DIALOGUE")
        For index1 As Integer = 0 To sub1
            string0 = "Meeting " & Str(index1 + 1)  & ": {"
            For index2 As Integer = 0 To 2
                If meetings(index1, index2) >= 0 Then
                    string0 &= Str(meetings(index1, index2) + 1)
                End If
            Next
            string0 &= "}"
            objStreamWriter.WriteLine(string0)
        Next
        objStreamWriter.Close()
        Console.WriteLine("Done.")
    End Sub
End Module
' ------------------------------------------------------------
 

 

 

 

 

Edited on November 8, 2005, 3:28 am
  Posted by Penny on 2005-11-08 03:22:27

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 (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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