<main.cc>=

#include <iostream>
#include "tableau.h"
#include "read.h"
#include "tableau-keeper.h"

// Deja vu, c++ style.

   static bool search(const tableau &, const deck &, tableau &);

int 
main() {

  std::string emsg;
  const deck hand = read_deck(std::cin, emsg);
  if (!emsg.empty()) {
    std::cerr << emsg;
    return EXIT_FAILURE;
    }

  const tableau_piles piles = read_tableau_piles(std::cin, emsg);
  if (!emsg.empty()) {
    std::cerr << emsg;
    return EXIT_FAILURE;
    }

  const tableau t(piles);
  tableau better = t;
  const bool sv = search(t, hand, better);

  if (!sv) {
    std::cerr << "Input tableau doesn't represent a legal game.\n";
    return EXIT_FAILURE;
    }
  if (better < t) {
    std::cout << better;
    return EXIT_FAILURE;
    }
  }


#define put_tableau(_t) \
  do { tableau _newt(_t); \
       if (!bettered or target.compatible(_newt)) \
         tableau_keeper::put(_newt); } while (false);

static bool
search(const tableau & target, const deck & hand, tableau & better) {

  // Return true iff a tableau equal to the target tableau results from deals 
  // from the given hand.  Store into the given tableau reference a tableau 
  // derived from the given deal that has fewer piles than does the target 
  // tableau.

  tableau t(hand);
  while (!t.hand_empty())
    t = t.deal_card();
  tableau_keeper::put(t);

  bool found = false;
  bool bettered = target.pile_cnt() == 1;

  better = target;

  do {
    t = tableau_keeper::get();
    
    found = found or (t == target);
    if (!bettered and (t < better)) {
      better = t;
      bettered = better < target;
      }

    if (found and bettered) 
      break;
    
    for (unsigned i = 1; i < t.pile_cnt(); i++) 
      for (unsigned j = 1; j <= 2; j++)
        if ((j <= i) and t.piles_match(i - j, i)) {
          put_tableau(t.move_card(i - j, i));
          if (t.pile_size(i) > 1)
            put_tableau(t.move_pile(i - j, i));
          }
    }
  while (!tableau_keeper::empty());

  return found;
  }

Defines main.cc (links are to index).

This code is written to a file (or else not used).

<tableau member functions>=

bool tableau::
compatible(const tableau & t) const {
  
  // Return true iff the given tableau is compatible with this tableau.

  if (pile_cnt() > t.pile_cnt())
    return false;

  piles_citer i = piles.begin();
  piles_citer j = t.piles.begin();

  while ((i != piles.end()) and (j != t.piles.end()))
    if (!(i->contains(*j)))
      return false;
    else if ((i++)->size() > (j++)->size())
      break;

  for (i = piles.begin(); i != piles.end(); i++)
    if (!(t.compatible(i->bottom_card())))
      return false;

  return true;
  }


bool tableau::
compatible(const card & c) const {
  
  // Return true iff this tableau is compatible with the given card.

  for (piles_citer i = piles.begin(); i != piles.end(); i++)
    if (c == i->bottom_card())
      return true;

  return false;
  }

Defines compatible (links are to index).

Used below; next definition.

*

<tableau data structures>=

typedef std::list<pile>       Piles;
typedef Piles::iterator       piles_iter;
typedef Piles::const_iterator piles_citer;

Piles piles;

Defines Piles, piles, piles_citer, piles_iter (links are to index).

Used below.

<tableau member functions>+=

tableau::piles_iter tableau::
pitr(unsigned i) {

  // Return an interator to the ith pile.

  assert(i < piles.size());

  piles_iter pci = piles.begin();
  std::advance(pci, i);

  return pci;
  }


tableau::piles_citer tableau::
pitr(unsigned i) const {

  // Return an interator to the ith pile.

  assert(i < piles.size());

  piles_citer pci = piles.begin();
  std::advance(pci, i);

  return pci;
  }

Defines pitr (links are to index).

Used below; previous definition.

*

<tableau.h>=

#ifndef _tableau_h_defined_
#define _tableau_h_defined_

#include <list>
#include <ostream>
#include "deck.h"
#include "pile.h"
#include "read.h"

struct tableau {

  // Return true iff the given tableau is compatible with this one.

     bool compatible(const tableau &) const;

  // Return a tableau that's identical to this tableau except that the new
  // tableau has a new pile dealt from the hand.

     tableau deal_card(void) const;

