// -----------------------------------------------------------------------------
// bridges.cpp : find low solutions for Mikero's grid puzzles fast
//
// See http://www.benzedrine.ch/grid-puzzle.txt for a description of this
// algorithm. Feedback to Daniel Hartmeier <daniel@benzedrine.ch>, 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 <iostream>
#include <fstream>
#include <set>
#include <stack>
#include <deque>
#include <string>

// -----------------------------------------------------------------------------
// 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<Tree> > TreeSet;
typedef std::set< const Bridge*, std::less<const Bridge*> > BridgeSet;
typedef std::stack<std::string, std::deque<std::string> > 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;
  }