2023パズルのソルバー(最適化版)

2023solver.d

// http://nmi.jp/2023-01-03-How-to-solve-2023-puzzle
// https://twitter.com/tkihira/status/1609313732034965506

module solver;
import std;
import std.datetime.stopwatch : StopWatch;

void main()
{
    StopWatch sw;
    sw.start();
    auto ans = solve();
    sw.stop();

    foreach (i, expr; ans)
    {
        writefln!"%d: %s"(i, print(expr));
    }
    writeln();
    writeln(ans.length);
    writeln(sw.peek());
}

enum
{
    ADD = -1,
    SUB = -2,
    MUL = -3,
    DIV = -4,
}

long counter = 0;
byte[19][] ans;

auto solve()
{
    byte[19] a = void;
    a[0] = 10;
    traverse(a, 1, 9, 0, 1, -1);
    writeln(counter);
    return ans;
}

void traverse(byte[19] expr, size_t len, int number, size_t ops, size_t nums, int eight_depth)
{
    if (len == 19)
    {
        counter++;
        if (is_2023(expr))
        {
            ans ~= expr;
        }
    }
    if (number > 0)
    {
        immutable ed = number == 8 ? 0 : (eight_depth < 0 ? eight_depth : eight_depth + 1);
        expr[len] = cast(byte) number;
        traverse(expr, len + 1, number - 1, ops, nums + 1, ed);
    }
    if (nums - ops >= 2)
    {
        expr[len] = DIV;
        traverse(expr, len + 1, number, ops + 1, nums, eight_depth - 1);
        if (eight_depth == 0)
        {
            return;
        }
        expr[len] = ADD;
        traverse(expr, len + 1, number, ops + 1, nums, eight_depth - 1);
        expr[len] = SUB;
        traverse(expr, len + 1, number, ops + 1, nums, eight_depth - 1);
        expr[len] = MUL;
        traverse(expr, len + 1, number, ops + 1, nums, eight_depth - 1);
    }
}

enum MAX_STACK_LEN = 10;

bool is_2023(const ref byte[19] expr)
{
    long[MAX_STACK_LEN] num_stack = void;
    long[MAX_STACK_LEN] denom_stack = void;
    long sp;
    foreach (inst; expr)
    {
        if (inst < 0)
        {
            assert(2 <= sp);
            long rhs_n = num_stack[sp - 1];
            long rhs_d = denom_stack[sp - 1];
            long lhs_n = num_stack[sp - 2];
            long lhs_d = denom_stack[sp - 2];

            switch (inst)
            {
            case ADD:
                num_stack[--sp - 1] = lhs_n * rhs_d + rhs_n * lhs_d;
                denom_stack[sp - 1] = lhs_d * rhs_d;
                break;
            case SUB:
                num_stack[--sp - 1] = lhs_n * rhs_d - rhs_n * lhs_d;
                denom_stack[sp - 1] = lhs_d * rhs_d;
                break;
            case MUL:
                num_stack[--sp - 1] = lhs_n * rhs_n;
                denom_stack[sp - 1] = lhs_d * rhs_d;
                break;
            case DIV:
                num_stack[--sp - 1] = lhs_n * rhs_d;
                denom_stack[sp - 1] = lhs_d * rhs_n;
                break;
            default:
                assert(0);
            }
        }
        else
        {
            num_stack[sp] = inst;
            denom_stack[sp++] = 1;
        }
    }
    assert(sp == 1);
    if (denom_stack[0] == 0)
    {
        return false;
    }
    if (num_stack[0] % denom_stack[0] != 0)
    {
        return false;
    }
    return num_stack[0] / denom_stack[0] == 2023;
}

static immutable priority = [-1, 0, 0, 1, 1];
static immutable op_char = [char.init, '+', '-', '*', '/'];

string print(const ref byte[19] expr)
{
    alias T = Tuple!(string, "text", long, "priority");
    T[MAX_STACK_LEN] stack = void;
    long sp;
    static Appender!(char[]) buffer;
    foreach (inst; expr)
    {
        if (inst < 0)
        {
            buffer.clear();
            auto rhs = stack[sp - 1];
            auto lhs = stack[sp - 2];
            long p = priority[-inst];
            if (lhs.priority <= p)
            {
                buffer.put('(');
                buffer.put(lhs.text);
                buffer.put(')');
            }
            else
            {
                buffer.put(lhs.text);
            }
            buffer.put(op_char[-inst]);
            if (rhs.priority <= p)
            {
                buffer.put('(');
                buffer.put(rhs.text);
                buffer.put(')');
            }
            else
            {
                buffer.put(rhs.text);
            }
            stack[--sp - 1] = T(buffer[].idup, p);
        }
        else
        {
            stack[sp++] = T(text(inst), 2);
        }
    }
    assert(sp == 1);
    return stack[0].text;
}