Print Story PROGRAMMING FUN CHALLENGE: TRAGIC
Boredom
By jacob (Mon Apr 05, 2004 at 12:55:24 AM EST) (all tags)
Hi there! In light of a recent opinion poll, I decided to post this little challenge for you based on a real problem.

In a certain card game called Tragic, each player is asked to build his or her own deck by drawing pictures using any combination of markers (black, blue, red, yellow, and green) on each card in a stack of blank index cards. While the rules of playing the game are quite complicated and intricate, we care only about whether or not decks are legal for play at all. For a deck to be legal, there must be a way to divide the deck into five piles, one for each color, so that every card in a pile has that color in its illustration somewhere and each pile has at least 20 cards in it. So for instance, a deck that had twenty-five black/yellow cards, twenty-five blue/yellow cards, twenty-five red/yellow cards and twenty-five green/yellow cards would be legal because you could take five cards from each of those to form a yellow pile and use the remainder for piles of their other colors, but a deck with 1 yellow/black card, 20 yellow cards, 20 black cards, 20 blue cards, 19 green cards, 19 red cards, and 1 red/green card would not pass because the red/green card can only go into one pile and so the other pile will have to have one too few cards.

Your task is to write a program in the language of your choice that accepts a list of cards and determines if it is a legal Tragic deck or not.



INPUT

Your program will get on standard input a sequence of lines each consisting of one or more numbers from 0 to 4 (0 = black, 1 = blue, 2 = red, 3 = yellow, 4 = green), each number separated by a space and within a line all numbers always presented in sorted order (with no duplicates); there is no particular ordering of lines themselves. For instance the first deck mentioned above might be presented as:


0 3
0 3
... twenty-three more times
1 3
1 3
... twenty-three more times
2 3
2 3
... twenty-three more times
3 4
3 4
... twenty-three more times

(pfc_tragic_input_1.txt contains a full input file with this example; pfc_tragic_input_2.txt contains an input file representing the other example from the problem description.)

Every input will contain at least 100 and no more than 400 cards.

