Flood-it solver

#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <assert.h>
#include <time.h>
#include <map>
#include <iomanip>

const int numColors = 6;
const int problemSize = 14;
const int boardSize = 25; // ceil( 14 * 14 / 8 )

int *problem[problemSize];
uint8_t colorCount[numColors];
char colorTranslation[numColors] = {
    '0',
    '1',
    '2',
    '3',
    '4',
    '5',
};

void randomProblem( void ) {
    srandom( time( 0 ) );

    for ( int c = 0; c < numColors; ++c ) {
        colorCount[c] = 0;
    }
    for ( int y = 0; y < problemSize; ++y ) {
        problem[y] = new int[problemSize];
        for ( int x = 0; x < problemSize; ++x ) {
            problem[y][x] = random() % numColors;
            colorCount[problem[y][x]] += 1;
        }
    }
}

unsigned char bitToMask[] = {
    0x1,
    0x2,
    0x4,
    0x8,
    0x10,
    0x20,
    0x40,
    0x80
 };

class BoardState {
public:
    unsigned char bits_[boardSize];
    uint8_t colorsLeft_[numColors];

    static const BoardState emptyExample;
    static const BoardState goalState;

    BoardState() {
        memset( bits_, 0, boardSize );
        for ( int c = 0; c < numColors; ++c ){
            colorsLeft_[c] = colorCount[c];
        }
    }

    BoardState( bool ) {
        int byte, mask;
        coordinatesToBit( problemSize - 1, problemSize - 1, byte, mask );
        memset( bits_, 0xff, byte );
        bits_[byte] = mask | ( mask - 1 );

        for ( int c = 0; c < numColors; ++c ){
            colorsLeft_[c] = 0;
        }
    }

    BoardState & operator=( const BoardState &other ) {
        memcpy( bits_, other.bits_, boardSize );
        for ( int c = 0; c < numColors; ++c ) {
            colorsLeft_[c] = other.colorsLeft_[c];
        }
        return *this;
    }

    bool operator==( const BoardState &other ) const {
        return memcmp( bits_, other.bits_, boardSize ) == 0;
    }

    bool operator!=( const BoardState &other ) const {
        return memcmp( bits_, other.bits_, boardSize ) != 0;
    }

    bool empty(void) const {
        return *this == emptyExample;
    }

    void coordinatesToBit( int x, int y, int &byte, int &mask ) const {
        int offset = y * problemSize + x;
        byte = offset / 8;
        mask = bitToMask[ offset % 8 ];
    }

    void set( int x, int y ) {
        int byte, mask;
        coordinatesToBit( x, y, byte, mask );
        bits_[byte] |= mask;
        int c = problem[y][x];
        colorsLeft_[c] -= 1;
    }

    bool present( int x, int y ) const {
        int byte, mask;
        coordinatesToBit( x, y, byte, mask );
        return bits_[byte] & mask;
    }

    int numColorsLeft( void ) const {
        int total = 0;
        for ( int c = 0; c < numColors; ++c ) {
            if ( colorsLeft_[c] > 0 ) total += 1;
        }
        return total;
    }

    bool adjacentPresent( int x, int y ) const {
        return ( x > 0 && present( x - 1, y ) ) ||
            ( y > 0 && present( x, y - 1 ) ) ||
            ( x < problemSize - 1 && present( x + 1, y ) ) ||
            ( y < problemSize - 1 && present( x, y + 1 ) );
    }

    void markDfs( int x, int y, int color ) {
        if ( present( x, y ) ) return;

        set( x, y );
        if ( x < problemSize - 1 && problem[y][x+1] == color )
            markDfs( x+1, y, color );
        if ( y < problemSize - 1 && problem[y+1][x] == color )
            markDfs( x, y+1, color );
        if ( x > 0 && problem[y][x-1] == color )
            markDfs( x-1, y, color );
        if ( y > 0 && problem[y-1][x] == color )
            markDfs( x, y-1, color );
    }

