solver.cpp

#include "Configuration.h"
#include "assert.h"
#include "time.h"
#include <algorithm>
#include <deque>
#include <iostream>
#include <fstream>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include <memory>
#include <unistd.h>  // for alarm()

static const int DR[8] = { -1,  0, +1,  0, -1, +1, +1, -1 };
static const int DC[8] = {  0, -1,  0, +1, -1, -1, +1, +1 };

struct Placement
{
    unsigned index, dirs;
};

static unsigned bitcount(unsigned mask)
{
    unsigned res = 0;
    while (mask != 0) ++res, mask &= mask - 1;
    return res;
}

template<typename CardIndex>
static void write_output( Configuration &config, std::string &output_path,
    int best_score, const std::vector<CardIndex> &best_board )
{
    std::ofstream ofs;
    if (output_path != "-" && !(ofs.open(output_path), ofs))
    {
        std::cerr << "Failed to open output file `" << output_path << "`!\n";
        output_path = "-";  // write to standard output instead
    }
    std::ostream &os = output_path == "-" ? std::cout : ofs;
    os << "Score:" << best_score << '\n';
    for (int r = config.board_height - 1; r >= 0; --r)
    {
        for (int c = 0; c < (int)config.board_width; ++c)
        {
            unsigned i = config.board_width*r + c;
            os << '[' << config.card_types[best_board[i]].name << ']';
        }
        os << '\n';
    }
}

