online advertising

Sunday, September 21, 2014

UVa Problem 127 - "Accordian" patience

Problem

Please find the problem here.

Solution

Competition programming already hinted on using stack. The less trivial part is how to manage the stacks. In my implementation, I decided to use a list<stack<card*>*>, a list is simply a doubly-linked list. The use of pointers free me from thinking about copying, and it also allow me to delete an element from a list without needing to move elements.

Initially, I wrote a loop like this.

foreach (card)
{
  // ... perform all the moves associated with the dealt card.
}

That quickly turn out to be a mess. Then I moved on to use a pull loop instead

while (true)
{
  if (there are more moves)
  {
    // perform the move
  }
  else
  {
     // deal a card - break if no more cards
  }
}

But how do I detect if there is a move. I originally devised an algorithm for that.

If a new card is dealt, the card is movable.
If a card is moved from position A and position B.
Position B is movable (it is a new card on top)
Position B + 1 is movable (it is possible that the move enabled the move)
Position B + 3 is movable (it is possible that the move enabled the move)
Position A (if the pile is not emptied) is movable
Position A + 1 is movable (the pile emptied or not, it has a new neighbor)
Position A + 3 is movable (the pile emptied or not, it has a new neighbor)

(A clever reader might have find the bug in my thoughts right now ... but let's me move on ...)

Getting all these coded right is not easy. In order to help me to find out what's wrong, I need to dry run and compare with the execution. The best way to do is to have an execution trace. So I code up the inspect() function to show the stacks as well as the movable cards. A good representation helps debugging a lot!.

Finally, I get the code to run correctly with the provided inputs and matches output. Then I submitted to the judge. Ooops - wrong answer.

The presentation is unlikely to have problem, so I need to figure out what's wrong with the algorithm. Just staring at it can't really find out what's going on. So I need something else. Apparently, the sample input is not good enough to find that bug, so I generated some random deck of cards and try it out. No crash, seems to be right, more frustrated.

Now I think maybe the movable card tracking is wrong (after all, that is the most complex part). So I eliminated the algorithm and use a brute force method instead. The brute force just try every card to see if a move is possible, now I get a baseline to compare against.

With more random inputs (around 50 of them), now I finally figure out what's the problem. The problem is, when a pile is removed, there are some more opportunity to move, and the movable card tracking algorithm is not tracking that. The opportunity is slim so I need to generate many inputs to find that out.

As the goal is really just to pass the judge, I submitted the brute force instead, and finally it got accepted!

What I learnt?
  • Code up inspect() - execution trace is very helpful to debug.
  • Code up brute_force() - having an oracle is good for debugging.
  • Use random inputs - I would not be able to find the bug otherwise.
Didn't bother to clean up the code - to clean up properly, I should remove all the movable card tracking. But screw it, the judge won't care, so am I, I just need to make sure I don't bring this practice back to my day-to-day coding, that sounds like scary.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=63

#include "UVa127.h"

#include <iostream>
#include <stack>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

struct card
{
    char rank;
    char suit;
};

bool read_cards(vector<card*>& deck)
{
    card* current_card = new card();
    cin >> current_card->rank;
    if (current_card->rank == '#')
    {
        delete current_card;
        return false;
    }
    cin >> current_card->suit;
    deck.push_back(current_card);
    current_card = NULL;

    for (int i = 0; i < 51; i++)
    {
        card* current_card = new card();
        cin.get(); /* Consume the whitespace */
        cin >> current_card->rank;
        cin >> current_card->suit;
        deck.push_back(current_card);
        current_card = NULL;
    }

    return true;
}

void delete_cards(vector<card*>& deck)
{
    for (vector<card*>::iterator ci = deck.begin(); ci != deck.end(); ci++)
    {
        delete (*ci);
    }
}

typedef stack<card*> pile;
typedef list<pile*> game;
typedef list<pile*>::iterator position;
typedef vector<position> positions;

bool deal(vector<card*>& deck, int& current_card, positions& movable_cards, game& current_game)
{
    if (current_card == deck.size())
    {
        return false;
    }

    card* next_card = deck[current_card++];
    pile* new_pile = new pile();
    new_pile->push(next_card);
    current_game.push_back(new_pile);
    position new_position = current_game.end();
    new_position--;
    movable_cards.push_back(new_position);
    return true;
}

void inspect(game& current_game, positions& movable_cards)
{
}

void inspect_disabled(game& current_game, positions& movable_cards)
{
    int num_stars = 0;
    for (position gi = current_game.begin(); gi != current_game.end(); gi++)
    {
        bool movable = false;
        for (positions::iterator mi = movable_cards.begin(); mi != movable_cards.end(); mi++)
        {
            if (*mi == gi)
            {
                movable  = true;
                break;
            }
        }
        if (movable)
        {
            num_stars++;
            cout << " * ";
        }
        else
        {
            cout << " - ";
        }
        pile temp_pile;
        pile* current_pile = *gi;
        while (current_pile->size() > 0)
        {
            temp_pile.push(current_pile->top());
            current_pile->pop();
        }
        while (temp_pile.size() > 0)
        {
            cout << temp_pile.top()->rank << temp_pile.top()->suit << " ";
            current_pile->push(temp_pile.top());
            temp_pile.pop();
        }
        cout << endl;
    }
    if (num_stars != movable_cards.size())
    {
        cout << "BOOM!" << endl;
    }
    cout << endl;
}

// I have to say - this is just awful design :(
void move(position& current_position, pile*& current_pile, position& neighbor_position, pile*& neighbor_pile, game& current_game, positions& movable_cards, positions& new_movable_cards)
{
    // Perform the move
    neighbor_pile->push(current_pile->top());
    current_pile->pop();
    
    current_position++;
    position current_next_position = current_position;
    current_position--;

    if (current_pile->size() == 0)
    {   
        current_game.erase(current_position);
        delete current_pile;        
    }
    else
    {
        new_movable_cards.push_back(current_position);           
    }

    if (current_next_position != current_game.end())
    {
        new_movable_cards.push_back(current_next_position);
        current_next_position++;
        if (current_next_position != current_game.end())
        {
            current_next_position++;
            if (current_next_position != current_game.end())
            {
                new_movable_cards.push_back(current_next_position);
            }
        }
    }
    
    neighbor_position++;
    position neighbor_next_position = neighbor_position;
    neighbor_position--;

    new_movable_cards.push_back(neighbor_position);
    if (neighbor_next_position != current_game.end())
    {
        new_movable_cards.push_back(neighbor_next_position);
        neighbor_next_position++;
        if (neighbor_next_position != current_game.end())
        {
            neighbor_next_position++;
            if (neighbor_next_position != current_game.end())
            {
                new_movable_cards.push_back(neighbor_next_position);
            }
        }
    }
}

void play_accordance_patience(vector<card*>& deck, bool brute_force)
{
    int current_card = 0;
    
    // Debug only
    int move_count = 0;

    positions movable_cards;
    game current_game;
    while (true)
    {
        if (movable_cards.size() == 0)
        {
            if (!deal(deck, current_card, movable_cards, current_game))
            {
                break;
            }

            if (brute_force)
            {
                // Brute force - force a star on every line
                movable_cards.clear();
                for (position gi = current_game.begin(); gi != current_game.end(); gi++)
                {
                    movable_cards.push_back(gi);
                }
            }

            // cout << "Deal: " << current_card << endl;
            inspect(current_game, movable_cards);
        }
        else
        {
            positions new_movable_cards;
            for (positions::iterator pi = movable_cards.begin(); pi != movable_cards.end(); pi++)
            {
                position current_position = *pi;
                pile* current_pile = *current_position;
                position neighbor_position = current_position;
                pile* neighbor_pile = NULL;
                if (neighbor_position != current_game.begin())
                {
                    neighbor_position--;
                    if (neighbor_position != current_game.begin())
                    {
                        neighbor_position--;
                        if (neighbor_position != current_game.begin())
                        {
                            neighbor_position--;
                            neighbor_pile = *neighbor_position;
                            if ((current_pile->top()->rank == neighbor_pile->top()->rank) || (current_pile->top()->suit == neighbor_pile->top()->suit))
                            {
                                move_count++;
                                move(current_position, current_pile, neighbor_position, neighbor_pile, current_game, movable_cards, new_movable_cards);
                                movable_cards.erase(pi);
                                break;
                            }
                            neighbor_position++;
                        }
                        neighbor_position++;
                    }
                    neighbor_pile = *neighbor_position;
                    if ((current_pile->top()->rank == neighbor_pile->top()->rank) || (current_pile->top()->suit == neighbor_pile->top()->suit))
                    {
                        move_count++;
                        move(current_position, current_pile, neighbor_position, neighbor_pile, current_game, movable_cards, new_movable_cards);
                        movable_cards.erase(pi);
                        break;
                    }
                }
            }

            if (new_movable_cards.size() == 0)
            {
                movable_cards.clear();
            }
            else
            {
                for (positions::iterator mi = movable_cards.begin(); mi != movable_cards.end(); mi++)
                {
                    new_movable_cards.push_back(*mi);
                }

                movable_cards.clear();
                for (position gi = current_game.begin(); gi != current_game.end(); gi++)
                {
                    for (positions::iterator nmi = new_movable_cards.begin(); nmi != new_movable_cards.end(); nmi++)
                    {
                        if (*nmi == gi)
                        {
                            movable_cards.push_back(gi);
                            break;
                        }
                    }
                }
                
                if (brute_force)
                {
                    // Brute force - force a star on every line
                    movable_cards.clear();
                    for (position gi = current_game.begin(); gi != current_game.end(); gi++)
                    {
                        movable_cards.push_back(gi);
                    }
                }
                // cout << "Move: " << move_count << endl;
                inspect(current_game, movable_cards);
            }
        }
    }

    cout << current_game.size() << " pile" << (current_game.size() == 1 ? "" : "s") << " remaining:";
    for (position gi = current_game.begin(); gi != current_game.end(); gi++)
    {
        pile* current_pile = *gi;
        cout << " " << current_pile->size();
        delete current_pile;
    }
    cout << endl;
}

int UVa127()
{
    while (true)
    {
        vector<card*> deck;
        if (read_cards(deck))
        {
            // play_accordance_patience(deck, false);
            play_accordance_patience(deck, true);
            delete_cards(deck);
        }
        else
        {
            break;
        }
    }
    return 0;
}

No comments :

Post a Comment