Assignment 3 Code Review

24 March 2003 - CS 509

Assignment 3 Code Review

• Design

• Analysis

• Test Cases

• Statistics

• Coding problems

Design

• This problem has two parts:

  • Is the given tableau legal?

  • Is the given tableau a winner?

• What to wish for.

  • For part 1, a procedure that returns all possible games.

  • For part 2, a procedure that returns the best possible game from a given hand.

  • Note that the part 1 wish also takes care of part 2.

• Ok, so *poof*

  std::vector<tableau> 
  play_all_games(const deck & hand)
  

The Solution

candidates = play_all_games(hand);
legal = smaller = false;

for (i = 0; i < candidates.size(); i++)
  if target == candidates[i]
    legal = true
  else if candidates[i] < target
    smaller = true  

• We also need equality and less relations between tableaus.

  • These require no further wishes.

• What about play_all_games()?

  • Well, If I had some way of getting the next possible tableaus from a given tableau, it would be easy.

• O.k., *poof*

  std::vector<tableau> 
  next_possible_games(tableau)
  

Playing All The Games

tvec play_all_games(hand)

  tvec candidates, final
  candidates.push_back(tableau(hand))

  while !candidates.empty()
    tableau t = candidates.back()
    candidates.pop_back()
    tvec new_tabs = possible_next_tabs(t)
    if (new_tabs.empty())
      final.push_back(t)
    else
      candidates.insert(
	candidates.end(),
	new_tabs.begin(), new_tabs.end())

  return final

• Everything left is mere detail.

  • next_possible_tableaus() should not require further wishes.

  • There are some bad assumptions in this design.

• Wow, that was quick. I wonder what's on TV?

But, Wait a Minute

• You know, there's maybe a lot of possible accordion games.

• How many? Let's do an estimate.

  • play_all_games() pops an old game and pushes new games.

  • Let's say it pushes t new games for each old game popped.
  

  • If each tableau leads to t new tableaus on each move, and there are n moves total, then there will be tⁿ tableaus.

• Oops, that's O(tⁿ) - exponential - behavior. Not good.

Can It Really Be That Bad?

• The solution's easy enough to implement - let's build and measure.

  $ time echo ac ad ah as | acheck     
  final.size() = 79.
      0.01s real
  
  $ time echo ac ad ah as 2c | acheck
  final.size() = 356.
      0.04s real
  
  $ time echo ac ad ah as 2c 2d | acheck
  final.size() = 5764.
      0.56s real
  
  $ time echo ac ad ah as 2c 2d 2h | acheck
  final.size() = 905187.
     76.75s real
  
  $ time echo ac ad ah as 2c 2d 2h 2s | acheck
  Abort 
   2982.37s real
  

• Any way you slice it, it looks bad.

Now What?

• The problem is solved, but not in a practical way.

  • You always lose against exponential behavior.

• There's two problems with our solution.

  • It grows too fast.

  • The search through the candidates is unordered.

  • Oh, and a third problem: there's no need to generate all the candidates before checking any of them.

• The solutions to these problems are:

  • Figure out ways to prune the candidates.

  • Figure out helpful ways to order the candidates.

    • More likely solutions first.

  • Combine generating and checking code to eliminate the intermediate data structure.

The Original Problem Reconsidered

• The original problem verified a legal and winning tableau.

• A winning tableau has the smallest number of piles possible.

  • Searching for a smaller number of piles implies an ascending order.

  • There is no useful pruning criterion.

    • Any tableau could lead to a smaller tableau.

    • But the search stops at the first smaller tableau.

• A legal tableau appears in the generated tableaus.

  • An exhaustive search, with no helpful order.

  • A pruning criteria based on compatible tableaus.

• This analysis suggests implementing each part separately.

  • The simple solution implementation is a big help here.

Finding A Smaller Tableau

static bool find_smaller(
  tableau tgt, deck hand, tableau & smlr)

  tvec candidates
  candidates.push_back(tableau(hand))

  do
    smlr = candidates.back()
    if smlr < tgt
      return true

    candidates.pop_back()

    tvec new_tabs = 
      possible_next_tableaus(smlr)
    candidates.insert(
      candidates.end(),
      new_tabs.begin(), new_tabs.end())
    std::sort(
      candidates.rbegin(), candidates.rend())
  while !candidates.empty()

  return false

Does Sorting Help?

• Always test your assumptions.

• Run the same input through both routines.

  • Count the number of tableaus searched before a finding a smaller one.
  

• Sorting appears to help, except when it doesn't (which is occasionally).

  • Warning: there's an enormous deception going on here. What is it?

  • Hint: also always make sure you're not paying too much for your benefits.

Target Tableau Search

• Not every candidate tableau can lead to the target tableau.

  • A tableau with all cards on the table and three piles can't lead to a tableau with all cards on the table and four piles. (why?)

• With for a predicate that returns true if and only if tableau t1 can lead to tableau t2.

  • *poof*

    bool tableau::
    compatible(const tableau & t) const
    

    returns true if and only if the given tableau leads to this tableau.

Compatible Tableaus

• Based on pile counts, it makes sense to wish for a compatible-tableau predicate.

• Does compatibility involve anything else?

  • The key is that legal moves always move cards to the left, never to the right (once all cards are on the table).

• Every card in a candidate tableau's ith pile must appear somewhere in the target tableau's first through ith pile.

  t1:	As 2s 3s	t2:	Ah As 2s 3s
  	Ah 2h		2h

  • t1 is compatible with t2; t2 is not compatible with t1.

• The set of bottom cards in the target tableau must be a subset of the set of bottom cards in the candidate tableau.

  t1:	As 2s 3s	t2:	As 2s 3s
  	Ah 2h		3c Ah 2h
  	3c

  • t1 is compatible with t2; t2 is not compatible with t1.

Finding A Target Tableau

bool find_target(tableau target, deck hand)

  tableau t
  tvec candidates
  candidates.push_back(tableau(hand))

  do
    do
      t = candidates.back()
      candidates.pop_back()
    while !target.compatible(t) and 
          !candidates.empty()

    if t == target
      return true
    if !target.compatible(t)
      return false

    const tvec new_tabs = 
      possible_next_tableaus(t)
    candidates.insert(
      candidates.end(),
      new_tabs.begin(), new_tabs.end())
  while !candidates.empty()

  return false

Does Compatibility Pruning Help?

• Um, no.

  • After 15 minutes, acheck was still working on an eight-card deck.

• Output the first million candidate tableaus.

  • There's got to be some redundancy; it's only eight cards.

• Sort and count the number of duplicates in the million lines.

  $ sort < o | uniq -c | sort -rn > o2
  
  $ wc -l o o2
   1000000 o
      2909 o2
  
  $ head -5 o2
  12388 2dadahac2c2h as2s 
  11410 2s2d2cacasadah2h 
  11410 2d2s2cacasadah2h 
  11410 2d2cacasadah2h 2s 
   8965 2s2d2cacadasah2h 
  
  $
  

• Never mind compatibility, prune the duplicates.

Pruning Duplicate Tableaus

static bool find_legal_dp(
  const tableau & target, const deck & hand)

  tvec candidates;
  candidates.push_back(t);
  strset considered;

  while (!candidates.empty())
    t = candidates.back()
    candidates.pop_back()

    if (t == target)
      return true

    tvec nt = possible_next_tableaus(t)
    for b = nt.begin(); b != nt.end(); b++
      std::string s = b->as_string()
      if considered.count(s) == 0
        considered.insert(s)
        candidates.back_insert(*b);

  return false

Does Duplicate Pruning Help?

• Sorta.

  $ ./gen-game -r1 | ./acheck 
  dp  probes = 18.
  
  $ ./gen-game -r1 | ./acheck 
  dp  probes = 18
  
  $ ./gen-game -r2 | ./acheck 
  dp  probes = 1362
  
  $ ./gen-game -r2 | ./acheck 
  dp  probes = 3488
  
  $ ./gen-game -r2 | ./acheck 
  dp  probes = 4471
  
  $ ./gen-game -r3 | ./acheck 
  dp  probes = 4417283
  

• How about duplicate and compatibility pruning?

Duplicate And Compatibility Pruning

if target.compatible(*b) and
   (considered.count(s) == 0)
  considered.insert(s)
  candidates.push_back(*b)

• Does it help?

  $ ./gen-game -r2 | ./acheck 
  dp  probes = 1362.
  bp  probes = 125.
  dp/bp time = 5.0
  
  $ ./gen-game -r2 | ./acheck 
  dp  probes = 3488.
  bp  probes = 3488.
  dp/bp time = 4.7
  
  $ ./gen-game -r2 | ./acheck 
  dp  probes = 4471.
  bp  probes = 627.
  dp/bp time = 4.4
  
  $ ./gen-game -r3 | ./acheck 
  dp  probes = 4417283.
  bp  probes = 574760.
  dp/bp time = 5.1
  

The Test Cases

1. Empty input.

2. Garbage input.

