/*  POTM ENTRY:  LastMinutePacking        */
/*  Your Name:   Ben Glasson              */
/*  Your email:  bglasson@bigpond.com     */
#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>

#define MAXPOSITIONS 750000
#define HASHTABLESIZE 3000000
#define MAXTIME 595
#define CLK_TCK 100

void swap(int i,int j);
void getsuitcase(char filename[]);
void analyzedata(void);
void setup(void);
void setuphashing(void);
void setupscoring(void);
int hashvalue(int piecepos[]);
void makegrid(int piecepos[], int grid[]);
void findmoves(int piecepos[]);
int fitpiece(int grid[], int piece, int row, int column);
void makenewpos(int piecepos[],int piece,int posi);
int findpos(int piecepos[]);
int comparepos(int piecepos[],int piecepos1[]);
int checkx(int piecepos[]);
void getsolution(int xmove,int ymove);
void printsolution(void);
void pqueueinsert(int pos);
void pqueuedelete(void);
int score(int piecepos[]);
int xcover(int grid[],int row, int col);
int movemin(int piecepos[]);
int xcovernum(int grid[],int row,int column);
void checktime(void);

int caserows,casecols;
int piecenum=0,piecerows[20],piececols[20];
int position[20];
int xrows=0,xcols=0;
int piecenum1=0,piecerows1[20],piececols1[20],piecepointer1[21];
int initpos[20];
int posdata[MAXPOSITIONS][20],mindata[MAXPOSITIONS];
int scoredata[MAXPOSITIONS],scorecoeff[480],scoremove[1000],mincoeff;
int movedata[MAXPOSITIONS][3],movenumdata[MAXPOSITIONS];
int posnum,bestpointer,move;
int hashtable[HASHTABLESIZE],piecehash[20][480];
int bestmovenum=1000,bestsolution[1000][2];
int pqueue[MAXPOSITIONS+1],pqueuesize=0;

int main(int argc,char* argv[]) 
{
getsuitcase(argv[1]);
setup();
analyzedata();
while (pqueuesize>0)
{ checktime();
bestpointer=pqueue[1];
pqueuedelete();
move=movenumdata[bestpointer];
findmoves(posdata[bestpointer]);
scoredata[bestpointer]=-scoredata[bestpointer];
}
printsolution();

return(0);
}

void setup(void)
{
setuphashing();
setupscoring();
return;
}

void setuphashing(void)
{
int i,j;

srand(1);
for (i=0;i<=19;i++)
{ for (j=0;j<=479;j++)
piecehash[i][j]=(rand()*32767+rand())%HASHTABLESIZE;
}
for (i=0;i<=HASHTABLESIZE-1;i++)
hashtable[i]=-1;

return;
}

void setupscoring(void)
{
int i,k;

k=(xrows+1)*(xcols+1);
for (i=0;i<=k/2;i++)
{ scorecoeff[i]=2000-(i*20);
scorecoeff[k-i]=scorecoeff[i];
scorecoeff[i]+=500;
}
for (i=0;i<=999;i++)
scoremove[i]=(10000-i*40);
mincoeff=5;

return;
}

void analyzedata(void)
{
int i,j;
int tempi,tempj;

for (i=0;i<=piecenum;i++)
initpos[i]=position[i];
/*SORT PIECES BY SIZE AND POS IF EQUAL SIZE*/
for (i=0;i<=piecenum-1;i++)
{ for (j=i+1;j<=piecenum;j++)
{ tempi=piecerows[i]*32+piececols[i];
tempj=piecerows[j]*32+piececols[j];
if ( (tempj>tempi) || ( (tempi==tempj) && (position[i]>position[j]) ) )
{ swap(piecerows[i],piecerows[j]);
swap(piececols[i],piececols[j]);
swap(position[i],position[j]);
}
}
}
/* CONSTRUCT PIECE TYPE STRUCTURE */
piecenum1=0;
piecerows1[0]=piecerows[0];
piececols1[0]=piececols[0];
piecepointer1[0]=0;
for (i=1;i<=piecenum;i++)
{ if ( (piecerows[i]!=piecerows1[piecenum1]) || (piececols[i]!=piececols1[piecenum1]) )
{ piecenum1++;
piecerows1[piecenum1]=piecerows[i];
piececols1[piecenum1]=piececols[i];
piecepointer1[piecenum1]=i;
}
}
piecepointer1[piecenum1+1]=piecenum+1;

posnum=0;
for (i=0;i<=piecenum;i++)
posdata[0][i]=position[i];
hashtable[hashvalue(position)]=0;
scoredata[0]=score(position);
pqueueinsert(0);
movenumdata[0]=0;
movedata[0][0]=-1;
movedata[0][1]=-1;
movedata[0][2]=-1;

return;
}

void makegrid(int piecepos[], int grid[])
{
int i,j,k;
for (i=0;i<=piecenum;i++)
{ for (j=0;j<=piecerows[i];j++)
{ for (k=0;k<=piececols[i];k++)
grid[piecepos[i]+j*32+k]=i+1;
}
}

return;
}

