Skip to content

Instantly share code, notes, and snippets.

@mfukar
Last active November 8, 2021 17:26
Show Gist options
  • Save mfukar/595005296ad09b8400a9edf6a7cd12fd to your computer and use it in GitHub Desktop.
Save mfukar/595005296ad09b8400a9edf6a7cd12fd to your computer and use it in GitHub Desktop.
Countdown
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment