/*  POTM ENTRY:  Huckermuck                                  */
/*  Your Name:   Michael Schatz                              */
/*  Your email:  mschatz@cigital.com                         */
/*  g++ -o huckermuck huckermuck.cpp                         */

#include <stack.h>
#include <vector.h>
#include <set.h>
#include <string>

#include <iostream>
#include <signal.h>
#include <unistd.h>
#include <fstream>

static const int TIMEOUT = 599;

// begin md4

extern "C"
{
/*
 ** ********************************************************************
 ** md4.h -- Header file for implementation of                        **
 ** MD4 Message Digest Algorithm                                      **
 ** Updated: 2/13/90 by Ronald L. Rivest                              **
 ** (C) 1990 RSA Data Security, Inc.                                  **
 ** ********************************************************************
 */

 /* MDstruct is the data structure for a message digest computation.
 */
 typedef struct {
   unsigned int buffer[4]; /* Holds 4-word result of MD computation */
   unsigned char count[8]; /* Number of bits processed so far */
   unsigned int done;      /* Nonzero means MD computation finished */
 } MDstruct, *MDptr;

 /* MDbegin(MD)

 ** Input: MD -- an MDptr
 ** Initialize the MDstruct prepatory to doing a message digest
 ** computation.
 */
 extern void MDbegin();

 /* MDupdate(MD,X,count)
 ** Input: MD -- an MDptr
 **        X -- a pointer to an array of unsigned characters.
 **        count -- the number of bits of X to use (an unsigned int).
 ** Updates MD using the first "count" bits of X.
 ** The array pointed to by X is not modified.
 ** If count is not a multiple of 8, MDupdate uses high bits of
 ** last byte.
 ** This is the basic input routine for a user.
 ** The routine terminates the MD computation when count < 512, so
 ** every MD computation should end with one call to MDupdate with a
 ** count less than 512.  Zero is OK for a count.
 */
 extern void MDupdate();

 /* MDprint(MD)
 ** Input: MD -- an MDptr
 ** Prints message digest buffer MD as 32 hexadecimal digits.
 ** Order is from low-order byte of buffer[0] to high-order byte
 ** of buffer[3].
 ** Each byte is printed with high-order hexadecimal digit first.
 */
 extern void MDprint();

/* Implementation notes:
 ** This implementation assumes that ints are 32-bit quantities.
 ** If the machine stores the least-significant byte of an int in the
 ** least-addressed byte (e.g., VAX and 8086), then LOWBYTEFIRST
 ** should be set to TRUE.  Otherwise (e.g., SUNS), LOWBYTEFIRST
 ** should be set to FALSE.  Note that on machines with LOWBYTEFIRST
 ** FALSE the routine MDupdate modifies has a side-effect on its input
 ** array (the order of bytes in each word are reversed).  If this is
 ** undesired a call to MDreverse(X) can reverse the bytes of X back
 ** into order after each call to MDupdate.

 */
 #define TRUE  1
 #define FALSE 0
 #define LOWBYTEFIRST FALSE

 /* Compile-time includes
 */
 #include <stdio.h>
 // #include "md4.h"

 /* Compile-time declarations of MD4 "magic constants".
 */
 #define I0  0x67452301       /* Initial values for MD buffer */
 #define I1  0xefcdab89
 #define I2  0x98badcfe
 #define I3  0x10325476
 #define C2  013240474631     /* round 2 constant = sqrt(2) in octal */
 #define C3  015666365641     /* round 3 constant = sqrt(3) in octal */
 /* C2 and C3 are from Knuth, The Art of Programming, Volume 2
 ** (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley.
 ** Table 2, page 660.
 */

 #define fs1  3               /* round 1 shift amounts */
 #define fs2  7
 #define fs3 11
 #define fs4 19
 #define gs1  3               /* round 2 shift amounts */
 #define gs2  5
 #define gs3  9
 #define gs4 13
 #define hs1  3               /* round 3 shift amounts */
 #define hs2  9
 #define hs3 11
 #define hs4 15

 /* Compile-time macro declarations for MD4.
 ** Note: The "rot" operator uses the variable "tmp".
 ** It assumes tmp is declared as unsigned int, so that the >>
 ** operator will shift in zeros rather than extending the sign bit.
 */
 #define f(X,Y,Z)             ((X&Y) | ((~X)&Z))
 #define g(X,Y,Z)             ((X&Y) | (X&Z) | (Y&Z))
 #define h(X,Y,Z)             (X^Y^Z)
 #define rot(X,S)             (tmp=X,(tmp<<S) | (tmp>>(32-S)))
 #define ff(A,B,C,D,i,s)      A = rot((A + f(B,C,D) + X[i]),s)
 #define gg(A,B,C,D,i,s)      A = rot((A + g(B,C,D) + X[i] + C2),s)
 #define hh(A,B,C,D,i,s)      A = rot((A + h(B,C,D) + X[i] + C3),s)

 /* MDprint(MDp)
 ** Print message digest buffer MDp as 32 hexadecimal digits.
 ** Order is from low-order byte of buffer[0] to high-order byte of
 ** buffer[3].
 ** Each byte is printed with high-order hexadecimal digit first.
 ** This is a user-callable routine.
 */
 void
 MDprint(MDptr MDp)
 { int i,j;
   for (i=0;i<4;i++)
     for (j=0;j<32;j=j+8)
       printf("%02x",(MDp->buffer[i]>>j) & 0xFF);
 }

 /* MDbegin(MDp)
 ** Initialize message digest buffer MDp.
 ** This is a user-callable routine.
 */
 void
 MDbegin(MDptr MDp)
 { int i;
   MDp->buffer[0] = I0;
   MDp->buffer[1] = I1;
   MDp->buffer[2] = I2;
   MDp->buffer[3] = I3;
   for (i=0;i<8;i++) MDp->count[i] = 0;
   MDp->done = 0;
 }

 /* MDreverse(X)
 ** Reverse the byte-ordering of every int in X.
 ** Assumes X is an array of 16 ints.
 ** The macro revx reverses the byte-ordering of the next word of X.
 */
 #define revx { t = (*X << 16) | (*X >> 16); \
      *X++ = ((t & 0xFF00FF00) >> 8) | ((t & 0x00FF00FF) << 8); }
 void MDreverse(unsigned int *X)
 { register unsigned int t;
   revx; revx; revx; revx; revx; revx; revx; revx;
   revx; revx; revx; revx; revx; revx; revx; revx;
 }

 /* MDblock(MDp,X)
 ** Update message digest buffer MDp->buffer using 16-word data block X.
 ** Assumes all 16 words of X are full of data.
 ** Does not update MDp->count.
 ** This routine is not user-callable.
 */
 static void
 MDblock(MDptr MDp, unsigned int *X)
 {
   register unsigned int tmp, A, B, C, D;
 #if LOWBYTEFIRST == FALSE
   MDreverse(X);
 #endif
   A = MDp->buffer[0];
   B = MDp->buffer[1];
   C = MDp->buffer[2];
   D = MDp->buffer[3];
   /* Update the message digest buffer */
   ff(A , B , C , D ,  0 , fs1); /* Round 1 */
   ff(D , A , B , C ,  1 , fs2);
   ff(C , D , A , B ,  2 , fs3);
   ff(B , C , D , A ,  3 , fs4);
   ff(A , B , C , D ,  4 , fs1);
   ff(D , A , B , C ,  5 , fs2);
   ff(C , D , A , B ,  6 , fs3);
   ff(B , C , D , A ,  7 , fs4);
   ff(A , B , C , D ,  8 , fs1);
   ff(D , A , B , C ,  9 , fs2);
   ff(C , D , A , B , 10 , fs3);
   ff(B , C , D , A , 11 , fs4);
   ff(A , B , C , D , 12 , fs1);
   ff(D , A , B , C , 13 , fs2);
   ff(C , D , A , B , 14 , fs3);
   ff(B , C , D , A , 15 , fs4);
   gg(A , B , C , D ,  0 , gs1); /* Round 2 */
   gg(D , A , B , C ,  4 , gs2);
   gg(C , D , A , B ,  8 , gs3);
   gg(B , C , D , A , 12 , gs4);
   gg(A , B , C , D ,  1 , gs1);
   gg(D , A , B , C ,  5 , gs2);
   gg(C , D , A , B ,  9 , gs3);
   gg(B , C , D , A , 13 , gs4);
   gg(A , B , C , D ,  2 , gs1);
   gg(D , A , B , C ,  6 , gs2);
   gg(C , D , A , B , 10 , gs3);
   gg(B , C , D , A , 14 , gs4);
   gg(A , B , C , D ,  3 , gs1);
   gg(D , A , B , C ,  7 , gs2);
   gg(C , D , A , B , 11 , gs3);
   gg(B , C , D , A , 15 , gs4);
   hh(A , B , C , D ,  0 , hs1); /* Round 3 */
   hh(D , A , B , C ,  8 , hs2);
   hh(C , D , A , B ,  4 , hs3);
   hh(B , C , D , A , 12 , hs4);
   hh(A , B , C , D ,  2 , hs1);
   hh(D , A , B , C , 10 , hs2);
   hh(C , D , A , B ,  6 , hs3);
   hh(B , C , D , A , 14 , hs4);
   hh(A , B , C , D ,  1 , hs1);
   hh(D , A , B , C ,  9 , hs2);
   hh(C , D , A , B ,  5 , hs3);
   hh(B , C , D , A , 13 , hs4);
   hh(A , B , C , D ,  3 , hs1);
   hh(D , A , B , C , 11 , hs2);
   hh(C , D , A , B ,  7 , hs3);
   hh(B , C , D , A , 15 , hs4);
   MDp->buffer[0] += A;
   MDp->buffer[1] += B;
   MDp->buffer[2] += C;
   MDp->buffer[3] += D;

 }

 /* MDupdate(MDp,X,count)
 ** Input: MDp -- an MDptr
 **        X -- a pointer to an array of unsigned characters.
 **        count -- the number of bits of X to use.
 **          (if not a multiple of 8, uses high bits of last byte.)
 ** Update MDp using the number of bits of X given by count.
 ** This is the basic input routine for an MD4 user.
 ** The routine completes the MD computation when count < 512, so
 ** every MD computation should end with one call to MDupdate with a
 ** count less than 512.  A call with count 0 will be ignored if the
 ** MD has already been terminated (done != 0), so an extra call with
 ** count 0 can be given as a "courtesy close" to force termination
 ** if desired.
 */
 void
 MDupdate(MDptr MDp, unsigned char *X, unsigned int count)
 { unsigned int i, tmp, bit, byte, mask;
   unsigned char XX[64];
   unsigned char *p;
   /* return with no error if this is a courtesy close with count
   ** zero and MDp->done is true.
   */
   if (count == 0 && MDp->done) return;
   /* check to see if MD is already done and report error */
   if (MDp->done)
          { printf("\nError: MDupdate MD already done."); return; }
   /* Add count to MDp->count */
   tmp = count;
   p = MDp->count;
   while (tmp)
     { tmp += *p;
       *p++ = tmp;
       tmp = tmp >> 8;
     }
   /* Process data */
   if (count == 512)
     { /* Full block of data to handle */
       MDblock(MDp,(unsigned int *)X);
     }
   else if (count > 512) /* Check for count too large */
     { printf("\nError: MDupdate called with illegal count value %d."
              ,count);
       return;

     }
   else /* partial block -- must be last block so finish up */
     { /* Find out how many bytes and residual bits there are */
       byte = count >> 3;
       bit =  count & 7;
       /* Copy X into XX since we need to modify it */
       for (i=0;i<=byte;i++)   XX[i] = X[i];
       for (i=byte+1;i<64;i++) XX[i] = 0;
       /* Add padding '1' bit and low-order zeros in last byte */
       mask = 1 << (7 - bit);
       XX[byte] = (XX[byte] | mask) & ~( mask - 1);
       /* If room for bit count, finish up with this block */
       if (byte <= 55)
         { for (i=0;i<8;i++) XX[56+i] = MDp->count[i];
           MDblock(MDp,(unsigned int *)XX);
         }
       else /* need to do two blocks to finish up */
         { MDblock(MDp,(unsigned int *)XX);
           for (i=0;i<56;i++) XX[i] = 0;
           for (i=0;i<8;i++)  XX[56+i] = MDp->count[i];
           MDblock(MDp,(unsigned int *)XX);
         }
       /* Set flag saying we're done with MD computation */
       MDp->done = 1;
     }
 }

}

