Comment On Kirkman's Ladies

Oh god, this is so easy, ten billion answers are all over the innertubes, I solved this in middle school during recess, can't you think up anything original, blah blah blah.

There, got all that out of the way fist.

"The Ladies' and Gentlemen's Diary" was not a mathematical journal as such. It styled itself a "repository of science and amusement" and devoted some of its pages to posing amusing mathematical problems for its (apparently lay but literate) readership. Most googlable sources insist that it never published more than three issues, namely for the years 1820, 1821, and 1822 -- so it was long dead in 1850.

The only googlable occurrences of TLaGD with the number 1850 are various references to Kirkman's problem -- so this possibly erroneous citation has a long history. Interestingly, some sources (one is Gerstein, Introduction to mathematical structures and proofs) says the the problem was posed by W.S.B. Woolhouse in 1844 (still in TLaGD) and solved by Kirkman in 1850.

Should this also consider best friends, sworn enemies and "She said.. she said.."?

(I went to a girls-only school for 5 years - it's war out there, with a very delicate political situation and alliances changing daily. I still don't know the rules! Despite being a girl...)

As with every BYOC so far, TRWTF is that the spec is borked. Is "n" in the medium difficulty version supposed to read "num_girls"? What does "no 2 girls are in the same group more than once a week" mean? There are two possibilities...

--
Submission attempt 2

I got as far as reading about fifteen young girls and their breasts but then my mind just wandered off. I don't think I'm going to be of much help for this Praxis.

I'm not saying this implementation is great, I'm just saying it works; solved for "hard" in PHP:

function getGirls($seed = 'a') {

	// due to the interesting way this function runs (poorly),

	// changing the seed will case all the combinations to change

	$base = range('A','O'); // 15

	if (empty($seed) || !in_array($seed = substr(ucfirst($seed),0,1), $base))

		return;

	

	if ($seed != 'A') {

		$base = array_merge(range($seed,'O'), range('A',chr(ord($seed)-1)));

	}

	

	$drillDown = array();	// the final array of 35 for a given week

	$seenCombos = array();	// 2-girl combination lookup table

	foreach ($base as $girl) {

		foreach ($base as $girl2) {

			foreach ($base as $girl3) {

				// make sure that no girl exists more than once in

				// the same space-time continuum

				if ($girl == $girl2 || $girl2 == $girl3 || $girl3 == $girl)

					continue;

				// create a possibility array

				$combo = array($girl, $girl2, $girl3);

				sort($combo);	// put them into a common order

				if (	// check the lookup table (maintaining the common order)

					isset($seenCombos[$combo[0].$combo[1]]) ||

					isset($seenCombos[$combo[1].$combo[2]]) ||

					isset($seenCombos[$combo[0].$combo[2]])

				)	continue;	// skip if this combo has been seen

				// otherwise, populate the lookup table

				$seenCombos[$combo[0].$combo[1]] = 1;

				$seenCombos[$combo[1].$combo[2]] = 1;

				$seenCombos[$combo[0].$combo[2]] = 1;

				// and the final array

				$drillDown[join($combo)] = 1;

			}

		}

	}

	

	print_r($drillDown);	// echo the array

	getGirls(chr(ord($seed) + 1));	// increase the seed

}

 

echo '<pre>';

getGirls();

Addendum (2009-09-16 10:59):
Note that this outputs the array as a series of keys with a value of 1; If you wanted it in some other format, I don't really care.

Why is that when a nice programming challenge is presented to a bunch of developers all they can do is argue about grammar and spelling?

Code Dependent:

Oh god, this is so easy, ten billion answers are all over the innertubes, I solved this in middle school during recess, can't you think up anything original, blah blah blah.

There, got all that out of the way fist.

If only you'd polished up on your PHP, you could have been a hero, rather than a snark. "Fist?" I mean, this would have been a genuinely great frist:

DrJDX:

I'm not saying this implementation is great, I'm just saying it works; solved for "hard" in PHP:

