#include <iostream>
#include <fstream>

using namespace std;

ofstream file;

const int grid[] = {
 0x0180, 0x03c0, 0x43c0, 0xc3c0,
 0xf7c0, 0x7fe0, 0x1fe0, 0x0fc0,
 0x0fe0, 0x07e0, 0x06f0, 0x07f0,
 0x07f0, 0x03f8, 0x03f0, 0x01e8,
 0x07f8, 0x0ff8, 0x1ffc, 0x3ffe,
 0x3ffe, 0x7ffe, 0x7ffc, 0x7ffc,
 0x7ff8, 0x7ff0, 0x7fe0, 0x3fc0,
 0x1b00,
};

int text[29][16];

const char* words[] = {
"OULU",
"WAKIKUBALIANA",
"IKAWANYESHEA",
"AMEJIPATIA",
"MKAHUBIRI", 
"IMEFAGIWA",
"KUYALINDA",
"UTASHUKA",
"ASIFANYE",
"ANATIWA",
"HAPASWI",
"JITUPE",
"INGALI",
"YULIO",
"HUKAA",
"NDIYE",
"OMEGA",
"SINIA",
"WAITE",
"FALME",
"AHADI",
"LUISA",
"EMAU",
"UKUU",
"ALFA",
"ENYI",
"KOSA",
"MPYA",
"WAMO",
"AHAA", 
}; 

bool wordplaced[30];
int depth[30];
int score = -1;  // OULU doesn't count
int bestscore = -1;

bool isgrid(int row, int col) {
  if (row < 0) return false;
  if (col < 0) return false;
  if (row > 28) return false;
  if (col > 15) return false;
  if (text[row][col] == 0) return false;
  return true;
}

bool hasletter(int row, int col) {
  if (!isgrid(row,col)) return false;
  if (text[row][col] == 1) return false;
  return true;
}

void placeword(int index, int row, int col, bool horiz, int dep) {
  // assumes word is valid.
  const char* word = words[index];
  for (int offset=0; offset<strlen(word); offset++) {
    if (hasletter(row,col)) {
      score += 2;
    } else {
      text[row][col] = index * 26 + (word[offset] - 'A');
    }
    if (horiz) col++;
    else row++;
  }
  score--;
  depth[index] = dep;
  wordplaced[index] = true;
}

void unplaceword(int index, int row, int col, bool horiz) {
  const char* word = words[index];
  if (horiz) {
    for (int offset=0; offset<strlen(word); offset++) {
      if (hasletter(row-1,col) || hasletter(row+1,col)) {
        score -= 2;
      } else {
        text[row][col] = 1;
      }
      col++;
    }
  } else {
    for (int offset=0; offset<strlen(word); offset++) {
      if (hasletter(row,col-1) || hasletter(row,col+1)) {
        score -= 2;
      } else {
        text[row][col] = 1;
      }
      row++;
    }
  }
  score++;
  depth[index] = -1;
  wordplaced[index] = false;
}

int wordfits(int index, int row, int col, bool horiz) {
  // if fits, returns dep.  else returns -1;
  const char* word = words[index];
  if (horiz && hasletter(row,col-1)) return -1;
  if (!horiz && hasletter(row-1,col)) return -1;
  bool touched = false;
  int dep = 40;
  for (int offset=0; offset<strlen(word); offset++) {
    if (!isgrid(row,col)) return -1;
    if (hasletter(row,col)) {
      if (text[row][col] % 26 != (word[offset]-'A') % 26) return -1;
      touched = true;
      int pardep = depth[text[row][col]/26];
      if (pardep < dep) dep = pardep+1;
    } else {
      if (horiz && hasletter(row-1,col)) return -1;
      if (horiz && hasletter(row+1,col)) return -1;
      if (!horiz && hasletter(row,col-1)) return -1;
      if (!horiz && hasletter(row,col+1)) return -1;
    }
    if (horiz) col++;
    else row++;
  }
  if (hasletter(row,col)) return -1; // letter after end
  if (!touched) return -1;
  int maxdep = -1;
  for (int i=0;i<30;i++) {
    if (depth[i] > maxdep) maxdep = depth[i];
    if (depth[i] == dep && i > index) return -1;
  } 
  if (dep < maxdep) return -1;
  return(dep);
}

void print(int wordcount, ostream & outputt) {
  outputt << "Words: " << wordcount - 1<< endl;
  outputt << "Xings: " << ((score + wordcount - 1)/2) << endl;
  outputt << "Score: " << score << endl;
  for (int d=0;d<10;d++) {
    cout << "depth " << (char)(d+'A') << ": ";
    for (int i=0;i<30;i++) {
      if (depth[i] == d)
        cout << words[i] << "(" << i << "), ";
    }
    cout << "\n";
  }
  for (int i=0;i<29;i++) {
    for (int j=0;j<16;j++) {
      if (text[i][j] == 1) outputt << '.';
      else if (text[i][j] == 0) outputt << ' ';
      else outputt << (char)((text[i][j] % 26) + 'A');
    }
    outputt << "   ";
    for (int j=0;j<16;j++) {
      if (text[i][j] == 1) outputt << '.';
      else if (text[i][j] == 0) outputt << ' ';
      else outputt << (char)((depth[text[i][j] / 26]) + 'A');
    }
    outputt << endl;
  }
}

int progress = 0;

void recurse(int wordcount, int depp) {
  if (wordcount > 30) return;
  progress++;
  if (progress > 300) {
    progress = 0;
    cout << "progress:\n";
    print(wordcount, cout);
  }
  if (score >= bestscore) {
    bestscore = score;
    if (score > 26)
      print(wordcount, file);
  }
  bool found = false;
  if (depp > 4 && wordcount < 11) return;  // not dense enough
  for (int w=0;w<30;w++) {
    if (wordplaced[w]) continue;
    for (int row=0;row<29;row++) {
      for (int col=0;col<16;col++) {
        int dep = wordfits(w,row,col,(depp % 2 == 0));
        if (dep == depp) {
          found = true;
          placeword(w,row,col,(depp % 2 == 0),dep);
          recurse(wordcount+1,depp);
          unplaceword(w,row,col,(depp % 2 == 0));
        }
      }
    }
  }
  if (found) recurse(wordcount,depp+1);
}

int main() {
  file.open ("answers2", ios::out);
  for (int i=0;i<29;i++) {
    for (int j=0;j<16;j++) {
      text[i][j] = ((grid[i] >> (15-j))&1)? 1 : 0;
    }
  }
  for (int i=0;i<30;i++) {
    wordplaced[i] = false;
    depth[i] = -1;
  }
  placeword(0, 15, 7, true, 0);
  recurse(1, 1);
  file.close();
}