// end md4


// begin of Object

class Object
{
public:

  const static int UNDEFINED;

  int m_x_pos;
  int m_y_pos;
  int m_width;
  int m_height;

  char m_name;
  char m_simple_name;

  Object();
  Object(const Object &rhs);
};

const int Object::UNDEFINED = -1;

Object::Object()
{
  m_x_pos = UNDEFINED;
  m_y_pos = UNDEFINED;
  m_width = UNDEFINED;
  m_height = UNDEFINED;

  m_name = '?';
  m_simple_name = '?';
}

Object::Object(const Object &rhs)
{
  m_x_pos = rhs.m_x_pos;
  m_y_pos = rhs.m_y_pos;
  m_width = rhs.m_width;
  m_height = rhs.m_height;

  m_name = rhs.m_name;
  m_simple_name = rhs.m_simple_name;
}

// end of Object


// begin of BoardReader

class BoardReader
{

public:

  void readBoard(std::istream &is);

  char** getBoard();
  int getWidth();
  int getHeight();
  char getMaxLetter();

  Object* getX();

  Object** getObjects();

private:

  char **m_board;
  int m_width;
  int m_height;

  Object m_x;
  Object **m_objects;

  char m_max_letter;

  void calcObjects();
  void findMaxLetter();
  Object *getObject(char name);
};