    void successor( int color, BoardState &out ) const {
        out = *this;

        for ( int y = 0; y < problemSize; ++y ) {
            for ( int x = 0; x < problemSize; ++x ) {
                if ( problem[y][x] == color && !present( x, y ) ) {
                    if ( adjacentPresent( x, y ) ) {
                        out.markDfs( x, y, color );
                    }
                }
            }
        }
    }

    bool possiblePredecessorTo( const BoardState &other ) const {
        // Can this state evolve into 'other'?
        // We should have no '1's where the other state has '0's.
        // 0 0 -- True
        // 1 0 -- False
        // 0 1 -- True
        // 1 1 -- True
        for ( int b = 0; b < boardSize; ++b ) {
            uint8_t tmp = bits_[b] & ~( other.bits_[b] );
            if ( tmp ) return false;
        }
        return true;
    }

    uint64_t hashValue( void ) const {
        uint64_t key = 0;
        for ( int i = 0; i < boardSize; ++i ) {
            key = ( key << 8 ) ^ ( key >> 56 ) ^ bits_[i];
        }

        // Those keys are *decidedly* nonrandom, use a mixing function to
        // distribute what entropy exists.
        // copied from http://www.concentric.net/~ttwang/tech/inthash.htm
        key = (~key) + (key << 21); // key = (key << 21) - key - 1;
        key = key ^ ( (key >> 24) | ( key >> 40 ) ) ; // key >>> 24
        key = (key + (key << 3)) + (key << 8); // key * 265
        key = key ^ ( (key >> 14) | ( key >> 50 ) ); // key >>> 14
        key = (key + (key << 2)) + (key << 4); // key * 21
        key = key ^ ( (key >> 28) | ( key >> 38 ) ); // key >>> 28;
        key = key + (key << 31);
        return key;
    }

    void print( std::ostream &out ) const {
        for ( int y = 0; y < problemSize; ++y ) {
            for ( int x = 0; x < problemSize; ++x ) {
                if ( present( x, y ) ) out << "X";
                else out << ".";
            }
            out << std::endl;
        }
        out << "Squares left:";
        for ( int c = 0; c < numColors; ++c ) {
            out << " " << (uint16_t)colorsLeft_[c];
        }
        out << std::endl;
    }

    void printWithProblem( std::ostream &out ) const {
        for ( int y = 0; y < problemSize; ++y ) {
            for ( int x = 0; x < problemSize; ++x ) {
                if ( present( x, y ) ) out << '*';
                else out << colorTranslation[ problem[y][x] ];
            }
            out << std::endl;
        }
        out << std::endl;
    }
} __attribute__(( packed ));

const BoardState BoardState::emptyExample;
const BoardState BoardState::goalState = true;

class BoardHashTable {
public:
    int numEntries_;
    int numUsed_;
    int depth_;
    int numCollisions_;

    BoardState *table_;

    BoardHashTable( int size, int depth = 0 ) {
        table_ = (BoardState *)calloc( size, sizeof( BoardState ) );
        numUsed_ = 0;
        numEntries_ = size;
        depth_ = depth;
        numCollisions_ = 0;
    }

    ~BoardHashTable() {
        free( table_ );
    }

    BoardState & bucket( const BoardState &s ) const {
        uint64_t offset = s.hashValue() % numEntries_;
        // std::cout << "hash " << s.hashValue() << " bucket " << offset << std::endl;
        // Quick and dirty linear probing.
        // FIXME: use quadratic instead?
        while ( !table_[offset].empty() && table_[offset] != s ) {
            offset += 1;
            offset %= numEntries_;
            const_cast<BoardHashTable *>( this )->numCollisions_ += 1;
        }
        return table_[offset];
    }

    void insert( const BoardState &s ) {
        BoardState &b = bucket( s );
        if ( b.empty() ) {
            numUsed_ += 1;
            b = s;
        }
    }