  // Return true iff the hand has no more cards to deal.

     bool hand_empty(void) const { return hand.empty(); }

  // Create a new tableau from this tableau by moving the top card of the right
  // pile to the top of the left pile; return the new tableau.

     tableau move_card(unsigned, unsigned) const;

  // Create a new tableau from this tableau by moving the right pile on top of
  // the left pile; return the new tableau.

     tableau move_pile(unsigned, unsigned) const;

  // Return true iff this tableau is identical to the given tableau.

     bool operator == (const tableau &) const;

  // Return the number of piles in this tableau.

     unsigned pile_cnt(void) const { return piles.size(); }

  // Return the number of cards in the given pile.

     unsigned pile_size(unsigned i) const;

  // Return true iff the (top cards of the) two given piles match.

     bool piles_match(unsigned, unsigned) const;

  // Create an empty tableau using the given initial hand.

     tableau(const deck &);

  // Create a tableau having the given piles and an empty hand.

     tableau(const tableau_piles &);

  deck hand;

  <tableau data structures>

  piles_citer pitr(unsigned) const;
  piles_iter pitr(unsigned);

  bool compatible(const card &) const;
  
  };


// Return true iff the first tableau has fewer piles than does the second
// tableau. 

   extern bool operator < (const tableau &, const tableau &);


// Write the given tableau to the given output stream.

   extern std::ostream & operator << (std::ostream &, const tableau &);

#endif

Defines tableau.h (links are to index).

This code is written to a file (or else not used).

*

<tableau.cc>=

#include <cassert>
#include <iostream>
#include "tableau.h"


tableau tableau::
deal_card(void) const {
  
  // Return a copy of this tableau, but with a new card dealt from the hand.

  tableau new_t = *this;

  const card c = new_t.hand.deal();
  new_t.piles.push_back(pile(c));

  return new_t;
  }


tableau tableau::
move_card(unsigned l, unsigned r) const {
  
  // Return a copy of this tableau, but with the top card of the rth pile
  // moved on top of the lth pile.

  tableau t = *this;

  piles_iter rpile = t.pitr(r);
  
  t.pitr(l)->stack(rpile->pop_card());
  if (rpile->empty())
    t.piles.erase(rpile);

  return t;
  }


tableau tableau::
move_pile(unsigned l, unsigned r) const {
  
  // Return a copy of this tableau, but with the rth pile moved on top of the 
  // lth pile.

  assert(piles_match(l, r));

  tableau t = *this;

  piles_iter rpile = t.pitr(r);
  
  t.pitr(l)->stack(*rpile);
  t.piles.erase(rpile);

  return t;
  }


bool
operator < (const tableau & t1, const tableau & t2) {

  // Return true iff tableau t1 is less than tableau t2.

  return t1.pile_cnt() < t2.pile_cnt();
  }


std::ostream & 
operator << (std::ostream & os, const tableau & t) {

  // Write the given tableau to the given output stream.

  for (tableau::piles_citer i = t.piles.begin(); i != t.piles.end(); i++)
    os << *i << '\n';

  return os;
  }


bool tableau::
operator == (const tableau & t) const {

  // Return true iff the given tableau is equal to this tableau.

  if (pile_cnt() != t.pile_cnt())
    return false;

  piles_citer 
    i = piles.begin(),
    j = t.piles.begin();

  while (i != piles.end())
    if (*i++ != *j++)
      return false;

  return true;
  }


unsigned tableau::
pile_size(unsigned i) const { 

  // Return the number of cards in the ith pile.

  return pitr(i)->size();
  }


<tableau member functions>

bool tableau::
piles_match(unsigned lpno, unsigned rpno) const {

  // Return true iff the given left pile matches the given right pile.

  assert((lpno < rpno) and (rpno < pile_cnt()));
  return pitr(lpno)->top_card().match(pitr(rpno)->top_card());
  }


tableau::
tableau(const deck & hand) : hand(hand) {

  // Create an empty tableau with the given hand.

  }


tableau::
tableau(const std::vector<pile> & p) {

  // Create a tableau with an emtpy hand from the given vector of piles.

  piles.assign(p.begin(), p.end());
  }

Defines tableau.cc (links are to index).

This code is written to a file (or else not used).

*

<tableau keeper data structures>=

typedef std::list<tableau> tlist;
typedef std::vector<tlist> tlistvec;
typedef tlistvec::iterator tlv_iter;

static tlistvec tableaus(52);

