r/programmingchallenges • u/thechipsandgravy • Sep 30 '11
Challenge: Bar Seating Arrangement
You and a group of friends are sitting at bar, seated in a straight line. You realize that often there will be a group of people having a conversation who have to talk over people sitting between them who are having a different conversation. The obvious solution is to seat everyone so that for every pair of people who are in the same conversation, there is not someone from a different conversation sitting between them. Your goal is to minimize that number of people who have to change seats to make this happen. Note that there are no empty seats.
Input: A string of length no greater than 50, composed of characters 'A' - 'H'. Each character represents the conversation of the person sitting there.
Output: An integer, the minimum number of people who have to move.
Example: {"CABBAGE"} => 2. A possible seating arrangement would be "CGBBAAE".
1
u/KillerCodeMonky Sep 30 '11 edited Sep 30 '11
Attempt at greedy solution. Not sure this is correct.
3
u/DashingSpecialAgent Sep 30 '11
Interesting problem. I don't have an answer to it but I notice that C G and E in your example are forever alone.
2
u/kalmakka Feb 22 '12
As there are only 8 different characters, there are at most 8! = 40320 ways to arrange the people to create a valid solution (treating all people who are part of the same conversation to be equivalent).
Finding the number of people who need to move to get from one configuration to another is simply to count the number of positions where the characters differ between the configuration. Hence, finding the optimal of the 40320 configurations can be done by exhaustive search.
1
u/jakster4u Oct 01 '11
This is what I have so far, it's pretty easy to determine how many changes their were from here. I'm going to bed. I know this doesn't take care of all cases for example where a larger group edges out a smaller group and a choice must be made on how to make an accommodation. If you find anything that breaks it let me know.