function getGirls($seed = 'a') {

	// due to the interesting way this function runs (poorly),

	// changing the seed will case all the combinations to change

	$base = range('A','O'); // 15

	if (empty($seed) || !in_array($seed = substr(ucfirst($seed),0,1), $base))

		return;

	

	if ($seed != 'A') {

		$base = array_merge(range($seed,'O'), range('A',chr(ord($seed)-1)));

	}

	

	$drillDown = array();	// the final array of 35 for a given week

	$seenCombos = array();	// 2-girl combination lookup table

	foreach ($base as $girl) {

		foreach ($base as $girl2) {

			foreach ($base as $girl3) {

				// make sure that no girl exists more than once in

				// the same space-time continuum

				if ($girl == $girl2 || $girl2 == $girl3 || $girl3 == $girl)

					continue;

				// create a possibility array

				$combo = array($girl, $girl2, $girl3);

				sort($combo);	// put them into a common order

				if (	// check the lookup table (maintaining the common order)

					isset($seenCombos[$combo[0].$combo[1]]) ||

					isset($seenCombos[$combo[1].$combo[2]]) ||

					isset($seenCombos[$combo[0].$combo[2]])

				)	continue;	// skip if this combo has been seen

				// otherwise, populate the lookup table

				$seenCombos[$combo[0].$combo[1]] = 1;

				$seenCombos[$combo[1].$combo[2]] = 1;

				$seenCombos[$combo[0].$combo[2]] = 1;

				// and the final array

				$drillDown[join($combo)] = 1;

			}

		}

	}

	

	print_r($drillDown);	// echo the array

	getGirls(chr(ord($seed) + 1));	// increase the seed

}

 

echo '<pre>';

getGirls();

$drillDown, tee hee hee.

Seriously, what is the point of this bollocks? What do you use to fill the holes in the woodwork after the worms have come out of it?

Actually, I do like the idea of a "2-girl combination lookup table." As usual with TDWTF, the comments are better than the original code. Is there a URL for this? (Not featuring cups, kthx.)

DrJDX:

I'm not saying this implementation is great, I'm just saying it works; solved for "hard" in PHP:

