174 - Strategy

[PMNOX]

Can someone test following test data:
CHEAT.
TRADE.
IF MY LAST1 = CHEAT OR MY LAST2 = CHEAT AND YOUR LAST2 = CHEAT THEN TRADE ELSE CHEAT.
IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN TRADE ELSE CHEAT ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADEELSECHEAT.
IF YOUR LAST2=CHEATORYOURLAST1=CHEATTHENCHEATELSETRADE.
IF YOUR LAST1#NULLTHENIF YOUR LAST1#NULLANDMYLAST1=TRADETHENTRADEELSETRADEELSEIF YOUR LAST1#NULLTHENTRADEELSETRADE.
IF MY LAST1 = CHEAT OR MY LAST2 = CHEAT AND YOUR LAST2 = CHEAT THEN TRADE ELSE CHEAT.
IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN IF MY LAST1 = CHEAT AND MY LAST2 = CHEAT THEN TRADE ELSE CHEAT ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADEELSECHEAT.
#


answer:
39
-12
-2
21
14
37
-12
-2
21
14










#include <iostream.h>
#include <string>
#define CHEAT 1
#define TRADE 0
#define NULLL -1
#define OR 0
#define AND 1
#define THEN -1

const int max=10;
const int maxx=256;

void czytaj(char A[max][maxx],int &ilosc,char &znak);
int checklast(char A[max][maxx],int i,int mema[2],int memb[2],int &last) ;
int memory(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int cond(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int search_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int ifstructure(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int condition(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int command(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
int statement(char A[max][maxx],int i,int mema[2],int memb[2],int &last);
void pamiec(int mema[2],int memb[2],int x,int y);
void wylicz(char A[max][maxx],int wart[],int ilosc,int i,int j);
void search_for_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last);



//n^3/2==500 //2000000 tyle moge zrobic

int checklast(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done//last zgadza sie
{
if(A[last] == '1')
return 0;
else if(A[last] == '2')
return 1;
else
{
//while(true);

cerr<<"bug in checklast"<<endl;
return 23;

}

}

int memory(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done//last zgadza sie
{
if((A[last] == 'M') && (A[last+1] == 'Y'))
{
//lastx = checklast(A,i,mema,memb,numer+6);
//return true;
last = last + 6;
return mema[checklast(A,i,mema,memb,last)];
}
else if((A[last] == 'Y') && (A[last+1] == 'O')&& (A[last+2] == 'U')&& (A[last+3] == 'R'))
{
//lastx = checklast(A,i,mema,memb,numer+8);
last = last + 8;
//return false;
return memb[checklast(A,i,mema,memb,last)];
}
else
{
//while(true);
cerr<<"bug in memory"<<endl;
return 23;
}
}


int cond(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done //last zgadza sie
{
int wartosc = memory(A,i,mema,memb,last); //pobiera wartosc
int wartoscb;
last++;//zwieksza wartosc od 1 i 2
if(A[last] == '=')
wartoscb=1;
else if(A[last] == '#')
wartoscb=-1;
else
{
cerr<<"bug in cond"<<endl;
return 23;
}
last++;//dalej od = i #
int wartoscfaktyczna=command(A,i,mema,memb,last);
if(wartoscfaktyczna == -1)
last += 2; // poprawiam NULL
if(wartoscb == 1)
{
if(wartoscfaktyczna == wartosc)
return true;
else
return false;
}
else
if(!wartoscfaktyczna == wartosc)
return true;
else
return false;
}

int search_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
if((A[i][last] == 'O') && (A[i][last+1] == 'R'))//or
{
last += 2;
return OR;
}
else if((A[i][last] == 'A') && (A[i][last+1] == 'N')&& (A[i][last+2] == 'D' ))//and
{
last += 3;
return AND;
}
else
return THEN;//then
}



int condition(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
int logika=cond(A,i,mema,memb,last);
int next=search_else(A,i,mema,memb,last);
int wynik;
if(next >= 0)
{
if(next == OR) //or
{
wynik = condition(A,i,mema,memb,last);
return (logika ||wynik );
}
else //and
{
wynik = condition(A,i,mema,memb,last);
return (logika && wynik);
}
}
else
return logika;
}

void search_for_else(char A[max][maxx],int i,int mema[2],int memb[2],int &last)
{
int number_of_then_else=0;
while(true)
{

if((A[i][last] == 'T') && (A[i][last+1] == 'H')&& (A[i][last+2] == 'E' )&& (A[i][last+3] == 'N' ))
{
number_of_then_else++;
last+=4;
}
if((A[i][last] == 'E') && (A[i][last+1] == 'L')&& (A[i][last+2] == 'S' )&& (A[i][last+3] == 'E' ))
if(number_of_then_else>0)
{
number_of_then_else--;
last+=4;
}
else
{
last += 4;
return;
}

last++;
}
}

int ifstructure(char A[max][maxx],int i,int mema[2],int memb[2],int &last)//done
{
if(condition(A,i,mema,memb,last))
{
last += 4;
return statement(A,i,mema,memb,last);
}
else
{
last += 4;
search_for_else(A,i,mema,memb,last);
return statement(A,i,mema,memb,last);
}
}

int command(char A[max][maxx],int i,int mema[2],int memb[2],int &last) //done
{
if((A[i][last] == 'C') && (A[i][last+1] == 'H')&& (A[i][last+2] == 'E')&& (A[i][last+3] == 'A')&& (A[i][last+4] == 'T') )
{
last+=5;//cheat 0
return CHEAT;
}
else if((A[i][last] == 'T') && (A[i][last+1] == 'R')&& (A[i][last+2] == 'A')&& (A[i][last+3] == 'D')&& (A[i][last+4] == 'E') )
{
last+=5;//trade 1
return TRADE;
}
else
{
last+=2;
return NULLL;//error lub null
}
}


int statement(char A[max][maxx],int i,int mema[2],int memb[2],int &last)//done
{
int wartosc=command(A,i,mema,memb,last);
if(wartosc >= 0)
return wartosc;
else return ifstructure(A,i,mema,memb,last);
}

void pamiec(int mema[2],int memb[2],int x,int y)
{
mema[1]=mema[0]; //zarzadzanie pamiencia
mema[0]=x;
memb[1]=memb[0];
memb[0]=y;
}


void wylicz(char A[max][maxx],int wart[],int ilosc,int i,int j)
{
int x,y;
int mema[2],memb[2];
mema[0] = NULLL;//-1 = NULL
mema[1] = NULLL;//0 = TRADE
memb[0] = NULLL;//1 = CHEAT
memb[1] = NULLL;
int ostatni;
for(int a=0;a<10;a++)
{
// 1 trade //0 cheatni
ostatni=0;
x = statement(A,i,mema,memb,ostatni);
ostatni=0;
y = statement(A,j,memb,mema,ostatni);
pamiec(mema,memb,x,y);
//give value
if(( x == TRADE) && (y == TRADE))
{
wart[i]++;
wart[j]++;
} else
if(( x == CHEAT) && (y == TRADE))
{
wart[i]+=2;
wart[j]-=2;
}else
if(( x == TRADE) && (y == CHEAT))
{
wart[i]-=2;
wart[j]+=2;
} else
//if(( x == CHEAT) && (y == CHEAT))
{
wart[i]--;
wart[j]--;
}
}
}




void czytaj(char A[max][maxx],int &ilosc,int &znak)
{

while(A[ilosc][znak]!= '.')
{
znak++;
cin>>A[ilosc][znak];
}
ilosc++;
znak=0;
cin>>A[ilosc][znak];

}

void write(int x)
{
//cout<<wart[i]<<endl;
if(x>99)
cout<<x<<endl;
else
if(x>9)
cout<<" "<<x<<endl;
else if(x>=0)
cout<<" "<<x<<endl;
else if(x> - 10)
cout<<" "<<x<<endl;
else
cout<<x<<endl;

}

void main()
{
char A[max][maxx];
int wart[max];
for(int i=0;i<max;i++)
{
//A[i] = "";
wart[i] = 0;
}

int ilosc = 0;
int znak=0;
cin>>A[ilosc][znak];
while((A[ilosc][znak]!= '#')) //read and ingorespaces
{
czytaj(A,ilosc,znak);
}
//wypisz stringi
// #ifndef ONLINE_JUDGE
// for(int i=0;i<=ilosc;i++)
// cout<<A[i]<<endl;
// #endif
//przetworz
// wyczysc tgablice wart

for(int i=0;i<ilosc-1;i++)
for(int j=i+1;j<ilosc;j++)
wylicz(A,wart,ilosc,i,j);


//wypisz dane
for(int i=0;i<ilosc;i++)
write(wart[i]);
#ifndef ONLINE_JUDGE
cin>>znak;
#endif
}

[ivec]

my AC prog generates the same output from the sample cases you provided.

Doesn't mean the program is correct though... for instance, there could be less than 10 strategies in the input.

I solved this problem by building a decision tree from the program, using something like:
[c]
typedef enum { cNull, cCheat, cTrade } Cmd;
typedef enum { mM1, mM2, mY1, mY2, mNone } MemInd;
typedef struct Step_ {
MemInd mem; /* if mNone then val is actual command */
Cmd val; /* value to test against */
struct Step_ *eq, *ne; /* next step if value is equal -,- not equal
} Step;
[/c]
The result is quite brief and nice actually...

Also, you may want to consider using strncmp() to simplify some tests in the code...

Regards,

[Quantris]

Anyone know what precedence to use for compound boolean operations in this problem?

meaning suppose I have <cond> AND <cond> OR <cond>

do I interpret as (<cond> AND <cond>) OR (<cond>) (left-to-right)

or as (<cond>) AND (<cond> OR <cond>) (right-to-left)

[mf]

The grammar clearly states that the operators are right-associative.
So, <cond> AND <cond> OR <cond> = <cond> AND (<cond> OR <cond>).

[Quantris]

It is not a given (in my opinion) that the operator associativity is determined by the grammar -- they are separate (in other words, I would see nothing wrong with having the same grammar definition, plus a statement that the operators are left-associative).

Anyway, thanks for your answer

[mf]

The grammar has this part:

<condition> ::= <cond> | <cond> <op> <condition>

According to it, the expression 'x AND y OR z' can be only parsed as:
x AND y OR z = <cond1> AND <condition1>, where
<cond1> = x
<condition1> = y OR z.

Parsing it the other way is against the grammar: 'x AND y' is not <cond>.

[Quantris]

I understood what you meant the first time.

But what I meant was that the grammar simply defines the form of the expression, and not it's meaning (since that is all that a grammar is supposed to do).

[LlatzerandToni]

Try.

Input:

Code: Select all

IFYOURLAST1=TRADEANDYOURLAST2#NULLORMYLAST1=NULLTHENCHEATELSETRAD

E.
IFMYLAST2#NULLTHENIFMYLAST1#CHEATTHENTRADEELSECHEATELSEIFYOURLAST

2=TRADETHENCHEATELSETRADE.
#

Output:

Code: Select all

 18
-14

[metaphysis]

mf is right, the operators are right-associative.
After several failed attempts, I got AC, and for clarity, "play each strategy against each other strategy 10 times" means:
a b c
1: clear the memory, a plays with b 10 times, clear the memory, a plays with c 10 times, output the scores of a;
2: clear the memory, b palys with a 10 times, clear the memory, b plays with c 10 times, output the scores of b;
3: clear the memory, c palys with a 10 times, clear the memory, c plays with b 10 times, output the scores of c.