void BoardReader::readBoard(std::istream &is)
{
  std::string m_strings[15];

  int total_rows = 0;

  for (int i = 0; i < 15; i++)
    {
      std::getline(is, m_strings[i]);

      if (m_strings[i].length() == 0)
	{
	  break;
	}
      total_rows++;
    }

  int space = m_strings[0].find(' ');
  m_width = space;
  m_height = total_rows;

  int x_width = m_strings[0].length() - m_width - 1;
  int x_height = 0;
  
  for
    (int i = 0; i < total_rows; i++)
    {
      if (m_strings[i].length() > (unsigned)m_width)
	{
	  x_height++;
	}
      else
	{
	  break;
	}
    }

  m_x.m_width = x_width;
  m_x.m_height = x_height;
  m_x.m_name = 'X';

  m_board = new char*[m_width];

  for (int i = 0; i < m_width; i++)
    {
      m_board[i] = new char[m_height];
      for (int j = 0; j < m_height; j++)
	{
	  m_board[i][j] = m_strings[j][i];
	}
    }

  calcObjects();
}


void BoardReader::calcObjects()
{
  findMaxLetter();

  int num = (int)m_max_letter - (int)'A' + 1;
  if (num < 1)
    {
      m_objects = 0;
      return;
    }

  m_objects = new Object*[num];

  for (int i = 0; i < num; i++)
    {
      char obj = 'A' + i;
      m_objects[i] = getObject(obj);
    }
}