[code]function getGirls($seed = 'a') {
// due to the interesting way this function runs (poorly),
// changing the seed will case all the combinations to change

$drillDown = array(); // the final array of 35 for a given week
$seenCombos = array(); // 2-girl combination lookup table
foreach ($base as $girl) {
foreach ($base as $girl2) {
foreach ($base as $girl3) {
// make sure that no girl exists more than once in
// the same space-time continuum
// create a possibility array
$combo = array($girl, $girl2, $girl3);
$drillDown[join($combo)] = 1;
getGirls(chr(ord($seed) + 1)); // increase the seed
}

I like this guys' thinking.
getGirls
drillDown
"changing the seed will cause the possibilities to change"
combos of girls
first base, second base, third base

He has all the good stuff...

SoaperGEM:

I hope I'm not the only here who still has no idea what this problem is really asking for, even after reading it a few times. The wording of this problem is just not very clear at all, IMO.

I'll be honest with you, I have no idea what that "medium" level problem was about. It took a few iterations before I really understood the problem overall, too, because I was coming up with thousands of combinations (2,730 to be precise).

Oh well, it worked out in the end, I suppose.

Does anybody actually like these? I don't think this is the place for such things; if I want questions like this there are plenty of sites.

But okay, my answer in bash:

function threeSomes()

{

  echo "Sun   Mon   Tue   Wed   Thu   Fri   Sat"

  echo A,F,K A,B,E B,C,F E,F,I C,E,K E,G,M K,M,D

  echo B,G,L C,D,G D,E,H G,H,K D,F,L F,H,N L,N,E

  echo C,H,M H,I,L I,J,M L,M,A G,I,O I,K,B O,B,H

  echo D,I,N J,K,N K,L,O N,O,C H,J,A J,L,C A,C,I

  echo E,J,O M,O,F N,A,G B,D,J M,N,B O,A,D F,G,J

}

1. Get three abreast counters. Make a counter for every girl, set it to 0.
2. Run the three counters forward until they have found a girl whose counter is the minimum of all girl counters. Increment the counters of the girls. That's an answer, go back to 2.
Step 2 has to be done sequentially for each counter, to avoid them pointing at the same girl.

Rick:

DrJDX:

I'm not saying this implementation is great, I'm just saying it works; solved for "hard" in PHP:

[code]function getGirls($seed = 'a') {
// due to the interesting way this function runs (poorly),
// changing the seed will case all the combinations to change

$drillDown = array(); // the final array of 35 for a given week
$seenCombos = array(); // 2-girl combination lookup table
foreach ($base as $girl) {
foreach ($base as $girl2) {
foreach ($base as $girl3) {
// make sure that no girl exists more than once in
// the same space-time continuum
// create a possibility array
$combo = array($girl, $girl2, $girl3);
$drillDown[join($combo)] = 1;
getGirls(chr(ord($seed) + 1)); // increase the seed
}

I like this guys' thinking.
getGirls
drillDown
"changing the seed will cause the possibilities to change"
combos of girls
first base, second base, third base

He has all the good stuff...

We have been writing getGirls() functions for years, they may compile, but they never work. Recently I found this one:

GetGirls($)

It only works in the states, and has more chance of success for higher values of $.

(3rd try, is this some sort of persistance captcha?)

Kev:

Why is that when a nice programming challenge is presented to a bunch of developers all they can do is argue about grammar and spelling?

Because they're reading this to take a break from their programming challenges?

With all this talk of num_girls, the only thing I can think of is Rohypnol...

Brute force solution is Haskell, main function is abreast (and not pretty printed):

data Girl = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O deriving (Show, Eq, Ord, Enum)



girls = [A .. O]



three = [ (a,b,c) | a <- girls , b <- girls , c <- girls , a < b , b < c ]



pairs a b c = filter (\(x,y,z) -> ( (cntThree a b c [x,y,z]) <= 1))



cntThree a b c xs = (foldl (\y x -> if ( (x==a) || (x==b) || (x==c) ) then y+1 else y) 0 xs)



abreast = abreast' three



abreast' [] = []

abreast' ((a,b,c):xs) = (a,b,c) : (abreast' (pairs a b c xs))

Is is just me, or doesn't Flo sell insurance, and ride a motorcycle (a 900 V-twin) to work. She isn't a school girl as far as I know. I could be mistaken, but I believe that Flo is a more Progressive person!

Herby:

Is is just me, or doesn't Flo sell insurance, and ride a motorcycle (a 900 V-twin) to work. She isn't a school girl as far as I know. I could be mistaken, but I believe that Flo is a more Progressive person!

Thats just her job. Take the namebadge off, and you get.... SCHOOLGIRL

select girl into #chicks from
(
select 'A' as girl
union all
select 'B'
union all
select 'C'
union all
select 'D'
union all
select 'E'
union all
select 'F'
union all
select 'G'
union all
select 'H'
union all
select 'I'
union all
select 'J'
union all
select 'K'
union all
select 'L'
union all
select 'M'
union all
select 'N'
union all
select 'O'
) harem

select top 35 * from
(
select a.girl + b.girl + c.girl as chickonchickonchick
from #chicks a cross join #chicks b cross join #chicks c
where a.girl <> b.girl and a.girl <> c.girl and b.girl <> c.girl
) morecrap

drop table #chicks

N0ob:

... incorrect SQL code ...

First five results:
ACB
ADB
AEB
AFB
AGB

Kev:

Why is that when a nice programming challenge is presented to a bunch of developers all they can do is argue about grammar and spelling?

Cause when they actually write the programs, we end up with fodder for thedailywft.com. :)

Guido:

N0ob:

... incorrect SQL code ...

First five results:
ACB
ADB
AEB
AFB
AGB

DOH! I'm an idiot :)

The wording is very unclear however given that it says 455 combinations I am assuming by abreast it means in the same row.

If they meant literally side by side then there would be 2730 combinations to choose from

Hatterson:

The wording is very unclear however given that it says 455 combinations I am assuming by abreast it means in the same row.

If they meant literally side by side then there would be 2730 combinations to choose from

Except that, during the course of one week, no two girls can ever be in the same group. E.g., if Group 1 is ABC, then AB, BC and AC *cannot* appear in any subsequent groups until the week is exhausted (35 entires), or you have not satisfied the requirements of the problem. Keeping this caveat in mind, there are only 455 combinations for a group of 15 individuals broken into groups of 3.

Evo:

Does anybody actually like these? I don't think this is the place for such things; if I want questions like this there are plenty of sites.

But okay, my answer in bash:

function threeSomes()

{

  echo "Sun   Mon   Tue   Wed   Thu   Fri   Sat"

  echo A,F,K A,B,E B,C,F E,F,I C,E,K E,G,M K,M,D

  echo B,G,L C,D,G D,E,H G,H,K D,F,L F,H,N L,N,E

  echo C,H,M H,I,L I,J,M L,M,A G,I,O I,K,B O,B,H

  echo D,I,N J,K,N K,L,O N,O,C H,J,A J,L,C A,C,I

  echo E,J,O M,O,F N,A,G B,D,J M,N,B O,A,D F,G,J

}

Computing and printing are not the same thing, or so I tell all the secretaries who show up at our developer interviews.

Mel:

Should this also consider best friends, sworn enemies and "She said.. she said.."?

(I went to a girls-only school for 5 years - it's war out there, with a very delicate political situation and alliances changing daily. I still don't know the rules! Despite being a girl...)

I'd love to go to an all-girl school

Compiler error: Too many arguments when calling Girl()

Haskell B Curry:

Brute force solution is Haskell, main function is abreast (and not pretty printed):

data Girl = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O deriving (Show, Eq, Ord, Enum)



girls = [A .. O]



three = [ (a,b,c) | a <- girls , b <- girls , c <- girls , a < b , b < c ]



pairs a b c = filter (\(x,y,z) -> ( (cntThree a b c [x,y,z]) <= 1))



cntThree a b c xs = (foldl (\y x -> if ( (x==a) || (x==b) || (x==c) ) then y+1 else y) 0 xs)



abreast = abreast' three



abreast' [] = []

abreast' ((a,b,c):xs) = (a,b,c) : (abreast' (pairs a b c xs))

Is it just me, or are the Haskell solutions to these things the only ones worth looking at?

I mean, I have no idea what this gibberish means.

But it looks right to me.

Hmm, I thought I'd better throw out a PERL implementation :)

sub test_threesomes {

    my $ladies = [qw (A B C D E F G H I J K L M N O)];

    my $threesomes = {};

    my $total = scalar(@$ladies);

    for (my $address1 = 0; $address1 <= $total; $address1++) {

        for (my $address2 = $address1+1; $address2 <= $total; $address2++) {

            for (my $address3 = $address2+1; $address3 <= $total; $address3++) {

                next if ( !$ladies->[$address1] || !$ladies->[$address2] || !$ladies->[$address3] );

                my @combo = ($ladies->[$address1], $ladies->[$address2], $ladies->[$address3] );

                # Sort the combo array to prevent collisions

                my @sorted_combo = sort(@combo);

                my $room = join ('', @sorted_combo);

                $threesomes->{$room} = $room;

            }

        }

    }

    use Data::Dumper;

    print Dumper(keys %$threesomes);

    print sprintf ("Combinations: %d \n", scalar keys %$threesomes);

}

Herby:

Is is just me, or doesn't Flo sell insurance, and ride a motorcycle (a 900 V-twin) to work. She isn't a school girl as far as I know. I could be mistaken, but I believe that Flo is a more Progressive person!

Flo shows up once a month, visits all the schoolgirls, and sells feminine products.

... snipped whining ...

When I first started coming here, about four years ago, this place was like a programmer's bar, where you could sit around, engage in friendly banter, throw darts at a target if you were so inclined, and generally relax and have a good time in the company of like-minded professionals.

Now, all of a sudden it's like being in 7th grade. YOU WILL PAY ATTENTION! YOU WILL TALK ABOUT THE SUBJECT AT HAND! OR YOU WILL BE SENT TO THE PRINCIPAL'S OFFICE!

... snipped tear shedding ...



Note from Alex: Yeah yeah, I get it, TDWTF has been going down hill since day two, I jump the shark at least once a week, you're going to stop reading, etc. You are more than welcome to hang out at the forums, where there is virtually no moderation... but most of the (silent) readers don't want to see you bloviate in the comments about nonsense, especially in a coding challenge article.

Ruby

require 'matrix'



class G

  def initialize ngirls

    @girlRange = 0...ngirls

    @nDays = 15

    @days = 0

    @matched = Matrix.identity(@girlRange.count).to_a

    until setup1 

    end

  end

  def setup1

    @girlRange.to_a.combination(3).to_a.each do |trip|

      return true if (@days += setup2 trip) >= @nDays

    end

  end

  def setup2 trip

    for m in 0..2

      for n in m.succ..2

        return 0 if @matched[trip[m]][trip[n]] > 0 

      end

    end 

    for m in 0..2

      for n in m.succ..2

        raise StandardError if @matched[trip[m]][trip[n]] > 0

        @matched[trip[m]][trip[n]] = 1

        @matched[trip[n]][trip[m]] = 1

      end

    end

    trip.each { |girl| print (girl + ?A).chr }; print "\n"

    return 1

  end

  G

end.new(15)

It's not really clear from the question what's being requested. This is my interpretation:

Given a unique list L of length LC, produce a set of sets SS of size G (girl count) arranged in N groups (rows) over D days (columns) such that:

1) The number of groups corresponds to orderings of subgroups from L, so N = LC / G

Easy:
1) For a list L of length LC=15, produce N=5 sets of G=3 girls over D=7 days (SS = 7*5=35 sets total)
2) No pair of girls may repeat throughout any set