(If you'd rather accept input as a file than as standard input, make your program accept a filename as its first command-line parameter and let me know about it. Also, if there are big objections to this input format I'll hold a vote and make an alternate format if there's enough interest.)

OUTPUT

Print out legal or illegal, followed by a newline. Please don't print out anything else; that will make it easier for me to write an auto-judge.

POSTING YOUR CODE

Probably the best way to post your code is to post a top-level comment announcing your code (don't describe it there, though!) and then a reply to it that contains the code itself, along with a description of the algorithm used and instructions for making the program run (remember to format your code for posting using tmoertel's code formatting program as described in How to post code to K5 -- the easy way!). Please do not post code, algorithm descriptions,  or any direct hints at solving the problem as root-level comments here — it could spoil the fun for people who haven't had a chance to take a stab at the problem yet, and for this challenge in particular I expect that even little tiny hints could ruin the puzzle value of the problem entirely.

JUDGING CRITERIA

Correctness, efficiency and clarity will be the primary criteria by which I'll judge your programs. Secondarily I'll look at the generality of your solution (could it scale up to larger problems, or is it hardwired to just this one problem instance?). I care more about algorithmic efficiency than micro-efficiency, so don't feel like you've got to write in assembly or something to have a shot at winning.

AN ADDITIONAL NOTE

If it becomes necessary, I and the other entrants would appreciate you posting any interesting test cases you discover.

I'll accept entries until Wednesday, April 14, at midnight. I expect many people will have come up with clever solutions by then, but there's still

Now, good luck and get coding!

Update [2004-4-5 6:32:16 by gazbo]: Fixed link, changed deadline as per request

< I'd work for Google on the moon... | BBC White season: 'Rivers of Blood' >
PROGRAMMING FUN CHALLENGE: TRAGIC | 133 comments (133 topical, 0 hidden) | Trackback
Are you trying to confuse us by TPD (3.00 / 0) #1 Mon Apr 05, 2004 at 01:13:38 AM EST
by posting 2 identical links (http://www.hulver.com/scoop-files/4/pfc_tragic_input_1.txt)....

Looks interesting though I'm not certain I've even quite understood the question yet.... hopefully I'll have a chance to have a go before friday, though the end date does seem a bit near. (what time zone is that)

why sit, when you can sit and swivel with The Ab-SwivellerTM

oops by jacob (3.00 / 0) #2 Mon Apr 05, 2004 at 01:16:57 AM EST
the second should have been pfc_tragic_input_2.txt.

--

[ Parent ]
Also by jacob (6.00 / 1) #3 Mon Apr 05, 2004 at 01:17:40 AM EST
Yeah, I wrote this up half a week ago and forgot to change the deadline. I'll post an extension :)

--

[ Parent ]
Fixed link, kthxlol! by gazbo (6.00 / 1) #4 Mon Apr 05, 2004 at 01:19:54 AM EST
Would you like me to change the date to something else while I'm at it?

I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

[ Parent ]
yeah by jacob (3.00 / 0) #6 Mon Apr 05, 2004 at 01:20:41 AM EST
see the comment

--

[ Parent ]
DEADLINE CHANGED by jacob (3.00 / 0) #5 Mon Apr 05, 2004 at 01:20:16 AM EST
When I wrote this, April 9 was something like 10 days away, I was dumb and forgot to update that deadline when I posted it. Let's move it until the next Wednesday after that, April 14, at 11:59 PM CDT.

--

total cards? by garlic (3.00 / 0) #7 Mon Apr 05, 2004 at 02:15:20 AM EST
Are there always only 100 cards, or is there no upper limit on the number of cards?


nevermind, i'm a moron. by garlic (3.00 / 0) #8 Mon Apr 05, 2004 at 02:16:35 AM EST


[ Parent ]
Indeed. by GRiNGO (3.00 / 0) #20 Mon Apr 05, 2004 at 11:02:49 PM EST


- - -
"I send you to Baghdad a long time. Do they care, buddy?" - Three Kings.

[ Parent ]
bookmarked (nt) by codemonkey uk (3.00 / 0) #9 Mon Apr 05, 2004 at 02:48:30 AM EST


--- Thad ---
Almost as Smart As you.
This requires thought by gazbo (3.00 / 0) #10 Mon Apr 05, 2004 at 02:51:39 AM EST
I've got a rather cunning idea - it may come to nothing, but it requires proper thought.  Annoyingly I'm off on holiday over Easter, so don't have as much time as I'd like.  However, I'll see if I can find some time.

I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

Question by celeriac (6.00 / 1) #11 Mon Apr 05, 2004 at 02:13:35 PM EST
Are you looking for absolute correctness, or will reasonable heuristics suffice? Integer programming problems like this one have an annoying tendency to be NP-complete and thus intractable.

Reasonableness, not absolute correctness by jacob (3.00 / 0) #12 Mon Apr 05, 2004 at 02:30:52 PM EST
Though I'd prefer a somewhat less-efficient but more correct program to a fast, dumb program.

As a sidenote, I'd be interested if someone could prove this problem NP-complete.

--

[ Parent ]
NP-complete? by jjayson (3.00 / 0) #96 Wed Apr 14, 2004 at 06:54:32 PM EST
Umm... I don't think so. I think the problem is linear in the size of the deck.

In each legal deck, there is a minimal 100-card legal deck. Finding that is (probably) NP-complete (reduction from set cover).

However, just verifying if a deck is legal is probably linear. At least my solution is linear (the second one I posted).


[ Parent ]
Linear by ucblockhead (3.00 / 0) #98 Thu Apr 15, 2004 at 07:49:54 AM EST
I agree...at least my solution is linear, and I've yet to find a case that breaks it. (Not that I've looked that hard.)
---
[ucblockhead is] useless and subhuman
[ Parent ]
O(decksize^2) by jjayson (3.00 / 0) #99 Thu Apr 15, 2004 at 08:38:18 AM EST
I was too quick to type. I have a sort step before I distribute the cards into piles that I forgot about. I sort the cards as if they were base 10 numbers. Then the distribution part of the code is just throwing the card into the first available pile (first color pile, from 0 to 4, that has fewer than 20 cards). No moving cards between piles or anything after distribution is done.

[ Parent ]
Yay, PFC by matthewg (3.00 / 0) #13 Mon Apr 05, 2004 at 02:59:57 PM EST
Hi, I'm matthewg, or Matthew, or Matt.  You may remember me from the PFCs of yore.  My solution is in this thread.

Algorithm Description by matthewg (3.00 / 0) #14 Mon Apr 05, 2004 at 03:00:54 PM EST
We sort the colors by card count, so we give higher
priority to the colors with the fewest cards.

For each color, take cards with that color, and sort them by how many different colors they have, giving priority to colors with fewer cards.  Take the top 20.  If there aren't 20 available, the deck is illegal.

[ Parent ]
Try this input deck by tmoertel (3.00 / 0) #46 Fri Apr 09, 2004 at 06:33:15 PM EST
for f in "0 1" "1 2" "2 3" "3 4" "4 0"; do yes $f | head -20; done; \
| ./matthewg.pl

On my RHL 8.0 host I get "illegal", but I believe that this is a legal deck.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Thanks by matthewg (3.00 / 0) #47 Fri Apr 09, 2004 at 07:21:35 PM EST

I should've been resorting the colors based on card count after assigning each card. Fixed version:

#!/usr/bin/perl

use strict;
use warnings;

my @cards;
my %counts = (0 => 0, 1 => 0, 2 => 0, 3 => 0, 4 => 0);

# Read in the input.
# Cards are stored as array of hashrefs, containing keys:
#    colors, listref, 0/1 for each color
#    colorcount, how many different colors the card has
# We also maintain a hash of counts, how many cards we have of that color.
while(<>) {
    my @colors = qw(0 0 0 0 0);
    my $colorcount = 0;

    foreach (split) {
        $colors[$_] = 1;
        $counts{$_}++;
        $colorcount++;
    }

    push @cards, {
        colors => \@colors,
        colorcount => $colorcount
    };
}

# If we have less than 20 of any color, it can't possibly be legal
if(grep { $_ < 20 } values %counts) {
    print "illegal\n";
    exit;
}

# Okay, now the fun part.
# We sort the colors by card count, so we give higher
# priority to the colors with the fewest cards.
#
# For each color, take cards with that color, and sort them by
# how many different colors they have, giving priority to colors
# with fewer cards.  Take the top 20.  If there aren't 20 available,
# the deck is illegal.

my @rankedcolors = sort { $counts{$a} <=> $counts{$b} } keys %counts;
foreach my $color (@rankedcolors) {
    my $cardcount = 0;

    foreach my $card (sort {
            my $countdiff = $a->{colorcount} <=> $b->{colorcount};
            return $countdiff if $countdiff;

            foreach(@rankedcolors) {
                my $cmp = $a->{colors}->[$_] <=> $b->{colors}->[$_];
                return $cmp if $cmp;
            }

            return 0;
        } grep {
            $_->{colors}->[$color]
        } @cards
    ) {
        $cardcount++;

        for(my $i = 0; $i < 5; $i++) { $counts{$i}-- if $card->{colors}->[$i] };
        @rankedcolors = sort { $counts{$a} <=> $counts{$b} } keys %counts;

        $card->{colors} = [qw(0 0 0 0 0)]; # Zero out the card's colors, effectively removing it
        last if $cardcount >= 20;
    }

    if($cardcount < 20) {
        print "illegal\n";
        exit;
    }
}

print "legal\n";
exit;



[ Parent ]
Still not good... by matthewg (3.00 / 0) #49 Fri Apr 09, 2004 at 08:40:29 PM EST
I've been running it against my random-legal-deck generator, and it's still pretty bad, I'll have to rewrite it tomorrow. So far what I'm seeing posted is variations on brute-forcing, would be nice if something different could work...

[ Parent ]
Withdrawn by matthewg (3.00 / 0) #68 Tue Apr 13, 2004 at 06:07:48 PM EST
I don't think this approach is workable. I'd like to withdraw my current entries. If I have time, I'll put a brute-forcer together in some bizarre language, probably PostScript.

[ Parent ]
The Code by matthewg (3.00 / 0) #15 Mon Apr 05, 2004 at 03:02:02 PM EST
#!/usr/bin/perl

use strict;
use warnings;

my @cards;
my %counts = (0 => 0, 1 => 0, 2 => 0, 3 => 0, 4 => 0);

# Read in the input.
# Cards are stored as array of hashrefs, containing keys:
#    colors, listref, 0/1 for each color
#    colorcount, how many different colors the card has
# We also maintain a hash of counts, how many cards we have of that color.
while(<>) {
    my @colors = qw(0 0 0 0 0);
    my $colorcount = 0;

    foreach (split) {
        $colors[$_] = 1;
        $counts{$_}++;
        $colorcount++;
    }

    push @cards, {
        colors => \@colors,
        colorcount => $colorcount
    };
}

# If we have less than 20 of any color, it can't possibly be legal
if(grep { $_ < 20 } values %counts) {
    print "illegal\n";
    exit;
}

# Okay, now the fun part.
# We sort the colors by card count, so we give higher
# priority to the colors with the fewest cards.
#
# For each color, take cards with that color, and sort them by
# how many different colors they have, giving priority to colors
# with fewer cards.  Take the top 20.  If there aren't 20 available,
# the deck is illegal.

my @rankedcolors = sort { $counts{$a} <=> $counts{$b} } keys %counts;
foreach my $color (@rankedcolors) {
    my $cardcount = 0;

    foreach my $card (sort {
            my $countdiff = $a->{colorcount} <=> $b->{colorcount};
            return $countdiff if $countdiff;

            foreach(@rankedcolors) {
                my $cmp = $a->{colors}->[$_] <=> $b->{colors}->[$_];
                return $cmp if $cmp;
            }


            return 0;
        } grep {
            $_->{colors}->[$color]
        } @cards
    ) {
        $cardcount++;
        $card->{colors} = [qw(0 0 0 0 0)]; # Zero out the card's colors, effectively removing it
        last if $cardcount >= 20;
    }

    if($cardcount < 20) {
        print "illegal\n";
        exit;
    }
}

print "legal\n";
exit;


[ Parent ]
My first PFC entry by Xenocide (3.00 / 0) #16 Mon Apr 05, 2004 at 03:03:39 PM EST
Long time lurker, first time I actually finished one, I think. My entry is provided below.

The algorithm by Xenocide (3.00 / 0) #17 Mon Apr 05, 2004 at 03:57:05 PM EST
Basically a brute force search with some heuristical short cuts that are pretty obvious. It feels like the problem is gonna be NP complete, and related to the 0-1 knapsack problem. But overall its really not too bad. The example files are 100 cards long and since the search isn't an optimization problem there's not much to it. Even on my amdk6-2 there's enough cycles to outpace the I/O, as I spend about twice as long in system than in userspace. That should be plenty fast to handle any Magic, err I mean, Tragic deck you throw at it. The meat of the solution is written in a recursive function called brute that simply starts with the first card in the file and does a depth first search for a valid placement of cards meeting the requirements.

The heuristics are fairly straightforward. As the program reads in cards it keeps two tallies of colors. One for cards that can only fit in one place and one for color counts in general. If one color isn't even represented in 20 cards then the answer is clear cut. The other heuristic helps prune branching prematurely. If a card has only one color, there's only one decision that can be made. Assigning it first means pruning several branches of recursion related to being able to place that card.

Also, once a card color is satisfied, there's no need to consider placing more cards in it. This really cuts down the search tree, and doesn't cost a damn thing in terms of correctness. The entire solution is correct, and I haven't found any test cases that throw it for a runtime jog yet.

[ Parent ]
The code by Xenocide (3.00 / 0) #18 Mon Apr 05, 2004 at 04:01:53 PM EST
/* Last Revision: 05 Apr 2004 Copyright 2004 Justin Dugger. */

/* Description
 *   this program takes a list of tragic card colors and makes sure
 *   that there's a rainbow spread of at least twenty in each.*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct card {
  int black;
  int red;
  int green;
  int yellow;
  int blue;
  struct card *next;
} CARD;

/* brute is a general brute forcing system, using a depth first
   search. If any of the choices results in a valid deck, immediately return 1.
*/

int brute(CARD* l, int black, int red, int green, int yellow, int blue) {
  if (l == NULL) {
    return (black>=20 && red>=20 && green>=20 && yellow>=20 && blue>=20);
  }
  if (l->black!=0 && black<20 &&brute(l->next,++black,red,green,yellow,blue)) {
    return 1;
  }
  if (l->blue!=0 && blue<20 && brute(l->next,black,red,green,yellow,++blue)) {
    return 1;
  }
  if (l->red!=0 && red<20 && brute(l->next,black,++red,green,yellow,blue)) {
    return 1;
  }
  if (l->yellow!=0&&yellow<20 &&brute(l->next,black,red,green,++yellow,blue)) {
    return 1;
  }
  if (l->green!=0 && green<20 &&brute(l->next,black,red,++green,yellow,blue)) {
    return 1;
  }
  return (black>=20 && red>=20 && green>=20 && yellow>=20 && blue>=20) ||
    brute(l->next,black,red,green,yellow,blue);
}

int main() {
  struct card* list=NULL;
  struct card* tmp=list;
  struct card* prev=NULL;
  char input[20];
  char* s;
 
  int black =0;
  int blue =0;
  int red = 0;
  int yellow =0;
  int green =0;
  int blackTally=0;
  int blueTally =0;
  int redTally = 0;
  int yellowTally =0;
  int greenTally =0;
  //read input 
  if (!feof(stdin)){
    list=calloc(1,sizeof(CARD));
    tmp=list;
    fgets(input,sizeof(char*)*20,stdin);   
    s=strtok(input," ");

    if (s!=NULL && atoi(s)==0) {
      tmp->black=1;
      s=strtok(NULL," ");
      blackTally++;
    }
    if (s != NULL && atoi(s)==1) {
      tmp->blue=1;
      s=strtok(NULL," ");
      blueTally++;
    }   
    if (s != NULL && atoi(s)==2) {
      tmp->red=1;
      s=strtok(NULL," ");
      redTally++;
    }
    if (s != NULL && atoi(s)==3) {
      tmp->yellow=1;
      s=strtok(NULL," ");
      yellowTally++;
    }
    if (s != NULL && atoi(s)==4) {
      tmp->green=1;
      greenTally++;
    }
  }

  while(!feof(stdin)) {

    tmp->next=calloc(1,sizeof(CARD));
    prev=tmp;
    tmp=tmp->next;
    fgets(input,sizeof(char)*20,stdin);   
    s=strtok(input," ");

    if (s != NULL && atoi(s)==0) {
      tmp->black=1;
      blackTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==1) {
      tmp->blue=1;
      blueTally++;
      s=strtok(NULL," ");
    }   

    if (s != NULL && atoi(s)==2) {
      tmp->red=1;
      redTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==3) {
      tmp->yellow=1;
      yellowTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==4) {
      greenTally++;
      tmp->green=1;
    }

    //remove cards of a single color from the decision list   
    if (tmp->green+tmp->red+tmp->blue+tmp->yellow+tmp->black==1) {
      if (tmp->green!=0) green++;
      if (tmp->red!=0) red++;
      if (tmp->blue!=0) blue++;
      if (tmp->yellow!=0) yellow++;
      if (tmp->black!=0) black++;
      tmp=prev;
      free(tmp->next);
      tmp->next=NULL;
    }
  }

  if (greenTally<20 || redTally<20 || blueTally<20 || blackTally<20 ||
      yellowTally<20) { printf("illegal\n"); }
   
  if (brute(list, black, red, green, yellow, blue)) { printf("legal\n");}
  else { printf("illegal\n"); }
  return 0;
}


[ Parent ]
embaressing errata - forgot an exit by Xenocide (3.00 / 0) #63 Mon Apr 12, 2004 at 06:26:46 AM EST
/* pfc.c - Justin Dugger jld5445@ksu.edu */
/* Last Revision: 12 Apr 2004 */
/* Copyright 2004 Justin Dugger. */

/*
 * Description
 *   this program takes a list of tragic card colors and makes sure that
 *   there's a rainbow spread of at least twenty in each. This solution uses
 *   a brute force recursion to search for a piling
 */

/* externals
 * standard libraries
 */

/* Revision History:
 *  05APR2004 - initial version
 *  12APR2004 - added return if one of the colors is short on cards
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct card {
  int black;
  int red;
  int green;
  int yellow;
  int blue;
  struct card *next;
} CARD;

/* brute is a general brute forcing system, using a depth first search.
   if any of the choices results in a valid deck, immediately return 1.
*/

int brute(CARD* l, int black, int red, int green, int yellow, int blue) {
  if (l == NULL) {
    return (black>=20 && red>=20 && green>=20 && yellow>=20 && blue>=20);
  }
  if (l->black!=0 && black<20 &&brute(l->next,++black,red,green,yellow,blue)) {
    return 1;
  }
  if (l->blue!=0 && blue<20 && brute(l->next,black,red,green,yellow,++blue)) {
    return 1;
  }
  if (l->red!=0 && red<20 && brute(l->next,black,++red,green,yellow,blue)) {
    return 1;
  }
  if (l->yellow!=0&&yellow<20 &&brute(l->next,black,red,green,++yellow,blue)) {
    return 1;
  }
  if (l->green!=0 && green<20 &&brute(l->next,black,red,++green,yellow,blue)) {
    return 1;
  }
  return (black>=20 && red>=20 && green>=20 && yellow>=20 && blue>=20) ||
    brute(l->next,black,red,green,yellow,blue);
}

int main() {
  struct card* list=NULL;
  struct card* tmp=list;
  struct card* prev=NULL;
  char input[20];
  char* s;
 
  //
  int black =0;
  int blue =0;
  int red = 0;
  int yellow =0;
  int green =0;
  int blackTally=0;
  int blueTally =0;
  int redTally = 0;
  int yellowTally =0;
  int greenTally =0;
  //read input 
  if (!feof(stdin)){
    list=calloc(1,sizeof(CARD));
    tmp=list;
    fgets(input,sizeof(char*)*20,stdin);   
    s=strtok(input," ");

    if (s!=NULL && atoi(s)==0) {
      tmp->black=1;
      s=strtok(NULL," ");
      blackTally++;
    }
    if (s != NULL && atoi(s)==1) {
      tmp->blue=1;
      s=strtok(NULL," ");
      blueTally++;
    }   
    if (s != NULL && atoi(s)==2) {
      tmp->red=1;
      s=strtok(NULL," ");
      redTally++;
    }
    if (s != NULL && atoi(s)==3) {
      tmp->yellow=1;
      s=strtok(NULL," ");
      yellowTally++;
    }
    if (s != NULL && atoi(s)==4) {
      tmp->green=1;
      greenTally++;
    }
  }

  while(!feof(stdin)) {

    tmp->next=calloc(1,sizeof(CARD));
    prev=tmp;
    tmp=tmp->next;
    fgets(input,sizeof(char)*20,stdin);   
    s=strtok(input," ");

    if (s != NULL && atoi(s)==0) {
      tmp->black=1;
      blackTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==1) {
      tmp->blue=1;
      blueTally++;
      s=strtok(NULL," ");
    }   

    if (s != NULL && atoi(s)==2) {
      tmp->red=1;
      redTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==3) {
      tmp->yellow=1;
      yellowTally++;
      s=strtok(NULL," ");
    }

    if (s != NULL && atoi(s)==4) {
      greenTally++;
      tmp->green=1;
    }

    //remove cards of a single color from the decision list   
    if (tmp->green+tmp->red+tmp->blue+tmp->yellow+tmp->black==1) {
      if (tmp->green!=0) green++;
      if (tmp->red!=0) red++;
      if (tmp->blue!=0) blue++;
      if (tmp->yellow!=0) yellow++;
      if (tmp->black!=0) black++;
      tmp=prev;
      free(tmp->next);
      tmp->next=NULL;
    }
  }

  if (greenTally<20 || redTally<20 || blueTally<20 || blackTally<20 ||
      yellowTally<20) { printf("illegal\n");
  return 0;}
   
  if (brute(list, black, red, green, yellow, blue)) { printf("legal\n");}
  else { printf("illegal\n"); }
  return 0;
}


[ Parent ]
History by matthewg (6.00 / 2) #19 Mon Apr 05, 2004 at 08:14:45 PM EST
I've added a history of PFC problems, including the host, the winner(s), and links to the problems and the results, at the Wiki.

Utterly Cowardly by codemonkey uk (3.00 / 0) #21 Tue Apr 06, 2004 at 09:03:55 AM EST
Before I post my entry, I just want to ask, seeing as there is no way I'm checking by hand, of the examples, is pfc_tragic_input_1.txt a legal deck, and pfc_tragic_input_2.txt an illegal deck?

Coding is fun, but coming up with my own test cases is a chore...

--- Thad ---
Almost as Smart As you.

That's correct (nt) by jacob (3.00 / 0) #22 Tue Apr 06, 2004 at 09:05:53 AM EST


--

[ Parent ]
And any card can have between 1 and 5 colours? by Dr H0ffm4n (6.00 / 1) #26 Thu Apr 08, 2004 at 04:44:55 AM EST
i.e. 31 effectively different cards?

[ Parent ]
yes (nt) by jacob (3.00 / 0) #27 Thu Apr 08, 2004 at 04:59:55 AM EST


--

[ Parent ]
My crappy entry by codemonkey uk (3.00 / 0) #23 Tue Apr 06, 2004 at 10:05:42 AM EST
Brute Force Ninja Solution, in C++. I've only tested it on the given example files, so it'll probably die a death on real data.

Took me just under 4 hours total to code, chat to a friend on IM, test, eat my dinner, tidy, comment and post. I've commented it quite a lot, so I won't repeat myself here...

Enjoy!

--- Thad ---
Almost as Smart As you.

Hurray for file upload! by Evil Cloaked User (5.50 / 2) #24 Tue Apr 06, 2004 at 10:22:52 AM EST
Makes code posting an entirely easier process.

[ Parent ]
one problem by codemonkey uk (3.00 / 0) #25 Tue Apr 06, 2004 at 07:34:32 PM EST
Due to my lazy file naming, and file area quotas, it is sure to vanish eventually, and so doesn't have the persistance of code in comments.

Not that code in comments really has an persistance, as it goes, just try looking for some olf PFC code on K5 ... oh no, K5's down, so I can't get to the code anyway...

--- Thad ---
Almost as Smart As you.

[ Parent ]
*cough* by codemonkey uk (3.00 / 0) #51 Sat Apr 10, 2004 at 12:21:59 AM EST
Update. Fixed a bug. Replaced the file.

--- Thad ---
Almost as Smart As you.
[ Parent ]
I have a one or two liner using Mathematica... by the (3.00 / 0) #28 Thu Apr 08, 2004 at 10:39:24 AM EST
...that's a lot more efficient than a brute force approach and, incidentally, counts the number of ways of doing it rather than just saying whether it's possible. Is Mathematica an acceptable computer language?

I'm porting it to C++ anyway and that'll probably make it 10 times faster too.

PS I'm not cheating by using built in combinatorial functions, not that I think there are any that would help here.

--
The Definite Article

mathematica is absolutely acceptable (nt) by jacob (3.00 / 0) #29 Thu Apr 08, 2004 at 11:04:42 AM EST


--

[ Parent ]
Quick stab at a Group bruteforcer by TPD (3.00 / 0) #30 Thu Apr 08, 2004 at 12:17:44 PM EST
It brute forces based on grouping of identical cards rather than the cards themselves.

It has a further (really hideously implemented) check to stop recursion into repeat states that could potentially come about via different routes (which given some unconforming test data looked like it was necessary) - Though with conforming data I think it might just be an unneccessary space hog. I may reimplement this as a best level states array (which would only need to be 31 states long per level) which would be a far better approach but I doubt I'll get round to it.

The loading code was just whacked together and is slightly more than required as it accepts some modifications to the file format....

http://www.hulver.com/scoop-files/102/TPDTragicPFC.dpr

Compile with Delphi or Free Pascal Compiler (http://www.freepascal.org/)

fpc TPDTragicPFC.dpr -Sd

very much a first play with the problem, have some other ideas which I might get a chance to look at but probably not.

why sit, when you can sit and swivel with The Ab-SwivellerTM

Minor Code update (file changed) by TPD (3.00 / 0) #66 Tue Apr 13, 2004 at 11:56:58 AM EST
I made a very very minor change to stop unneccessary work in the final group that it recurses into.

I'd hoped to get a chance to look at the problem some more but never got the time. The hideous RepeatedStatesArray remains but I'm wholely unconvinced whether in actual conforming data it will much if any effect, but the intended effect can be seen by sending a file (when the NOSIZECHECK conditional is defined) of the form

0 1 2 3*20
1 2 3 4*20
0 2 3 4*20
0 1 3 4*20
0 1 2 4*19

(It's slow with the RepeatedStatesArray in place but I've never waited arround long enough to see just how slow it is without it.)

why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
Here is my entry by edwin (3.00 / 0) #31 Thu Apr 08, 2004 at 03:50:55 PM EST
It's in C++ aand requires the Boost library (http://www.boost.org). Compile with g++ tragic.cpp -o tragic.

The code by edwin (3.00 / 0) #32 Thu Apr 08, 2004 at 03:56:06 PM EST
// Program to determine if a set of cards is a valid Tragic deck
// (whatever that is).

// This problem is equivalent to bipartite matching on a graph (the two
// parts are the piles and the cards). This in turn is equivalent to
// network flow. Since network flow is a well-studied problem and solvers
// are available, I've used an existing one from the Boost graph library.

// We need to construct a graph which has:
// src-----------------------------
// |   |    |   |    |     |   |  | <- capacity 1 links to each card
// o   o    o   o    o     o   o  o <- cards
// |            |                   <- capacity 1 links from each card to
// |--------|   |                   <- piles it can be placed on
// o        o   |----o     o      o <- 5 nodes for piles
// |        |        |     |      | <- capacity-20 links from piles to sink
// -----------------------------sink

// If the total flow through this graph == 100, the deck is valid.

#include <cassert>

#include <vector>
#include <list>

#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <sstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmunds_karp_max_flow.hpp>

using namespace boost;


// typedefs
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<vecS, vecS, directedS,
               property<vertex_name_t, std::string>,
               property<edge_capacity_t, long,
               property<edge_residual_capacity_t, long,
               property<edge_reverse_t, Traits::edge_descriptor> > >
    > Graph;

typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;


// globals
Graph g;
std::vector<vertex_descriptor> verts;

property_map<Graph, edge_capacity_t>::type
    capacity = get(edge_capacity, g);
property_map<Graph, edge_reverse_t>::type
    rev = get(edge_reverse, g);
property_map<Graph, edge_residual_capacity_t>::type
    residual_capacity = get(edge_residual_capacity, g);

// utility to connect in both directions
void
connect_nodes(int a, int b, int cap)
{
    edge_descriptor e1, e2;
    bool in1,in2;
    tie(e1, in1) = add_edge(verts[a], verts[b], g);
    tie(e2, in2) = add_edge(verts[b], verts[a], g);
    assert(in1 && in2);
    capacity[e1] = cap;
    capacity[e2] = 0;
    rev[e1] = e2;
    rev[e2] = e1;
}

int
main()
{

    Traits::vertex_descriptor s, t;   

    // 0 = src
    // 1 = sink
    // 2-6 = piles
    for(int i = 0; i < 7; ++i)
    {
    verts.push_back(add_vertex(g));
    }

    s = verts[0]; t = verts[1];

    // connect piles to sink
    for(int i = 0; i < 5; ++i)
    {
    connect_nodes(i+2,1,20);
    }

    int this_vertex = 7;
    std::string line;
    while(std::getline(std::cin,line))
    {               
    verts.push_back(add_vertex(g));
        std::istringstream ss(line.c_str());

    connect_nodes(0,this_vertex,1);

    int pile;
    while(ss >> pile)
    {
        connect_nodes(this_vertex,pile+2,1);
    }   
    this_vertex++;
    }

    // compute max flow
    long flow = edmunds_karp_max_flow(g,s,t);

    if(flow == 100)
    {
    std::cout << "legal" << std::endl;
    }
    else
    {
    std::cout << "illegal" << std::endl;
    }
}


[ Parent ]
Algorithm Notes by edwin (3.00 / 0) #33 Thu Apr 08, 2004 at 04:07:30 PM EST
I spent a while mulling over the problem and looking through Steven Skiena's fabulous Algorithm Design Manual. I noticed that the problem could be modelled in terms of bipartite graph matching, and Skiena said that was the same as network flow. So I looked up network flow in Sedgewick and was all ready to code it up, when I noticed there was already an implementation in Boost, so I used that. You could argue that this crosses the line from "elegant code reuse" to "outright cheating" - I leave this to the judge. The actual code took under an hour.

The worst case for this network flow algorithm is O(cards * (cards * colors)^2), but in practice it seems to go very fast - I got a 400-node test which had the most arcs possible without being a solution in about half a second.

[ Parent ]
I got... by TPD (3.00 / 0) #34 Thu Apr 08, 2004 at 10:15:11 PM EST
I got a 400-node test which had the most arcs possible without being a solution in about half a second,

could you post it?

why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
Here comes my entry... by the (3.00 / 0) #35 Fri Apr 09, 2004 at 11:38:19 AM EST
Standard C++. (Well I used hash_set<> from the extensions but you can replace it with set<> if you like.)

--
The Definite Article
The Source by the (3.00 / 0) #36 Fri Apr 09, 2004 at 11:40:58 AM EST

#include <iostream>
#include <sstream>
#include <set>
#include <ext/hash_set>

using namespace std;
using namespace __gnu_cxx;

typedef int BitSet;

inline bool Contains(BitSet i,int j) {
    return !!(i & (1<<j));
}

inline int Remove(BitSet j,int i) {
    return j & ~(1<<i);
}

class Monomial {
    int n[31];
public:
    int &operator[](BitSet i) {
        return n[i-1];
    }
    const int &operator[](BitSet i) const {
        return n[i-1];
    }
    bool operator==(const Monomial &m) const {
        for (BitSet j = 1; j<32; ++j) {
            if (n[j-1]!=m[j]) {
                return false;
            }
        }
        return true;
    }
    Monomial() {
        fill(n,n+31,0);
    }
};

namespace __gnu_cxx {
template<> struct hash<Monomial> {
    size_t operator()(const Monomial &m) const {
        int total = 0;
        for (BitSet i = 1; i<32; ++i) {
            total = (total << 1) ^ m[i];
        }
        return total;
    }
};
}

typedef hash_set<Monomial> Polynomial;
typedef Polynomial::const_iterator PolyIterator;

struct Derivative {
    template<class I> void operator()(I l,Monomial a,int i) {
        for (BitSet j = 1; j<32; ++j) {
            if (Contains(j,i) && a[j]>0) {
                Monomial m = a;
                --m[j];
                *l++ = m;
            }
        }
    }
};

struct EvalAtZero {
    template<class I> void operator()(I l,const Monomial &a,int i) {
        Monomial m = a;
        for (BitSet j = 1; j<32; ++j) {
            if (Contains(j,i) && a[j]>0) {
                int reduced = Remove(j,i);
                if (reduced) {
                    m[reduced] += m[j];
                }
                m[j] = 0;
            }
        }
        *l++ = m;
    }
};

template<class F>
Polynomial *PolyMap(F f,const Polynomial *p,int d) {
    Polynomial *q = new Polynomial;
    for (PolyIterator i = p->begin(); i!=p->end(); ++i) {
        f(inserter(*q,q->begin()),*i,d);
    }
    delete p;
    return q;
}

int main() {
    int target[5];
    fill(target,target+5,20);
    Monomial m;
    string line;
    while (getline(cin,line)) {
        istringstream lineStream(line);
        BitSet monomialType = 0;
        int i;
        while (lineStream >> i) {
            monomialType |= 1<<i;
        }
        bool monochromatic = false;
        for (int l = 0; l<5; ++l) {
            if (monomialType==(1<<l)) {
                --target[l];
                monochromatic = true;
            }
        }
        if (!monochromatic) {
            ++m[monomialType];
        }
    }
    Polynomial *p = new Polynomial;
    p->insert(m);
    for (int r = 0; r<5; ++r) {
        for (int k = 0; k<target[r]; ++k) {
            p = PolyMap(Derivative(),p,r);
        }
        p = PolyMap(EvalAtZero(),p,r);
    }
    cout << (p->size() ? "legal" : "illegal") << endl;
}


--
The Definite Article
[ Parent ]
The Comments by the (3.00 / 0) #37 Fri Apr 09, 2004 at 11:57:46 AM EST
Let's say the colors are a, b, c, d, e.

Then given a card we can form a linear polynomial by adding 1 to the sum of the colors. So from a card with colors a and c we can form 1+a+c. Given a deck of cards we can multiply all of these linear terms together. So a deck with two of these cards and a single monochromatic e card would give rise to (1+a+c)2e. This is the polynomial of the deck - call it f(a,b,c,d,e).

The deck is legal iff the coefficient of a20b20...e20 in the expansion of f(a,b,c,d,e) is non-zero. This is the same as saying that the 20th derivative w.r.t. a of the 20th derivative w.r.t. b ... of the 20th derivative w.r.t. e of f(a,b,c,d,e) evaluated at (a,b,c,d,e)=(0,0,0,0,0) is non-zero. We call a term that is a product of these linear terms a Monomial.

We can simplify further. The multiple derivative above actually counts the legal arrangements. We just care if it's non-zero. So we do all our work in the idempotent algebraic structure in which 1+1=1, a+a=a, et.c.

So the code basically does some simple symbolic algebra - hence the symbols Monomial, Polynomial, Derivative and EvalAtZero. As this structure is idempotent there are no numbers bigger than 1. So in a polynomial the coefficients are either 0 or 1. That means a polynomial can be represented as a set<> (or a hash_set<> for efficiency). A Monomial is represented simply as a list of the exponents of each of the types of linear factor it can have, with the types conveniently encoded as integers (use a proper bitset type to scale the code). The Derivative() and EvalAtZero() evaluate w.r.t. the ith variable, or set the ith variable to zero, respectively.

I've strived for purity of the code but I did make one concession to quick and dirty shortcuts - I immediately throw out monochromatic cards to simplify the problem.

Actually it's equivalent to a brute force breadth first search with a hash table for memoization to save repeated searches of the same thing - but it's easier to think about polynomials.

--
The Definite Article

[ Parent ]
Errata by the (3.00 / 0) #39 Fri Apr 09, 2004 at 12:32:38 PM EST
The example f should be (1+a+c)2(1+e)

--
The Definite Article
[ Parent ]
Jesus fuck by komet (3.00 / 0) #70 Tue Apr 13, 2004 at 11:11:16 PM EST
that is clever.

--
<ni> komet: You are functionally illiterate as regards trashy erotica.
[ Parent ]
But it's still just... by the (3.00 / 0) #74 Wed Apr 14, 2004 at 05:00:53 AM EST
...brute force in disguise. However, there is a way to efficiently solve this problem that is still based on looking at polynomial coefficients using Groebner bases. But that just requires me copy-and-pasting someone else's integer programming code (http://library.wolfram.com/infocenter/Articles/1434/).

--
The Definite Article
[ Parent ]
A little more complex than necessary? by jjayson (3.00 / 0) #95 Wed Apr 14, 2004 at 06:37:57 PM EST
I think he made it a little more complex than necessary.

Think of the "1+a+c" term representing the fact that from a card with colors a and c, you can make any of three decks: a deck with zero cards (1), a deck with a single card of color a (a), or a deck with a single card of color c (c).

Each term is a deck.

Multiplying is just listing all possible combination of decks: "(1+a+c)(1+e) = 1 + a + c + e + ae + ce" means you can make either the null deck (1); or single card decks that have a card of either color a, c, or e; or decks of two cards with colors of a and e or c and e.

We don't really care about not counting a card. As in, there is never a case when counting the card hurts. At worst, we get a pile with more than 20 card. So we can get rid of all the 1s:"(a+c)e = ae + ce". That makes sense when compared to the previous answer. Given those two cards, using both we only have decks of either a and e or c and e. This reduces the size of the equation substantially.

He only looked for the term "(a^20)(b^20)(c^20)(d^20)(e^20)" because any legal deck of more than 100 cards will contain a minimal deck of exactly 100 cards that is also legal and using the "1+" allows you to not use cards, so if the deck is legal then this "(a^20)(b^20)(c^20)(d^20)(e^20)" term will exist. (Finding this minimal deck is NP-complete, think set-cover, I think.)

Hoever, when you get rid of that "1+" part, using every card, you need to see if there is a term "(a^v)(b^w)(c^x)(d^y)(e^z)" where v,w,x,y,z >= 20. You still take the 20th partial derivative of with respect to a of the 20th partial wrt b of the.... Do this in a similar way. Take that 20th of 20th... partial, set a=b=c=d=e=1, and make sure it isn't zero.

Keeping in the interpretation that the exponent represents the number of cards of that color, v+w+x+y+z will equal the number of cards in the input file.


[ Parent ]
I think he made it a little more complex than... by the (3.00 / 0) #101 Thu Apr 15, 2004 at 12:04:27 PM EST
See Version 2.0 with comments and change of type names.

But your description is exactly right. And the "1+" part is a good explanation. For a short while I was pondering how to detect the presence of any term with exponent>=20 and then realised that "1+" did the trick and meant I only have to test for exponent=20.

--
The Definite Article

[ Parent ]
Seen it before by jjayson (3.00 / 0) #102 Thu Apr 15, 2004 at 01:10:28 PM EST
The first time I saw this done was on one of my very first jobs about 6 years ago working on currency trading software. The last time I actually used a similar formulation wasn't too long ago, less than two years. More financial software, I was working on something to analyze a portfolio, determine exposure to certain risks, and give hedging suggestions.

We broke down individual positions into components, such as think of a gold ans silver fund that held stock in companies that mined those metals. That fund has stocks and we broke down those stocks into components on how they moved with respect to various factors. If you took all the holding of a portfolio -- different funds, stocks, bonds, or whatever -- and multiplied them, you would find your exposure to various factors. More complex than this, but you get the idea.

It wasn't exatly the same, but we used SAS to derive these huge equations and took partials to find solutions to the problem in a similar way.

[ Parent ]
Generating functions by the (3.00 / 0) #103 Fri Apr 16, 2004 at 09:45:07 AM EST
That's what these polynomials are. See here for more details. I think this stuff is incredibly beautiful - especially chapter 3 of that book where the exponential of a generating function turns out to have an amazing meaning.

Your application sounds interesting. Using algebra this way to model exchange between different types of currency is a fun theoretical exercise (eg. the fact that 1 quarter = 25 pennies can be written as p^15=q) but I didn't know you could turn it into a practical application.

--
The Definite Article

[ Parent ]
I dont get this part by Siddhi (3.00 / 0) #104 Mon Apr 19, 2004 at 09:09:02 PM EST
(eg. the fact that 1 quarter = 25 pennies can be written as p^15=q)

I dont get this part. Could you explain it further ?

[ Parent ]
So I made a mistake! by the (3.00 / 0) #126 Wed May 12, 2004 at 04:22:57 PM EST
:-)

p^25=q

--
The Definite Article

[ Parent ]
I still dont get it... by Siddhi (3.00 / 0) #127 Mon May 17, 2004 at 04:45:55 PM EST
No, apart from the typo, I still dont get the concept. How does representing 1 quarter = 25 pennies as p^25 = q help in the calculations ? Normally, I would put it as p*25 = q, but how does it work in this representation ?

[ Parent ]
PS Mathematica solution by the (3.00 / 0) #38 Fri Apr 09, 2004 at 12:02:52 PM EST
I won't bother posting this as I've decided it's cheating. Mathematica has a Coefficient[] function that makes light work of the problem.

--
The Definite Article
[ Parent ]
Version 2.0. Clearer, more comments, but slower. by the (6.00 / 1) #56 Sun Apr 11, 2004 at 09:28:47 AM EST


#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
#include <set>
#include <ext/hash_set>

using namespace std;
using namespace __gnu_cxx;

//
// # of colors in game
//
const int n_colors = 5;

//
// # cards required in each pile.
//
const int n_legal = 20;

//
// # of distinct types of card (+1 for colorless).
//
const int n_cards = 1 << n_colors;

//
// An individual card is represented as a binary coded integer.
// Bit n in the integer is set if color n is present.
//
typedef unsigned int Card;

//
// A deck of colors is an array of colors
//
typedef vector<int> Deck;

//
// We need to hash decks of colors in order to have hash_sets
// of them.
// Note that here, and onwards, we have loops from 1 upwards as
// colors of type zero don't exist (or aren't relevant if they
// do.)
//
struct DeckHash {
    size_t operator()(const Deck &m) const {
        int total = 0;
        for (Card i = 1; i<n_cards; ++i) {
            total = (total << 1) ^ m[i];
        }
        return total;
    }
};

typedef hash_set<Deck,DeckHash> DeckSet;

//
// Test to see whether a card contains
// a specific color.
//
inline bool UsesColor(Card i,int j) {
    return !!(i & (1<<j));
}

//
// Erase a specific color from a card.
//
inline Card EraseColor(Card j,int i) {
    return j & ~(1<<i);
}

//
// Given a deck as input the functoid Take(n)
// produces the set of decks that could be formed by
// taking exactly one card bearing color n.
// Rather than return a set it uses the input iterator
// to collect the elements. This saves having
// top copy sets around.
//
struct Take {
    int i;
    Take(int i0) : i(i0) { }
    template<class I> void operator()(I l,const Deck &a) {
        for (Card card = 1; card<n_cards; ++card) {
            if (UsesColor(card,i) && a[card]>0) {
                Deck m(a);
                --m[card];
                *l++ = m;
            }
        }
    }
};

//
// Erase(n) completely erases color n from its argument deck.
// Note that this means that cards of previously different
// types may now be indistinguishable. For example
// if red is deleted then red and green cards are now merged
// into the green cards.
//
struct Erase {
    int i;
    Erase(int i0) : i(i0) { }
    template<class I> void operator()(I l,const Deck &a) {
        Deck m(a);
        for (Card card = 1; card<n_cards; ++card) {
            if (UsesColor(card,i) && a[card]>0) {
                int erased = EraseColor(card,i);
                if (erased) {
                    //
                    // Merge cards with color j
                    // into cards without j
                    //
                    m[erased] += m[card];
                }
                //
                // Remove cards with color j
                //
                m[card] = 0;
            }
        }
        *l++ = m;
    }
};

//
// Given a functoid acting on a deck this function lifts
// it so as to act on sets of decks.
// I.e. DeckMap(f,{a1,a2,...,an}) = {f(a1),f(a2),...,f(an)}
// Note that the ouput set may be smaller than the input set
// because f(a)=f(b) even when a!=b.
// This is crucial: it significantly reduces the workload
// compared to a brute force search as multiple ways to
// achieve a given state aren't iterated over multiple
// times.
//
template<class F>
DeckSet *DeckMap(F f,const DeckSet *p) {
    DeckSet *q = new DeckSet;
    for (DeckSet::const_iterator i = p->begin(); i!=p->end(); ++i) {
        f(inserter(*q,q->begin()),*i);
    }
    delete p;
    return q;
}

int main() {
    assert(n_colors<=8*sizeof(Card));

    //
    // The array of targets represents how many colors of each
    // color are required to form a legal deck. This may
    // change if monochromatic colors are present.
    //
    int target[n_colors];
    fill(target,target+n_colors,n_legal);

    Deck m(n_cards);
    fill(m.begin(),m.end(),0);

    string line;
    while (getline(cin,line)) {
        set<int> s;
        istringstream lineStream(line);
        //
        // Read a row of white space separated integers.
        //
        copy(istream_iterator<int>(lineStream),istream_iterator<int>(),inserter(s,s.begin()));

        Card card = 0;

        //
        // We have special handling for monochromatic colors.
        // These are simply discarded and the target requirements
        // correspondingly reduced.
        //
        if (s.size()==1) {
            --target[*s.begin()];
        } else {
            for (set<int>::iterator p = s.begin(); p!=s.end(); ++p) {
                card |= 1 << *p;
            }
            ++m[card];
        }
    }
    DeckSet *p = new DeckSet;
    p->insert(m);
    for (int r = 0; r<n_colors; ++r) {
        for (int k = 0; k<target[r]; ++k) {
            //
            // Take a card of color r in every possible way.
            //
            p = DeckMap(Take(r),p);
        }
        //
        // We aren't going to take any more colors
        // colored with r so we may as well erase
        // this color from the rest of the deck.
        //
        p = DeckMap(Erase(r),p);
    }
    //
    // Are there any decks remaining in the set?
    //
    cout << (p->size() ? "legal" : "illegal") << endl;
}


--
The Definite Article
[ Parent ]
He he. I just spotted that I accidentally... by the (3.00 / 0) #62 Mon Apr 12, 2004 at 05:46:07 AM EST
...did a search and replace on that code replacing occurences of 'card' with 'color'. The code itself is fine but some of the comments may now be a bit cryptic.

--
The Definite Article
[ Parent ]
ok by edwin (3.00 / 0) #40 Fri Apr 09, 2004 at 02:09:33 PM EST
You want:

0 1 2 3 4 x 381
0 1 2 3 x 19


oops, this is a response to TPDs query above [nt] by edwin (3.00 / 0) #52 Sat Apr 10, 2004 at 02:28:13 AM EST


[ Parent ]
ummm... by codemonkey uk (3.00 / 0) #53 Sat Apr 10, 2004 at 05:28:01 AM EST
How is that not a solution? That is trivially a legal deck, isn't it? With more than 320 card each with all four colours, you've got a legal deck four times over!

--- Thad ---
Almost as Smart As you.
[ Parent ]
Oops by edwin (5.50 / 2) #54 Sat Apr 10, 2004 at 06:31:24 AM EST
I mean,

0 1 2 3 x 381
0 1 2 3 4 x 19

That should give all piles plenty except for the last one which has only 19.

[ Parent ]
Yup, that's illegal by codemonkey uk (3.00 / 0) #55 Sat Apr 10, 2004 at 07:16:26 AM EST
I'm pretty sure my algorithm 'solves' it without going into the search tree.

--- Thad ---
Almost as Smart As you.
[ Parent ]
Tom's Haskell entry by tmoertel (3.00 / 0) #41 Fri Apr 09, 2004 at 05:32:49 PM EST
In follow-up comments.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

General notes by tmoertel (3.00 / 0) #42 Fri Apr 09, 2004 at 05:40:28 PM EST
Zeroth, I'm posting two versions of the same code, one commented, the other not, because there are a lot of comments, and some people (you know who you are) like to figure things out from the code.

First, I called it TragicPfc because I couldn't resist. ;-)

Second, I have no idea what approaches other people have tried, so it's entirely possible that I missed something fundamental and thus my code will be intensely stupid by comparison. (Even so, it runs in respectable time.)

Third, I compiled it with GHC 6.2.1 on Red Hat Linux 8.0.

Fourth, let's all give a big round of applause to the list monad, who does the heavy lifting (as usual).

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
One interesting thing that I forgot to mention by tmoertel (3.00 / 0) #45 Fri Apr 09, 2004 at 06:06:46 PM EST
The code is general in the number of colors and in the number of cards required from each color in a legal deck:
$ ./TragicPfc 2 2
0 1
0 1
1
1
^D

legal

$ ./TragicPfc 2 2
0 1
0 1
0
^D

illegal

$ ./TragicPfc 2 1
0 1
0 1
0
^D

legal

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Code (w/o comments) by tmoertel (3.00 / 0) #43 Fri Apr 09, 2004 at 05:42:35 PM EST
-- Tom Moertel <tom /at/ moertel.com>
-- Pfc 2004-04-05
-- Compilation notes at end.

module Main (main) where

import Control.Exception as Ex
import Control.Monad
import Control.Monad.State
import Data.FiniteMap
import Data.List
import System.Environment
import System.Exit
import System.IO


type Color     = Int
type Card      = [Color]
type Pile      = FiniteMap Card Int
type CardStack = (Card, Int)  -- ^ Stack of cards, all sharing the same colors
type PileSpec  = [CardStack]  -- ^ Assoc-list form of a 'Pile'.

defaultDeckColorRequirements :: [(Int, Color)]
defaultDeckColorRequirements =  [ (20, c) | c <- [0..4] ]

main :: IO ()
main = do
    args <- getArgs
    reqs <- case args of [] -> return defaultDeckColorRequirements
                         _  -> parseArgs args
    interact $ readSolveAndShow reqs

parseArgs :: [String] -> IO [(Int, Color)]
parseArgs args = do
    reqs <- Ex.catch (evaluate $ let rs = map read args in
                                 foldr seq () rs `seq` rs)
                     (const $ return [])
    case reqs of
        rs@(_:_) | all (>= 0) rs -> return $ zip rs [0..]
        _ -> do hPutStrLn stderr $
                  "Usage: TragicPfc [color0min color1min...] < deck.txt\n" ++
                  "    where colorNmin is a non-negative integer giving\n" ++
                  "    the minimum number of cards of color N that must\n" ++
                  "    be available in the deck."
                exitFailure

readSolveAndShow :: [(Int, Color)] -> String -> String
readSolveAndShow deckColorRequirements =
    showResult . buildDecks deckColorRequirements . readPile

readPile :: String -> Pile
readPile =
    addListToFM_C (+) emptyFM
  . map (flip (,) 1 . map read . words)
  . lines

showResult :: [Pile] -> String
showResult p''s =
    if null p''s then "illegal\n" else "legal\n"

buildDecks :: [(Int, Color)] -> Pile -> [Pile]
buildDecks colorRequirements p =
    foldl satisfyColorRequirement [p] colorRequirements

    where

    satisfyColorRequirement ps (r, c) =
        concat . concatMap (removeFromSubset r) . groupLikeSubsets $
        map (partitionOnColor c) ps

    groupLikeSubsets =
        fmToList . addListToFM_C (flip (++)) emptyFM
                 . map (\ (c_p, p') -> (c_p, [p']) )

    removeFromSubset r (c_p, p's) =
        let c_p's = remove r c_p in [ map (plusFM p') c_p's | p' <- p's ]