template<typename CardIndex, typename CardCount>
static int solve(Configuration &config, std::string output_path)
{
    std::cerr << "sizeof(CardIndex)=" << sizeof(CardIndex) << std::endl;
    std::cerr << "sizeof(CardCount)=" << sizeof(CardCount) << std::endl;

    static const unsigned H = config.board_height,
                          W = config.board_width,
                          HW = H*W;

    // Shuffle cards (except last, the empty cards)
    for (size_t i = 0; i < config.card_types.size(); ++i)
    {
        size_t j = i + rand()%(config.card_types.size() - i);
        std::swap(config.card_types[i], config.card_types[j]);
    }

    // Add a bunch of empty cards:
    config.card_types.push_back(CardType{ "", HW - 2 });
    // FIXME: this may cause the final board to be not connected!

    const unsigned C = config.card_types.size();

    // Precalculate placement data
    std::vector<Placement> places;
    {
        std::vector<std::pair<int,int> > queue;
        std::vector<std::vector<int> > seen(H, std::vector<int>(W, -1));
        for (int i = 0; i < 2; ++i)
        {
            seen[config.home_row][config.home_col + i] = i;
            queue.push_back(std::make_pair(config.home_row, config.home_row + i));
        }

        for (int pos = 0; pos < (int)queue.size(); ++pos)
        {
            const int r1 = queue[pos].first, c1 = queue[pos].second;
            Placement place = { W*r1 + c1, 0 };
            for (int dir = 0; dir < 8; ++dir)
            {
                const int dr = DR[dir], dc = DC[dir], r2 = r1 + dr, c2 = c1 + dc;
                if (r2 >= 0 && r2 < (int)H && c2 >= 0 && c2 < (int)W)
                {
                    if (seen[r2][c2] < 0)
                    {
                        seen[r2][c2] = (int)queue.size();
                        queue.push_back(std::make_pair(r2, c2));
                    }
                    if (seen[r2][c2] < pos)
                    {
                        // Only count against one house card:
                        if (seen[r2][c2] < 2 && c1 == c2) continue;
                        place.dirs |= 1u << dir;
                    }
                }
            }
            if (pos >= 2) places.push_back(place);
        }
    }

    // Find index for home card:
    int home_index = 0;
    while ( home_index < (int)config.card_types.size() &&
            config.card_types[home_index].name != "huis" ) ++home_index;
    if (home_index == (int)config.card_types.size())
    {
        std::cerr << "Missing home card type!" << std::endl;
        return 1;
    }

    // Precalculate card combination scores:
    std::vector<signed char> combis(C*C*8);
    for (size_t c = 0; c < C; ++c)
    {
        const CardType &a = config.card_types[c];
        for (size_t d = 0; d < C; ++d)
        {
            const CardType &b = config.card_types[d];
            for (int dir = 0; dir < 8; ++dir)
            {
                signed char &score = combis[8*(C*c + d) + dir];
                assert(score == 0);
                score += bitcount(a.inputs & b.outputs);
                score += bitcount(b.inputs & a.outputs);
                if (DC[dir] > 0)
                {
                    score += a.wind_provided    && b.wind_required;
                    score += a.shelter_provided && b.shelter_required;
                    score -= a.wind_provided    && b.shelter_required;
                    score -= a.shelter_provided && b.wind_required;
                }
                if (DC[dir] < 0)
                {
                    score += b.wind_provided    && a.wind_required;
                    score += b.shelter_provided && a.shelter_required;
                    score -= b.wind_provided    && a.shelter_required;
                    score -= b.shelter_provided && a.wind_required;
                }
                if (DR[dir] > 0)
                {
                    score += a.sun_provided   && b.sun_required;
                    score += a.shade_provided && b.shade_required;
                    score -= a.sun_provided   && b.shade_required;
                    score -= a.shade_provided && b.sun_required;
                }
                if (DR[dir] < 0)
                {
                    score += b.sun_provided   && a.sun_required;
                    score += b.shade_provided && a.shade_required;
                    score -= b.sun_provided   && a.shade_required;
                    score -= b.shade_provided && a.sun_required;
                }
            }
        }
    }

    // Initialize board array:
    std::vector<CardIndex> initial_board(HW, (CardIndex)-1);
    for (int i = 0; i < 2; ++i)
    {
        initial_board[W*config.home_row + config.home_col + i] = home_index;
    }
    std::vector<CardCount> initial_avail(C);
    for (int c = 0; c < (int)C; ++c)
    {
        if (c != home_index)
        {
            initial_avail[c] = std::min( config.card_types[c].count,
                                         (unsigned)(CardCount)~0 );
        }
    }

    int best_score = -999999999;
    for (size_t max_queue_size = 4; ; max_queue_size *= 2)
    {
        time_t iteration_start_time = time(NULL);

        // Breadth-first search, keeping the best max_queue_size candidates.
        std::vector<std::deque<std::pair< std::vector<CardIndex>,
                                        std::vector<CardCount> > > > queue;
        // Note: initial score is set to 10 to allow states with negative scores
        //       (up to -10) to be queued initially.
        const int score_offset = -10;
        queue.resize(1 - score_offset);
        queue[-score_offset].push_back(std::make_pair(initial_board, initial_avail));
        for (size_t place_index = 0; place_index < places.size(); ++place_index)
        {
            auto const &place = places[place_index];
            decltype(queue) next_queue;
            int next_queue_min_score = 0;
            size_t next_queue_size = 0;
            for (int score = (int)queue.size() - 1; score >= 0; --score)
            {
                for (auto const &entry : queue[score])
                {
                    auto const &board = entry.first;
                    auto const &avail = entry.second;
                    assert(board[place.index] >= C);
                    for (unsigned c = 0; c < C; ++c)
                    {
                        if (avail[c] > 0)
                        {
                            int add_score = 0;
                            for (int dir = 0; dir < 8; ++dir)
                            {
                                if (place.dirs & 1u<<dir)
                                {
                                    unsigned d = board[place.index + W*DR[dir] + DC[dir]];
                                    assert(d < C);
                                    add_score += combis[8*(C*c + d) + dir];
                                }
                            }
                            int new_score = score + add_score;
                            if (next_queue_size == max_queue_size)
                            {
                                if (new_score <= next_queue_min_score) continue;
                                next_queue[next_queue_min_score].pop_front();
                                while (next_queue[next_queue_min_score].empty())
                                    ++next_queue_min_score;
                                --next_queue_size;
                            }
                            if (new_score >= (int)next_queue.size())
                                next_queue.resize(new_score + 1);
                            auto &q = next_queue[new_score];
                            q.push_back(entry);
                            auto &new_entry = q.back();
                            new_entry.first[place.index] = c;
                            new_entry.second[c] -= 1;
                            if ( next_queue_size++ == 0 ||
                                 new_score < next_queue_min_score )
                            {
                                next_queue_min_score = new_score;
                            }
                        }
                    }
                }
            }
            next_queue.swap(queue);
        }

        const int score = (int)queue.size() + score_offset - 1;
        auto const &board = queue.back()[0].first;
        std::cerr << "Queue size " << max_queue_size
                  << " yielded score " << score
                  << " in " << time(NULL) - iteration_start_time << "s.\n";
        if (score > best_score)
        {
            write_output<CardIndex>(config, output_path, score, board);
            best_score = score;
        }
    }
}

int main(int argc, const char *argv[])
{
    // Initialize the RNG
    srand(time(NULL));

    // Kill our process after 5 minutes:
    alarm(297);

    // Read game configuration:
    Configuration config;
    try
    {
        config = read_configuration();
    }
    catch (const char *error)
    {
        std::cerr << "Failed to read configuration: " << error << "!" << std::endl;
        return 1;
    }

    // Calculate maximum card count:
    unsigned max_card_count = 0;
    for (auto const &ct : config.card_types)
    {
        max_card_count = std::max(max_card_count, ct.count);
    }
    max_card_count = std::min( max_card_count,
                               config.board_height*config.board_width );

    std::string output_path = argc > 1 ? argv[1] : "output.ini";
    if (config.card_types.size() < 256 && max_card_count < 256)
    {
        return solve<unsigned char, unsigned char>(config, output_path);
    }
    if (config.card_types.size() < 256)
    {
        return solve<unsigned char, unsigned short>(config, output_path);
    }
    if (max_card_count < 256)
    {
        return solve<unsigned short, unsigned short>(config, output_path);
    }
    return solve<unsigned short, unsigned short>(config, output_path);
}