Object *BoardReader::getObject(char name)
{
  Object *o = new Object();
  o->m_name = name;

  int i, j;
  bool found = false;
  for (i = 0; (i < m_width) && !found; i++)
    {
      for (j = 0; (j < m_height) && !found; j++)
	{
	  if (m_board[i][j] == name)
	    {
	      found = true;
	      o->m_x_pos = i;
	      o->m_y_pos = j;
	      break;
	    }
	}
    }

  for ( ; i < m_width; i++)
    {
      if (m_board[i][j] != name)
	{
	  o->m_width = i - o->m_x_pos;
	  break;
	}
    }
  if (o->m_width == Object::UNDEFINED)
    {
      o->m_width = m_width - o->m_x_pos;
    }

  for (i--, j++ ; j < m_height; j++)
    {
      if (m_board[i][j] != name)
	{
	  o->m_height = j - o->m_y_pos;
	  break;
	}
    }
  if (o->m_height == Object::UNDEFINED)
    {
      o->m_height = m_height - o->m_y_pos;
    }

  return o;
}

void BoardReader::findMaxLetter()
{
  m_max_letter = '\0';

  for (int i = 0; i < m_width; i++)
    {
      for (int j = 0; j < m_height; j++)
	{
	  if (m_board[i][j] != '_')
	    {
	      if (m_board[i][j] > m_max_letter)
		{
		  m_max_letter = m_board[i][j];
		}
	    }
	}
    }
}

char **BoardReader::getBoard()
{
  return m_board;
}

int BoardReader::getWidth()
{
  return m_width;
}

int BoardReader::getHeight()
{
  return m_height;
}

Object *BoardReader::getX()
{
  return &m_x;
}

char BoardReader::getMaxLetter()
{
  return m_max_letter;
}

Object** BoardReader::getObjects()
{
  return m_objects;
}

// end of BoardReader

// begin of AStar

typedef struct
{
  char m_move[3];
} Move;

typedef vector<Move> MoveList;