remove :: Int -> Pile -> [Pile]
remove num =
    map toPile . remove' . fromPile

    where

    remove' ps =
        [ ps' | (0, _, ps') <- foldM removeDistinctly (num, depth ps, []) ps ]

    removeDistinctly (n, depthLeft, cs) (colors, count)
        | n > depthLeft = fail "not enough cards left"
        | otherwise     = [ (n - i, depthLeft - count, (colors, count - i):cs)
                            | i <- [0 .. min n count] ]

depth :: PileSpec -> Int
depth = sum . map snd

partitionOnColor :: Color -> Pile -> (Pile, Pile)
partitionOnColor c p =
    (c_p, p')
    where
    (c_p, p') = (filterFM (\kcs _ -> c `elem` kcs) p, minusFM p c_p)

toPile :: PileSpec -> Pile
toPile = listToFM . filter (\ (_, count) -> count /= 0)

fromPile :: Pile -> PileSpec
fromPile = fmToList

instance (Show a, Show b) => Show (FiniteMap a b)
    where show p = show (fmToList p)

instance (Ord a, Ord b) => Ord (FiniteMap a b)
    where
    compare p1 p2 = compare (fmToList p1) (fmToList p2)

-- Local Variables:
-- compile-command: "ghc -O2 -Wall -o TragicPfc --make TragicPfc.hs"
-- End:

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Code (w/ horrifically long comments) by tmoertel (3.00 / 0) #44 Fri Apr 09, 2004 at 05:55:15 PM EST
{-
   Tom Moertel <tom /at/ moertel.com>
   2004-04-09

   Observations

   - There are five colors and thus 2^5 = 32 possible color
     combinations and hence 32 possible distinct cards.  (Possibly,
     the no-color combination is disallowed, but that doesn't
     affect us.)

   - We can completely describe a deck by the count of each distinct
     card (of the possible 32) that the deck contains.  For example,
     in one particular deck there may be 3 cards with the 0---- color,
     4 with the 0-2-- color, and so on.

   The approach

   - We determine whether the input pile represents a legal deck by
     trying to "prove" it so by enumerating all of the distinct legal
     subdecks within the pile.  We only need one such subdeck to prove
     legality, but we need to exhaust all *distinct* possibilities
     before ruling the input pile as an illegal deck.  Because the
     number of distinct possibilities is limited, this exhaustive
     search doesn't take that long. (Or so I hope!)

   Overview of the method

   - Let R be the required number of cards of each color.  In the
     card game Tragic, R = 20.

   - Convert the input deck into a "Pile" P which is simply the deck
     in [(colors, count)] format.

   - Starting with C = the first color:

     1 Partition the pile into (P_C, P'), where P_C is the subset of
       cards having color C, and P', the other cards.

     2 If P_C contains fewer than R cards, fail.

     3 Otherwise, for each of the distinct ways to select 20 cards
       from the subset P_C, remove those 20 cards from P_C leaving
       P_C'.  Let P'' be the union of P' and P_C'.  If C is the
       last color, return P'' as success.  Otherwise, repeat
       the whole process (at step 1) with P'' as the input pile
       and C as the next color.

   - Iff the above produces any non-failure output, we have a legal deck.

   Refinements

   - The code within is completely general in the number of colors and
     the number of cards required from each color in a legal deck.
     For example, if you want to test the legality of three-color
     decks where legal decks must contain 7 cards of color 0, 33 cards
     of color 1, and 8 cards of color 2, you can do so like this:

         $ ./TragicPfc 7 33 8 < deck.txt
         illegal

     You can use 0, too, if you don't require any of a particular
     color:

         $ ./TragicPfc 0 0 0 0 < /dev/null
         legal

   - The actual implementation is somewhat more aggressive at
     eliminating unneeded work than the overview above suggests.  In
     particular, the implementation uses an intermediate optimization
     in the recursion implied by step 3 that coalesces all of the
     piles that share a common subset of cards of a given color.  In
     this way, only the one subset need be processed, greatly reducing
     the threat of combinatorial explosion.

   Other stuff

   - The implementation seems to work well for trivial yet large
     examples.  For example, using input piles of 130,000 cards:

         $ { for f in 0 1 2 3 4; do yes $f | head -26000; done; } |
           time ./TragicPfc 1000 21001 1000 1000 26000
         legal
         3.04user 0.04system 0:03.13elapsed 98%CPU

         $ { for f in 0 1 2 3 4; do yes $f | head -26000; done; } |
           time ./TragicPfc 1000 21001 1000 1000 26001
         illegal
         3.05user 0.05system 0:03.15elapsed 98%CPU

         $ { yes 0 1 2 3 4 | head -130000; } |
           time ./TragicPfc 1000 1001 1000 1000 26000 +RTS -K64M
         legal
         14.09user 0.15system 0:14.88elapsed 95%CPU

         $ { yes 0 1 2 3 4 | head -130000; } |
           time ./TragicPfc 1000 1001 120000 1000 26000 +RTS -K64M
         illegal
         14.16user 0.14system 0:14.64elapsed 97%CPU

         (Timings done my my 1.6-GHz Celeron laptop.)

     Note that if you're running massive decks like those above,
     you had best give the runtime a reasonable amount of stack
     (that's the +RTS -K64M part).
-}

module Main (main) where

import Control.Exception as Ex
import Control.Monad
import Control.Monad.State
import Data.FiniteMap
import Data.List
import System.Environment
import System.Exit
import System.IO

-- | Colors are given unique names (nonnegative integers), starting with 0.

type Color     = Int

-- | A card is specified by the colors on it.  Here, we use a list
-- representation where, if a color is present on a card, the color's
-- name appears in the card's list.  Since this list is orderless, we
-- require that the names in 'Card' values shall always be sorted in
-- ascending order.  E.g., a card with colors 3 and 0 on it is given by
-- the 'Card' value [0,3].  (In case you're wondering why I didn't use
-- a "faster" Int representation, it's just as easy to use a list of
-- Colors in Haskell and has little performance penalty for the
-- algorithms I chose. The big win is that the list-of-Colors
-- representation results in intermediate output that is readily
-- understandable.)

type Card      = [Color]

-- | We can represent any pile of cards as a mapping from each of the
-- possible cards (color combinations) to the count of such cards
-- within the pile.  (In the game Tragic, where there are five colors,
-- there are 2^5 possible distinct cards.)  E.g., an empty pile is
-- [], and a pile of ten cards all having the single color 0 is [([0],
-- 10)].

type Pile      = FiniteMap Card Int
type CardStack = (Card, Int)  -- ^ Stack of cards, all sharing the same colors
type PileSpec  = [CardStack]  -- ^ Assoc-list form of a 'Pile'.

-- | The number of cards of each color needed to form a legal deck.
-- In Tragic, there are five colors ([0..4]), and 20 cards of each color
-- are required.  This is our default.

defaultDeckColorRequirements :: [(Int, Color)]
defaultDeckColorRequirements =  [ (20, c) | c <- [0..4] ]

-- | This is the main entry point.  We get the command line arguments
-- parse them (if any), and call 'readSolveAndShow' to do the real
-- work.

main :: IO ()
main = do
    args <- getArgs
    reqs <- case args of [] -> return defaultDeckColorRequirements
                         _  -> parseArgs args
    interact $ readSolveAndShow reqs

-- | Parse the command-line args, which must be non-negative integers.

parseArgs :: [String] -> IO [(Int, Color)]
parseArgs args = do
    reqs <- Ex.catch (evaluate $ let rs = map read args in
                                 foldr seq () rs `seq` rs)
                     (const $ return [])
    case reqs of
        rs@(_:_) | all (>= 0) rs -> return $ zip rs [0..]
        _ -> do hPutStrLn stderr $
                  "Usage: TragicPfc [color0min color1min...] < deck.txt\n" ++
                  "    where colorNmin is a non-negative integer giving\n" ++
                  "    the minimum number of cards of color N that must\n" ++
                  "    be available in the deck."
                exitFailure

-- | Read the input pile, try (lazily) to build legal decks that
-- satisfy the given color requirements, and show the result of our
-- efforts.

readSolveAndShow :: [(Int, Color)] -> String -> String
readSolveAndShow deckColorRequirements =
    showResult . buildDecks deckColorRequirements . readPile

-- | Parse a deck.  (No error checking because the challenge-task
-- input requirements don't allow for errors.)

readPile :: String -> Pile
readPile =
    addListToFM_C (+) emptyFM
  . map (flip (,) 1 . map read . words)
  . lines

-- | Shows whether we had a legal input pile by examining the list of
-- piles left over when we constructed all of the legal subdecks.  We
-- had a legal input pile iff we have a non-empty list of remainder
-- piles (even if the remainder piles themselves are empty).  The
-- input to this function is the list of remainder piles.

showResult :: [Pile] -> String
showResult p''s =
    if null p''s then "illegal\n" else "legal\n"

-- | Given a set of color requirements and an initial pile, compute
-- (lazily) all of the possible ways to satisfy the requirements, and
-- return the piles of cards that are left over, one such remainder
-- pile for each way to satisfy the requirements. If there is no way
-- to satisfy the requirements (i.e., the input pile represents an
-- illegal deck), the output list will be empty.

buildDecks :: [(Int, Color)] -> Pile -> [Pile]
buildDecks colorRequirements p =
    foldl satisfyColorRequirement [p] colorRequirements

    where

    satisfyColorRequirement ps (r, c) =
        concat . concatMap (removeFromSubset r) . groupLikeSubsets $
        map (partitionOnColor c) ps

    groupLikeSubsets =
        fmToList . addListToFM_C (flip (++)) emptyFM
                 . map (\ (c_p, p') -> (c_p, [p']) )

    removeFromSubset r (c_p, p's) =
        let c_p's = remove r c_p in [ map (plusFM p') c_p's | p' <- p's ]

-- | Find all the distinct ways to remove 'num' cards from the given
-- pile and return the remaining cards for each way.

remove :: Int -> Pile -> [Pile]
remove num =
    map toPile . remove' . fromPile

    where

    -- This helper function is where most of the magic happens.  Note
    -- that the use of foldM computes inside of the list monad.

    remove' ps =
        [ ps' | (0, _, ps') <- foldM removeDistinctly (num, depth ps, []) ps ]

    removeDistinctly (n, depthLeft, cs) (colors, count)
        | n > depthLeft = fail "not enough cards left"
        | otherwise     = [ (n - i, depthLeft - count, (colors, count - i):cs)
                            | i <- [0 .. min n count] ]

-- | Determine how deep a pile of cards is (i.e., count the cards).

depth :: PileSpec -> Int
depth = sum . map snd

-- | Partition a pile by the given color.  Returns a pair comprising,
-- first, the subset of cards containing the given color and, second,
-- all of the other cards.

partitionOnColor :: Color -> Pile -> (Pile, Pile)
partitionOnColor c p =
    (c_p, p')
    where
    (c_p, p') = (filterFM (\kcs _ -> c `elem` kcs) p, minusFM p c_p)


-- Helpers that convert to Pile format from a PileSpec and vice versa.

toPile :: PileSpec -> Pile
toPile = listToFM . filter (\ (_, count) -> count /= 0)

fromPile :: Pile -> PileSpec
fromPile = fmToList

-- Rules that let us show and order FiniteMap values.

instance (Show a, Show b) => Show (FiniteMap a b)
    where show p = show (fmToList p)

instance (Ord a, Ord b) => Ord (FiniteMap a b)
    where
    compare p1 p2 = compare (fmToList p1) (fmToList p2)


-- Local Variables:
-- compile-command: "ghc -O2 -Wall -o TragicPfc --make TragicPfc.hs"
-- End:

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
random legal deck generator by matthewg (3.00 / 0) #48 Fri Apr 09, 2004 at 07:36:29 PM EST
#!/usr/bin/perl

use strict;
use warnings;

for my $pilecolor (0..4) {
    for (1..20) {
        my @card;
        for my $color (0..4) {
            if($color == $pilecolor or int(rand(2))) {
                push @card, $color;
            }
        }

        print join(" ", @card), "\n";
    }
}


thanks (nt) by codemonkey uk (3.00 / 0) #50 Sat Apr 10, 2004 at 12:19:05 AM EST
One caveat by Siddhi (3.00 / 0) #67 Tue Apr 13, 2004 at 01:44:38 PM EST
It only generates decks which have exactly 20 cards per pile. So other combinations, like having more than 20 cards in a pile are never generated. A nice modification would be to generate a random legal deck given the total number of cards and the number of cards per pile for the deck to be legal.

[ Parent ]
Entry in python by Siddhi (3.00 / 0) #57 Sun Apr 11, 2004 at 01:16:21 PM EST
My entry in python. Takes input from standard input. I have to say that its horribly coded, so its probably bigger and bulkier than it needs to be. If I have the time, I might clean it up a bit. It works on the two test cases given, but its not exhaustively tested by any means. Code and comments follow in the replies.

Code by Siddhi (3.00 / 0) #58 Sun Apr 11, 2004 at 01:19:51 PM EST
import sys

import string

import copy



# The number of cards in each pile to be a legal deck

LEGAL_TOTAL = 20



# Parse the input. The card is stored as an array.

def parse(card):

    cardColours = [0, 0, 0, 0, 0]

    cardArray = card.split()

    for i in cardArray:

        if (i = '0'):

            cardColours[0] = 1

        elif (i =
'1'):

            cardColours[1] = 1

        elif (i = '2'):

            cardColours[2] = 1

        elif (i =
'3'):

            cardColours[3] = 1

        elif (i = '4'):

            cardColours[4] = 1

    return cardColours



# Do a few simple checks

# 1. There should be at least 5*LEGAL_TOTAL cards

# 2. There should be at least LEGAL_TOTAL colours in all cards put together

def passedSimpleChecks(cardArray):

    if len(cardArray) < LEGAL_TOTAL*5:

        return 0

    for i in range(5):

        total = 0

        for j in cardArray:

            if j[i] =
1:

                total = total + 1

        if (total < LEGAL_TOTAL):

            return 0

    return 1



# Check if the current card distribution is legal

def check(pileArray):

    for i in range(5):

        total = srcColourCount(pileArray, i)

        if (total < LEGAL_TOTAL):

            return 0

    return 1



# Returns 1 if the card has the particular colour

def hasColour(card, colour):

    return card[colour]



# Move a card with from one pile to another

#

# Some heuristics -

# If the card doesnt have the colour of the destination, then dont move

#

# pileArray - the array of piles

# src - the source pile

# dest - the destination pile

# srcIndex - the index of the card to move in source pile

# destIndex - the index in the destination pile to move to

def doMove(pileArray, src, dest, srcIndex, destIndex):

    card = pileArray[src][srcIndex]

    if (hasColour(card, dest)):

        del pileArray[src][srcIndex]

        pileArray[dest].insert(destIndex, card)

    else:

        raise IndexError

    return pileArray



# Count the number of cards with the colour in the given pile

def srcColourCount(pileArray, srcPile):

    total = 0

    for card in pileArray[srcPile]:

        total = total + card[srcPile]

    return total



# Move a card from source to destination and then recursively call doAlgorithm

# Some heuristics -

# If moving this card will bring the colour count for the source below the limit,

#    then dont move

def makeAMove(pileArray, pileCopy, srcPile, destPile, srcIndex, destIndex):

    try:

        pileArray = copy.deepcopy(pileCopy)

        if (srcColourCount(pileArray,srcPile) > LEGAL_TOTAL):

            pileArray = doMove(pileArray, srcPile, destPile,srcIndex ,destIndex)

            doAlgorithm(pileArray)

    except IndexError:

        pass



# Create an array with the index of every unique card in the pile

# This way, you dont need to move around duplicate cards

def createUniqueIndices(pile):

    indexArray = []

    oldCard = [0, 0, 0, 0, 0]

    for i in range(len(pile)):

        if (compareCards(pile[i], oldCard) != 0):

            indexArray.append(i)

            oldCard = pile[i]

    return indexArray



# Comparision function for cards. Used in sorting and equality checks

def compareCards(card1, card2):

    for i in range(5):

        if (card1[i] < card2[i]):

            return 1

        elif (card1[i] > card2[i]):

            return -1

    return 0



# The actual brute force algorithm

# Recursively move cards around in all possible permutations :-O

def doAlgorithm(pileArray):

    if (check(pileArray) = 1):

        print "legal"

        sys.exit(1)

    pileCopy = copy.deepcopy(pileArray)

    pileCopy[0].sort(compareCards)

    pileCopy[1].sort(compareCards)

    pileCopy[2].sort(compareCards)

    pileCopy[3].sort(compareCards)

    pileCopy[4].sort(compareCards)

    indexArray = createUniqueIndices(pileCopy[0])

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 0, 1, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 0, 2, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 0, 3, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 0, 4, i, 0)

    indexArray = createUniqueIndices(pileCopy[1])

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 1, 2, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 1, 3, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 1, 4, i, 0)

    indexArray = createUniqueIndices(pileCopy[2])

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 2, 3, i, 0)

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 2, 4, i, 0)

    indexArray = createUniqueIndices(pileCopy[3])

    for i in indexArray:

        makeAMove(pileArray, pileCopy, 3, 4, i, 0)



# Set the initial distribution of cards

# Put each card in the pile of its first colour

def distribute(cardArray):

    initialPileArray = [[], [], [], [], []]

    for card in cardArray:

        if (hasColour(card, 0) =
1):

            initialPileArray[0].append(card)

        elif (hasColour(card, 1) = 1):

            initialPileArray[1].append(card)

        elif (hasColour(card, 2) =
1):

            initialPileArray[2].append(card)

        elif (hasColour(card, 3) = 1):

            initialPileArray[3].append(card)

        elif (hasColour(card, 4) =
1):

            initialPileArray[4].append(card)

    initialPileArray[0].sort(compareCards)

    initialPileArray[1].sort(compareCards)

    initialPileArray[2].sort(compareCards)

    initialPileArray[3].sort(compareCards)

    initialPileArray[4].sort(compareCards)

    return initialPileArray



# Main program

cardArray = []

for line in sys.stdin:

    card = string.strip(line) #read the input after truncating the trailing newline

    cardColours = parse(card)

    cardArray.append(cardColours)

if (passedSimpleChecks(cardArray) == 0):

    print "illegal"

    sys.exit(1)

initialPileArray = distribute(cardArray)

doAlgorithm(initialPileArray)

# Couldnt find a combination

print "illegal"

sys.exit(1)




[ Parent ]
Code again by Siddhi (3.00 / 0) #59 Sun Apr 11, 2004 at 01:34:06 PM EST
Posted in autoformat by mistake, which lead to some errors in the code. Anyway, here is the code again -

import sys
import string
import copy

# The number of cards in each pile to be a legal deck
LEGAL_TOTAL = 20

# Parse the input. The card is stored as an array.
def parse(card):
    cardColours = [0, 0, 0, 0, 0]
    cardArray = card.split()
    for i in cardArray:
        if (i == '0'):
            cardColours[0] = 1
        elif (i == '1'):
            cardColours[1] = 1
        elif (i == '2'):
            cardColours[2] = 1
        elif (i == '3'):
            cardColours[3] = 1
        elif (i == '4'):
            cardColours[4] = 1
    return cardColours

# Do a few simple checks
# 1. There should be at least 5*LEGAL_TOTAL cards
# 2. There should be at least LEGAL_TOTAL colours in all cards put together
def passedSimpleChecks(cardArray):
    if len(cardArray) < LEGAL_TOTAL*5:
        return 0
    for i in range(5):
        total = 0
        for j in cardArray:
            if j[i] == 1:
                total = total + 1
        if (total < LEGAL_TOTAL):
            return 0
    return 1

# Check if the current card distribution is legal
def check(pileArray):
    for i in range(5):
        total = srcColourCount(pileArray, i)
        if (total < LEGAL_TOTAL):
            return 0
    return 1

# Returns 1 if the card has the particular colour
def hasColour(card, colour):
    return card[colour]

# Move a card with from one pile to another
#
# Some heuristics -
# If the card doesnt have the colour of the destination, then dont move
#
# pileArray - the array of piles
# src - the source pile
# dest - the destination pile
# srcIndex - the index of the card to move in source pile
# destIndex - the index in the destination pile to move to
def doMove(pileArray, src, dest, srcIndex, destIndex):
    card = pileArray[src][srcIndex]
    if (hasColour(card, dest)):
        del pileArray[src][srcIndex]
        pileArray[dest].insert(destIndex, card)
    else:
        raise IndexError
    return pileArray

# Count the number of cards with the colour in the given pile
def srcColourCount(pileArray, srcPile):
    total = 0
    for card in pileArray[srcPile]:
        total = total + card[srcPile]
    return total

# Move a card from source to destination and then recursively call doAlgorithm
# Some heuristics -
# If moving this card will bring the colour count for the source below the limit,
#    then dont move
def makeAMove(pileArray, pileCopy, srcPile, destPile, srcIndex, destIndex):
    try:
        pileArray = copy.deepcopy(pileCopy)
        if (srcColourCount(pileArray,srcPile) > LEGAL_TOTAL):
            pileArray = doMove(pileArray, srcPile, destPile,srcIndex ,destIndex)
            doAlgorithm(pileArray)
    except IndexError:
        pass

# Create an array with the index of every unique card in the pile
# This way, you dont need to move around duplicate cards
def createUniqueIndices(pile):
    indexArray = []
    oldCard = [0, 0, 0, 0, 0]
    for i in range(len(pile)):
        if (compareCards(pile[i], oldCard) != 0):
            indexArray.append(i)
            oldCard = pile[i]
    return indexArray

# Comparision function for cards. Used in sorting and equality checks
def compareCards(card1, card2):
    for i in range(5):
        if (card1[i] < card2[i]):
            return 1
        elif (card1[i] > card2[i]):
            return -1
    return 0

# The actual brute force algorithm
# Recursively move cards around in all possible permutations :-O
def doAlgorithm(pileArray):
    if (check(pileArray) == 1):
        print "legal"
        sys.exit(1)
    pileCopy = copy.deepcopy(pileArray)
    pileCopy[0].sort(compareCards)
    pileCopy[1].sort(compareCards)
    pileCopy[2].sort(compareCards)
    pileCopy[3].sort(compareCards)
    pileCopy[4].sort(compareCards)
    indexArray = createUniqueIndices(pileCopy[0])
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 0, 1, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 0, 2, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 0, 3, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 0, 4, i, 0)
    indexArray = createUniqueIndices(pileCopy[1])
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 1, 2, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 1, 3, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 1, 4, i, 0)
    indexArray = createUniqueIndices(pileCopy[2])
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 2, 3, i, 0)
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 2, 4, i, 0)
    indexArray = createUniqueIndices(pileCopy[3])
    for i in indexArray:
        makeAMove(pileArray, pileCopy, 3, 4, i, 0)