    bool present( const BoardState &s ) const {
        BoardState &b = bucket( s );
        return !b.empty();
    }
};

uint64_t pruneHit = 0;
uint64_t pruneLookup = 0;
uint64_t historyHit = 0;
uint64_t historyLookup = 0;
uint64_t colorPrune = 0;
uint64_t colorLookup = 0;

void resetStats( void ) {
    pruneHit = 0;
    pruneLookup = 0;
    historyHit = 0;
    historyLookup = 0;
    colorPrune = 0;
    colorLookup = 0;
}


BoardHashTable *
nextDepth( BoardHashTable *prev,
           int depth,
           bool log,
           BoardHashTable *extraPrune,
           int depthBound ) {
    if ( log ) {
        std::cout << "===== Depth " << depth << " =====" << std::endl;
    }

    const int maxSize = 20000000;
    int estimate =  5 * prev->numUsed_ * 10 / 6 + 6;
    int prune = 0;
    int prune2 = 0;
    BoardHashTable *next =
        new BoardHashTable( std::min( estimate, maxSize ), depth );
    if ( log ) {
        std::cout << "Table size: " << next->numEntries_ << std::endl;
    }
    bool colorBoundActive = ( depthBound - depth <= 6 );

    for ( int i = 0; i < prev->numEntries_; ++i ) {
        BoardState &s = prev->table_[ i ];
        if ( !s.empty() ) {
            for ( int c = 0; c < numColors; ++c ) {
                BoardState successor;
                s.successor( c, successor );

                if ( successor != s ) { // valid move

                    if ( colorBoundActive ) {
                        colorLookup += 1;
                        if ( depth + successor.numColorsLeft() >= depthBound ) {
                            colorPrune += 1;
                            continue;
                        }
                    }

                    pruneLookup += 1;
                    if ( extraPrune ) historyLookup += 1;

                    if ( prev->present( successor ) ) {
                        prune += 1;
                        pruneHit += 1;
                    } else if ( extraPrune &&
                                extraPrune->present( successor ) ) {
                        prune += 1;
                        prune2 += 1;
                        historyHit += 1;
                    } else {
                        next->insert( successor );
                    }
                    /*
                      std::cout << "Color " << c << " successor: " << std::endl;
                      successor.print( std::cout );
                    */
                }
            }
        }
        assert( next->numUsed_ <= next->numEntries_ * 8 / 10 );
    }
    if ( log ) {
        std::cout << "Found " << next->numUsed_ << " successor states."
                  << std::endl
                  << next->numCollisions_ << " hash table collisions."
                  << std::endl
                  << prune << " dominated paths pruned." << std::endl;
        if ( extraPrune && prune2 > 0 ) {
            std::cout << "(" << prune2 << " from extra hints.)" << std::endl;
        }
    }
    return next;
}

bool
leafSearch( BoardHashTable *prev ) {
    for ( int i = 0; i < prev->numEntries_; ++i ) {
        BoardState &s = prev->table_[ i ];
        if ( !s.empty() ) {
            for ( int c = 0; c < numColors; ++c ) {
                BoardState successor;
                s.successor( c, successor );

                if ( successor == BoardState::goalState ) return true;
            }
        }
    }
    return false;
}

uint64_t successorsGenerated = 0;
uint64_t prunedByIntermediate = 0;

bool
dfs( std::vector<int> &solution,
     const BoardState &begin,
     const BoardState &goal,
     int maxDepth,
     bool checkIntermediateAgainstGoal,
     int lastColor = -1 ) {
    for ( int c = 0; c < numColors; ++c ) {
        if ( c == lastColor ) continue;
        if ( begin.colorsLeft_[c] == 0 ) continue;

        BoardState s;
        begin.successor( c, s );
        successorsGenerated += 1;
        if ( s == begin ) continue;

        if ( s == goal ) {
            solution.push_back( c );
            return true;
        }
        if ( maxDepth == 1 ) continue;

        if ( checkIntermediateAgainstGoal &&
             !s.possiblePredecessorTo( goal ) ) {
            prunedByIntermediate += 1;
            continue;
        }

        bool succeed = dfs( solution,
                            s, goal, maxDepth - 1,
                            checkIntermediateAgainstGoal,
                            c );
        if ( succeed ) {
            solution.push_back( c );
            return true;
        }
    }
    return false;
}

