- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Please tell me I've failed to see some crucial bit of humour in this ridiculous example.
do { a; } while(x); b;Did they not teach you the wonders of do-while during your "proper programming education"?
Admin
Obviously, not enough. I will take a penny if you have one to spare.
Admin
Hmmm.
Two things: first, it doesn't seem to solve the task, since two ladies aren't supposed to be paired more than once.
Second, sorting @combo is never needed.
Btw: why Data::Dumper and not just print "$_\n" for keys %$threesomes?
Admin
Alex,
Seriously, I must thank you for posting this interesting problem, but also congratulate you, you clever sod. After all the whining we've seen about BYOC in the past, making this week's problem something that looks simple but quickly leads to combinatorial explosion if approached naively, was nothing short of brilliant. :D
Thank you, and keep them coming!
Admin
PHP Code:
error_reporting(E_ALL); function printGroups($girls) { $d = 1; $b = array(); foreach($girls as $g1){ $b[$g1] = array(); foreach($girls as $g2) $b[$g1][$g2] = false; } foreach($girls as $g1) foreach($girls as $g2) foreach($girls as $g3) if(!$b[$g1][$g2] && !$b[$g1][$g3] && !$b[$g2][$g3] && !$b[$g3][$g1] && $g1 != $g2 && $g2 != $g3 && $g3 != $g1) { echo $g1.$g2.$g3." "; if($d++ % 7 == 0) echo "\n"; $b[$g1][$g2] = $b[$g1][$g3] = $b[$g2][$g3] = true; } if(($d-1)%7!=0) echo "\n"; } printGroups(str_split("ABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890abcdefghijklm"));Admin
for (int i = 0; i < 35; i++) { Current = new String[3]; bool needing = true; while(needing) { needing = false; 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])) { needing = true; } if(!needing){ if (Current[0].Equals(Current[2])) { needing = true; } if(!needing){ if (Current[1].Equals(Current[2])) { needing = true; } if(!needing){ 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])) { needing = true; } else if (Current[2].Equals(results.ElementAt(a)[0]) || Current[2].Equals(results.ElementAt(a)[1]) || Current[2].Equals(results.ElementAt(a)[2])) { needing = true; } } if(!needing){ 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])) { needing = true; } else if (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2])) { needing = true; } } if(!needing){ 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])) { needing = true; } else if (Current[0].Equals(results.ElementAt(a)[0]) || Current[0].Equals(results.ElementAt(a)[1]) || Current[0].Equals(results.ElementAt(a)[2])) { needing = true; } } } }} if(!needing){ results.AddLast(Current); }}}} } Console.WriteLine(results.ElementAt(results.Count-1)[0].ToString() + results.ElementAt(results.Count-1)[1].ToString() + results.ElementAt(results.Count-1)[2].ToString()); }PS I don't really have coworkers to worry about, I am usually left to handle coding all by myself. :-|
Admin
I've thought about this for a while, but I haven't managed to come up with any particularly efficient solutions yet. It's surprisingly tricky...
Admin
@Mr.'; Drop Database:
Absolutely, that's what I find brilliant about this problem. Coming up with a horribly slow or downright nonfunctional solution, as many have done here, is easy. Coming up with something that works and works well is nowhere near amateur level.
I solved it by implementing algorithm X (http://en.wikipedia.org/wiki/Knuth's_Algorithm_X) as has been suggested by other commenters, using the dancing links technique (http://en.wikipedia.org/wiki/Dancing_Links). It works well, although remains slow for num_girls=21.
The nice thing is, once you have implemented algorithm X, solving the Kirkman's Ladies problem boils down to expressing it as a boolean matrix representing an exact cover problem. It needs a little analytical thinking and possibly a piece of paper to visualize, but once you've got it you can basically solve all the (reasonably sized) problems of the same type.
This is a particularly rewarding BYOC problem, especially if you've not done deep algorithmic work in a while. I hope the upcoming ones will be as good. :)
Admin
Maybe I should debug it on just nine girls first...
Admin
Hi Mr. Drop Database,
I did it in Python too, although it's admittedly not the most efficient language for putzing around with links. I wonder if a numpy-based implementation would be thinkable.
All the same, 15925 rows sounds way too much for the N=15 problem. Even for the N=21 I 'only' have 13300 rows. For N=15 I have 3185 rows. What does your matrix look like then?
Admin
Admin
Hi Mr. DropDB (getting less and less formal here, am I?),
Yes, accounting for different positions each day is unneeded since you can trivially switch around a given day's girl triplets without impacting the validity of the solution. :)
Admin
Admin
Hi pjt33,
Nope, an NP problem stays so even given a non-naive algorithm, but those still work a hell of a lot better than naive algorithms. Remember, NP problems with a perfect theoretical heuristic can be solved in polynomial time, by definition. In practice a good heuristic -- like the selection of the column with the least 1s in algorithm X -- already makes a world of difference.
Admin
I finally got my implementation to work for n = 15 in a couple of seconds. I had to upgrade my DLX implementation to allow constraints that could be satisfied an arbitrary number of times. Even so, it seems to take an awfully long time for n = 21.
Admin
You need to be really patient to compile this. All I can say is it takes more than 4 hours for MSVC9 to compile it on Intel Core2 Duo with 2GB system memory! What's good for this is that it does all calculations in compile time so the resulting program will be super fast! Changing number_of_days constant to some value under 10 will help your compiler a lot, although you will only get results for first few days.
Q: Template metaprograms are too difficult to read. They are write-only code. A: No, come on. Look at my code! It's even quite readable without a single comment
Q: Compilation takes too much time. A: Who cares? We compile it and ship to customers. Our customers will run super-fast program and be happy.
#include <stdio.h> void functionWhichSolvesKirkmansLadiesProblem(); typedef int TypeDefForGirl; enum{ number_of_girls = 15 }; enum{ number_of_days = 35 }; #define I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE template < TypeDefForGirl a_girl_in_abreast, TypeDefForGirl another_girl_in_abreast, TypeDefForGirl even_another_girl_in_abreast> struct TemplateStructWhichRepresentsAnAbreast {}; template < typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast> struct TemplateStructWhichDefinesAStaticFunctionWhichPrintsTheAbrest; template < TypeDefForGirl a_girl_in_abreast, TypeDefForGirl another_girl_in_abreast, TypeDefForGirl even_another_girl_in_abreast> struct TemplateStructWhichDefinesAStaticFunctionWhichPrintsTheAbrest < TemplateStructWhichRepresentsAnAbreast<a_girl_in_abreast, another_girl_in_abreast, even_another_girl_in_abreast>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> { static void staticFunctionWhichprintsTheAbrest() { printf( "%c %c %c\n", static_cast<char>('A' + a_girl_in_abreast), static_cast<char>('A' + another_girl_in_abreast), static_cast<char>('A' + even_another_girl_in_abreast) ); } }; template < typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast> struct TemplateStructWhichDefinesNextValidAbreastInside; template < TypeDefForGirl a_girl_in_abreast, TypeDefForGirl another_girl_in_abreast, TypeDefForGirl even_another_girl_in_abreast> struct TemplateStructWhichDefinesNextValidAbreastInside < TemplateStructWhichRepresentsAnAbreast<a_girl_in_abreast, another_girl_in_abreast, even_another_girl_in_abreast>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> { typedef TemplateStructWhichRepresentsAnAbreast< a_girl_in_abreast, another_girl_in_abreast, static_cast<TypeDefForGirl>(even_another_girl_in_abreast+1)> ASpecializationOfTemplateStructWhichRepresentsAnAbreastWhichIsNextValidAbreast; }; template < TypeDefForGirl a_girl_in_abreast, TypeDefForGirl another_girl_in_abreast> struct TemplateStructWhichDefinesNextValidAbreastInside < TemplateStructWhichRepresentsAnAbreast<a_girl_in_abreast, another_girl_in_abreast, static_cast<TypeDefForGirl>(number_of_girls-1)>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> { typedef TemplateStructWhichRepresentsAnAbreast< a_girl_in_abreast, static_cast<TypeDefForGirl>(another_girl_in_abreast+1), static_cast<TypeDefForGirl>(another_girl_in_abreast+2)> ASpecializationOfTemplateStructWhichRepresentsAnAbreastWhichIsNextValidAbreast; }; template < TypeDefForGirl a_girl_in_abreast> struct TemplateStructWhichDefinesNextValidAbreastInside < TemplateStructWhichRepresentsAnAbreast<a_girl_in_abreast, static_cast<TypeDefForGirl>(number_of_girls-2), static_cast<TypeDefForGirl>(number_of_girls-1)>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> { typedef TemplateStructWhichRepresentsAnAbreast< static_cast<TypeDefForGirl>(a_girl_in_abreast+1), static_cast<TypeDefForGirl>(a_girl_in_abreast+2), static_cast<TypeDefForGirl>(a_girl_in_abreast+3)> ASpecializationOfTemplateStructWhichRepresentsAnAbreastWhichIsNextValidAbreast; }; template < typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast, typename AnotherSpecializationOfTemplateStructWhichRepresentsAnAbreast> struct TemplateStructWhichChecksIfAbreastsConflictEachOther; template < TypeDefForGirl a_girl_in_an_abreast, TypeDefForGirl another_girl_in_an_abreast, TypeDefForGirl even_another_girl_in_an_abreast, TypeDefForGirl a_girl_in_another_abreast, TypeDefForGirl another_girl_in_another_abreast, TypeDefForGirl even_another_girl_in_another_abreast> struct TemplateStructWhichChecksIfAbreastsConflictEachOther < TemplateStructWhichRepresentsAnAbreast<a_girl_in_an_abreast, another_girl_in_an_abreast, even_another_girl_in_an_abreast>, TemplateStructWhichRepresentsAnAbreast<a_girl_in_another_abreast, another_girl_in_another_abreast, even_another_girl_in_another_abreast>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> { enum{ do_they_conflict = ( a_girl_in_an_abreast== a_girl_in_another_abreast || a_girl_in_an_abreast== another_girl_in_another_abreast || a_girl_in_an_abreast==even_another_girl_in_another_abreast ) + ( another_girl_in_an_abreast== a_girl_in_another_abreast || another_girl_in_an_abreast== another_girl_in_another_abreast || another_girl_in_an_abreast==even_another_girl_in_another_abreast ) + ( even_another_girl_in_an_abreast== a_girl_in_another_abreast || even_another_girl_in_an_abreast== another_girl_in_another_abreast || even_another_girl_in_an_abreast==even_another_girl_in_another_abreast ) >= 2 ? 1 : 0 }; }; template < typename SomeTypeWhichRepresentsSchedule, typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast, int index_of_day, int shall_we_stop> struct TemplateStructWhichChecksIfAnAbreastConflictsWithExistingSchedule { enum{ does_it_conflict = TemplateStructWhichChecksIfAbreastsConflictEachOther< typename SomeTypeWhichRepresentsSchedule ::template TemplateWhoseEachSpecializationContainsTheAbreastOfDay<index_of_day> ::ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay, ASpecializationOfTemplateStructWhichRepresentsAnAbreast >::do_they_conflict ? 1 : TemplateStructWhichChecksIfAnAbreastConflictsWithExistingSchedule< SomeTypeWhichRepresentsSchedule, ASpecializationOfTemplateStructWhichRepresentsAnAbreast, index_of_day+1, index_of_day+1 == SomeTypeWhichRepresentsSchedule::number_of_days_of_schedule >::does_it_conflict ? 1 : 0 }; }; template < typename SomeTypeWhichRepresentsSchedule, typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast, int index_of_day> struct TemplateStructWhichChecksIfAnAbreastConflictsWithExistingSchedule < SomeTypeWhichRepresentsSchedule, ASpecializationOfTemplateStructWhichRepresentsAnAbreast, index_of_day, 1> { enum{ does_it_conflict = 0 }; }; template < typename SomeTypeWhichRepresentsSchedule, typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast, int does_it_conflict> struct TemplateStructWhichQuitsIfCurrentCombinationIsValidOrProceedToNextOtherwise { typedef typename TemplateStructWhichQuitsIfCurrentCombinationIsValidOrProceedToNextOtherwise< SomeTypeWhichRepresentsSchedule, typename TemplateStructWhichDefinesNextValidAbreastInside<ASpecializationOfTemplateStructWhichRepresentsAnAbreast> ::ASpecializationOfTemplateStructWhichRepresentsAnAbreastWhichIsNextValidAbreast, TemplateStructWhichChecksIfAnAbreastConflictsWithExistingSchedule< SomeTypeWhichRepresentsSchedule, typename TemplateStructWhichDefinesNextValidAbreastInside<ASpecializationOfTemplateStructWhichRepresentsAnAbreast> ::ASpecializationOfTemplateStructWhichRepresentsAnAbreastWhichIsNextValidAbreast, 0, 0 == SomeTypeWhichRepresentsSchedule::number_of_days_of_schedule>::does_it_conflict> ::ASpecializationOfTemplateStructWhichRepresentsTheAbreastWhichCausedThisQuit ASpecializationOfTemplateStructWhichRepresentsTheAbreastWhichCausedThisQuit; }; template < typename SomeTypeWhichRepresentsSchedule, typename ASpecializationOfTemplateStructWhichRepresentsAnAbreast> struct TemplateStructWhichQuitsIfCurrentCombinationIsValidOrProceedToNextOtherwise < SomeTypeWhichRepresentsSchedule, ASpecializationOfTemplateStructWhichRepresentsAnAbreast, 0> { typedef ASpecializationOfTemplateStructWhichRepresentsAnAbreast ASpecializationOfTemplateStructWhichRepresentsTheAbreastWhichCausedThisQuit; }; template <typename SomeTypeWhichRepresentsSchedule> struct TemplateStructWhichDeterminesANewAbreastCombination : TemplateStructWhichQuitsIfCurrentCombinationIsValidOrProceedToNextOtherwise < SomeTypeWhichRepresentsSchedule, TemplateStructWhichRepresentsAnAbreast< static_cast<TypeDefForGirl>(0), static_cast<TypeDefForGirl>(1), static_cast<TypeDefForGirl>(2)>, TemplateStructWhichChecksIfAnAbreastConflictsWithExistingSchedule< SomeTypeWhichRepresentsSchedule, TemplateStructWhichRepresentsAnAbreast< static_cast<TypeDefForGirl>(0), static_cast<TypeDefForGirl>(1), static_cast<TypeDefForGirl>(2)>, 0, 0 == SomeTypeWhichRepresentsSchedule::number_of_days_of_schedule>::does_it_conflict> {}; template <int number_of_days> struct TemplateStructWhichIsANonConflictingScheduleWithGivenLength { enum{ number_of_days_of_schedule = number_of_days }; template<int day> struct TemplateWhoseEachSpecializationContainsTheAbreastOfDay { typedef typename TemplateStructWhichIsANonConflictingScheduleWithGivenLength<number_of_days-1> ::template TemplateWhoseEachSpecializationContainsTheAbreastOfDay<day> :: ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay; static void staticFunctionWhichPrintsThisAndSoOn() { TemplateStructWhichDefinesAStaticFunctionWhichPrintsTheAbrest < ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay> ::staticFunctionWhichprintsTheAbrest(); TemplateWhoseEachSpecializationContainsTheAbreastOfDay<day+1> ::staticFunctionWhichPrintsThisAndSoOn(); } }; template<> struct TemplateWhoseEachSpecializationContainsTheAbreastOfDay<number_of_days-1> { typedef typename TemplateStructWhichDeterminesANewAbreastCombination< TemplateStructWhichIsANonConflictingScheduleWithGivenLength<number_of_days-1>I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE> ::ASpecializationOfTemplateStructWhichRepresentsTheAbreastWhichCausedThisQuit ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay; static void staticFunctionWhichPrintsThisAndSoOn() { TemplateStructWhichDefinesAStaticFunctionWhichPrintsTheAbrest < ASpecializationOfTemplateStructWhichRepresentsTheAbreastForThisDay> ::staticFunctionWhichprintsTheAbrest(); } }; static void staticFunctionWhichPrintsThisSchedule() { TemplateWhoseEachSpecializationContainsTheAbreastOfDay<0> ::staticFunctionWhichPrintsThisAndSoOn(); } }; template <> struct TemplateStructWhichIsANonConflictingScheduleWithGivenLength <0> { enum{ number_of_days_of_schedule = 0 }; template<int day> struct TemplateWhoseEachSpecializationContainsTheAbreastOfDay; static void staticFunctionWhichPrintsThisSchedule() {} }; void functionWhichSolvesKirkmansLadiesProblem() { TemplateStructWhichIsANonConflictingScheduleWithGivenLength<number_of_days> ::staticFunctionWhichPrintsThisSchedule(); }Admin
That's a pretty clever solution. The I_CANNOT_PUT_TWO_ANGLE_BRACKETS_HERE part just floored me. :)
Admin
Admin
I lost it at this comment.
Admin
This wouldn't work in real life - girls go round in cliques and have enemies they would never talk to, so the answer is:
ABC DEF GHI JKL MNO ABC DEF GHI JKL MNO ABC DEF GHI JKL MNO ... ... ... ... ...
Admin
class Program { static char[, ,] rota = new char[7, 5, 3]; static int solutions = 0; static void displaySolution() { Console.WriteLine("Solution: {0}", ++solutions); for (int i = 0; i < 105; i++) { Console.Write(rota[i / 15, (i % 15) / 3, i % 3]); if (i % 3 == 2) Console.Write(' '); if (i % 15 == 14) Console.WriteLine(); } Console.WriteLine(); } // check if a pair of letters has been used already in previous weeks static bool pairUsed(char a, char b, int currentWeek) { bool used = false; for (int week = 0; !used && week < currentWeek; week++) for (int day = 0; day < 5 && rota[week, day, 0] != '\0'; day++) { if (rota[week, day, 1] == '\0') continue; if (rota[week, day, 0] == a) { if (rota[week, day, 1] == b) { used = true; break; } if (rota[week, day, 2] == b) { used = true; break; } } if (rota[week, day, 1] == a && rota[week, day, 2] == b) { used = true; break; } } return used; } static void choose(int chosen) // chosen is the count of choices made so far (0 to 104) { int week = chosen / 15; char choice = (char)(chosen % 15 + 'A'); for (int day = 0; day < 5; day++) // days 'column', Mon-Fri { int posn; // find the first empty position of the three for each day (if one remains) for (posn = 0; posn < 3; posn++) if (rota[week, day, posn] == '\0') // position is empty break; if (posn < 3) // empty position found { // to avoid duplicate solutions, rows must be in alphabetical order. // as each row will begin with A, just check order of 2nd character if (day == 0 && posn == 1 && week > 0 && choice < rota[week - 1, day, posn]) continue; // check whether letter pair(s) has/have been used before, and continue if so if (posn >= 1 && pairUsed(rota[week, day, 0], choice, week)) continue; if (posn == 2 && pairUsed(rota[week, day, 1], choice, week)) continue; rota[week, day, posn] = choice; // record the choice if (chosen == 104) displaySolution(); else choose(chosen + 1); // else choose next letter rota[week, day, posn] = '\0'; // remove choice from records if (posn == 0) // was first choice for a day, no need to consider other days. break; } } } static void Main(string[] args) { // fix first row to avoid trivial duplicate solutions. for (int i = 0; i < 15; i++) rota[0, i / 3, i % 3] = (char)(i + 'A'); choose(15); Console.WriteLine("Done. Press any key"); Console.ReadKey(); } } }Admin
Your code don't run. It looks very c-ish to be ruby. And what are you trying to do with:
trip.each { |girl| print (girl + ?A).chr }; print "\n"
???
The error is on this line:
"in `+': String can't be coerced into Fixnum (TypeError)"