# Set the initial distribution of cards
# Put each card in the pile of its first colour
def distribute(cardArray):
    initialPileArray = [[], [], [], [], []]
    for card in cardArray:
        if (hasColour(card, 0) == 1):
            initialPileArray[0].append(card)
        elif (hasColour(card, 1) == 1):
            initialPileArray[1].append(card)
        elif (hasColour(card, 2) == 1):
            initialPileArray[2].append(card)
        elif (hasColour(card, 3) == 1):
            initialPileArray[3].append(card)
        elif (hasColour(card, 4) == 1):
            initialPileArray[4].append(card)
    initialPileArray[0].sort(compareCards)
    initialPileArray[1].sort(compareCards)
    initialPileArray[2].sort(compareCards)
    initialPileArray[3].sort(compareCards)
    initialPileArray[4].sort(compareCards)
    return initialPileArray

# Main program
cardArray = []
for line in sys.stdin:
    card = string.strip(line)
    cardColours = parse(card)
    cardArray.append(cardColours)
if (passedSimpleChecks(cardArray) == 0):
    print "illegal"
    sys.exit(1)
initialPileArray = distribute(cardArray)
doAlgorithm(initialPileArray)
# Couldnt find a combination
print "illegal"
sys.exit(1)


[ Parent ]
Comments by Siddhi (3.00 / 0) #60 Sun Apr 11, 2004 at 01:57:04 PM EST
Okay, this is a pure brute force algorithm, with a couple of conditions to make it a bit faster. First, we create five empty piles and assign one pile to each colour. So pile 0 is for colour 0, pile 1 is for colour 1 and so on. For a legal deck, each pile should have at least 20 cards containing that colour. So pile 0 should have at least 20 cards of colour 0 and so on. Say pile 0 has 20 cards of colour 1, pile 1 has 20 cards of colour 0 etc, then although it is a legal distribution, my algorithm wont recognise it as legal. For it to be legal in my algorithm, the cards must be in the pile assigned to that colour. The reason for doing this is that by assigning a colour to a pile, I can implement a couple of speedups, which I describe in the next paragraph. I debated for a long time whether the speedups were worth the flip side of recognising only 1 out of 120 identical distributions (i.e permuting the piles), but in the end I went with it this way. I havent implemented it the other way, so I have no idea whether its faster or not. The first speedup is in setting the initial distribution of the cards to the various piles. I put each card in the pile corresponding to its lowest colour. Card 0 1 3 will end up on pile 0, card 4 will end up on pile 4, card 3 1 will end up on pile 1. In the worst case, all cards will have colour 0, and all cards will end up on pile 0. For more even distribution of colours, it will work well. Next, it brute forces the permutations. It first tries moving a card from pile 0 to pile 1, then recurses. There are a couple of rules regarding moving the cards. Firstly, it only moves a card if the card has the colour of the destination pile. So it will try moving a card 0 1 3 (which initially starts off on pile 0) to piles 1 and 3. There is no point trying to move this card to piles 2 and 4. It only moves unique cards. So if a pile contains 5 cards of 0 1 3, then it will only try to move one of them. If it fails, it wont try moving the other cards, and will instead move on to the next unique card in the pile. Finally, it wont move a card, if it causes the card count for the colour corresponding to the source pile to fall below the 20 card limit. So if we have exactly 20 cards with colour 0 on pile 0, then it will not try to move any move cards containing colour 0. It does not recognise the equivalence of moves. For instance, moving a card 0 1 3 to from pile 0 to pile 1, and then moving it to from pile 1 to pile 3 is equivalent to moving it from pile 0 straight to pile 3. The algorithm is a bit dumb in the sense that it will try both combinations, plus all the recursion which is common to both moves will be done twice. Recognising this should be easy to add and is something that I might add if I have time. I also suspect that it will lead to substantial speed gains.