typedef struct BoardStateStruct
{
  char m_board[20][2];
  MoveList m_moves;
  int m_fitness;

  bool operator<(const struct BoardStateStruct &rhs) const
  {
    // intentionally backwards
    //    return (rhs.m_fitness < m_fitness);

    // now forwards
    return (m_fitness < rhs.m_fitness);
  }

} BoardState;

typedef struct MD4_stuff
{
  int m_buffer[4];

  struct MD4_stuff &operator=(const struct MD4_stuff &rhs)
  {
    if (&rhs != this)
      {
	for (int i = 0; i < 4; i++)
	  {
	    m_buffer[i] = rhs.m_buffer[i];
	  }
      }
    return *this;
  }

  bool operator<(const struct MD4_stuff &rhs) const
  {
    for (int i = 0; i < 4; i++)
      {
	if (m_buffer[i] < rhs.m_buffer[i])
	  {
	    return true;
	  }
	else if (m_buffer[i] > rhs.m_buffer[i])
	  {
	    return false;
	  }
      }
    return false;
  }

  bool operator==(const struct MD4_stuff &rhs) const
  {
    for (int i = 0; i < 4; i++)
      {
	if (m_buffer[i] != rhs.m_buffer[i])
	  {
	    return false;
	  }
      }
    return true;
  }
} MD4Struct;

class AStar
{
public:

  AStar(int width, int height, char max_piece, Object **pieces, Object *x);

  bool findSolution();

  MoveList getSolution();

private:

  bool findSolutionImpl();

  bool checkSetUnique(const char *buffer);
  void getArray(const BoardState &position);
  bool pieceFits(char p, char x, char y);
  void move(char p, BoardState &position, char x, char y);
  void unMove(char p, BoardState &position, char x, char y);
  int getFitness(const BoardState &position);
  void recordSolution(const BoardState &position, char x, char y);
  void simplifyObjects();

  bool breadthFirst();

  static const char EMPTY = '_';

  static const int MAXDEPTH = 150;

  int FIT;
  int DEPTH;


  typedef priority_queue<BoardState> QType;
  
  QType m_q;
  set<MD4Struct> m_repeats;

  unsigned char m_md4_buffer[512];
  int m_width;
  int m_height;
  int m_size;
  int m_max;

  int *m_fitness_store;

  int m_number_pieces;
  char m_max_piece;
  Object **m_objects;
  Object *m_x;

  char *m_array;

  char m_last_x;
  char m_last_y;

  MoveList m_solution;
};

AStar::AStar(int width, int height, char max_piece,
	     Object **pieces, Object *x)
{
  m_width = width;
  m_height = height;
  m_size = width * height;

  m_max_piece = max_piece;
  m_number_pieces = max_piece - 'A' + 1;

  m_objects = pieces;
  m_x = x;

  m_max = m_x->m_width * m_x->m_height;

  m_fitness_store = new int[m_height];

  m_array = new char[m_size];

  m_last_x = 0;
  m_last_y = 0;

  //  FIT = 1;
  //  DEPTH = 20000;

  FIT = 5;
  DEPTH = 1;
}

MoveList AStar::getSolution()
{
  return m_solution;
}

bool AStar::checkSetUnique(const char *o_buffer)
{
  memcpy(m_md4_buffer, o_buffer, m_size);

  MD4Struct md4;
  // calculate MD4 hash
  MDstruct md;
  MDbegin(&md);
  int ctr;
  for (ctr = 0; ctr+64 < m_size; ctr+=64)
    {
      MDupdate(&md, m_md4_buffer + ctr , 512);
    }
  MDupdate(&md, m_md4_buffer + ctr, (m_size - ctr)*8);
  
  for (int i = 0; i < 4; i++)
    {
      md4.m_buffer[i] = md.buffer[i];
    }
  if (m_repeats.find(md4) == m_repeats.end())
    {
      // Not a repeat
      
      m_repeats.insert(md4);
      return true;
    }
  else
    {
      // is a repeat

      return false;
    }

  // end MD 4 stuff
}

void AStar::getArray(const BoardState &position)
{
  memset(m_array, EMPTY, m_size);
  for (int i = 0; i < m_number_pieces; i++)
    {
      Object *o = m_objects[i];
      for (int j = 0; j < o->m_height; j++)
	{
	  memset(m_array + position.m_board[i][0] + 
		 (position.m_board[i][1] + j) * m_width, 
	  o->m_simple_name, o->m_width);
	}
    }
}