Defines tableaus, tlist, tlistvec, tlv_iter (links are to index).

Used below; next definition.

<tableau keeper data structures>+=

static tlist old_tableaus;

Defines old_tableaus (links are to index).

Used below; previous definition.

*

<tableau keeper functions>=

void put(const tableau & t) {

  // Put the given tableau in the tableau list if it hasn't been put into 
  // the list before.

  attempts++;
  const tlist::iterator e = old_tableaus.end();
  if (std::find(old_tableaus.begin(), e, t) == e) {
    inserts++;
    old_tableaus.push_back(t);

    const unsigned i = t.pile_cnt();
    assert(i > 0);
    tableaus[i - 1].push_back(t);
    }
  }

Defines put (links are to index).

Used below.

<tableau-keeper.h>=

#ifndef _tableau_keeper_h_defined_
#define _tableau_keeper_h_defined_

#include "tableau.h"

namespace tableau_keeper {

  bool empty(void);

  tableau get(void);

  void put(const tableau &);

  void stats(void);
  }

#endif

Defines tableau-keeper.h (links are to index).

This code is written to a file (or else not used).

*

<tableau-keeper.cc>=

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include "tableau-keeper.h"


<tableau keeper data structures>


// The number of unique tableaus added to the list (inserts) vs. 
// the total number of tableaus added (attempts).

   static unsigned
     inserts = 0,
     attempts = 0;


// Deja vu, c++ style.

   static bool nonempty_tlist(const tlist);


static tlv_iter
find_nonempty(void) {

  // Return a iterator to a non-empty tlist or to the end of the tableau list 
  // if there's no such tlist.

  return std::find_if(tableaus.begin(), tableaus.end(), nonempty_tlist);
  }


static bool
nonempty_tlist(const tlist tl) {

  // Return true iff the given tlist is empty.

  return !tl.empty();
  }


namespace tableau_keeper {


  bool empty(void) {

    // Return true iff the tableau list is empty.

    return find_nonempty() == tableaus.end();
    }


  tableau get(void) {

    // Return the next tableau from the list, which must not be empty.

    const tlv_iter i = find_nonempty();
    assert(i != tableaus.end());

    const tableau t = i->front();
    i->pop_front();

    return t;
    }

  <tableau keeper functions>

  void stats(void) {

    // Print the attempted and inserted statistics.

    std::cerr << "attempts = " << attempts
              << ", inserts = " << inserts << ".\n";
    }
  }

Defines tableau-keeper.cc (links are to index).

This code is written to a file (or else not used).

*

<read.h>=

#ifndef _read_h_defined_
#define _read_h_defined_

#include <istream>
#include <string>
#include "pile.h"
#include "deck.h"

typedef std::vector<pile> tableau_piles;

// Read from the given input stream the piles in a tableau; returning the
// tableau read.  If the value in the given string is empty after the call, no
// errors occured during the read; otherwsie, the given string contains an 
// error message.

   extern tableau_piles read_tableau_piles(std::istream &, std::string &);

// Read from the given input stream a deck of cards, returning the deck read.  
// If the value in the given string is empty after the call, no errors occured 
// during the read; otherwsie, the given string contains an error message.

    extern deck read_deck(std::istream &, std::string &);

#endif

Defines read.h (links are to index).

This code is written to a file (or else not used).

*

<read.cc>=

#include "read.h"
#include "str-utils.h"

deck 
read_deck(std::istream & is, std::string & emsg) {

  // Return the deck read from the given input stream, returning errors
  // in the given string reference.

  std::string ln;

  if (!str_utils::read_next_nonblank_line(is, ln)) {
    emsg = "Unexpected eof while reading deck.\n";
    return deck();
    }
  else
    return deck(ln, emsg);
  }


tableau_piles
read_tableau_piles(std::istream & is, std::string & emsg) {

  // Return the tableau piles read from the given input stream, returning 
  // errors in the given string reference.

  tableau_piles piles;
  std::string ln;

  while (str_utils::read_next_nonblank_line(is, ln)) {
    piles.push_back(pile(ln, emsg));
    if (!emsg.empty())
      return piles;
    }

  if (piles.empty())
    emsg = "No tableau piles input.\n";
  else if (piles.size() > 52)
    emsg = "More than 52 tableau piles input.\n";
    
  return piles;
  }

Defines read.cc (links are to index).

This code is written to a file (or else not used).

*

<card.h>=

