The Daily WTF: Curious Perversions in Information Technology

Code Dependent · 2009-09-16 Reply Admin

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.

2009-09-16 Reply Admin

"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.

Mel · 2009-09-16 Reply Admin

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...)

pjt33 · 2009-09-16 Reply Admin

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

2009-09-16 Reply Admin

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.

DrJDX · 2009-09-16 Reply Admin

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 '';
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.

2009-09-16 Reply Admin

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?

2009-09-16 Reply Admin

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 '';
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.)

2009-09-16 Reply Admin

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...

DrJDX · 2009-09-16 Reply Admin

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.

Evo · 2009-09-16 Reply Admin

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
}

TGV · 2009-09-16 Reply Admin

Get three abreast counters. Make a counter for every girl, set it to 0.
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.

2009-09-16 Reply Admin

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?)

Markp · 2009-09-16 Reply Admin

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?

2009-09-16 Reply Admin

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

2009-09-16 Reply Admin

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))

2009-09-16 Reply Admin

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!

2009-09-16 Reply Admin

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

2009-09-16 Reply Admin

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

2009-09-16 Reply Admin

N0ob:
... incorrect SQL code ...

First five results: ACB ADB AEB AFB AGB

2009-09-16 Reply Admin

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. :)

2009-09-16 Reply Admin

Guido:
N0ob:
... incorrect SQL code ...

First five results: ACB ADB AEB AFB AGB

DOH! I'm an idiot :)

2009-09-16 Reply Admin

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

DrJDX · 2009-09-16 Reply Admin

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.

2009-09-16 Reply Admin

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.

2009-09-16 Reply Admin

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

2009-09-16 Reply Admin

Compiler error: Too many arguments when calling Girl()

2009-09-16 Reply Admin

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.

rurouni88 · 2009-09-16 Reply Admin

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);
}

Code Dependent · 2009-09-16 Reply Admin

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.

Code Dependent · 2009-09-16 Reply Admin

... 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.

2009-09-17 Reply Admin

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)

2009-09-17 Reply Admin

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:

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

Easy:

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)
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.

2009-09-17 Reply Admin

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

2009-09-17 Reply Admin

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.

2009-09-17 Reply Admin

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. [image]

dkf · 2009-09-17 Reply Admin

what the real wtf the:
3 abreast brings total recall to mind.

You'd be better off recalling Eccentrica Gallumbits.

Code Dependent · 2009-09-17 Reply Admin

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.

2009-09-17 Reply Admin

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...

2009-09-17 Reply Admin

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

2009-09-17 Reply Admin

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:

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

Easy:

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)

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.

2009-09-18 Reply Admin

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?

pjt33 · 2009-09-18 Reply Admin

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.

2009-09-18 Reply Admin

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. :-)

2009-09-18 Reply Admin

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.

pjt33 · 2009-09-18 Reply Admin

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.

2009-09-18 Reply Admin

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.

2009-09-18 Reply Admin

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?

2009-09-18 Reply Admin

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.

2009-09-18 Reply Admin

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?

Kirkman's Ladies

Leave a comment on “Kirkman's Ladies”