BoardState
showSolution( std::vector<int> &solution,
              int &move,
              const BoardState &start ) {
    std::reverse( solution.begin(), solution.end() );
    BoardState curr = start;
    for ( std::vector<int>::iterator i = solution.begin();
          i != solution.end(); ++i ) {
        std::cout << "move " << ++move
                  << " pick " << colorTranslation[*i] << std::endl;
        BoardState nextBoard;
        curr.successor( *i, nextBoard );
        nextBoard.printWithProblem( std::cout );
        curr = nextBoard;
    }

    return curr;
}

void
readProblem( const char *filename ) {
    std::ifstream in( filename );
    std::map< char, int > translate;
    int nextColor = 0;

    for ( int c = 0; c < numColors; ++c ) {
        colorCount[c] = 0;
    }
    for ( int y = 0; y < problemSize; ++y ) {
        problem[y] = new int[problemSize];
        for ( int x = 0; x < problemSize; ++x ) {
            char c = in.get();
            int color;
            if ( c >= '0' && c <= '9' ) {
                color = c - '0';
            } else {
                std::map<char, int>::iterator i = translate.find( c );
                if ( i == translate.end() ) {
                    color = nextColor;
                    translate.insert( std::make_pair( c, color ) );
                    colorTranslation[color] = c;
                    nextColor += 1;
                } else {
                    color = i->second;
                }
            }
            problem[y][x] = color;
            colorCount[color] += 1;
        }
        in >> std::ws;
    }
}