3. Irreducible deck.

4. Fully collapsible deck.

5. Non-optimal tableau.

6. Recycled tableau.

The Results

• Grades are R (right), +, -, W (wrong), C (crashed or coredumped).

  Tests	C	W	-	+	R
  1	1	1	1	0	7
  2	1	0	0	0	9
  3	1	6	0	0	3
  4	2	4	1	0	3
  5	1	6	1	1	1
  6	0	3	1	2	4

Line Statistics - Newlines

Line Statistics - Semicolons

Procedure Statistics

Follow Directions

• Output a smaller tableau, an error message, or nothing.

  • Not

    PLAYING GAME
    a       c
    ************************
    a|c     
    ************************
    2       c
    ************************
    2|c     a|c     
    ************************
    3       c
    

  • Not

    A better game is :
    7dqd2d3d7hah9d8d9cjd9s7c6dtd
    3h8h6h3s5hqh
    asad4d5sksjs
    qctcthkh9h2c2s7s8skckdac4c5c
    4h2h
    ts6s
    6c3cjc8c
    jh
    qs4s
    5d
    

Don't Kill Yourself

void Cards::out()
  unsigned i
  for i = 0; i < deal.size(); i += 2
    cout << deal[i] << deal[i+1] << " "
    cout << endl << endl
  for i = 0; i < piles.size(); i++
    cout << piles[i] << endl

• What's wrong with this code?

• Here's a hint:

  ./acheck < ../../t3
  String index 107 is out of the range [0..106].
  Program received signal SIGABRT, Aborted.
  

Ouch

for int i = 0; i <= line.size(); i++
  if !isspace(line[i])
    // whatever

• What's wrong with this code?

  • Here's a hint:

    $ ./acheck < ../../t3
    String index 107 is out of the range [0..106].
    Program received signal SIGABRT, Aborted.
    

• If this is the best code you can write, you're going to fail.

Understand the Problem

• Space characters are unimportant.

  while getline(cin, s, '\n')
    lineno++
    if s.size() != 0
     if state == INIT 
       if s.size() != 104
         cerr << "Input not valid"
        exit (1)
     else
       if (s.size() % 2 != 0) || (s.size() > 104)
         cerr << "Input not valid"
         exit (1)
  

• Also, what is this code doing?

  • Control complexity.

  • Students who write code like this do indeed work hard.

Omit Needless Code

• Verbose code is hard to understand.

  bool 
  Card::operator == (const Card& c1) const
  
    bool match;
  
    if (this->getSuit() == c1.getSuit()) &&
       (this->getRank() == c1.getRank())
  	  match = true;
    else
  	  match = false;
  
    return (match);
  

• Small code is beautiful code.

  bool 
  Card::operator == (const Card& c1) const
  
    return (this->getSuit() == c1.getSuit()) &&
           (this->getRank() == c1.getRank())
  

Duplicate Code is Bad Code

• If you're writing duplicate code, stop and think.

  rank_Set.insert("a");
  rank_Set.insert("1");
  rank_Set.insert("2");
  rank_Set.insert("3");
  rank_Set.insert("4");
  rank_Set.insert("5");
  rank_Set.insert("6");
  rank_Set.insert("7");
  rank_Set.insert("8");
  rank_Set.insert("9");
  rank_Set.insert("t");
  rank_Set.insert("j");
  rank_Set.insert("q");
  rank_Set.insert("k");
  

• Is there a better way?

  const char ranks[] = "a123456789tjqk";
  std::set<char> rank_set(
    ranks, ranks + strlen(ranks));
  

No Magic Numbers

int findidx(string & s)
 int i=-1, j = -1;

 switch (s[0]) 
  case 'c' : i = CLUB   ; break;
  case 'd' : i = DIAMOND; break;
  case 'h' : i = HEART  ; break;
  case 's' : i = SPADE  ; break;
  default : break;

 switch (s[1])
  case 'a' : j=1; break;
  case 't' : j=10; break;
  case 'j' : j=11; break;
  case 'q' : j=12; break;
  case 'k' : j=13; break;
  default :  j=(s[1] - '0');

 assert ( i >= CLUB && i <= SPADE );
 assert ( j > 0 && i < 13 );

 int idx = i*13+j;
 return idx;

Points To Remember

• You always lose against exponential growth.

  • Know when you're up against it.

  • Don't out run it, out think it.

• If you make an assumption, test it.

  • You'll probably be surprised.

• Performance often comes at the cost of clarity.

  • Make sure you can pay for it; make sure you need it.

This page last modified on 5 April 2003.