127 - "Accordian" Patience

[oriol78]

using Visual C++ the pair Template is on utility library

[Betty]

Hey, I'm rather stuck again =( although I have managed to pump out a few problems since my last question, so guess thats good
I'm getting WA on 127 now, it works for the sample data, but that's not saying alot (as its fairly simple), however I've played round with it and can't see what's going wrong. Anyone see anything glaringly obvious or have sample data around? Krzysztof Duleba offered a 1.5 MB sample data at one point, if he's around that would be awesome

[cpp]
old code removed
[/cpp]

[Krzysztof Duleba]

You can find it on http://rainbow.mimuw.edu.pl/~kd209203/127.

[Betty]

Hey thanks, I figured out my problem quickly after getting those files, now I have exact same output as you, although I still seem to be WA.
I thought I was being clever by comparing I to I+1 and then I+3
in a loop, but then I realised if I+1 matched I+2 it should be moved before I+3 (if that makes any sence to you)

Thanks heaps anyway

[cpp]

//@BEGIN_OF_SOURCE_CODE

#include <stdio.h>
#include <string.h>
#include <vector>
using std::vector;

struct card{
public:
card(char c,char s){
suit.push_back(s);
type.push_back(c);
esuit = s;
etype = c;
pile = 1;
}

int getSize(){return pile;}

bool match(card *c){
return (etype==c->etype||esuit==c->esuit);
}

void combine(card *c){

esuit = c->suit.back();
etype = c->type.back();
suit.push_back(esuit);
type.push_back(etype);

pile ++;

c->type.pop_back();
c->suit.pop_back();
c->esuit = c->suit.back();
c->etype = c->type.back();
c->pile--;

}

void print(){
printf("%c%c",type.back(),suit.back());
}

private:
char esuit; //used to speed up comparisons
char etype; //as suit.back() is slow

vector <char> suit;
vector <char> type;
int pile;
};


void readCards(char* line,vector <card*> &v){
int i=0;
while(i<26){
card *c = new card(*line,*(line+1));
v.push_back(c);
line+=3;
i++;
}
}


void doMove(vector <card*> &v){
bool move = true;
if(v.size()<2)return;
while(move){
move = false;
int current = 1;
for(vector <card*>::iterator i = (v.begin()+1);i!=v.end();i++){

if(current-3>=0&&(*i)->match(*(i-3))){
(*(i-3))->combine(*(i));
if((*(i))->getSize()==0){
delete *(i);
v.erase((i));

}
move = true;
break;
}

if(current-1>=0&&(*i)->match(*(i-1))){
(*(i-1))->combine(*(i));

if((*(i))->getSize()==0){
delete *(i);
v.erase((i));
}
move = true;

break;
}

current++;
}
}
}