int main( int argc, char *argv[] ) {
    int midpointDepth = 13;

    if ( argc == 1 ) {
        randomProblem();
    }
    if ( argc >= 2 ) {
        midpointDepth = atoi( argv[1] );
    }
    if ( argc >= 3 ) {
        readProblem( argv[2] );
    }

    std::cout << "====== Problem instance =====" << std::endl;
    for ( int y = 0; y < problemSize; ++y ) {
        for ( int x = 0; x < problemSize; ++x ) {
            std::cout << problem[y][x];
        }
        std::cout << std::endl;
    }

    BoardHashTable *prev = new BoardHashTable( 3, 0 );
    BoardState start;
    start.markDfs( 0, 0, problem[0][0] );
    prev->insert( start );
    std::cout << std::endl;
    start.print( std::cout );
    std::cout << std::endl;
    BoardState::goalState.print( std::cout );

    for ( int depth = 1; depth <= midpointDepth; ++depth ) {
        BoardHashTable *next = nextDepth( prev, depth, true, 0, 26 );
        delete prev;
        prev = next;
    }

    std::cout << "Hit rate on previous depth " << pruneHit * 1.0 / pruneLookup
              << std::endl;
    resetStats();

    std::cout << "===== Subtree search starting from depth " << midpointDepth << " =====" << std::endl;


    int depthBound = 26;
    BoardState best;
    BoardHashTable *midpoint = prev;

    // Cache is only correct if we remember one additional level of depth.
    // It looks like about ~10% hit rate with lookups at depth + 2
    // and 5% hit rate at depth + 3, so +3 looks like a win.
    int maxRemembered = midpointDepth + 1;
    int maxHistoryLookupDepth = midpointDepth + 3;
    BoardHashTable *explored = new BoardHashTable( 20000000, 0 );
    for ( int i = 0; i < midpoint->numEntries_; ++i ) {
        BoardState &s = midpoint->table_[ i ];
        if ( !s.empty() ) {
            explored->insert( s );
        }
    }

    int rootCount = 0;
    for ( int i = 0; i < midpoint->numEntries_; ++i ) {
        BoardState &s = midpoint->table_[ i ];
        if ( !s.empty() ) {
            rootCount += 1;

            if ( depthBound - midpointDepth <= 6 ) {
                // color bound active
                colorLookup += 1;
                if ( midpointDepth + s.numColorsLeft() >= depthBound ) {
                    colorPrune += 1;
                    continue;
                }
            }

            int nodeCount = 0;
            bool success = false;
            prev = new BoardHashTable( 3, midpointDepth );
            prev->insert( s );
            int depth;
            for ( depth = midpointDepth + 1;
                  depth < depthBound - 1 && prev->numUsed_ > 0;
                  ++depth ) {
                BoardHashTable *hint = explored;
                if ( depth > maxHistoryLookupDepth ) {
                    hint = 0;
                }
                BoardHashTable *next =
                    nextDepth( prev, depth,
                               false && rootCount % 1000 == 0,
                               hint,
                               depthBound );

                if ( depth <= maxRemembered ) {
                    if ( explored->numUsed_ + next->numUsed_ <
                         explored->numEntries_ * 8 / 10 ) {
                        if ( false ) {
                            std::cout << "Adding " << next->numUsed_ << " visited entries to remembered history." << std::endl;
                        }
                        for ( int j = 0; j < next->numEntries_; ++j ) {
                            BoardState &s = next->table_[ j ];
                            if ( !s.empty() ) {
                                explored->insert( s );
                            }
                        }

                    }
                }

                nodeCount += next->numUsed_;
                if ( next->present( BoardState::goalState ) ) {
                    depthBound = depth;
                    success = true;
                    best = s;
                }
                delete prev;
                prev = next;
            }
            if ( depth < depthBound && prev->numUsed_ > 0 ) {
                assert( !success );
                // No solution found yet.  Don't bother generating a
                // hash table this time.
                success = leafSearch( prev );
                if ( success ) {
                    depthBound = depth;
                    best = s;
                }
            }
            delete prev;

            if ( success ) {
                std::cout << "Subtree root " << rootCount << " nodecount " << nodeCount << " success " << success << " bound " << depthBound << std::endl;
                std::cout << "Pruning history size " << explored->numUsed_
                          << " HR prev " << pruneHit * 1.0 / pruneLookup
                          << " HR history " << historyHit * 1.0 / historyLookup
                          << " PR color " << colorPrune * 1.0 / colorLookup
                          << std::endl;
            }
            if ( success ) {
                s.print( std::cout );
                resetStats();
            }
        }
    }

    std::cout << "===== Subtree search complete =====" << std::endl;
    std::cout << "Pruning history size " << explored->numUsed_
              << " HR prev " << pruneHit * 1.0 / pruneLookup
              << " HR history " << historyHit * 1.0 / historyLookup
              << " PR color " << colorPrune * 1.0 / colorLookup
              << std::endl;
    std::cout << "Color prune checks: " << colorLookup << std::endl;

    std::cout << "===== Searching for path to midpoint =====" << std::endl;
    std::vector<int> solution;
    assert( dfs( solution, start, best, midpointDepth, true ) );

    std::cout << successorsGenerated << " nodes generated, "
              << prunedByIntermediate << " pruned by comparison with goal."
              << std::endl;
    successorsGenerated = 0;

    int move = 0;
    BoardState afterMoves = showSolution( solution, move, start );
    assert( afterMoves == best );

    std::cout << "===== Searching for path to goal =====" << std::endl;
    solution.clear();
    assert( dfs( solution, best, BoardState::goalState,
                 depthBound - midpointDepth, false ) );
    std::cout << successorsGenerated << " nodes generated." << std::endl;

    afterMoves = showSolution( solution, move, afterMoves );
    assert( afterMoves == BoardState::goalState );

    return 0;
}