Medium:
3) Solve for any length LC, and for the day count ((LC-1)/2), given LC mod 3 == 0 and LC mod 2 == 1

Difficult:
4) Extend Easy as one week to 13 weeks, such that no complete set repeats ever, and such that the pair restriction is set per-week

Given that interpretation, it's actually just a pretty straightforward column/row restrained depth first search, and this basically boils down to a freshman example of Don Knuth's algorithm X.

WHERE IS ALICE?!?!? AND EVE!!!!

Since everyone loves C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace ladies

{

    class Program

    {

        static void Main(string[] args)

        {

            String[] Ladies = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O" };

            LinkedList<String[]> results = new LinkedList<String[]>();

            String[] Current;

            Random Rand = new Random();

            for (int i = 0; i < 35; i++)

            {

                Current = new String[3];

            giveup:

                try

                {

                    Current[0] = Ladies[Rand.Next(Ladies.Length)];

                    Current[1] = Ladies[Rand.Next(Ladies.Length)];

                    Current[2] = Ladies[Rand.Next(Ladies.Length)];

                    int j = Int32.Parse("0");

                    if (Current[0].Equals(Current[1])) { int k = 1 / j; }

                    if (Current[0].Equals(Current[2])) { int k = 1 / j; }

                    if (Current[1].Equals(Current[2])) { int k = 1 / j; }

                    for (int a = 0; a < results.Count; ++a)

                    {

                        if (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2]))

                        {

                            if (Current[1].Equals(results.ElementAt(a)[0]) || Current[1].Equals(results.ElementAt(a)[1]) || Current[1].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                            else if (Current[2].Equals(results.ElementAt(a)[0]) || Current[2].Equals(results.ElementAt(a)[1]) || Current[2].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                        }

                        if (Current[1].Equals(results.ElementAt(a)[0]) || Current[1].Equals(results.ElementAt(a)[1]) || Current[1].Equals(results.ElementAt(a)[2]))

                        {

                            if (Current[2].Equals(results.ElementAt(a)[0]) || Current[2].Equals(results.ElementAt(a)[1]) || Current[2].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                            else if (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                        }

                        if (Current[2].Equals(results.ElementAt(a)[0]) || Current[2].Equals(results.ElementAt(a)[1]) || Current[2].Equals(results.ElementAt(a)[2]))

                        {

                            if (Current[1].Equals(results.ElementAt(a)[0]) || Current[1].Equals(results.ElementAt(a)[1]) || Current[1].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                            else if (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2]))

                            {

                                int k = 1 / j;

                            }

                        }

                    }

                    results.AddLast(Current);



                }

                catch

                {

                    goto giveup;

                }

                Console.WriteLine(results.ElementAt(results.Count-1)[0].ToString() + results.ElementAt(results.Count-1)[1].ToString() + results.ElementAt(results.Count-1)[2].ToString());

            }

            Console.ReadLine();

        }

    }

}

It may be possible to optimise this by replacing Random with a quantum-based generator, and putting a DestroyUniverse() in the catch block.

Anonymous:

I got as far as reading about fifteen young girls and their breasts but then my mind just wandered off. I don't think I'm going to be of much help for this Praxis.

You are not alone. 3 abreast brings total recall to mind.

what the real wtf the:

3 abreast brings total recall to mind.

You'd be better off recalling Eccentrica Gallumbits.

Code Dependent:

Note from Alex: Yeah yeah, I get it, TDWTF has been going down hill since day two, I jump the shark at least once a week, you're going to stop reading, etc. You are more than welcome to hang out at the forums, where there is virtually no moderation... but most of the (silent) readers don't want to see you bloviate in the comments about nonsense, especially in a coding challenge article.

Thanks, Alex. Point understood.

MikeK:

Since everyone loves C#

I'd rather love to see proper C#... not this silly throw-catch jump followed by goto. :-w

            for (int i = 0; i < 35; i++)

            {

                Current = new String[3];

                while(true)

                {

                    Current[0] = Ladies[Rand.Next(Ladies.Length)];

                    Current[1] = Ladies[Rand.Next(Ladies.Length)];

                    Current[2] = Ladies[Rand.Next(Ladies.Length)];

                    if (Current[0].Equals(Current[1])) continue;

                    if (Current[0].Equals(Current[2])) continue;

                    if (Current[1].Equals(Current[2])) continue;

                    if (AlreadyContains(results, Current))

                    {

                        continue;

                    }

                    results.AddLast(Current);

                    break;

                }

                Console.WriteLine(results.ElementAt(results.Count-1)[0].ToString() +

                    results.ElementAt(results.Count-1)[1].ToString() +

                    results.ElementAt(results.Count-1)[2].ToString());

            }

            Console.ReadLine();

Anyway, IMO the problem with your solution is that you can't guarantee that any (random) choice of results for the first days will be extensible to a solution...

The relevant graph theory construction is called a Steiner Triple System.

John Haugeland:

It's not really clear from the question what's being requested. This is my interpretation:

Given a unique list L of length LC, produce a set of sets SS of size G (girl count) arranged in N groups (rows) over D days (columns) such that:

1) The number of groups corresponds to orderings of subgroups from L, so N = LC / G

