127 - "Accordian" Patience

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

Post by oriol78 » Sun Jul 20, 2003 7:44 pm

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

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

[127]WA: Accordian Patience

Post by Betty » Wed Aug 20, 2003 7:49 am

Hey, I'm rather stuck again =( although I have managed to pump out a few problems since my last question, so guess thats good :D
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]
Last edited by Betty on Thu Aug 21, 2003 2:58 am, edited 1 time in total.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Aug 20, 2003 1:26 pm


Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Thu Aug 21, 2003 2:55 am

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]

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Aug 21, 2003 3:36 pm

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

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Sun Aug 24, 2003 3:41 am

yep still WA =(
Krzysztof Duleba wrote:Still WA? Strange. I've just compared your code with mine on 50 000 test cases, all results were the same.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Aug 24, 2003 4:10 am

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?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Aug 24, 2003 4:52 am

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
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Sun Aug 24, 2003 1:48 pm

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

Thanks heaps for both your guys help

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

127 - "Accordian" Patience

Post by xbeanx » Fri Aug 29, 2003 7:32 pm

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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Aug 29, 2003 8:40 pm

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Aug 29, 2003 8:41 pm

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 29, 2003 9:01 pm

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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Aug 29, 2003 9:18 pm

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Aug 29, 2003 9:21 pm

Exactly. The destructor is messed up.

Post Reply

Return to “Volume 1 (100-199)”