void findmoves(int piecepos[])
{
int i,j,k,x,y;
int grid[480];

if (move+mindata[bestpointer]>bestmovenum)
return;

for (i=0;i<=479;i++)
grid[i]=0;

makegrid(piecepos,grid);
for (i=0;i<=piecenum1;i++)
{ x=piecerows1[i];
y=piececols1[i];
for (j=0;j<=caserows-x;j++)
{ for (k=0;k<=casecols-y;k++)
{ if (fitpiece(grid,i,j,k)==1)
makenewpos(piecepos,i,j*32+k);
if (move>=bestmovenum-1)
return;
}
}
}

return;
}

int fitpiece(int grid[],int piece,int row,int column)
{
int i,j;

if (piece==99)
{ for (i=row;i<=row+xrows;i++)
{ for (j=column;j<=column+xcols;j++)
{ if (grid[i*32+j]!=0)
return 0;
}
}
}
else
{ for (i=row;i<=row+piecerows1[piece];i++)
{ for (j=column;j<=column+piececols1[piece];j++)
{ if (grid[i*32+j]!=0)
return 0;
}
}
}
return 1;
}

void makenewpos(int piecepos[],int piece,int posi)
{
int i,j,k,p1,p2,temp,temp1;
int piecepos1[21];

p1=piecepointer1[piece];
p2=piecepointer1[piece+1]-1;
for (i=p1;i<=p2;i++)
{ for (j=0;j<=piecenum;j++)
piecepos1[j]=piecepos[j];
temp1=piecepos1[i];
piecepos1[i]=posi;
for (j=p1;j<=p2-1;j++)
{ for (k=j+1;k<=p2;k++)
{ if (piecepos1[j]>piecepos1[k])
{ temp=piecepos1[j];
piecepos1[j]=piecepos1[k];
    piecepos1[k]=temp;
}
}
}
/* STORE POSITION*/
k=findpos(piecepos1);
if (k >= 0)
{ posnum++;
for (j=0;j<=piecenum;j++)
posdata[posnum][j]=piecepos1[j];
mindata[posnum]=movemin(piecepos1);
scoredata[posnum]=score(piecepos1)-mincoeff*mindata[posnum];
movenumdata[posnum]=move+1;
movedata[posnum][0]=temp1;
movedata[posnum][1]=posi;
movedata[posnum][2]=bestpointer;
hashtable[k]=posnum;
pqueueinsert(posnum);
j=checkx(piecepos1);
if (j>=0)
{getsolution(j,posnum);
return;
}
}
else
{ k=-k;
if (move+1<movenumdata[k])
{ if (scoredata[k]<0)
{ scoredata[k]=score(piecepos1)-mincoeff*mindata[k];
pqueueinsert(k);
}
movenumdata[k]=move+1;
movedata[k][0]=temp1;
movedata[k][1]=posi;
movedata[k][2]=bestpointer;
j=checkx(piecepos1);
if (j>=0)
{ getsolution(j,k);
return;
}
}
}

if (posnum>=MAXPOSITIONS-1)
printsolution();
}

return;
}

int findpos(int piecepos[])
{
int hash;

hash=hashvalue(piecepos);

while (hashtable[hash]>=0)
{ if ( comparepos(piecepos,posdata[hashtable[hash]])==1 )
return -hashtable[hash];
else
hash=(hash+1)%HASHTABLESIZE;
}

return hash;
}

int comparepos(int piecepos[], int piecepos1[])
{
int i;

for (i=0;i<=piecenum;i++)
{ if (piecepos[i]!=piecepos1[i])
return 0;
}

return 1;
}

int checkx(int piecepos[])
{
int i,j,k;
int grid[480];

for (i=0;i<=479;i++)
grid[i]=0;

makegrid(piecepos,grid);
for (j=0;j<=caserows-xrows;j++)
{ for (k=0;k<=casecols-xcols;k++)
{ if (fitpiece(grid,99,j,k)==1)
return j*32+k;
}
}

return -1;
}

void getsuitcase(char filename[])
{
FILE *infile;
char buff[64];
int grid[17][64];
int i,j,k;

infile=fopen(filename,"r");
for (i=0;i<=16;i++)
{ for (j=0;j<=63;j++)
grid[i][j]=-999;
}
for (i=0;i<=19;i++)
{ piecerows[i]=0;
piececols[i]=0;
position[i]=-1;
}
piecenum=-1;
caserows=-1;
casecols=0;

while (fgets(buff,63,infile)!=NULL)
{ 
caserows++;
i=0;
while (buff[i]==' ' || buff[i]=='_' || (buff[i]>='A' && buff[i]<='X'))
{ grid[caserows][i]=buff[i];
if (caserows==0 && buff[i]==' ')
casecols=i-1;
i++;
}
}
fclose(infile);

 for (i=0;i<=caserows;i++)
 { for (j=0;j<=casecols;j++)
  { k=grid[i][j];
   if (k>=65 && k<=84)
   { if (position[k-65]<0)
    { piecenum++;
     position[k-65]=i*32+j;
     while (grid[i][j+piececols[k-65]]==k)
      piececols[k-65]++;
     while (grid[i+piecerows[k-65]][j]==k)
      piecerows[k-65]++;
    }
   }
  }
 }

 while (grid[0][casecols+2+xcols]==88)
  xcols++;
 while (grid[xrows][casecols+2]==88)
  xrows++;

 for (i=0;i<=piecenum;i++)
 { piecerows[i]--;
  piececols[i]--;
 }
 xrows--;
 xcols--;

 return;
}