bool AStar::pieceFits(char p, char x, char y)
{
  Object *o = m_objects[p - 'A'];
  if ((x + o->m_width > m_width) ||
      (y + o->m_height > m_height))
    {
      // piece won't fit so continue;
      return false;
    }

  for (int i = 0;i < o->m_width; i++)
    {
      for (int j = 0;j < o->m_height; j++)
	{
	  if (m_array[i+x + (j+y)*m_width] != EMPTY)
	    {
	      return false;
	    }
	}
    }

  return true;
}

void AStar::move(char p, BoardState &position, char x, char y)
{
  int piece = p - 'A';
  Object *o = m_objects[piece];

  m_last_x = position.m_board[piece][0];
  m_last_y = position.m_board[piece][1];
  position.m_board[piece][0] = x;
  position.m_board[piece][1] = y;

  for (int j = 0; j < o->m_height; j++)
    {
      memset(m_array + x + (y + j) * m_width, 
	     o->m_simple_name, o->m_width);
      memset(m_array + m_last_x + (m_last_y + j) * m_width, 
	     EMPTY, o->m_width);
    }

}

void AStar::unMove(char p, BoardState &position, char x, char y)
{
  int piece = p - 'A';
  Object *o = m_objects[piece];

  position.m_board[piece][0] = m_last_x;
  position.m_board[piece][1] = m_last_y;

  for (int j = 0; j < o->m_height; j++)
    {
      memset(m_array + x + (y + j) * m_width, 
	     EMPTY, o->m_width);
      memset(m_array + m_last_x + (m_last_y + j) * m_width, 
	     o->m_simple_name, o->m_width);

    }

}

// higher fitness is better
int AStar::getFitness(const BoardState &position)
{
  int x, y;

  for (y = 0; y < m_height; y++)
    {
      m_fitness_store[y] = 0;
      for (x = 0; x < m_x->m_width; x++)
	{
	  if (m_array[x + y*m_width] == EMPTY)
	    {
	      m_fitness_store[y]++;
	    }
	}
    }

  x = 0;
  y = 0;
  int sum = 0;
  int best;

  for (int j = 0; j < m_x->m_height; j++)
    {
      sum += m_fitness_store[j];
    }
  best = sum;
  if (best == m_max)
    {
      recordSolution(position, 0, 0);
      return -1;
    }

  for (y = 0; y < m_height - m_x->m_height; y++)
    {
      sum -= m_fitness_store[y];
      sum += m_fitness_store[y + m_x->m_height];

      if (sum > best)
	{
	  best = sum;
	  if (best == m_max)
	    {
	      recordSolution(position, 0, y+1);
	      return -1;
	    }
	}
    }

  for (x = 0; x < m_width - m_x->m_width; x++)
    {
      for (int j = 0; j < m_height; j++)
	{
	  m_fitness_store[j] -= (m_array[x + j*m_width] == EMPTY) ? 1 : 0;
	  m_fitness_store[j] +=
	    (m_array[ x + m_x->m_width + j*m_width] == EMPTY) ? 1 : 0;
	}
      sum = 0;
      for (int j = 0; j < m_x->m_height; j++)
	{
	  sum += m_fitness_store[j];
	}

      if (best < sum)
	{
	  best = sum;
	  if (best == m_max)
	    {
	      recordSolution(position, x+1, 0);
	      return -1;
	    }
	}

      for (y = 0; y < m_height - m_x->m_height; y++)
	{
	  sum -= m_fitness_store[y];
	  sum += m_fitness_store[y + m_x->m_height];
	  
	  if (sum > best)
	    {
	      best = sum;
	      if (best == m_max)
		{
		  recordSolution(position, x+1, y+1);
		  return -1;
		}
	    }
	}

    }

  int depth = position.m_moves.size() + 1;
  return FIT * best + DEPTH * (MAXDEPTH - depth);

}

void AStar::recordSolution(const BoardState &position, char x, char y)
{
  m_solution = position.m_moves;
  Move m = {{'X', x, y}};
  m_solution.push_back(m);
}

void AStar::simplifyObjects()
{
  for (int i = 0; i < m_number_pieces; i++)
    {
      for (char j = 0; j <= i; j++)
	{
	  Object *o1 = m_objects[i];
	  Object *o2 = m_objects[j];

	  if ((o1->m_width == o2->m_width) &&
	      (o1->m_height == o2->m_height) )
	    {
	      o1->m_simple_name = o2->m_name;
	      break;
	    }
	}
    }
}