Easy:
1) For a list L of length LC=15, produce N=5 sets of G=3 girls over D=7 days (SS = 7*5=35 sets total)
2) No pair of girls may repeat throughout any set

Medium:
3) Solve for any length LC, and for the day count ((LC-1)/2), given LC mod 3 == 0 and LC mod 2 == 1

Difficult:
4) Extend Easy as one week to 13 weeks, such that no complete set repeats ever, and such that the pair restriction is set per-week

Given that interpretation, it's actually just a pretty straightforward column/row restrained depth first search, and this basically boils down to a freshman example of Don Knuth's algorithm X.

Which is actually a pretty neat basis for tackling these things. It certainly beats nightmare posts involving VB, PHP, Perl, random seeds, etc. At least we're in the world of algorithmic complexity.

What would be really cool would be a solution involving a not-yet-invented language, such as C++0x with added constraints goodness. (See Stepanov's latest book for possible approaches.) At least that way you'd be writing algorithms with the possibility of reuse.

Other than that, I'm sticking with my theory that Haskell is the way to go. I can't write it, but I can appreciate it.

Bim Job:

What would be really cool would be a solution involving a not-yet-invented language, such as C++0x with added constraints goodness. (See Stepanov's latest book for possible approaches.) At least that way you'd be writing algorithms with the possibility of reuse.

Prolog?

John Haugeland:

Given that interpretation, it's actually just a pretty straightforward column/row restrained depth first search, and this basically boils down to a freshman example of Don Knuth's algorithm X.

Dancing Links was my thought on how to solve it too. I find a solution to the easy problem in 550ms, to the medium problem with n=9 in 20ms; I ran the hard problem overnight without finding a solution and aborted it in the morning. Medium problem with n=21 and modification to the easy problem to find all solutions rather than the first are also rather slow.

Easy problem: 3185 rows x 210 columns
Medium problem, n=21: 13300 rows x 420 columns
Hard: 41405 rows x 3185 columns

As the algorithm is exponential in the worst case it's a question of being lucky with the heuristics.

pjt33:

Easy problem: 3185 rows x 210 columns

How do you arrive at these numbers? It would seem that there are 35 slots (7 days times 5 groups) to fill with a selection from 455 possible groups. This gives a rowcount of 35 * 455 = 15925 rows. Also the column count (number of restraints) would be 245 = 210 (only one of each pair) + 35 (only one group in each slot).

Also, kudos to BYOC for bringing a problem which made me try out several different approaches. :-)

holgaard:

210 (only one of each pair) + 35 (only one group in each slot)

Imprecisely worded. There are 15*14/2 = 105 pair restraints (each pair only once, 7*15 = 105 person restraints (only one appearance each day), and the 35 group restraint (only one slot for each group) - for a grand total of 245.

holgaard:

pjt33:

Easy problem: 3185 rows x 210 columns

How do you arrive at these numbers?

Each girl is paired up with each other girl precisely once (pigeon-hole principle: the number of days is such that this is necessary to avoid repeating a pairing); each girl sallies forth each day. Denote the set of girls as G, define an arbitary total ordering on them (e.g. Ashley < Beth < ... < Odessa). Denote the set of days as D.

The set I try to cover is {(g1, g2) | g1,g2 in G and g1 < g2} U {(g, d) | g in G and d in D}.

The sets I use to cover it are {S(g1, g2, g3, d) | g1,g2,g3 in G and g1 < g2 < g3 and d in D} where S(g1, g2, g3, d) = {(g1, g2), (g1, g3), (g2, g3), (g1, d), (g2, d), (g3, d)}.

Therefore the medium problem has (num_girls CHOOSE 3) * num_days rows and (num_girls CHOOSE 2) + (num_girls * num_days) columns.

Following some research, and relying on an unproven conjecture, I have now solved (an interpretation of) the hard problem by the simple technique of finding a solution to the easy problem, removing the corresponding rows from the matrix, and trying again. I tried to post a solution here, but apparently it looks like spam: I shall post it in the forum.

Addendum (2009-09-18 09:21):
Oops. I wasn't removing all the rows I should have done. Now fixed and 6 weeks generated after 10 minutes...

Addendum (2009-09-18 12:21):
And still only 6 weeks generated after more than 3 hours. How embarrassing.

C:

I'd rather love to see proper C#... not this silly throw-catch jump followed by goto. :-w

Riiight. Because a "while(true){ continue;/break;} is much more proper... <rolleyes/>

Here's a nickel kid. Go buy yourself a proper programming education.

Lumberjack:

Riiight. Because a "while(true){ continue;/break;} is much more proper... <rolleyes/>

So you really suggest i use a boolean flag and extra (nested) if's?

C:

Lumberjack:

Riiight. Because a "while(true){ continue;/break;} is much more proper... <rolleyes/>

So you really suggest i use a boolean flag and extra (nested) if's?

The mere fact that you would find that suggestion laughable does confirm the fact that you need proper programming education.

while(true)

{

    a;

    if(x)

    {

        continue;

    }

    b;

    break;

}

can be converted to:

done = false;

while(!done)

{

    a;

    if(!x)

    {

        b;

        done = true;

    }

}

God have mercy on your coworkers' souls.

Slightly less non-serious solution.

            String[] Ladies = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O" };

            LinkedList<String[]> results = new LinkedList<String[]>();

            String[] Current = new String[3];

            bool sadface = false;

            int x,y,z,a;

            bool b1,b2,b3;

            for (x = 0; x < 15; ++x)

            {

                Current[0] = Ladies[x];

                for (y = 0; y < 15; ++y)

                {

                    Current[1] = Ladies[y];

                    for (z = 0; z < 15; ++z)

                    {

                        Current[2] = Ladies[z];

                        if (Current[0].Equals(Current[1])) { continue; }

                        if (Current[0].Equals(Current[2])) { continue; }

                        if (Current[1].Equals(Current[2])) { continue; }

                        for (a = 0; a < results.Count; ++a)

                        {

                            b1 = (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2]));

                            b2 = (Current[1].Equals(results.ElementAt(a)[0]) || Current[1].Equals(results.ElementAt(a)[1]) || Current[1].Equals(results.ElementAt(a)[2]));

                            b3 = (Current[2].Equals(results.ElementAt(a)[0]) || Current[2].Equals(results.ElementAt(a)[1]) || Current[2].Equals(results.ElementAt(a)[2]));

                            if (b1 && b2 || b1 && b3 || b2 && b3)

                            {

                                sadface=true; break;

                            }

                        }

                        if (sadface) { sadface = false; continue; }

                        String[] res = new String[3];

                        Current.CopyTo(res, 0);

                        results.AddLast(res);

                        Console.WriteLine(results.Count.ToString() + ":" + results.ElementAt(results.Count - 1)[0].ToString() + results.ElementAt(results.Count - 1)[1].ToString() + results.ElementAt(results.Count - 1)[2].ToString());

                    }

                }

            }

            Console.ReadLine();

I don't suppose there's a cleaner way to break out of two loops?