[ Parent ]
Proper formatting by Siddhi (3.00 / 0) #61 Sun Apr 11, 2004 at 02:02:35 PM EST
This time I posted in HTML formatting instead of auto format :P So here we go again...

Okay, this is a pure brute force algorithm, with a couple of conditions to make it a bit faster.

First, we create five empty piles and assign one pile to each colour. So pile 0 is for colour 0, pile 1 is for colour 1 and so on.

For a legal deck, each pile should have at least 20 cards containing that colour. So pile 0 should have at least 20 cards of colour 0 and so on. Say pile 0 has 20 cards of colour 1, pile 1 has 20 cards of colour 0 etc, then although it is a legal distribution, my algorithm wont recognise it as legal. For it to be legal in my algorithm, the cards must be in the pile assigned to that colour. The reason for doing this is that by assigning a colour to a pile, I can implement a couple of speedups, which I describe in the next paragraph. I debated for a long time whether the speedups were worth the flip side of recognising only 1 out of 120 identical distributions (i.e permuting the piles), but in the end I went with it this way. I havent implemented it the other way, so I have no idea whether its faster or not.

The first speedup is in setting the initial distribution of the cards to the various piles. I put each card in the pile corresponding to its lowest colour. Card 0 1 3 will end up on pile 0, card 4 will end up on pile 4, card 3 1 will end up on pile 1. In the worst case, all cards will have colour 0, and all cards will end up on pile 0. For more even distribution of colours, it will work well.

Next, it brute forces the permutations. It first tries moving a card from pile 0 to pile 1, then recurses.

There are a couple of rules regarding moving the cards. Firstly, it only moves a card if the card has the colour of the destination pile. So it will try moving a card 0 1 3 (which initially starts off on pile 0) to piles 1 and 3. There is no point trying to move this card to piles 2 and 4.

It also only moves unique cards. So if a pile contains 5 cards of 0 1 3, then it will only try to move one of them. If it fails, it wont try moving the other cards, and will instead move on to the next unique card in the pile.

Finally, it wont move a card, if it causes the card count for the colour corresponding to the source pile to fall below the 20 card limit. So if we have exactly 20 cards with colour 0 on pile 0, then it will not try to move any move cards containing colour 0.

It does not recognise the equivalence of moves. For instance, moving a card 0 1 3 to from pile 0 to pile 1, and then moving it to from pile 1 to pile 3 is equivalent to moving it from pile 0 straight to pile 3. The algorithm is a bit dumb in the sense that it will try both combinations, plus all the recursion which is common to both moves will be done twice. Recognising this should be easy to add and is something that I might add if I have time. I also suspect that it will lead to substantial speed gains.

[ Parent ]
Code version 2 by Siddhi (3.00 / 0) #64 Mon Apr 12, 2004 at 02:50:56 PM EST
import sys
import string
import copy

# The number of cards in each pile to be a legal deck
LEGAL_TOTAL = 20

# Parse the input. The card is stored as an array.
def parse(card):
    cardColours = [0, 0, 0, 0, 0]
    cardArray = card.split()
    for i in cardArray:
        if (i == '0'):
            cardColours[0] = 1
        elif (i == '1'):
            cardColours[1] = 1
        elif (i == '2'):
            cardColours[2] = 1
        elif (i == '3'):
            cardColours[3] = 1
        elif (i == '4'):
            cardColours[4] = 1
    return cardColours