bool AStar::findSolution()
{
  simplifyObjects();

  BoardState init_position;

  for (int i = 0; i < m_number_pieces; i++)
    {
      init_position.m_board[i][0] = m_objects[i]->m_x_pos;
      init_position.m_board[i][1] = m_objects[i]->m_y_pos;
    }

  getArray(init_position);

  int fitness = getFitness(init_position);

  if (fitness < 0 )
    {
      return true;
    }

  checkSetUnique(m_array);

  init_position.m_fitness = fitness;
  m_q.push(init_position);

  if (breadthFirst())
    {
      return true;
    }

  return findSolutionImpl();
}

bool AStar::breadthFirst()
{
  const int MAX_SIZE = 128000;
  BoardState array[MAX_SIZE];

  array[0] = m_q.top();
  m_q.pop();

  int start = 0;
  int stop = 1;

  bool full = false;

  while ((start != stop) && !full)
    {
      BoardState position = array[start];

      // don't pop first off till end of move

      getArray(position);

      for (char x = 0; (x < m_width) && !full; x++)
	{
	  for (char y = 0; (y < m_height) && !full; y++)
	    {
	      if (m_array[x + y*m_width] != EMPTY)
		{
		  continue;
		}

	      for (char p = 'A'; (p <= m_max_piece) && !full; p++)
		{
		  if (! pieceFits(p, x, y))
		    {
		      continue;
		    }

		  move(p, position, x, y);
		  if (! checkSetUnique(m_array) )
		    {
		      unMove(p, position, x, y);
		      continue;
		    }
		  Move m = {{p, x, y}};
		  position.m_moves.push_back(m);

		  int fitness = getFitness(position);

		  // stores solution if found
		  if (fitness < 0)
		    {
		      // found solution
		      return true;
		    }
		  position.m_fitness = fitness;
		  array[stop] = position;
		  ++stop;
		  stop %= MAX_SIZE;
		  if (start == stop)
		    {
		      full = true;
		    }
		  position.m_moves.pop_back();
		  unMove(p, position, x, y);
		}
	    }
	}
      // now pop off first element
      ++start;
      start %= MAX_SIZE;
    }

  if (full)
    {
      // filled up queue, go to fitness approach
      for (int i = 0; i < MAX_SIZE; i++)
	{
	  m_q.push(array[i]);
	}
    }

  return false;

}

bool AStar::findSolutionImpl()
{
  while (! m_q.empty())
    {
      BoardState position = m_q.top();
      m_q.pop();
      getArray(position);


      for (char x = 0; x < m_width; x++)
	{
	  for (char y = 0; y < m_height; y++)
	    {
	      if (m_array[x + y*m_width] != EMPTY)
		{
		  continue;
		}

	      for (char p = 'A'; p <= m_max_piece; p++)
		{
		  if (! pieceFits(p, x, y))
		    {
		      continue;
		    }

		  move(p, position, x, y);

		  if (! checkSetUnique(m_array) )
		    {
		      unMove(p, position, x, y);
		      continue;
		    }

		  Move m = {{p, x, y}};
		  position.m_moves.push_back(m);

		  int fitness = getFitness(position);

		  // stores solution if found
		  if (fitness < 0)
		    {
		      // found solution
		      return true;
		    }
		  position.m_fitness = fitness;
		  m_q.push(position);
		  position.m_moves.pop_back();
		  unMove(p, position, x, y);
		}
	    }
	}
    }

  return false;
}

// end of AStar

// begin of main

void timeout()
{
  std::cout << "NO SOLUTION" << std::endl;

  exit(0);
}

void sigalarm(int num)
{
  timeout();
}


int main(int argc, char *argv[])
{
  BoardReader reader;

  signal(SIGALRM, sigalarm);
  alarm(TIMEOUT);

  std::ifstream infile(argv[1]);
  reader.readBoard(infile);


  AStar astar(reader.getWidth(), reader.getHeight(),
	      reader.getMaxLetter(), reader.getObjects(),
	      reader.getX());

  if (astar.findSolution())
    {
      MoveList l = astar.getSolution();
      for (MoveList::iterator i = l.begin(); i != l.end(); i++)
	{
	  std::cout << (*i).m_move[0] << " " << (*i).m_move[2] + 1 << "-"
		    << (*i).m_move[1] + 1 << std::endl;
	}
    }
  else
    {
      std::cout << "NO SOLUTION" << std::endl;
    }

  return 0;
}