int hashvalue(int piecepos[])
{
int i;
int value=0;
for (i=0;i<=piecenum;i++)
value=(value+piecehash[i][piecepos[i]])%HASHTABLESIZE;
return value;
}

int score(int piecepos[])
{ 
int i,j,k;
int grid[480];
int score=0;

for (i=0;i<=479;i++)
grid[i]=0;
makegrid(piecepos,grid);
for (j=0;j<=caserows-xrows;j++)
{ for (k=0;k<=casecols-xcols;k++)
score+=scorecoeff[xcover(grid,j,k)];
}
score+=scoremove[move];
if (score<1)
score=1;
return score;
}

int xcover(int grid[],int row, int column)
{
int i,j;
int answer=0;

for (i=row;i<=row+xrows;i++)
{ for (j=column;j<=column+xcols;j++)
{ if (grid[i*32+j]!=0)
answer++;
} 
} 

return answer;
}

void getsolution(int xmove,int ymove)
{ 
int i,j,pointer;
int temppos[20];

for (i=0;i<=piecenum;i++)
temppos[i]=initpos[i];


pointer=ymove;
for (i=move;i>=0;i--)
{ bestsolution[i][0]=movedata[pointer][0];
bestsolution[i][1]=movedata[pointer][1];
pointer=movedata[pointer][2];
}

for (i=0;i<=move;i++)
{for (j=0;j<=piecenum;j++)
{ if (temppos[j]==bestsolution[i][0])
{ bestsolution[i][0]=j+65;
temppos[j]=bestsolution[i][1];
break;
}
}
}
bestmovenum=move+1;
bestsolution[bestmovenum][0]=88;
bestsolution[bestmovenum][1]=xmove;
return;
}

void printsolution(void)
{
int i,j,k;
if (bestmovenum==1000)
printf("NO SOLUTION\n");
else
{ for (i=0;i<=bestmovenum;i++)
{ j=bestsolution[i][0];
k=bestsolution[i][1];
printf("%c %d-%d\n",j,(k/32)+1,(k%32)+1);
}
}
exit(0);
return;
}

void swap(int i,int j)
{
int temp;

temp=i;
i=j;
j=temp;

return;
}

void pqueueinsert(int pos)
{
int pointer;

pqueuesize++;
pointer=pqueuesize;
while (scoredata[pos]>scoredata[pqueue[pointer/2]] && pointer>1)
{ pqueue[pointer]=pqueue[pointer/2];
pointer/=2;
}
pqueue[pointer]=pos;

return;
}

void pqueuedelete(void)
{
int pointer=1;

pqueuesize--;
while (pointer*2<pqueuesize)
{ pointer*=2;
if (pointer<pqueuesize && scoredata[pqueue[pointer+1]]>scoredata[pqueue[pointer]])
pointer++;
if (scoredata[pqueue[pointer]]>scoredata[pqueue[pqueuesize+1]])
pqueue[pointer/2]=pqueue[pointer];
else
{ pointer/=2;
break;
}
}
pqueue[pointer]=pqueue[pqueuesize+1];

return;
}

int movemin(int piecepos[])
{
int i,j,k;
int answer=21;
int grid[480];

for (i=0;i<=479;i++)
grid[i]=0;

makegrid(piecepos,grid);
for (j=0;j<=caserows-xrows;j++)
{ for (k=0;k<=casecols-xcols;k++)
i=xcovernum(grid,j,k);
if (i<answer)
answer=i;
}

return answer;
}

int xcovernum(int grid[],int row, int column)
{
int i,j,k;
int answer=0,hash[20];

for (i=0;i<=19;i++)
hash[i]=0;

for (i=row;i<=row+xrows;i++)
{ for (j=column;j<=column+xcols;j++)
{ k=grid[i*32+j]; 
if (k!=0 && hash[k-1]==0)
{ answer++;
hash[k-1]=1;
}
}
}

return answer;
}

void checktime(void)
{
int seconds;
static struct tms TMS;
times(&TMS);
seconds = (TMS.tms_stime + TMS.tms_utime)/CLK_TCK ;

if (seconds >= MAXTIME)
{
printsolution();
}
return;
}