the second should have been pfc_tragic_input_2.txt.

--

[ Parent ]

Yeah, I wrote this up half a week ago and forgot to change the deadline. I'll post an extension :)

--

[ Parent ]

Suck it
[ Parent ]

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 ]

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 ]

#!/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 ]

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 ]

/* 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 ]

--

[ Parent ]

Makes code posting an entirely easier process.


--
Still, I think most of the problem is just a mental hurdle to overcome, - Cloaked User
[ Parent ]

Update. Fixed a bug. Replaced the file.

--- Thad ---
Growing a mustache for charity.
[ Parent ]

--

[ Parent ]

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

Rock Hard Abs are just a sw-sw-swivel away!
[ Parent ]

// 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 ]

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 ]

#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 ]

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)²e. This is the polynomial of the deck - call it f(a,b,c,d,e).

The deck is legal iff the coefficient of a²⁰b²⁰...e²⁰ 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 ]

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 ]

#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 ]

[ Parent ]

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 ]

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

{-
   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 ]

--- Thad ---
Growing a mustache for charity.
[ Parent ]

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 ]

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 ]

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 ]

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 ]

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 ]

Code is in here. It is my first proper Python program; critique the style if you're into that sort of thing.

[ Parent ]

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 c ⋅ x while Ax ≤ b and x_i ≥ 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 x_i (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 c ⋅ x 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 ]

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 T_ij 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(T_ij) >= 20 for each color j
Sum(T_ij) <= (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 ]

\ 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 ]

I apologize for posting the algorithm in the head post.
---
[ucblockhead is] useless and subhuman
[ Parent ]

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 ]

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 ]

My crappy Forth implementation takes 40 milliseconds and probably takes less than 40k RAM...
---
[ucblockhead is] useless and subhuman
[ Parent ]

Can you actually read that ?!?!

[ Parent ]

You posted the code in a top level comment and gave away the algorithm.

[ Parent ]

--

[ Parent ]

#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 ]

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 ]

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 ]

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 ]

Too busy to do it before then.

--

[ Parent ]

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


--
Still, I think most of the problem is just a mental hurdle to overcome, - Cloaked User
[ Parent ]