# Do a few simple checks
# 1. There should be at least 5*LEGAL_TOTAL cards
# 2. There should be at least LEGAL_TOTAL colours in all cards put together
def passedSimpleChecks(cardArray):
    if len(cardArray) < LEGAL_TOTAL*5:
        return 0
    for i in range(5):
        total = 0
        for j in cardArray:
            if j[i] == 1:
                total = total + 1
        if (total < LEGAL_TOTAL):
            return 0
    return 1

# Check if the current card distribution is legal
def check(pileArray):
    for i in range(5):
        total = srcColourCount(pileArray, i)
        if (total < LEGAL_TOTAL):
            return 0
    return 1

# Returns 1 if the card has the particular colour
def hasColour(card, colour):
    return card[colour]

# Move a card with from one pile to another
#
# Some heuristics -
# If the card doesnt have the colour of the destination, then dont move
#
# pileArray - the array of piles
# src - the source pile
# dest - the destination pile
# srcIndex - the index of the card to move in source pile
# destIndex - the index in the destination pile to move to
def doMove(pileArray, src, dest, srcIndex, destIndex):
    card = pileArray[src][srcIndex]
    if (hasColour(card, dest)):
        del pileArray[src][srcIndex]
        pileArray[dest].insert(destIndex, card)
    else:
        raise IndexError
    return pileArray

# Count the number of cards with the colour in the given pile
def srcColourCount(pileArray, srcPile):
    total = 0
    for card in pileArray[srcPile]:
        total = total + card[srcPile]
    return total

# Move a card from source to destination and then recursively call doAlgorithm
# Some heuristics -
# If moving this card will bring the colour count for the source below the limit,
#    then dont move
def makeAMove(pileArray, pileCopy, srcPile, destPile, srcIndex, destIndex):
    try:
        pileArray = copy.deepcopy(pileCopy)
        if (srcColourCount(pileArray,srcPile) > LEGAL_TOTAL):
            pileArray = doMove(pileArray, srcPile, destPile,srcIndex ,destIndex)
            doAlgorithm(pileArray)
    except IndexError:
        pass

# Create an array with the index of every unique card in the pile
# This way, you dont need to move around duplicate cards
def createUniqueIndices(pile):
    indexArray = []
    oldCard = [0, 0, 0, 0, 0]
    for i in range(len(pile)):
        if (compareCards(pile[i], oldCard) != 0):
            indexArray.append(i)
            oldCard = pile[i]
    return indexArray

# Comparision function for cards. Used in sorting and equality checks
def compareCards(card1, card2):
    for i in range(5):
        if (card1[i] < card2[i]):
            return 1
        elif (card1[i] > card2[i]):
            return -1
    return 0

# Find the next pile to move the card to
def findNextPile(currentPile, card):
    for colour in range(currentPile + 1, 5):
        if hasColour(card, colour):
            return colour
    return -1

# The actual brute force algorithm
# Recursively move cards around in all possible permutations :-O
def doAlgorithm(pileArray):
    if (check(pileArray) == 1):
        print "legal"
        sys.exit(1)
    pileCopy = copy.deepcopy(pileArray)
    pileCopy[0].sort(compareCards)
    pileCopy[1].sort(compareCards)
    pileCopy[2].sort(compareCards)
    pileCopy[3].sort(compareCards)
    pileCopy[4].sort(compareCards)
    indexArray = createUniqueIndices(pileCopy[0])
    for cardIndex in indexArray:
        card = pileCopy[0][cardIndex]
        nextPile = findNextPile(0, card)
        if (nextPile != -1):
            makeAMove(pileArray, pileCopy, 0, nextPile, cardIndex, 0)
    indexArray = createUniqueIndices(pileCopy[1])
    for cardIndex in indexArray:
        card = pileCopy[1][cardIndex]
        nextPile = findNextPile(1, card)
        if (nextPile != -1):
            makeAMove(pileArray, pileCopy, 1, nextPile, cardIndex, 0)
    indexArray = createUniqueIndices(pileCopy[2])
    for cardIndex in indexArray:
        card = pileCopy[2][cardIndex]
        nextPile = findNextPile(2, card)
        if (nextPile != -1):
            makeAMove(pileArray, pileCopy, 2, nextPile, cardIndex, 0)
    indexArray = createUniqueIndices(pileCopy[3])
    for cardIndex in indexArray:
        card = pileCopy[3][cardIndex]
        nextPile = findNextPile(3, card)
        if (nextPile != -1):
            makeAMove(pileArray, pileCopy, 3, nextPile, cardIndex, 0)

# Set the initial distribution of cards
# Put each card in the pile of its first colour
def distribute(cardArray):
    initialPileArray = [[], [], [], [], []]
    for card in cardArray:
        if (hasColour(card, 0) == 1):
            initialPileArray[0].append(card)
        elif (hasColour(card, 1) == 1):
            initialPileArray[1].append(card)
        elif (hasColour(card, 2) == 1):
            initialPileArray[2].append(card)
        elif (hasColour(card, 3) == 1):
            initialPileArray[3].append(card)
        elif (hasColour(card, 4) == 1):
            initialPileArray[4].append(card)
    initialPileArray[0].sort(compareCards)
    initialPileArray[1].sort(compareCards)
    initialPileArray[2].sort(compareCards)
    initialPileArray[3].sort(compareCards)
    initialPileArray[4].sort(compareCards)
    return initialPileArray

# Main program
cardArray = []
for line in sys.stdin:
    card = string.strip(line)
    cardColours = parse(card)
    cardArray.append(cardColours)
if (passedSimpleChecks(cardArray) == 0):
    print "illegal"
    sys.exit(1)
initialPileArray = distribute(cardArray)
doAlgorithm(initialPileArray)
# Couldnt find a combination
print "illegal"
sys.exit(1)


[ Parent ]
Comments for code version 2 by Siddhi (3.00 / 0) #65 Mon Apr 12, 2004 at 02:58:32 PM EST
This code is pretty much the same as the previous one, only that I added in some code to prevent equivalent moves from being executed. I'm not sure if this breaks the algorithm or not, but the code still works on the two test cases (which are admittedly rather simple). I would like to try it out on some more complext test cases, but I'm too lazy to come up with them ;)

[ Parent ]
Don't be dissin my van. by celeriac (3.00 / 0) #69 Tue Apr 13, 2004 at 11:05:07 PM EST
My van is fast, fool. You want the Python Numeric library to run it. Sucka.

And now I will settle down with a nice glass of milk.



Code by celeriac (3.00 / 0) #71 Tue Apr 13, 2004 at 11:13:17 PM EST
Code is in here. It is my first proper Python program; critique the style if you're into that sort of thing.

[ Parent ]
Small update by celeriac (3.00 / 0) #82 Wed Apr 14, 2004 at 12:05:00 PM EST
Changed the name to be less ambiguous, if it's going to be hanging around in my user files. Also added some command line options to change the number of colors and the required pile height, and a --test option that prints out a random valid deck:

$ python pfc_tragic.py --colors=8 --pile=125000 --test
one_million_cards.txt
$ time python pfc_tragic.py -c 8 -p 125000 one_million_cards.txt
legal

real 0m35.492s
user 0m32.968s
sys 0m2.311s


[ Parent ]
Crash Course in Linear Optimization by celeriac (3.00 / 0) #72 Tue Apr 13, 2004 at 11:16:10 PM EST
Let's look at a problem with just two colors.

[0]   * 15
[1]   * 12
[0,1] * 13

Call "a" the number of card [0] dealt into the 0 pile, "b" the number of card [1] dealt into the 1 pile, "c" the number of card [0,1] dealt into the 0 pile, and "d" the number of card [0,1] dealt into the 1 pile. Then we can express the problem as a system of inequalities:

a ≤ 15
b ≤ 12
c + d ≤ 13
a + c ≥ 20
b + d ≥ 20
with a, b, c, d ≥ 0.

This is a simple instance of an integer linear programming problem. A general statement of the linear programming problem is,

Find x which maximizes cx while Axb and xi ≥ 0,
where c and x are vectors and A is an N-by-M matrix. In this case we are just looking for a feasible solution and we have no c. More importantly, we are constrained to integer values of the xi (no tearing cards in half and putting them in two decks!)

Now, I had some notion that problems like this were well studied, since I've used other people's algorithms to solve them.

I figured this was a good opportunity to brush up on some linear algebra and use Python, which I just started learning a couple of weeks ago. So, ah, I'd like it if someone could critique my Python style if they're into that sort of thing.

Anyhow, the algorithm I chose is the simplex algorithm, because it sounded the simplest. Basically, the idea is that each constraint equation defines a half-space, where on one side of a plane the constraint is satisfied. When all the half-spaces intersect, the result is a convex polyhedron. Each vertex of the polyhedron is a point where N of the M constraints are satisfied at equality, and the other constraints have "slack." Because the function cx is linear, its maximum must occur at one of the vertices of the polyhedron. The algorithm is a bunch of matrix manipulation that effectively "walks" over the vertices of the polyhedron by changing which constraints are tight and which ones have slack, and just climbs up the gradient until it finds the right vertex.

I was worried with this approach that I would run into problems at the end with requiring the variables to be integers--integer linear programming problems are generally HP-hard, and most approaches to them amount to trying to break them down into an exponential number of linear problems. I started out with some code for doing branch and bound, but after a while I realized I couldn't come up with a deck that could be fractionally valid but not integrally valid. Well, it turns out that the matrix M is totally unimodular. This means that all the vertices of the polyhedron lie on integers, which is pretty convenient. It also means the problem is dual to a network flow problem, which seems to be the approach that edwin chose.

The runtime complexity of this program is somewhere around O(N^4), where N is the number of distinct cards. The deck size itself doesn't matter much.

(I'd like to thank Mr. Ian Craw for putting this awesome set of course notes online. I was stuck on some details yesterday and these notes cleared up just about everything.)

[ Parent ]
damn you! by spcmanspiff (3.00 / 0) #76 Wed Apr 14, 2004 at 06:15:22 AM EST
It appears we had the same insight ... alas, it looks like your version actually worked :)

As I've never implemented simplex before, and I tried to do it in hacky C w/in only a few hours, I fail.

[ Parent ]
Non-entry by spcmanspiff (3.00 / 0) #73 Wed Apr 14, 2004 at 04:50:57 AM EST
Alas, I did not have time to debug my spaghetti1 C code.

Algorithm is posted in child comment.

[1] Spaghetti was somewhat intentional, as I wanted to toy around with obfuscating C and this was a good candidate problem. However, I went a bit too far along that path on my first-cut and ended up with something un-debuggable. Alas.

Algorithm: by spcmanspiff (3.00 / 0) #75 Wed Apr 14, 2004 at 05:12:34 AM EST
Ignore the fact that we have to have integer solutions for the moment.

For each card type (31 of them), there is a set of valid destination piles. E.g., for color 0, valid source cards are 1,3,5,...

We can then form a set of variables Tij where Tij = number of cards that should be taken from source i and put into pile j. (Not all ij combinations are valid, since a card must have color j present to be placed in pile j).

These lead to two inequalities:
Sum(Tij) >= 20 for each color j
Sum(Tij) <= (number of cards provided) for each card type i.

If a solution exists to these inequalities, then the deck is valid.

Now, about that ignoring-integers thing:
I think this is totally valid, but don't really have the maths to back it up. Note that the enequalities above have no coefficients; my belief is that this property means that all 'corner' solutions (as found by non-interior linear programming methods) will lie on an integer intersection.

(With just 2 variables, this seems obviously true -- any number of lines at 45 degrees and with integer y-intercepts should intersect only at integer coordinates.)

The algorithm then, is nothing more than linear programming:

  • Setup the above inequalities into a big fat matrix.
  • Follow the simplex algorithm to find a solution to above matrix.
  • If you get as far as a basic feasible solution, then you know the deck is good.

Hopefully this was somewhat intelligible; I wrote it in a bit of a hurry.

If anyone knows for sure whether I'm correct (or if I screwed up) in the basic assumption that all corner solutions to the above system of inequalities lie on integers, then I'd love to learn it either way...

[ Parent ]
Read celeriac's excellent solution for... by the (3.00 / 0) #77 Wed Apr 14, 2004 at 07:03:28 AM EST
...an answer to your final question.

--
The Definite Article
[ Parent ]
My entry by ucblockhead (3.00 / 0) #78 Wed Apr 14, 2004 at 08:12:05 AM EST
Ok, I didn't get near enough time, so it's barely tested, but what the hell...

I've been meaning to do one of these in Forth, and this problem was conducive to it. It uses gforth

You can run it as a script like this:

gforth tragic.fs -e main <input1.txt

(The -e flag tells it to execute the word "main" after loading the file.)

One cool thing about Forth is that you can "compile" it to make it run faster. To do this, you'd do this:

gforth tragic.fs

Then at the forth prompt, type "savesystem tragic.fi". This saves an "image" file. You can use this image file without reinterpreting the source like this:

gforth -i tragic.fi -e main <input1.txt

Not that there's much point in something so simple.

The algorithm I used is fast but perhaps braindead. It works basically like a human would in doing this task. First, it goes through the cards one by one, putting each card in the smallest stack it can. Then, if this isn't enough, it searchs the other stacks from the biggest to the next to smallest for a card that could be put on the smallest stack. Once all stacks have at least twenty, it declares "legal" and quits. If it ever fails to find a card to move, it declares "illegal" and quits.

There remains the problem of infinite loops...the above could easily get into a situation where it moves a card back and forth, or moves a few cards in a circular manner. Instead of doing something really smart to detect this, I simply give up if I can't find anything in a reasonable amount of time. In practice, this should always work, assuming I've set the number of attempts high enough. (I chose 1000...I suspect 100 would work.)
---
[ucblockhead is] useless and subhuman

The entry by ucblockhead (3.00 / 0) #79 Wed Apr 14, 2004 at 08:12:50 AM EST
\ Convenience function.  Allocates in 4-byte chuncks and terminates on error
: 4alloc
    4 * allocate
    0 <> IF
        ." Could not allocate memory"
        quit
    THEN
;

\ Constant.  Number of possible colors
: NumColors 5 ;
: PileSize 20 ;
: CardWithAllColors
    0
    NumColors 0 ?DO
        1 I lshift or
    LOOP
;

\ Convert an ASCII color value to an integer and add it to the current card
: ParseColor    ( Card Digit - Card )
    48 -                  \ convert to int
    1 SWAP lshift or    \ set bit in current card
;

: NewCard
    SWAP 1 +     \ increment count
    0             \ put new card on stack
;

\ Read cards while there is data, leaving them on the stack
: ReadInput        ( - [Cards] Count )
    0        \ count
    0        \ current card
    BEGIN
        key?
    WHILE
        \ On newline, start a new card
        key DUP 10 = OVER 13 = OR IF  \ carriage return
            DROP
            DUP 0 <> IF  \ Allow for blank lines
                NewCard
            THEN
        \ Otherwise, add any color to the current card
        ELSE
            DUP 32 = IF  \ space
                DROP
            ELSE
                ParseColor
            THEN
        THEN
    REPEAT
    DROP    \ null card left after last CR
;

\ Convenience.  Cards take 4 bytes.
: StoreCard ( Card Addr idx -- )
    4 * + !
;

\ Create a temporary spot to store the cards and then store them
: StoreInput ( [cards] NumCards -- addr )
    DUP 4alloc

    SWAP 0 ?DO
        SWAP OVER I StoreCard
    LOOP
;

\ True of the card has the color
: IsColor ( card color -- flag )
    1 SWAP lshift and 0 <>
;

\ ------------------ Card Pile ----------------------
Variable cards             \ Starting card pile
Variable numcards         \ The number of cards read

\ Fetch the card from the card file
: @Card ( idx -- card )
    4 * cards @ + @
;

\ Put the card in the card file
: !Card ( card idx -- )
    4 * cards @ + !
;

\ True if the card in the pile has the color
: CardIsColor  ( color idx -- flag )
    @Card SWAP IsColor   
;

\ ------------------ End Card Pile ----------------------

\ ------------------ Color Counts ----------------------

Variable colorcounts        \ number of cards with a particular color

\ Create the colorcounts array, initializing to zero
: MakeColorCounts
    NumColors 4alloc
    colorcounts !
    NumColors 0 ?DO
        0 I 4 * colorcounts + !
    LOOP
;

\ Fetch a count
: @ColorCount         ( Color - Count )
    4 * colorcounts + @
;

\ Store a count
: !ColorCount         ( Count Color - )
    4 * colorcounts + !
;

\ Increment a count
: ColorCount++        ( Color - )
    DUP @ColorCount
    1+
    SWAP !ColorCount
;

\ Count colors in the initial card set
: CountColors
    4 0 ?DO 0 I !ColorCount LOOP

    numcards @ 0 ?DO
        4 I CardIsColor IF 4 ColorCount++ THEN
        3 I CardIsColor IF 3 ColorCount++ THEN
        2 I CardIsColor IF 2 ColorCount++ THEN
        1 I CardIsColor IF 1 ColorCount++ THEN
        0 I CardIsColor IF 0 ColorCount++ THEN
    LOOP