#ifndef _card_h_defined_
#define _card_h_defined_

#include <cassert>
#include <ostream>

struct card {

  typedef unsigned char rank;
  typedef unsigned char suit;

  rank r;
  suit s;

  // Create a card with the given suit and rank.

     card(rank r, suit s) : r(r), s(s) { 
       assert((r < 13) and (s < 4));
       }

  // Return true iff this card matches the given card.

      bool match(const card & c) const {
        return (r == c.r) or (s == c.s);
        }

  // Return true iff this card is equal to the given card.

     bool operator == (const card & c) const {
       return (r == c.r) and (s == c.s);
       }

  // Return true iff this card is less than the given card.

     bool operator < (const card & c) const {
       return (r < c.r) or ((r == c.r) and (s < c.s));
       }
  };

extern std::ostream & operator << (std::ostream &, const card &);

#endif

Defines card.h (links are to index).

This code is written to a file (or else not used).

*

<card.cc>=

#include "card.h"


std::ostream & 
operator << (std::ostream & os, const card & c) {

  // Write the given card into the given output stream.

  const char suits[] = { 'c', 'd', 'h', 's' };
  const char ranks[] = 
    { '1', '2', '3', '4', '5', '6', '7', '8', '9', 't', 'j', 'q', 'k' };
  
  assert((c.r < 13) and (c.s < 4));

  return os << ranks[c.r] << suits[c.s];
  }

Defines card.cc (links are to index).

This code is written to a file (or else not used).

*

<card member functions>=

void pile::
stack(const pile & p) {

  // Put the given pile on top of this pile.

  cards.insert(cards.end(), p.cards.begin(), p.cards.end());
  }


void pile::
stack(const card & c) {

  // Put the given card on top of this card.

  cards.push_back(c);
  }


card pile::
pop_card(void) {

  // Remove and return the top card of this pile, which must not be empty.

  assert(!empty());
  const card c = cards.back();
  cards.pop_back();
  return c;
  }

Defines pop_card, stack (links are to index).

Used below; next definition.

*

<card member functions>+=

const card & pile::
bottom_card(void) const {

  // Return a reference to the card on the bottom of this pile, which must not 
  // be empty.

  assert(!empty());
  return cards.front();
  }

const card & pile::
top_card(void) const {

  // Return a reference to the top card in this pile, which should not be 
  // empty.

  assert(!empty());
  return cards.back();
  }

Defines bottom_card, top_card (links are to index).

Used below; previous definition.

<pile.h>=

#ifndef _pile_h_defined_
#define _pile_h_defined_

#include <string>
#include <vector>
#include "card.h"

struct pile {

  // Return a reference to the bottom card of this pile.

     const card & bottom_card(void) const;

  // Return true iif the this pile contains all the cards in the given pile.

     bool contains(const pile &) const;

  // Return true iff this pile's empty.

     bool empty() const { return cards.empty(); }

  // Return true iff the given pile is different from this pile.

     bool operator != (const pile &) const;

  // Create an empty pile.

     pile() { };

  // Create a pile from the cards stored in the first string; the second string
  // contains any error messages.

     pile(const std::string &, std::string &);

  // Create a pile from the given card.

     pile(const card &);

  // Return the number of cards in this pile.

     unsigned size(void) const { return cards.size(); }

  // Stack the given card on top of this pile.

     void stack(const card &);

  // Stack the given pile on top of this pile.

     void stack(const pile &);

  // Return a reference to the top card of this pile.

     const card & top_card(void) const;

  // Write the given pile to the given output stream.

     friend std::ostream & operator << (std::ostream &, const pile &);

  // Pop and return this pile's top card; die with an error if the pile's
  // empty. 

     card pop_card(void);

  private:

     // The rightmost card in the vector is the top card.

        typedef std::vector<card>    Pile;
        typedef Pile::iterator       pile_iter;
        typedef Pile::const_iterator pile_citer;

     Pile cards;

     void read_cards(const std::string &, std::string &);
  };


extern std::ostream & operator << (std::ostream &, const pile &);

#endif

Defines pile.h (links are to index).

This code is written to a file (or else not used).

*

<pile.cc>=

#include <algorithm>
#include <iostream>
#include <sstream>
#include "pile.h"


// Deja vu c++ style.

   static bool suitify(char, card::suit &);


<card member functions>