int main(){
char line[1000];


vector <card*> cards;
vector <card*> playfield;
card *next;

while(fgets(line,1000,stdin)){

cards.clear();
playfield.clear();
if(line[0]=='#')break;
readCards(line,cards);
strcpy(line,"");
fgets(line,1000,stdin);
readCards(line,cards);
strcpy(line,"");


while(cards.size()>0){
next = cards[0];
cards.erase(cards.begin());
playfield.push_back(next);
doMove(playfield);
}

printf("%d %s remaining:",playfield.size(),(playfield.size()==1?"pile":"piles"));
for(int i=0;i<playfield.size();i++){
printf(" %d",((card*)playfield)->getSize());
}
printf("\n");

for(int i=0;i<playfield.size();i++){
delete playfield;
}
playfield.clear();
}

return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[Krzysztof Duleba]

Still WA? Strange. I've just compared your code with mine on 50 000 test cases, all results were the same.

[Betty]

yep still WA =(

Still WA? Strange. I've just compared your code with mine on 50 000 test cases, all results were the same.

[Krzysztof Duleba]

Now your're kidding, aren't you?. I checked our solutions on 100 000 more test cases with identical results. So I submited your code to see what would happed. I got AC.
How could you possibly get WA sending the same? Are you sure you typed the right problem name? Did you submit the code you posted here?

[UFP2161]

Since you have a "// BEGIN .." line, I'm assuming you're emailing the program. Hence, you have a line which is > 72 characters, and most likely is getting truncated by your e-mail program. Either submit your solution via the online interface, or put an enter in an appropriate position on the offending line: =)
[cpp] printf("%d %s remaining:",playfield.size(),(playfield.size()==1?"pile":"piles"));
123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789 123456789
1 2 3 4 5 6 7 8[/cpp]
It's probably inserting a newline in one of the "pile" parts. (72 or 80).

[Betty]

looks like I'll be using the online submissions from now on, got a nice AC sooo annoying I must have submitted like 10x via email, the same code, and yet it was always a WA

Thanks heaps for both your guys help

[xbeanx]

Hi guys. Do you think someone can look over my code and tell me how to fix my memory routines??

I'm not that great a C++ programmer, so I'm probably missing something totaly obvious. If that is the case I ask you to not make fun of me for being an idiot.

[cpp]#include <iostream>

class Pile {
public:
int ncards;
char **cards;

Pile() {
ncards = 0;
cards = new char*[52];
for(int i = 0; i < 52; i++) cards = new char[2];
}

~Pile() {
for(int i = 0; i < 52; i++) delete [] cards;
delete [] cards;
}

void push(char *card)
{cards[ncards++] = card;}

void pop()
{if(ncards > 0) ncards--;}

char* top()
{return cards[ncards-1];}

bool isEmpty()
{return ncards == 0;}
};

int npiles;
Pile *piles;

inline void clean(int pos) {
npiles--;
for(int i = pos; i < npiles; i++)
piles = piles[i+1];
}

bool makeMove() {
for(int i = 1; i < npiles; i++) {
char *cardA = piles.top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff].top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff].push(cardA);
piles.pop();
if(piles.isEmpty()) clean(i);
return true;
}
diff -= 2;
}
}
return false;
}

using namespace std;
int main() {
char *card = new char[2];
while(cin >> card) {

if(card[0] == '#') return 0;

npiles = 0;
piles = new Pile[52];

piles[npiles++].push(card);

for(int i = 1; i < 52; i++) {
card = new char[2];
cin >> card;
piles[npiles++].push(card);
}

while(makeMove());

cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles.ncards;
cout << endl;
}

return 0;
}[/cpp]

My program works, but it just uses way to much memory (like 35MB). Thanks everyone! You rock!

BTW, I did this program in JAVA, and tested it against a 400k input file.. It took 35 seconds to run. The corresponding C++ version took less than a second.

[UFP2161]

[cpp]piles = new Pile[52];[/cpp]
Every time you iterate through a deck, you make 52 new piles for it, and don't clean up the old ones. Thus, your memory goes up up and away! =P .. either delete[] piles at the end of the loop or better yet, just write a cleanup function so you can reuse the already allocated memory.

Yes, C++ does not have garbage collection like Java does =)

(and if you think your destructor is being called, put a cout statement in it, and you'll see that it doesn't..)

[Krzysztof Duleba]

Add
[cpp]delete [] piles;[/cpp]
at the end of your main while loop.
You have delete operators in pile class destructor, but actually they aren't launched at all.

[xbeanx]

Thanks guy. I noticed that and actually tried adding it. However, when I add a delete [] piles to the end of my loop I get the following:

garfield% a.out < input
6 piles remaining: 40 8 1 1 1 1
Memory fault

So as you see, it makes it through the first input set, and for some reason dies after I delete the piles. I am not sure what's going on. I do not access the deleted piles before reallocating them next time through the loop.

Its probably something super simple, but as I am super-super simple, it defies me.

Thanks again guys!!!!

[UFP2161]

Try and trace through what happens to your *card variable in main after your call to the Pile destructor. Therein lies the problem. =)

[Krzysztof Duleba]

Exactly. The destructor is messed up.