;

\ Output the color counts
: .ColorCounts
    NumColors 0 ?DO
        I @ColorCount .
    LOOP
    CR
;

: CountsLegal ( -- flag )
    NumColors 0 ?DO
        I @ColorCount PileSize < IF
            false
            UNLOOP EXIT
        THEN
    LOOP
    true
;

\ ------------------ End Color Counts ----------------------

\ Print a card
: .Card
    ." ["
    NumColors 0 ?DO
        DUP I IsColor IF I . THEN
    LOOP
    DROP
    ." ]"
;

\ ------------------ Piles ----------------------

Variable piles    \ This contains one array for each color with a length bite
                \ at the end

\ Fetch location of the array for a color
: @Pile ( color -- addr )
    4 * piles @ +
;

\ Fetch the location of an item in the array for a color
: Pile[] ( Index Color -- Addr )
    @Pile @
    SWAP 4 * +
;

\ Fetch an item from a pile
: @Pile[]    ( Index Color -- Card )
    Pile[] @   
;

\ Store an item on a pile
: !Pile[]    ( Card Index Color -- )
    Pile[] !   
;

\ Create the memory for a pile
: MakePiles
    PileSize 4alloc piles !
    NumColors 0 ?DO
        numcards @ 4 + 4alloc \ size at end
        I @pile !
    LOOP
;

\ Get the address that contains the count of cards in the pile
: CardsInPileAddr    ( Color -- Addr )
    @pile 400 +
;

\ Fetch the number of cards in the pile
: @CardsInPile     ( Color -- Number )
    CardsInPileAddr @
;

\ Set the number of cards in the pile
: !CardsInPile     ( Number Color -- )
    CardsInPileAddr !
;

\ Decrement the number of cards in the pile
: CardsInPile-- ( Color -- )
    DUP @CardsInPile 1- SWAP !CardsInPile
;

\ Increment the number of cards in the pile
: CardsInPile++ ( Color -- )
    DUP @CardsInPile 1+ SWAP !CardsInPile
;

\ Find the smallest pile for a color not on the given card
: SmallestPile ( Card -- Color )
    0 99999
    NumColors 0 ?DO
        2 PICK I IsColor IF
            I @CardsInPile Over < IF
                DROP DROP
                I I @CardsInPile
            THEN
        THEN
    LOOP
    DROP SWAP DROP
;

\ Find the largest pile for a color not on the given card
: BiggestPile ( Card -- Color )
    0 0
    NumColors 0 ?DO
        2 PICK I IsColor IF
            I @CardsInPile Over > IF
                DROP DROP
                I I @CardsInPile
            THEN
        THEN
    LOOP
    DROP SWAP DROP
;

\ Take a card and change it to not have a particular color
: RemoveColor ( Card Color -- Card )
    1 SWAP lshift XOR
;

\ Print the contents of a pile (for debugging)
: .Pile ( Color -- )
    DUP .
    ." :"
    DUP @CardsInPile 0 ?DO
        DUP I SWAP @Pile[] .Card
    LOOP
    DROP
    CR
;

\ Print the contents of all piles (for debugging)
: .Piles ( -- )
    NumColors 0 ?DO
        I .Pile
    LOOP
;

: AddCardToPile ( Card Color -- )
    DUP @CardsInPile    ( Card Color Number )   
    OVER CardsInPile++  ( Card Color Number )
    SWAP !Pile[]       
;

: RemoveCardFromPile ( Color Idx -- Card )
    2DUP SWAP @Pile[]               ( Color Idx Card )
    -ROT                          ( Card Color Idx )
    OVER                            ( Card Color Idx Color )
    DUP CardsInPile--             
    DUP @CardsInPile                ( Card Color Idx Color Number )
    SWAP @Pile[]                  ( Card Color Idx Card )
    -ROT                              ( Card Card Color Idx )
    SWAP !Pile[]
;

\ Move a card from the inital card set to a pile
: MoveCardToPile ( Color idx - )
    DUP @Card
    SWAP 0 SWAP !Card
    SWAP AddCardToPile
;

\ Move a card from one pile to another.
: MoveCard ( TargetColor Idx SourceColor - )
    SWAP RemoveCardFromPile
    SWAP AddCardToPile
;

\ True if the piles are organized in a legal manner.  (i.e. PileSize per pile)
: IsLegal
    NumColors 0 ?DO
        I @CardsInPile PileSize < IF
            false
            UNLOOP EXIT
        THEN

    LOOP
    true
;

\ Find a card in a pile of a particular color and return its index. 
\ Return 999999 if none exists
: FindCard     ( Pile Color -- Idx )
    SWAP
    DUP
    @CardsInPile 0 ?DO
        I OVER @Pile[]
        2 PICK IsColor IF
            DROP DROP
            I
            UNLOOP EXIT
        THEN
    LOOP
    DROP DROP
    999999
;

\ ------------------ End Piles ----------------------

\ Make an initial guess by moving all cards from the inital card list
\ to the piles.
: PassOne
    numcards @ 0 ?DO
        I @Card
        SmallestPile        \ Put a card in the smallest pile it goes with
        I MoveCardToPile
    LOOP
;

\ Main program        (A horrible C-Ism, I know...)
: main

    \ Read the input and save it to the initial card area
    ReadInput
    DUP numcards !        \ Save off the number of cards
    StoreInput
    cards !
   
    \ Count the number of colors to see if there's any point in going further.
    MakeColorCounts
    CountColors
    CountsLegal IF
    ELSE
        ." illegal" CR
        quit
    THEN

    \ Create the piles data structure
    MakePiles

    \ Move the cards to the piles
    PassOne

    \ Repeatedly move cards to the smallest pile until we either find
    \ a legal set of piles or we've made 1000 moves.  It's assumed that
    \ on any reasonable set, 1000 moves means infinit loop.

    CardWithAllColors
    1000 0 ?DO
        DUP

        \ Look for a card to move to the smallest pile in each pile,
        \ from biggest to next to smallest.
        BEGIN
            DUP 0 <>
        WHILE
            DUP SmallestPile    \ Find the smallest pile
            2DUP RemoveColor
            BiggestPile            \ Find biggest pile
            SWAP 2DUP
            FindCard
            \ If we don't find something to move, try the next smallest
            \ pile
            DUP 999999 = IF
                DROP DROP DROP
                DUP BiggestPile RemoveColor
            \ Move the card
            ELSE
                2 ROLL
                MoveCard
                DROP
                0        \ Signal the end of the inner loop
            THEN
        REPEAT
        DROP
        IsLegal IF
            DROP
            ." legal" CR
            quit
        THEN
    LOOP
    DROP
    ." illegal" CR
    quit
;

\ savesystem tragic.fi



---
[ucblockhead is] useless and subhuman
[ Parent ]
Bleah by ucblockhead (3.00 / 0) #80 Wed Apr 14, 2004 at 08:30:27 AM EST
I apologize for posting the algorithm in the head post.
---
[ucblockhead is] useless and subhuman
[ Parent ]
End swapping by ucblockhead (3.00 / 0) #84 Wed Apr 14, 2004 at 12:16:10 PM EST
I'm fairly certain that there can't be more than 21 card swaps required after the initial piles are built. (Slightly fewer than the 1000 I allow for!)

In the worst case, the smallest pile after the initial sort will be four. This is caused by the edge case where the first twenty cards have all four colors and then the next eighty cards have any set of colors except for one. That one color pile with then have four cards.

I am also fairly sure that the most number of swaps in a circular loop are five. (The number of cards, basically.) I'm still trying to prove that completely. If so, that means that the most swaps you could ever have are sixteen to fill out the smallest pile and then five more to go in a circle. (And actually I suppose it's twenty as the twenty-first move just brings you back to a bad state.)

If I can prove that this is indeed the most card move attempts needed after the initial sort, then I'd guess this algorithm is faster than any sort of search tree, despite it's kludy appearance.
---
[ucblockhead is] useless and subhuman

[ Parent ]
Ok... by ucblockhead (3.00 / 0) #88 Wed Apr 14, 2004 at 02:56:33 PM EST
Ok, I'm wrong about the twenty, but I'm convinced that the number of card moves that will find a legal position if available is small.
---
[ucblockhead is] useless and subhuman
[ Parent ]
Can't get it to run -- doesn't take input by tmoertel (3.00 / 0) #105 Tue Apr 20, 2004 at 07:52:19 AM EST
I tried running your program under Fedora Core 1 using GForth 0.62, but the program doesn't seem to be able to accept input. It returns immediately with "illegal" without reading anything, and the input ends up going to the Forth command line:
$ gforth ucblockhead.fs -e main < input.txt
illegal

0 2  ok
0 2  ok
and so on
Any suggestions?

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Hmmm... by ucblockhead (3.00 / 0) #106 Tue Apr 20, 2004 at 08:17:22 AM EST
I dunno...I just copied my source out of my post, the input out of the story and it worked fine...

I run Debian with gforth 0.6.2. It shouldn't make a difference.

You could try editing the file, adding the word "main" at the bottom, and doing:

gforth ucblockhead.fs <input.txt
---
[ucblockhead is] useless and subhuman

[ Parent ]
Can you post a link to the code? by tmoertel (3.00 / 0) #107 Tue Apr 20, 2004 at 08:43:06 AM EST
Maybe something is getting killed during copy-and-paste.

thx.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
sure thing by ucblockhead (3.00 / 0) #108 Tue Apr 20, 2004 at 09:31:12 AM EST
here. In my files section.
---
[ucblockhead is] useless and subhuman
[ Parent ]
Thanks, but still no luck. by tmoertel (3.00 / 0) #109 Tue Apr 20, 2004 at 10:06:53 AM EST
How hard would it be to take input from a file?

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Not hard... by ucblockhead (3.00 / 0) #110 Tue Apr 20, 2004 at 10:15:56 AM EST
It shouldn't be hard at all. Sounds like it thinks it is seeing end-of-file.

Unfortunately, this is the first Forth I've done in fifteen years, so I'm not sure about the quirks of gforth.

I suppose I could work on a file handling version.

(Forth is so retro that do this is not trivial.)
---
[ucblockhead is] useless and subhuman

[ Parent ]
The problem by ucblockhead (3.00 / 0) #112 Tue Apr 20, 2004 at 02:24:48 PM EST
Are you piping rather than redirecting? I got a chance to run your scripts, and I see what you're seeing when I do this:

./deck-tgm-003.sh | gforth tragic.fs -e main
---
[ucblockhead is] useless and subhuman

[ Parent ]
That works. by tmoertel (3.00 / 0) #113 Tue Apr 20, 2004 at 03:04:41 PM EST
It never occurred to me that the Forth I/O subsystem might care whether the file descriptor represented a file or pipe. Thanks for taking the time to look into the situation.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Forth IO by ucblockhead (3.00 / 0) #114 Tue Apr 20, 2004 at 03:35:42 PM EST
Yeah...I suspect it's just poorly done.
---
[ucblockhead is] useless and subhuman
[ Parent ]
Can you explain this behavior? by tmoertel (3.00 / 0) #115 Tue Apr 20, 2004 at 04:09:35 PM EST
Just to make sure that something isn't wrong with GForth under FC1, can you explain if the following behavior is intended?