bool pile::
contains(const pile & p) const {

  // Return true iff this pile contains all the cards in the given pile.

  for (pile_citer i = p.cards.begin(); i != p.cards.end(); i++)
    if (std::find(cards.begin(), cards.end(), *i) == cards.end())
      return false;

  return true;
  }


static bool
find_index(const char * chars, char c, unsigned & i) {

  // Return true iff the given character appears in the given character array. 
  // If it does, set the int reference to the index of the character in the 
  // array.

  const std::string chrs(chars);
  i = chrs.find(std::tolower(c));

  return i != std::string::npos;
  }


bool pile::
operator != (const pile & p) const {

  // Return true iff the given pile is equal to this pile.

  return cards != p.cards;
  }


std::ostream & 
operator << (std::ostream & os, const pile & p) {

  // Write the given pile to the given output stream.

  pile::Pile::const_reverse_iterator i;
  for (i = p.cards.rbegin(); i != p.cards.rend(); i++)
    os << *i;

  return os;
  }


pile::
pile(const std::string & deal, std::string & emsg) { 

  // Create a pile from the given string of cards.  Return any error messages 
  // in the given string reference.

  read_cards(deal, emsg);
  }


pile::
pile(const card & c) {
  
  // Create a pile containing the given card.

  cards.push_back(c);
  }


static bool
rankify(char c, card::rank & r) {

  // Translate the given rank character to the associated rank value; return
  // true if the character was translated.

  unsigned i;

  if (!find_index("123456789tjqk", c, i))
    return false;
  else
    r = i;

  return true;
  }


static bool
read_card(
  std::istream & is, card::rank & r, card::suit & s, std::string & emsg) {
  
  // Read the next card from the given input stream.

  char c1, c2;

  if (!(is >> c1) || !(is >> c2))
    return false;

  if (rankify(c1, r) and suitify(c2, s))
    return true;

  if (rankify(c2, r) and suitify(c1, s))
    return true;

  emsg = "Input error during card read.\n";

  return false;
  }


void pile::
read_cards(const std::string & hand, std::string & emsg) {

  // Read cards from the given string into this pile; return any errors in the 
  // given string reference.

  std::istringstream iss(hand);
  card::rank r;
  card::suit s;

  while (read_card(iss, r, s, emsg) and emsg.empty())
    cards.push_back(card(r, s));

  if (emsg.empty()) {
    Pile cds(cards);
    const pile_iter e = cds.end();
    std::sort(cds.begin(), e);
    const pile_iter d = std::adjacent_find(cds.begin(), e);
    if (d != e) {
      std::ostringstream oss;
      oss << "The deck contains duplicates of card " << *d << ".\n";
      emsg = oss.str();
      }
    }
  }


static bool
suitify(char c, card::suit & s) {

  // Translate the given suit character to the associated suit value; return
  // true if the character was translated.

  unsigned i;

  if (!find_index("cdhs", c, i))
    return false;
  else
    s = i;

  return true;
  }

Defines pile.cc (links are to index).

This code is written to a file (or else not used).

<deck.h>=

#ifndef _deck_h_defined_
#define _deck_h_defined_

#include "card.h"
#include "pile.h"

class deck { 

  public:

    // Create an empty deck of cards.

       deck();

    // Create a deck of cards from the given string.  If the return string is
    // empty, no error occured; otherwise the return string contains an error.

       deck(const std::string &, std::string &);

    // Return true iff this deck has no more cards to deal.

       bool empty(void) const;

    // Deal and return a card from this deck; die with an error if the deck has
    // no more cards to deal.

       card deal(void);

  private:

    pile cards;
  };

#endif

Defines deck.h (links are to index).

This code is written to a file (or else not used).

*

<deck.cc>=

#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include "deck.h"
#include "pile.h"


deck::deck() { 

  // Create an empty deck of cards.
  }


deck::
deck(const std::string & deal, std::string & emsg) 
  : cards(deal, emsg) {

  // Create a deck from the cards in the given string, returning errors in the 
  // given string reference.

  if (emsg.empty() && (cards.size() != 52)) {
    std::ostringstream oss;
    oss << "The deck should have 52 cards, but actually has " 
        << cards.size() << ".\n";
    emsg = oss.str();
    }
  }


card deck::
deal(void) {

  // Return the next card in the deck, which must not be empty.

  assert(!cards.empty());
  return cards.pop_card();
  }


bool deck::
empty(void) const {

  // Return true iff this deck has no more cards to deal.

  return cards.empty();
  }

Defines deck.cc (links are to index).

This code is written to a file (or else not used).

*