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();
    writeln();
    writeln(ans.length);
    writeln(sw.peek());
}

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

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

synchronized class SafeArray(T)
{
    private T[] arr;
    size_t length()
    {
        return arr.length;
    }

    void append(T v)
    {
        arr ~= cast(shared) v;
    }

    T[] dup()
    {
        return cast(T[]) arr.dup;
    }
}

long[19][] solve()
{
    auto ans = new shared(SafeArray!(long[19]));
    long[19] init;
    dfs(ans, init, 0, 10, 9);
    return ans.dup;
}

void dfs(shared(SafeArray!(long[19])) ans, long[19] seq, size_t seq_len, long num_remain, long op_remain)
{
    Task!(dfs, shared(SafeArray!(long[19])), long[19], size_t, long, long)*[] tasks;

    void run_dfs(shared(SafeArray!(long[19])), long[19] seq, size_t seq_len, long num_remain, long op_remain)
    {
        if (seq_len < 3)
        {
            synchronized
            {
                writefln!"[%d] put new task"(taskPool.workerIndex);
            }
            auto t = task!dfs(ans, seq, seq_len, num_remain, op_remain);
            taskPool.put(t);
            tasks ~= t;
        }
        else
        {
            dfs(ans, seq, seq_len, num_remain, op_remain);
        }
    }

    long remain = 19 - seq_len;
    auto scratch = seq;
    if (op_remain == 0 && num_remain != 0)
    {
        return;
    }
    if (4 < seq_len && seq[seq_len - 1] < 0 && !validate(seq, seq_len))
    {
        return;
    }
    if (remain != 0)
    {
        if (0 < num_remain)
        {
            scratch[seq_len] = num_remain;
            run_dfs(ans, scratch, seq_len + 1, num_remain - 1, op_remain);
        }
        if (0 < op_remain)
        {
            scratch[seq_len] = ADD;
            run_dfs(ans, scratch, seq_len + 1, num_remain, op_remain - 1);
            scratch[seq_len] = SUB;
            run_dfs(ans, scratch, seq_len + 1, num_remain, op_remain - 1);
            scratch[seq_len] = MUL;
            run_dfs(ans, scratch, seq_len + 1, num_remain, op_remain - 1);
            scratch[seq_len] = DIV;
            run_dfs(ans, scratch, seq_len + 1, num_remain, op_remain - 1);
        }
    }
    else
    {
        assert(num_remain == 0);
        if (is_2023(seq))
        {
            synchronized
            {
                writefln!"[T%d]%d: %s"(taskPool.workerIndex, ans.length, print(seq));
                ans.append(seq);
            }
        }
    }
    foreach (t; tasks)
    {
        t.yieldForce();
    }
}

enum STACK_MAX_LEN = 10;

bool validate(long[19] seq, size_t seq_len)
{
    if (seq[seq_len - 1] == DIV)
        return true;
    long[STACK_MAX_LEN] stack;
    size_t sp;
    foreach (i; 0 .. seq_len)
    {
        if (0 <= seq[i])
        {
            stack[sp++] = seq[i];
        }
        else if (sp < 2)
        {
            return true;
        }
        else
        {
            long a = stack[--sp];
            long b = stack[--sp];
            if (b < a)
            {
                swap(a, b);
            }
            if (a == 8 && b == 9)
            {
                return seq[i] == DIV;
            }
            else if (a == 8 || b == 8)
            {
                stack[sp++] = 8;
            }
            else if (a == 9 || b == 9)
            {
                stack[sp++] = 9;
            }
            else
            {
                stack[sp++] = 0;
            }
        }
    }
    return true;
}

bool is_2023(long[19] seq)
{
    long[STACK_MAX_LEN] num_stack;
    long[STACK_MAX_LEN] denom_stack;
    size_t sp;

    foreach (i; 0 .. seq.length)
    {
        if (seq[i] >= 0)
        {
            num_stack[sp] = seq[i];
            denom_stack[sp] = 1;
            sp++;
        }
        else
        {
            if (sp < 2)
                return false;
            sp--;
            long num_rhs = num_stack[sp];
            long denom_rhs = denom_stack[sp];
            sp--;
            long num_lhs = num_stack[sp];
            long denom_lhs = denom_stack[sp];
            switch (seq[i])
            {
            case ADD:
                num_stack[sp] = num_lhs * denom_rhs + num_rhs * denom_lhs;
                denom_stack[sp] = denom_lhs * denom_rhs;
                sp++;
                break;
            case SUB:
                num_stack[sp] = num_lhs * denom_rhs - num_rhs * denom_lhs;
                denom_stack[sp] = denom_lhs * denom_rhs;
                sp++;
                break;
            case MUL:
                num_stack[sp] = num_lhs * num_rhs;
                denom_stack[sp] = denom_lhs * denom_rhs;
                sp++;
                break;
            case DIV:
                num_stack[sp] = num_lhs * denom_rhs;
                denom_stack[sp] = denom_lhs * num_rhs;
                sp++;
                break;
            default:
                assert(0);
            }
        }
    }

    if (sp != 1)
        assert(0);
    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;
}

string print(long[19] seq)
{
    alias T = Tuple!(string, "str", long, "level");
    DList!T stack;
    foreach (i; 0 .. seq.length)
    {
        if (0 <= seq[i])
        {
            stack.insertBack(T(seq[i].text, 4));
        }
        else
        {
            long level = op_levels[-seq[i]];
            auto rhs = stack.back;
            stack.removeBack();
            auto lhs = stack.back;
            stack.removeBack();
            string s;
            s ~= (lhs.level <= level) ? "(" ~ lhs.str ~ ")" : lhs.str;
            s ~= op_char[-seq[i]];
            s ~= (rhs.level <= level) ? "(" ~ rhs.str ~ ")" : rhs.str;
            stack.insertBack(T(s, level));
        }
    }
    return stack.back().str;
}