// ----------------------------------------------------------------------------- // bridges.cpp : find low solutions for Mikero's grid puzzles fast // // See http://www.benzedrine.cx/grid-puzzle.txt for a description of this // algorithm. Feedback to Daniel Hartmeier , please. // // ANSI C++, should compile on any compliant compiler. 32-bit unsigneds are // required. Status information is sent to cerr, solutions to cout, so if you // run the program like "program.exe > out.txt", you get the status information // on screen and the solutions in a text file (best solution at the bottom). // // The solutions do not include a complete path, but a clear description, for // instance: // // Found tree with score 83 // // A--B C--D // | | | |// E F G H // | | | |// I J--K L // | | | |// M N O P // // Start at M // When coming to J, exit through K // When coming to K, exit through G // // The second type of direction means that you have to enter and return from // any additional bridges besides the one you're coming from and the one you // have to exit through. Here, the complete path is MIEABFJNJKOKGCDHLP. // Note that if there are several side-paths in a city, the order in which // you complete them is not relevant for the score. // ----------------------------------------------------------------------------- #include #include #include #include #include #include // ----------------------------------------------------------------------------- // Global variables // ----------------------------------------------------------------------------- unsigned *costs; unsigned size; unsigned square_size; unsigned key_size; // ----------------------------------------------------------------------------- // Forward declarations // ----------------------------------------------------------------------------- class Tree; class Town; class Bridge; class TreeRepresentation; typedef std::set< Tree, std::less > TreeSet; typedef std::set< const Bridge*, std::less > BridgeSet; typedef std::stack > Path; inline unsigned char letter(unsigned number); inline void sumBridges(Path *path, const Town *town, const Bridge *bridge, unsigned &sumReturn, unsigned &sumNoReturn); // ----------------------------------------------------------------------------- // Class Tree : low-level representation of the bridges of a grid // // Example: 3x3 grid -> 12 bridges -> 12 bits needed // To simplify access, we waste some bits and enumerate the bridges like this: // // A 0 B 2 C 4 // 1 3 5 // D 6 E 8 F 10 // 7 9 11 // G 12 H 14 I 16 // 13 15 17 // // Bits 4, 10, 13, 15, 16 and 17 are never used // ----------------------------------------------------------------------------- class Tree { public: inline Tree(); inline Tree(const Tree &other); inline ~Tree(); inline bool operator<(const Tree &other) const; inline bool isBridgeSet(unsigned i) const; inline unsigned getScore() const; inline void setScore(unsigned s); void insertRelated(TreeSet &trees, unsigned &inserted, unsigned &bestScore) const; bool isSpanning() const; void print() const; private: unsigned *key, score, limit; }; // ----------------------------------------------------------------------------- // Class Town high-level representation of a town (for TreeRepresentation) // ----------------------------------------------------------------------------- class Town { public: Town(unsigned number = 0); inline ~Town(); inline unsigned getNumber() const; inline const BridgeSet &getBridges() const; inline void insertBridge(const Bridge *bridge); inline void eraseBridge(const Bridge *bridge); private: unsigned number; BridgeSet bridges; }; // ----------------------------------------------------------------------------- // Class Bridge : high-level representation of a bridge (for TreeRepresentation) // ----------------------------------------------------------------------------- class Bridge { public: inline Bridge(Town *a, Town *b, unsigned cost); inline ~Bridge(); inline unsigned getCost() const; inline Town *getPeer(const Town *x) const; private: Town *a, *b; unsigned cost; }; // ----------------------------------------------------------------------------- // Class TreeRepresentation : high-level representation of the bridges of a grid // // To simplify the implementation of the calculateScore() function, a low-level // tree is first converted into a (temporary) hi-level tree, and the calculation // is done using this model. // ----------------------------------------------------------------------------- class TreeRepresentation { public: inline TreeRepresentation(const Tree &tree); inline ~TreeRepresentation(); inline unsigned calculateScore(bool explain = false) const; inline const Town *getTown(unsigned i) const; private: Town *towns; }; // ----------------------------------------------------------------------------- // Class Tree implementation // ----------------------------------------------------------------------------- inline Tree::Tree() { key = new unsigned[key_size]; for (unsigned i = 0; i < key_size; ++i) key[i] = 0; for (unsigned y = 0; y < size; ++y) for (unsigned x = 0; x < size; ++x) { unsigned i = (y*size + x)*2; if ((y == 0) && (x < size-1)) key[ i /32] |= (1 << ( i %32)); if (y < size-1) key[(i+1)/32] |= (1 << ((i+1)%32)); } score = 999999; limit = square_size-2*size+2; } inline Tree::Tree(const Tree &other) : score(other.score), limit(other.limit) { key = new unsigned[key_size]; for (unsigned i = 0; i < key_size; ++i) key[i] = other.key[i]; } inline Tree::~Tree() { delete [] key; } inline bool Tree::operator<(const Tree &other) const { if (score != other.score) return score < other.score; else { int i = key_size-1; while ((i >= 0) && (key[i] == other.key[i])) i--; if (i < 0) return false; else return key[i] < other.key[i]; } } inline bool Tree::isBridgeSet(unsigned i) const { return key[i/32] & (1 << (i%32)); } inline unsigned Tree::getScore() const { return score; } inline void Tree::setScore(unsigned s) { score = s; return; } void Tree::insertRelated(TreeSet &trees, unsigned &inserted, unsigned &bestScore) const { for (unsigned d = 0; d < square_size*2; ++d) if (!(key[d/32] & (1 << (d%32)))) if (!((d%(2*size) == 2*size-2) || (((d/(2*size) == size-1) && (d%2 == 1))))) for (unsigned s = 0; s < square_size*2; ++s) if (key[s/32] & (1 << (s%32))) { Tree related(*this); related.key[s/32] ^= (1 << (s%32)); related.key[d/32] |= (1 << (d%32)); related.limit--; if (related.isSpanning()) { related.score = 999999; if (trees.find(related) == trees.end()) { related.setScore(TreeRepresentation(related).calculateScore()); if (related.score < bestScore) { bestScore = related.score; related.print(); TreeRepresentation(related).calculateScore(true); for (unsigned i = 0; i < 79; ++i) cout << '-'; cout << endl; } if (related.limit) trees.insert(related); inserted++; if (!(inserted % 1000)) cerr << "inserted " << inserted << ", size " << trees.size() << ", best score " << bestScore << endl; } } } return; } bool Tree::isSpanning() const { bool *visited = new bool[square_size]; for (unsigned i = 0; i < square_size; ++i) visited[i] = false; int x = 0, y = 0, d = 1, count = 1; visited[0] = true; do { int rx = x, ry = y, b; if (d == 0) { ry--; b = 1; } else if (d == 1) { b = 0; } else if (d == 2) { b = 1; } else { rx--; b = 0; } unsigned i = (ry*size + rx)*2 + b; if ((rx >= 0) && (ry >= 0) && (rx < (b == 0 ? size-1 : size)) && (ry < (b == 1 ? size-1 : size)) && (key[i/32] & (1 << (i%32)))) { if (d == 0) y--; else if (d == 1) x++; else if (d == 2) y++; else x--; if (!visited[y*size+x]) { visited[y*size+x] = true; count++; } d = (d + 3) % 4; } else d = (d + 1) % 4; } while ((x != 0) || (y != 0) || (d != 1)); delete [] visited; return count == square_size; } void Tree::print() const { cout << "Found tree with score " << score << endl << endl; unsigned i; for (unsigned y = 0; y < size; ++y) { for (unsigned x = 0; x < size; ++x) { cout << letter(y*size+x); if (x < size-1) { i = y*size*2 + x*2 + 0; if (key[i/32] & (1 << (i%32))) cout << "--"; else cout << " "; } } cout << endl; if (y < size-1) { for (unsigned x = 0; x < size; ++x) { i = y*size*2 + x*2 + 1; if (key[i/32] & (1 << (i%32))) cout << "|"; else cout << " "; if (x < size-1) cout << " "; } cout << endl; } } cout << endl; return; } // ----------------------------------------------------------------------------- // Class Town implementation // ----------------------------------------------------------------------------- inline Town::Town(unsigned number) : number(number) { } inline Town::~Town() { while (!bridges.empty()) delete *bridges.begin(); } inline unsigned Town::getNumber() const { return number; } inline const BridgeSet &Town::getBridges() const { return bridges; } inline void Town::insertBridge(const Bridge *bridge) { bridges.insert(bridge); return; } inline void Town::eraseBridge(const Bridge *bridge) { bridges.erase(bridge); return; } // ----------------------------------------------------------------------------- // Class Bridge implementation // ----------------------------------------------------------------------------- inline Bridge::Bridge(Town *a, Town *b, unsigned cost) : a(a), b(b), cost(cost) { a->insertBridge(this); b->insertBridge(this); } inline Bridge::~Bridge() { a->eraseBridge(this); b->eraseBridge(this); } inline unsigned Bridge::getCost() const { return cost; } inline Town *Bridge::getPeer(const Town *x) const { if (x == a) return b; else return a; } // ----------------------------------------------------------------------------- // Class TreeRepresentation implementation // ----------------------------------------------------------------------------- inline TreeRepresentation::TreeRepresentation(const Tree &tree) { towns = new Town[square_size]; for (unsigned i = 0; i < square_size; ++i) towns[i] = Town(i); // create bridges for (unsigned y = 0; y < size; ++y) for (unsigned x = 0; x < size; ++x) { unsigned i = (y*size + x)*2; if (tree.isBridgeSet(i )) new Bridge(&towns[y*size+x], &towns[y*size+(x+1)], costs[i ]); if (tree.isBridgeSet(i+1)) new Bridge(&towns[y*size+x], &towns[(y+1)*size+x], costs[i+1]); } } inline TreeRepresentation::~TreeRepresentation() { delete [] towns; } inline const Town *TreeRepresentation::getTown(unsigned i) const { return &towns[i]; } inline unsigned TreeRepresentation::calculateScore(bool explain) const { Path *minpath = 0; if (explain) minpath = new Path; unsigned minimum = 999999, x = 0; for (unsigned i = 0; i < square_size; ++i) { if (towns[i].getBridges().size() == 1) { Path *path = 0; if (explain) { path = new Path; } unsigned sumReturn = 0, sumNoReturn = 0; sumBridges(path, &towns[i], *towns[i].getBridges().begin(), sumReturn, sumNoReturn); if (sumNoReturn < minimum) { x = i; minimum = sumNoReturn; if(explain) *minpath = *path; } if (explain) delete path; } } if (explain) { std::string p = "Start at "; p.append(1, letter(x)); minpath->push(p); do { cout << minpath->top() << endl; minpath->pop(); } while (!minpath->empty()); } return minimum; } // ----------------------------------------------------------------------------- // letter() converts city numbers into letters // ----------------------------------------------------------------------------- inline unsigned char letter(unsigned number) { unsigned char c = number % 52; return c + (c < 26 ? 65 : 71); } // ----------------------------------------------------------------------------- // sumBridges() : return minimal cost of going from a town over a bridge // ----------------------------------------------------------------------------- inline void sumBridges(Path *path, const Town *town, const Bridge *bridge, unsigned &sumReturn, unsigned &sumNoReturn) { Town *peer = bridge->getPeer(town); sumNoReturn += bridge->getCost(); sumReturn += 2*bridge->getCost(); // there's a maximum of 3 other bridges (exluding the one we're coming from) unsigned s[3][3]; s[0][0] = s[0][1] = s[1][0] = s[1][1] = s[2][0] = s[2][1] = 0; unsigned i = 0; for (BridgeSet::const_iterator b = peer->getBridges().begin(); b != peer->getBridges().end(); ++b) if (*b != bridge) { sumBridges(path, peer, *b, s[i][0], s[i][1]); Town *t = (*b)->getPeer(peer); s[i][2] = t->getNumber(); i++; } if (i == 0) { // no further routes (we ended up in a leaf) return; } else if (i == 1) { // only one possible route (we have to take it) sumReturn += s[0][0]; sumNoReturn += s[0][1]; } else { // two or three possible routes (find the cheapest combination) // if we return, all routes must return for (unsigned j = 0; j < i; ++j) sumReturn += s[j][0]; // if we don't return, terminate in the most expensive route unsigned x, m, min = 999999; for (unsigned j = 0; j < i; ++j) { m = 0; for (unsigned k = 0; k < i; ++k) m += s[k][(k == j ? 1 : 0)]; if (m < min) { min = m; x = j; } } sumNoReturn += min; if (path) { std::string p = "When coming to "; p.append(1, letter(peer->getNumber())); p.append(", exit through "); p.append(1, letter(s[x][2])); path->push(p); } } return; } // ----------------------------------------------------------------------------- // loadCosts() reads an input file containing the cost values (detecting and // supporting different grid sizes automatically) // // The input is expected in the following format (example 3x3 grid) // // 9 1 // 1 1 1 // 9 1 // 1 1 9 // 1 5 // // Superflous whitespace (spaces, tabs, newlines) is ignored // ----------------------------------------------------------------------------- unsigned *loadCosts(const char *filename) { unsigned *costs = 0; ifstream f; f.open(filename); if (!f.good()) cerr << "Couldn't open input file " << filename << endl; else { unsigned count = 0, cost; while (f >> cost) count++; size = 1; while (2*size*(size-1) < count) size++; if (2*size*(size-1) != count) cerr << "Input file " << filename << " contains invalid number of values (" << count << ")" << endl; else { square_size = size*size; key_size = (2*size*size-1)/32+1; costs = new unsigned[size*size*2]; f.close(); f.clear(); f.open(filename); for (unsigned y = 0; y < size; ++y) { for (unsigned x = 0; x < size-1; ++x) { f >> cost; costs[(y*size+x)*2] = cost; } if (y < size-1) for (unsigned x = 0; x < size; ++x) { f >> cost; costs[(y*size+x)*2+1] = cost; } } } f.close(); } return costs; } // ----------------------------------------------------------------------------- // Main program // ----------------------------------------------------------------------------- int main(int argc, const char *argv[]) { if (sizeof(unsigned) < 4) { cerr << "Error: sizeof(unsigned) < 4" << endl; return EXIT_FAILURE; } if (sizeof(unsigned) > 4) cerr << "Warning: sizeof(unsigned) > 4, wasting too much memory" << endl; if (argc != 2) { cerr << "Invalid number of parameters" << endl; return EXIT_FAILURE; } else if (!(costs = loadCosts(argv[1]))) return EXIT_FAILURE; TreeSet trees; Tree initial; initial.setScore(TreeRepresentation(initial).calculateScore()); trees.insert(initial); unsigned inserted = 1, bestScore = 999999; cerr << "Starting" << endl; TreeSet::const_iterator i = trees.begin(); do { Tree tree(*i); tree.insertRelated(trees, inserted, bestScore); trees.erase(tree); tree.setScore(999999); trees.insert(tree); i = trees.begin(); } while ((i != trees.end()) && ((*i).getScore() < 999999)); cerr << "Done" << endl; delete [] costs; return EXIT_SUCCESS; }