I added a call to .Piles immediately after PassOne. When the code is run against the monochromatic test (deck 000 in my earlier decks posting, it appears that the 0-pile has 23 cards, three of which are empty:

0 :[][][][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ][0 ]
1 :[1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ][1 ]
2 :[2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ][2 ]
3 :[3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ][3 ]
4 :[4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ][4 ]

(widen screen to prevent wrap-around)

Can you explain? Or is this GForth acting weird? Does this happen on your computer?

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
The reason I ask: It causes false legals by tmoertel (3.00 / 0) #116 Tue Apr 20, 2004 at 04:22:23 PM EST
For example, consider this illegal deck:

{ yes 0 | head -19;  for c in "0 1" 2 3 4; do yes $c | head -20; done; }

On my system your code classifies it as "legal," but the deck actually requires another 0 or 1 card before all the requirements are satisfied.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
damnit! by ucblockhead (3.00 / 0) #117 Tue Apr 20, 2004 at 04:44:04 PM EST
It's some IO issue. On my machine, it appears to correctly deal with both versions. .Piles does not have the blank cards.

It appears that the PassOne code can't deal with blank cards, and puts them in the first stack. (The actual problem is in SmallestPile...I assume at least one of the colors will match.

This only shows up when the IO stuff generates blank cards, something that doesn't appear to happen on my machine. I need to research it more. It appears to me that Gforth's support for standard input is not good. (Not a surprise, since stdin and stdout are not concepts that were in the original Forth language.)
---
[ucblockhead is] useless and subhuman

[ Parent ]
Looking at "info gforth" ... stdin by tmoertel (3.00 / 0) #118 Tue Apr 20, 2004 at 05:41:41 PM EST
In the "Gforth in pipes" section of the Gforth info pages, I see the following:
If you pipe into Gforth, your program should read with `read-file' or `read-line' from `stdin' (*note General files::). `Key' does not recognize the end of input.
This same section also shows how to read from stdin. Here's a provided example that copies the input verbatim to the output:
cat startup.fs |
gforth -e ": foo begin pad dup 80 stdin read-file throw dup while \
type repeat ; foo bye" |
head
Might be the way to go.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
er... by ucblockhead (3.00 / 0) #119 Wed Apr 21, 2004 at 03:04:03 AM EST
Yeah, I'm sre that is the way to go. I'll look at it...
---
[ucblockhead is] useless and subhuman
[ Parent ]
K entry by jjayson (3.00 / 0) #81 Wed Apr 14, 2004 at 11:46:37 AM EST
Sorry I missed the deadline, so I just got this done as quickly as possible at lunch today. I also tried to make it as short as possible. I know I can shave about ten charaters off it, but here it is anyways. It is basically brute force breadth-first search with some small exceptions. Such as once it gets to 20 cards of a color, it stop adding to it. This is done by the 20-min (20&) operation before I collapse the frontier to only unique elements (?). On my (random) test cases this cuts the frontier/open-list down down by about 85%.

I'll try to get something a little more intelligent done tonight since the problem is simple and interesting.

On the test data, it runs in a few seconds on the machines at my office, but those have massive caches and memories and blazing processors, built for running numerical simulations. If too much of the frontier spills out of cache, it will take significantly longer. God help you if you actually start swapping. On my beater home machine when it start swapping, tragic1.txt takes about 3 minutes. It only has a final frontier size of about 200,000 (16 bytes per entry), but the disk gnashes away.

Save the following as tragic.k and give it the filename as an argument (such as "k tragic input"):

`0::[(5#20)_in(?20&,/@[;;1+]\:/:)/[,&5;{0$(0,&x=" ")_ x}'0:_i 0];"";"il"],"legal\n"
\\
Translation available is you care for one.

3 minutes!?!? by ucblockhead (3.00 / 0) #83 Wed Apr 14, 2004 at 12:08:59 PM EST
My crappy Forth implementation takes 40 milliseconds and probably takes less than 40k RAM...
---
[ucblockhead is] useless and subhuman
[ Parent ]
yep by jjayson (3.00 / 0) #85 Wed Apr 14, 2004 at 12:17:40 PM EST
I didn't say it was fast, just short. It does an almost exhaustive search even well past once it has found a solution. Didn't have time for amything else.

The machine in question is a very old P-133 and w/128M of memory and a 16K cache (I think). With NT, Moz open (taking up 40M, IE crapped out long ago), and downloading something, there is virtually nothing left of system resournce. Doing anything, even just starts the machine swapping like mad.


[ Parent ]
Good God by Siddhi (3.00 / 0) #97 Wed Apr 14, 2004 at 06:54:39 PM EST
Can you actually read that ?!?!

[ Parent ]
No by jjayson (3.00 / 0) #100 Thu Apr 15, 2004 at 09:08:30 AM EST
I tried to make it as short as possible and that lead to some ugliness, like factoring out "legaln" from the "legaln" and "illegaln" (leaving "" and "il"). However, it was too slow so I had to make a couple concessions, ruining it from being the shortest possible.

The other entry (http://www.hulver.com/scoop/comments/2004/4/5/55524/44031/93#93) is much more readable and not unlike other K code, although maybe a little more messy than usual since it wasn't really planned and just hacked out in the interpreter.


[ Parent ]
Spoiler. by ambrosen (3.00 / 0) #133 Fri Jun 18, 2004 at 12:09:32 PM EST
You posted the code in a top level comment and gave away the algorithm.

[ Parent ]
Which time zone for the deadline? by the (3.00 / 0) #86 Wed Apr 14, 2004 at 01:54:12 PM EST
Just that I have an algorithm that blows everything else out of the water but it's not quite finished...

--
The Definite Article
CDT - it's 9;00 here (nt) by jacob (3.00 / 0) #87 Wed Apr 14, 2004 at 02:01:15 PM EST


--

[ Parent ]
Still accepting? by jjayson (3.00 / 0) #94 Wed Apr 14, 2004 at 04:38:43 PM EST
You said midnight. Did that mean tonight or last night? Anyways, if so, here's the new entry:
 http://www.hulver.com/scoop/comments/2004/4/5/55524/44031/93#93

Thanks.


[ Parent ]
My entry by george (3.00 / 0) #89 Wed Apr 14, 2004 at 03:30:15 PM EST
It's basically just a breadth-first search in C. Each card-type is treated as a search level, as opposed to treating each card as a search level. All memory is statically allocated. Before searching, some heuristics are used in an attempt to reduce the number of colors involved in the problem. If I had more time, I'd probably work on better problem-reduction heuristics. It hasn't been tested much.


C code by george (3.00 / 0) #90 Wed Apr 14, 2004 at 03:34:26 PM EST
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <assert.h>

#define POW_21_5 (21 * 21 * 21 * 21 * 21)

#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))

typedef struct {
  int         ncolors;
  int         count[32];
} problem_t;

typedef struct {
  signed char ncards[5];
} state_t;

typedef struct {
  int     nents;
  char    uniqvec[(POW_21_5 + CHAR_BIT - 1) % CHAR_BIT];
  state_t states[POW_21_5];
} statevec_t;

typedef struct {
  int     cnt;
  int     limit[5];
  int     allocation[5];
  int     sumalloc[5];
} searchiter_t;


void SVaddstate(statevec_t *SV, const state_t *s)
{
  int bitvecidx = ((((s->ncards[0] * 21 | s->ncards[1])
                                   * 21 | s->ncards[2])
                                   * 21 | s->ncards[3])
                                   * 21 | s->ncards[4]);

  if (!(SV->uniqvec[bitvecidx/CHAR_BIT] & (1 << bitvecidx%CHAR_BIT)))
  {
    SV->uniqvec[bitvecidx/CHAR_BIT] |= (1 << bitvecidx%CHAR_BIT);
    SV->states[SV->nents++] = *s;
  }
}

void SVinit(statevec_t *SV)
{
  SV->nents = 0;
  memset(SV->uniqvec, 0, sizeof(SV->uniqvec));
}


void initSearchIterator(searchiter_t *SI, state_t *s, int idx, int cnt)
{
  int i;

  SI->cnt = cnt;

  for (i = 0; i < 5; ++i)
  {
    if (idx & (1 << i))
      SI->limit[i] = min(cnt, s->ncards[i]);
    else
      SI->limit[i] = 0;
  }

  for(i = 4; i >= 0; --i)
  {
    SI->allocation[i] = min(cnt, SI->limit[i]);
    cnt -= SI->allocation[i];
  }
  SI->cnt -= cnt;

  SI->sumalloc[0] = SI->allocation[0];
  for (i = 1; i < 5; ++i)
    SI->sumalloc[i] = SI->sumalloc[i-1] + SI->allocation[i];
}


int nextSearchIterator(searchiter_t *SI)
{
  int i;
  int lcvpos;

 retry:

  for (lcvpos = 3; lcvpos >= 0; --lcvpos)
  {
    if (SI->allocation[lcvpos] < SI->limit[lcvpos] &&
        SI->sumalloc[lcvpos] < SI->cnt)
    {
      SI->allocation[lcvpos]++;
      SI->sumalloc[lcvpos]++;
      for (i = lcvpos+1; i < 4; ++i)
      {
        SI->allocation[i] = 0;
        SI->sumalloc[i] = SI->sumalloc[i-1];
      }

      SI->allocation[4] = SI->cnt - SI->sumalloc[3];

      if (SI->allocation[4] <= SI->limit[4])
        return 1;
    }
  }

  for (i = 0; i < 5; ++i)
    if (SI->allocation[i] < SI->limit[i] && SI->sumalloc[i] < SI->cnt)
      goto retry;

  return 0;
}

int bfsSearch(problem_t *P)
{
  int         i, j, idx;
  int         cardIdxBound = (1 << P->ncolors)-1;
  int         nWildcard = P->count[cardIdxBound];
  int         nCards;
  state_t     s;
  statevec_t  SV0, SV1;
  statevec_t *newvec = &SV0, *oldvec = &SV1, *tmpvec;

  SVinit(oldvec);
  SVinit(newvec);

  for(i = 0; i < P->ncolors; ++i)
  {
    idx = (1 << i);

    s.ncards[i] = max(0, 20 - P->count[idx]);
    P->count[idx] = 0;
  }

  SVaddstate(oldvec, &s);

  for (idx = 1, nCards = 0; idx < cardIdxBound; ++idx, nCards += P->count[idx])
    ;

  for (idx = 1;
       nCards -= P->count[idx], (idx < cardIdxBound && oldvec->nents > 0);
       ++idx)
  {
    if (P->count[idx] == 0) continue;

    SVinit(newvec);

    for (i = 0; i < oldvec->nents; ++i)
    {
      int          SImore = 1;
      searchiter_t SI;
      int          togo;

      for (initSearchIterator(&SI, &oldvec->states[i], idx, P->count[idx]);
           SImore;
           SImore = nextSearchIterator(&SI))
      {
        for (j = 0, togo = 0; j < P->ncolors; ++j)
        {
          s.ncards[j] = oldvec->states[i].ncards[j] - SI.allocation[j];
          togo += s.ncards[j];
        }

        /* check if we've found a solution */
        if (togo <= nWildcard)
          return 1;

        /* add to newvec, if it could lead to a solution */
        if (togo <= nWildcard + nCards)
          SVaddstate(newvec, &s);
      }
    }

    tmpvec = oldvec;
    oldvec = newvec;
    newvec = tmpvec;
  }
  return 0;
}

/* good place for a lookup table */
int numBitsOn(int color)
{
  int i, n;
  for(i=0, n=0; i < 5; ++i)
    if (color & (1 << i)) ++n;
  return n;
}

/* simplify a problem by removing a eliminating of colors */
void removeColor(problem_t *P, int color)
{
  problem_t  newP;
  int        oldidx, i, newidx, shift;

  for (i = 0; i < 32; ++i) newP.count[i] = 0;
  newP.ncolors = P->ncolors - numBitsOn(color);

  if (newP.ncolors == 0)
  {
    *P = newP;
    return;
  }

  for (oldidx = 1; oldidx < (1 << P->ncolors); ++oldidx)
  {
    newidx = 0;
    shift = 0;

    for (i = 0; i < P->ncolors; ++i)
    {
      if (color & (1 << i))
        ++shift;
      else
        newidx |= ((oldidx & (1 << i)) >> shift);
    }

    assert(0 <= newidx && newidx < (1 << newP.ncolors));
    if (newidx)
      newP.count[newidx] += P->count[oldidx];
  }
  *P = newP;
}

int heuristicReduceProblem(problem_t *P)
{
  int i, j, nbits;

 reset:

  if (P->ncolors > 0)
  {
    /* We can reduce if we have 20 of a mono-chromatic card, 40 of a
     * di-chromatic, 60 of a tri-chromatic, etc.
     */
    for (i = 1; i < (1 << P->ncolors); ++i)
    {
      nbits = numBitsOn(i);

      if (P->count[i] >= nbits*20)
      {
        removeColor(P, i);
        goto reset;
      }
    }

    /* For each sub-problem, check how many cards we have to use for
     * solving the sub-problem.
     */
    for (i = 1; i < (1 << P->ncolors); ++i)
    {
      /* sub_ ==> not necessarily strict subset of colors
       * int_ ==> intersection, but not subset, of colors
       */
      int cnt, sub_cnt;
      int int_cardtyp[32], int_cardtypcnt = 0;

      cnt = 0;
      sub_cnt = 0;

      for (j = 1; j < (1 << P->ncolors); ++j)
        if ((i & j) != 0 && P->count[j] > 0)
        {
          cnt += P->count[j];

          if ((i | j) == i)
            sub_cnt += P->count[j];
          else
            int_cardtyp[int_cardtypcnt++] = j;
        }

      nbits = numBitsOn(i);

      /* Check if we have enough cards to solve the sub-problem */
      if (cnt < 20 * nbits)
      {
        return 0;
      }

      if (nbits <= 2)
      {
        if (sub_cnt >= 20 * nbits)
        {
          removeColor(P, i);
          goto reset;
        }

        if (nbits == 1)
        {
          /* Check if we have exactly enough cards to solve a
           * mono-chromatic sub-problem
           */
          if (cnt == 20)
          {
            for (j = 0; j < int_cardtypcnt; ++j)
              P->count[int_cardtyp[j]] = 0;
            removeColor(P, i);
            goto reset;
          }

          /* If we don't have enough cards for a mono-chromatic
           * sub-problem, and there is a single card type w/
           * intersecting colors then we can reduce the problem.
           */
          if (int_cardtypcnt == 1)
          {
            P->count[int_cardtyp[0]] -= (20 - sub_cnt);
            removeColor(P, i);
            goto reset;
          }
        }
      }
    }
  }

  return 1;
}

void readGame(problem_t *P)
{
  int  i;
  char s[81], *ch;

  P->ncolors = 5;
  for (i = 0; i < 32; ++i)
    P->count[i] = 0;

  while (fgets(s, sizeof(s), stdin))
  {
    i = 0;
    for (ch = s; *ch; ++ch)
      if ('0' <= *ch && *ch <= '4')
        i |= (1 << (*ch - '0'));

    if (i > 0)
      P->count[i]++;
  }
}

int main(int argc, char *argv[])
{
  problem_t P;

  readGame(&P);

  if (heuristicReduceProblem(&P) &&
      (P.ncolors == 0 || bfsSearch(&P)))
  {
    printf("legal\n");
  }
  else
  {
    printf("illegal\n");
  }

  return 0;
}


[ Parent ]
oops - a bug by george (3.00 / 0) #125 Wed Apr 28, 2004 at 05:04:32 AM EST
There is a bad bug in my code that could cause wrong results.
char uniqvec[(POW_21_5 + CHAR_BIT - 1) % CHAR_BIT];
should, of course, read:
char uniqvec[(POW_21_5 + CHAR_BIT - 1) / CHAR_BIT];

Also, fyi, the function bfsSearch() needs about 40M of stack space. To run with a small stack, statevec_t SV0 and SV1 can be turned into globals.



[ Parent ]
Another approach by the (3.00 / 0) #91 Wed Apr 14, 2004 at 03:45:47 PM EST
I ain't gonna have time...so below is a description of what I was working on.

--
The Definite Article
This can be converted to a coin echange problem by the (3.00 / 0) #92 Wed Apr 14, 2004 at 03:57:48 PM EST
Instead of cards consider coins. Like cards, the coins have colors on them in just the same way. However there are two types of coin, gold and silver, each that can have up to 5 colors on them. Additionally there are 5 chips, each of one of the 5 colors.

The idea is this: initially you are given a bunch of silver coins and 20 chips of each color. You have to use the current exchange rates to spend your chips. The exchange rates look something like this:

(red chip) + (silver with red and blue) can be exchanged for (gold with red and blue)
(blue chip) + (silver with red and blue) can be exchanged for (gold with red and blue)
.   .    .

Well an algorithm for eliminating your chips and converting them to gold coins is well known. You basically need to convert everything to polynomials, form a Groebner basis, and reduce. There's a chapter in here on how to do it. Except that I've implemented Groebner basis extraction in C++.

The cool thing about this approach is that the Groebner basis represents a finite set of rewrite rules. Bascially it's a new set of exchange rules. But unlike the original set of rules, that are tricky to use in the right order (i.e. that's the problem we have to solve), this new set of rules can be used in any order you like and it's guaranteed to eventually give a solution. What's more, this solution is very quick to find because this reduction is trivial to implement and typically just requires scanning through the new exchange rules trying everything in turn a handful of times.

But dammit! There's a bug in my code and I ain't gonna fix it by 10. I could cheat and use Mathematica's built in Groebner basis functions but it's so much cooler in C++ where it's implementation is quite elegant.

Hmmm...I think I know what my bug is, I also need two types of chip otherwise the algorithm might 'borrow' chips (which it pays back) in order to get a solution. Hmmm...no time...damn...

--
The Definite Article

[ Parent ]
New K entry by jjayson (3.00 / 0) #93 Wed Apr 14, 2004 at 04:32:06 PM EST
Try this. Again save as "tragic.k" or whatever, and run with "k tragic input". I actually had a hard time trying to wrap my head about figuring out if the algorithm is correct. I still am not sure if this is perfectly correct, but I ran it agaist a few thousand tests and wasn't able to get a false negative (and it shouldn't give off false positives).
n:-1+(+10_vs{x@<x}10_sv'1+{0$(0,&x=" ")_ x}'0:_i 0)_dv'0
p:{@[x; y@*&(x<20)y; 1+]}/[&5;n]
`0::[(5#20)~20&p; "legal\n"; "illegal\n"]
\\


Some decks to try by tmoertel (6.00 / 1) #111 Tue Apr 20, 2004 at 10:15:57 AM EST
Here are some bash scripts to generate decks with interesting properties. All decks are legal.

deck-tgm-000.sh

#!/bin/bash

# trivial monochromatic deck
for c in 0 1 2 3 4; do yes $c | head -20; done

deck-tgm-001.sh

#!/bin/bash

yes 0      | head -19
yes 0 1    | head -1
yes 1      | head -19
yes 1 2    | head -1
yes 1 3    | head -1
yes 3 4    | head -1
yes 2      | head -19
yes 3      | head -19
yes 4      | head -20

deck-tgm-002.sh

#!/bin/bash

yes 0      | head -19
yes 0 1    | head -19
yes 1      | head -1
yes 1 2    | head -20
yes 1 3    | head -20
yes 3 4    | head -20
yes 4      | head -1

deck-tgm-003.sh

#!/bin/bash

yes 0 1 | head -20
yes 0 2 | head -40
yes 0 3 | head -20
yes 0 4 | head -20

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

Also try the reverse decks by tmoertel (3.00 / 0) #120 Wed Apr 21, 2004 at 09:26:13 AM EST
You should also try those decks in reverse order. Sometimes, it makes a difference. The unix tac(1) program makes this easy:
$ ./deck-tgm-002.sh | tac

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Also try the color-traded decks by tmoertel (3.00 / 0) #121 Wed Apr 21, 2004 at 09:45:11 AM EST
You should also try the color-traded versions of the decks where each color c in the input deck is mapped to 4 - c in the color-traded output deck.

The following Perl one-liner will color trade a deck.

perl -pale'$_="@{[sort map{4-$_}@F]}"'
The stand-alone version color-trade.pl:
#!/usr/bin/perl -pal
$_ = "@{[sort map {4-$_} @F]}"
Example usage:
$ ./deck-tgm-002.sh | ./color-trade.pl

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

[ Parent ]
Any info on when the results come out? [nt] by edwin (3.00 / 0) #122 Thu Apr 22, 2004 at 05:13:26 AM EST


I'll get to them this weekend by jacob (5.00 / 1) #123 Thu Apr 22, 2004 at 05:50:13 AM EST
Too busy to do it before then.

--

[ Parent ]
Dude! It's been a month! by edwin (3.00 / 0) #128 Sat May 22, 2004 at 02:10:46 AM EST
Unless the results are out and I missed them?

[ Parent ]
You missed nothing by codemonkey uk (3.00 / 0) #129 Sat May 22, 2004 at 03:34:17 AM EST
I've been watching this and Jacob's diary like a hawk.

--- Thad ---
Almost as Smart As you.
[ Parent ]
I know by jacob (6.00 / 1) #130 Sat May 22, 2004 at 04:35:04 AM EST
I am bad. I basically picked the worst possible time to have to judge PFCs, and I just haven't had time. But I finally have a lull this weekend.

Hoping to beat the archiving deadline ...

--

[ Parent ]
No results yet by jacob (6.00 / 2) #124 Mon Apr 26, 2004 at 03:07:13 AM EST
Sorry about the wait, folks. The problem is just that made exceptionally poor scheduling decisions and had preparations for an important talk, a major class project, a move, and a software release all to do last week and this one. I'm trying to find time for the PFC stuff, though, really, honestly, and I haven't forgotten about it!

--

Beat the archiving deadline! by jacob (3.00 / 0) #131 Fri Jun 18, 2004 at 10:56:46 AM EST
Results.

--

Thank god by Evil Cloaked User (3.00 / 0) #132 Fri Jun 18, 2004 at 11:14:29 AM EST
I can finally take this off the hotlist. (Hotlist is not in the spell-check dictionary BTW (but BTW is, BTW (And also, can we get spellcheck to include parenthesis checks? (And maybe even the word "Spellcheck" while we're at it?)))).

[ Parent ]
PROGRAMMING FUN CHALLENGE: TRAGIC | 133 comments (133 topical, 0 hidden) | Trackback