Hi,
Here's the code I wrote on 0.94 level (sorry, haven't tried 0.95 much yet).
It will require the following change in gaddag.h in order to handle the
negative indexing generated by the gaddgag minimization:
inline const GaddagNode *
GaddagNode::firstChild() const
{
int p = (data[0] << 16) + (data[1] << 8) + (data[2]);
if (p == 0) {
return 0;
} else {
if(p & 0x00800000)
p |= 0xff000000;
return this + p;
}
}
That's it. With that change the minimized gaddag, quacletest seemed to
work. Let me know how it goes.
On a separate note, every time I compile the Qt based code, it fails to
find the built libraries, because they are placed either under release
or debug directories. Am I missing something to make my life easier?
Francisco Moraes
/*
* Quackle -- Crossword game artificial intelligence and analysis tool
* Copyright (C) 2005-2006 Jason Katz-Brown and John O'Laughlin.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*/
#include <stdio.h>
#include <string>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
using namespace std;
class Node {
public:
char c;
bool t;
vector<Node> children;
Node* parent;
int pointer;
int location;
int oldpointer;
bool lastchild;
void pushword(string word);
void print(string prefix, int nthChild, Node* parent);
bool dexplored;
bool sexplored;
bool lexplored;
int d;
int s;
int l;
int depth();
int subtreesize();
int lettersum();
bool equals(Node &n);
bool deleted;
Node* cloneof;
bool written;
};
vector< Node* > nodelist;
Node root;
vector< int > ofdepth[20][100];
bool Node::equals(Node &n)
{
if (c != n.c)
return false;
if (children.size() != n.children.size())
return false;
if (t != n.t)
return false;
if (l != n.l)
return false;
if (s != n.s)
return false;
if (d != n.d)
return false;
for (int i = 0; i < children.size(); i++)
if (!children[i].equals(n.children[i]))
return false;
return true;
}
int Node::depth()
{
if (dexplored)
return d;
dexplored = true;
if (children.size() == 0)
{
d = 1;
return d;
}
int childmax = 0;
for (int i = 0; i < children.size(); i++)
{
int d = children[i].depth();
if (d > childmax)
childmax = d;
}
d = 1 + childmax;
return d;
}
int Node::subtreesize()
{
if (sexplored)
return s;
sexplored = true;
if (children.size() == 0)
{
s = 1;
return s;
}
int childsum = 0;
for (int i = 0; i < children.size(); i++)
{
int s = children[i].subtreesize();
childsum += s;
}
s = 1 + childsum;
return s;
}
int Node::lettersum()
{
if (lexplored)
return l;
lexplored = true;
int thisletter = c - 'A' + 1;
if (children.size() == 0)
{
l = thisletter;
return l;
}
int childsum = 0;
for (int i = 0; i < children.size(); i++)
{
int s = children[i].lettersum();
childsum += s;
}
l = thisletter + childsum;
return l;
}
void Node::print(string prefix, int nthChild, Node* parent) {
written = true;
if (t) {
// cout << prefix << endl;
}
// cout << "prefix: " << prefix << ", children: " << children.size() <<
", deleted: " << deleted << ", oldpointer: " << oldpointer << ", nthChild: " <<
nthChild << endl;
if (children.size() == 0)
{
// cout << " no children. nothing to do." << endl;
return;
}
if (!deleted)
{
// cout << " Setting pointer to " << nodelist.size() << " before
I push_back the children." << endl;
pointer = nodelist.size();
}
else
{
pointer = cloneof->pointer;
// cout << " Setting pointer to clone's (" << pointer << ") and
not pushing anything." << endl;
}
if (!deleted)
{
for (int i = 0; i < children.size(); i++) {
children[i].parent = this;
nodelist.push_back(&children[i]);
}
for (int i = 0; i < children.size(); i++) {
if (!children[i].deleted)
children[i].print(prefix + children[i].c, i, this);
else if (!children[i].cloneof->written)
children[i].cloneof->print(prefix +
children[i].c, i, this);
}
}
if (children.size() > 0)
children[children.size() - 1].lastchild = true;
}
void Node::pushword(string word) {
if (word.length() == 0) {
t = true;
}
else {
char first = word[0];
string rest = word.substr(1, word.length() - 1);
int index = -1;
// cout << "first: " << first << ", rest: " << rest << endl;
for (int i = 0; i < children.size(); i++) {
if (children[i].c == first) {
index = i;
i = children.size();
}
}
if (index == -1) {
Node n;
n.c = first;
n.t = false;
n.pointer = 0;
n.oldpointer = 0;
n.lastchild = false;
children.push_back(n);
index = children.size() - 1;
}
children[index].pushword(rest);
}
dexplored = false;
sexplored = false;
lexplored = false;
deleted = false;
written = false;
}
void minimize()
{
nodelist[0]->depth();
nodelist[0]->subtreesize();
nodelist[0]->lettersum();
for (int i = 0; i < nodelist.size(); i++)
{
int d = nodelist[i]->d;
if ((d >= 1) & (d <= 20))
ofdepth[d - 1][nodelist[i]->l%100].push_back(i);
}
for (int d = 0; d < 20; d++)
{
for (int l = 0; l < 100; l++)
{
//cout << "l: " << l << endl;
if (ofdepth[d][l].size() > 0)
for (vector<int>::iterator it =
ofdepth[d][l].begin(); it != ofdepth[d][l].end() - 1; it++)
{
if (!nodelist[(*it)]->deleted)
{
for (vector<int>::iterator jt =
it + 1; jt != ofdepth[d][l].end(); jt++)
{
if
(!nodelist[(*jt)]->deleted)
{
// cout <<
"Comparing " << (*it) << " and " << (*jt) << endl;
if
(nodelist[(*it)]->equals(nodelist[(*jt)][0]))
{
//
cout << "Hey! " << (*it) << " == " << (*jt) << endl;
//
ones[l].erase(jt);
nodelist[(*jt)]->deleted = true;
nodelist[(*jt)]->cloneof = nodelist[(*it)];
}
}
}
}
}
}
for (int i = 0; i < nodelist.size(); i++)
{
nodelist[i]->oldpointer = nodelist[i]->pointer;
nodelist[i]->pointer = 0;
nodelist[i]->written = false;
}
}
nodelist.clear();
nodelist.push_back(&root);
root.print("", 0, NULL);
cout << "nodelist.size(): " << nodelist.size() << endl;
}
int main() {
ifstream file("gaddaginput.raw");
root.t = false;
root.c = '.';
root.pointer = 0;
root.lastchild = true;
while(!file.eof()) {
string word;
file >> word;
if (!file.eof()) {
root.pushword(word);
}
}
nodelist.push_back(&root);
root.print("", 0, NULL);
cout << "nodelist.size(): " << nodelist.size() << endl;
minimize();
ofstream out("output.gaddag", ios::out | ios::binary);
for (int i = 0; i < nodelist.size(); i++) {
//cout << nodelist[i]->c << " " << nodelist[i]->pointer << " " <<
nodelist[i]->t << " " << nodelist[i]->lastchild << endl;
Node* n = nodelist[i];
unsigned int p;
if (n->deleted)
{
p = (unsigned int)(n->cloneof->pointer);
// n = nodelist[i]->cloneof;
}
else
p = (unsigned int)(n->pointer);
if(p != 0)
p -= i;
char bytes[4];
unsigned char n1 = (p & 0x00FF0000) >> 16;
unsigned char n2 = (p & 0x0000FF00) >> 8;
unsigned char n3 = (p & 0x000000FF);
unsigned char n4;
if (n->c == '^') {
n4 = 27; // 26 is reserved for blank
} else
n4 = n->c - 'A';
if (n->t) {
n4 |= 32;
}
if (n->lastchild) {
n4 |= 64;
}
bytes[0] = n1; bytes[1] = n2; bytes[2] = n3; bytes[3] = n4;
out.write(bytes, 4);
}
}
