Logic puzzle
Posted: Wed Apr 22, 2009 10:16 pm
I'm not sure if this is the right forum, but just in case anyone enjoys a brain teaser, here goes ...
I am musically associated with a bunch of lady Morris dancers (but please don't hold that against me). They have the same problem each time they dance in public: given the individual dancers who have turned up, which of their dances can they perform as a team ?
If it were just a question of who knows which dance, we can do that with just a spreadsheet:
- Set up a grid of people down the left, dances across the top; enter a "1" in the grid for each person who knows that dance. Underneath each dance name, enter the minimum number of people needed to perform the dance (some need 4, others 6 or occasionally 8 ). Also set up a total for each dance column.
- Using a copy of this data, delete rows for anyone who is not there. If the total for a dance column is GTE the minimum needed for that dance, we can do it.
The problem is that each dance has up to 8 positions, and many of the newer dancers have only learned a dance in one or two of the positions. So now, for each dance, we need to find a combination of dancers (at least the minimum number for that dance), each of whom knows at least one of the positions, so that each position is filled. You can't just do totals for each position now; one of the dancers may well know all of the positions, but she can only dance one of them at a time !
I've almost accepted that I'm going to have to work out the logic to grind through all of the possible permuations, but I thought I'd sound out the experts, in case anyone can see a clever logical shortcut. Failing that, there is always the organic, "ooh can we do this one ?" approach, which usually works (eventually).
Pete
I am musically associated with a bunch of lady Morris dancers (but please don't hold that against me). They have the same problem each time they dance in public: given the individual dancers who have turned up, which of their dances can they perform as a team ?
If it were just a question of who knows which dance, we can do that with just a spreadsheet:
- Set up a grid of people down the left, dances across the top; enter a "1" in the grid for each person who knows that dance. Underneath each dance name, enter the minimum number of people needed to perform the dance (some need 4, others 6 or occasionally 8 ). Also set up a total for each dance column.
- Using a copy of this data, delete rows for anyone who is not there. If the total for a dance column is GTE the minimum needed for that dance, we can do it.
The problem is that each dance has up to 8 positions, and many of the newer dancers have only learned a dance in one or two of the positions. So now, for each dance, we need to find a combination of dancers (at least the minimum number for that dance), each of whom knows at least one of the positions, so that each position is filled. You can't just do totals for each position now; one of the dancers may well know all of the positions, but she can only dance one of them at a time !
I've almost accepted that I'm going to have to work out the logic to grind through all of the possible permuations, but I thought I'd sound out the experts, in case anyone can see a clever logical shortcut. Failing that, there is always the organic, "ooh can we do this one ?" approach, which usually works (eventually).
Pete