Countdown

countdown.cpp

/**
 * Solver for the Countdown numbers game. Branch-and-bound search.
 * Compile with:
 * clang++ -std=c++17 -O3 -o countdown countdown.cpp
 *
 * Should find answers in much less than a second.
 */
#include <limits>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <chrono>

static long target = 0; /** Target to hit */
static const long N = 6; /** Amount of given numbers expected */
static const long expN = 1 << N;
enum op_e { IMM = 0, ADD, SUB, MUL, DIV }; /** Operators, incl. immediates */

struct expression {
    op_e op;
    const expression *lhs, *rhs;
    long value;

    expression() : op(IMM), lhs(nullptr), rhs(nullptr), value(0) {}
    expression(long v) : op(IMM), lhs(nullptr), rhs(nullptr), value(v) {}
    expression(op_e op, const expression *lhs, const expression *rhs, long v) :
        op(op), lhs(lhs), rhs(rhs), value(v) {}
};

/* pools[N] contains all the expressions that may be created with the set of inputs N.
 * N is a bitmap, initialised with the first draw (see `main`): */
static std::vector<const expression *> pools[expN];
static const expression *best_result = nullptr; /** Best result achieved */
static long best_distance = std::numeric_limits<long>::max(); /** Best distance (of result) from target */

/* Sink an expression in a pool. Update the best distance from the target.
 * Returns true if a solution has been found, false otherwise:
 */
bool pool(op_e op, const expression *lhs, const expression *rhs, long value, long bitmap) {
    long distance = std::abs(target - value);
    auto elem = new expression(op, lhs, rhs, value);

    pools[bitmap].insert(pools[bitmap].end(), elem);
    if (distance < best_distance) {
        best_result = elem;
        best_distance = distance;
    }
    return distance == 0;
}

/* Grab all the expressions from two disjoint sets of inputs, and explode them.
 * Returns true if a solution is found while exploding, false otherwise:
 */
bool explode(long r, long s) {
    /* The numbers used: */
    long bitmap = r | s;

    bool ret = false;
    for (const auto rhs : pools[r]) {
        for (const auto lhs : pools[s]) {
            /* The expressions we can produce from two expressions are:
             * a+b a-b a*b a/b
             * Bound based on distance of left-hand-side from target, and game rules.
             * Evaluate them and cache them:
             */
            ret |= pool(ADD, lhs, rhs, lhs->value + rhs->value, bitmap);
            ret |= pool(MUL, lhs, rhs, lhs->value * rhs->value, bitmap);
            if (lhs->value > rhs->value) {
                ret |= pool(SUB, lhs, rhs, lhs->value - rhs->value, bitmap);
            }
            if (lhs->value % rhs->value == 0) {
                ret |= pool(DIV, lhs, rhs, lhs->value / rhs->value, bitmap);
            }
            /* Save time if solution found: */
            if (ret) goto solved;
        }
    }
solved:
    return ret;
}

static const short prec[] = { 0, 1, 1, 2, 2 };
static const short rprec[] = { 0, 1, 2, 2, 3 };
static const std::string opstring[] = { "", " + ", " - ", " * ", " / "};

void walk(const expression expr, int p, std::stringstream &output) {
    if (expr.op == IMM) {
        output << expr.value;
        return;
    }

    int xp = prec[expr.op], rp = rprec[expr.op];
    if (xp < p) output << "(";
    walk(*expr.lhs, xp, output);
    output << opstring[expr.op];
    walk(*expr.rhs, rp, output);
    if (xp < p) output << ")";
}

const std::string stringify_solution(const expression expr) {
    std::stringstream output;
    walk(expr, 1, output);
    return output.str();
}

int main (int argc, char *argv[]) {
    if (argc != N + 2) {
        std::cerr << "Usage: " << argv[0] << " [NUMBERS] <TARGET>" << std::endl;
        return -1;
    }

    /* Init bitcounts with the recurrence `count[i+2^n] = count[i] + 1`: */
    unsigned long bitcount[expN] = {0};
    for (size_t i = 0; i < N; ++i) {
        size_t t = 1 << i;
        for (size_t r = 0; r < t; ++r)
            bitcount[t + r] = bitcount[r] + 1;
    }

    target = std::stoi(argv[N + 1]);
    std::cout << "Target: " << target << std::endl;

    auto time_start = std::chrono::high_resolution_clock::now();

    for (size_t idx = 0; idx < N; ++idx) {
        pool(IMM, nullptr, nullptr, std::stoi(argv[idx + 1]), 1 << idx);
    }

    for (size_t noperands = 2; noperands <= N; ++noperands) {
        for (size_t r = 1; r < expN; ++r) {
            for (size_t s = 1; s < expN; ++s) {
                /* Find expressions that use `noperands` inputs in total: */
                if (bitcount[r] + bitcount[s] == noperands
                /* and those expressions use completely disjoint inputs: */
                &&  (r & s) == 0) {
                    if (explode(r, s)) {
                        goto done;
                    }
                }
            }
        }
    }

done:
    auto time_end = std::chrono::high_resolution_clock::now();
    std::cout << "Best  : " << best_result->value << " = ";
    std::cout << stringify_solution(*best_result) << std::endl;
    std::cout << "Time  : "
        << std::chrono::duration<double, std::milli>(time_end - time_start).count()
        << " ms" << std::endl;

    return 0;
}