Last One solver

lastone.cpp

// Last One solver  by nox, 14 Oct. 2011

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

using namespace std;

typedef unsigned long long state_t;
typedef int score_t;

const int N = 33;  // number of cells

class LastOne {
private:
    vector<vector<pair<int, int> > > D;  // table of directions
    state_t start, goal;
    vector<state_t> ans;  // solution

public:
    LastOne(const string datafile="");
    ~LastOne() { }

    void read(const string datafile);
    int movable(state_t state);
    void next(state_t state, vector<state_t>& neighbors);
    bool search();
    void show(state_t state);
    void answer();
};

// initialize and make table
LastOne::LastOne(const string datafile)
{
    if (!datafile.empty()) read(datafile);

    vector<pair<int, int> > v;
    v.push_back(make_pair(1, 2));
    v.push_back(make_pair(3, 8));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(4, 9));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(1, 0));
    v.push_back(make_pair(5, 10));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(4, 5));
    v.push_back(make_pair(8, 15));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(9, 16));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(4, 3));
    v.push_back(make_pair(10, 17));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(7, 8));
    v.push_back(make_pair(13, 20));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(8, 9));
    v.push_back(make_pair(14, 21));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(3, 0));
    v.push_back(make_pair(7, 6));
    v.push_back(make_pair(9, 10));
    v.push_back(make_pair(15, 22));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(4, 1));
    v.push_back(make_pair(8, 7));
    v.push_back(make_pair(10, 11));
    v.push_back(make_pair(16, 23));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(5, 2));
    v.push_back(make_pair(9, 8));
    v.push_back(make_pair(11, 12));
    v.push_back(make_pair(17, 24));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(10, 9));
    v.push_back(make_pair(18, 25));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(11, 10));
    v.push_back(make_pair(19, 26));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(14, 15));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(15, 16));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(8, 3));
    v.push_back(make_pair(14, 13));
    v.push_back(make_pair(16, 17));
    v.push_back(make_pair(22, 27));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(9, 4));
    v.push_back(make_pair(15, 14));
    v.push_back(make_pair(17, 18));
    v.push_back(make_pair(23, 28));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(10, 5));
    v.push_back(make_pair(16, 15));
    v.push_back(make_pair(18, 19));
    v.push_back(make_pair(24, 29));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(17, 16));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(18, 17));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(13, 6));
    v.push_back(make_pair(21, 22));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(14, 7));
    v.push_back(make_pair(22, 23));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(15, 8));
    v.push_back(make_pair(21, 20));
    v.push_back(make_pair(23, 24));
    v.push_back(make_pair(27, 30));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(16, 9));
    v.push_back(make_pair(22, 21));
    v.push_back(make_pair(24, 25));
    v.push_back(make_pair(28, 31));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(17, 10));
    v.push_back(make_pair(23, 22));
    v.push_back(make_pair(25, 26));
    v.push_back(make_pair(29, 32));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(18, 11));
    v.push_back(make_pair(24, 23));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(19, 12));
    v.push_back(make_pair(25, 24));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(22, 15));
    v.push_back(make_pair(28, 29));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(23, 16));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(24, 17));
    v.push_back(make_pair(28, 27));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(27, 22));
    v.push_back(make_pair(31, 32));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(28, 23));
    D.push_back(v);

    v.clear();
    v.push_back(make_pair(29, 24));
    v.push_back(make_pair(31, 20));
    D.push_back(v);
}

// read LastOne data
void LastOne::read(const string datafile)
{
    fstream fs(datafile.c_str(), ios_base::in);
    string line;

    goal = 0x10000;
    start = 0ULL;
    while (getline(fs, line)) {
        for (string::iterator p = line.begin(); p != line.end(); ++p) {
            if (*p == 'o') { start <<= 1; start |= 1ULL; }
            else if (*p == '.') start <<= 1;
        }
    }

    fs.close();
}

// number of movable pieces
int LastOne::movable(state_t state)
{
    int s = 0;
    for (int i = 0; i < N; i++)
        if ((state >> i) & 1)
            for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p)
                s += ((state >> p->first) & 1) & !((state >> p->second) & 1);
    return s;
}

// next states
void LastOne::next(state_t state, vector<state_t>& neighbors)
{
    neighbors.clear();
    for (int i = 0; i < N; i++)
        if ((state >> i) & 1)
            for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p)
                if (((state >> p->first) & 1) & !((state >> p->second) & 1))
                    neighbors.push_back(state ^ (1ULL << p->first) ^ (1ULL << p->second) ^ (1ULL << i));
}

// search solution
bool LastOne::search()
{
    vector<state_t> checked(1, start);
    priority_queue<pair<score_t, vector<state_t> > > queue;
    queue.push(make_pair(1, checked));

    vector<state_t> neighbors;
    while (!queue.empty()) {
        pair<score_t, vector<state_t> > q(queue.top());
        queue.pop();
        state_t last = q.second.back();
        if (last == goal) {
            ans = q.second;
            return true;
        }
        next(last, neighbors);
        for (vector<state_t>::iterator p = neighbors.begin(); p != neighbors.end(); ++p) {
            if (binary_search(checked.begin(), checked.end(), *p)) continue;
            if (movable(*p) == 0 && *p != goal) continue;
            checked.insert(upper_bound(checked.begin(), checked.end(), *p), *p);
            vector<state_t> path(q.second);
            path.push_back(*p);
            queue.push(make_pair(static_cast<score_t>(path.size()), path));
        }
    }

    return false;
}

// show state
void LastOne::show(state_t state)
{
    string line;

    while (state) {
        if (state & 1ULL) line.push_back('o');
        else line.push_back('.');
        state >>= 1;
    }

    int n = N - line.size();
    for (int i = 0; i < n; i++) line.push_back('.');
    reverse(line.begin(), line.end());

    cout << "  " << line.substr(0, 3) << endl;
    cout << "  " << line.substr(3, 3) << endl;
    cout << line.substr(6, 7) << endl;
    cout << line.substr(13, 7) << endl;
    cout << line.substr(20, 7) << endl;
    cout << "  " << line.substr(27, 3) << endl;
    cout << "  " << line.substr(30, 3) << endl;
}

// show solution
void LastOne::answer()
{
    for (vector<state_t>::iterator p = ans.begin(); p != ans.end(); ++p) {
        show(*p);
        cout << endl;
    }
}

int main(int argc, char* argv[])
{
    if (argc < 2) {
        cerr << "Usage: " << argv[0] << " datafile" << endl;
        exit(1);
    }

    LastOne lastone(argv[1]);

    if (lastone.search()) lastone.answer();
    else cout << "No solution." << endl;

    return 0;
}

http://handasse.blogspot.com/2011/10/blog-post_19.html