与えた条件を満たす候補 in C++ DouKaku?

与えた条件を満たす候補

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。ご投稿ありがとうございました。
元ネタの充足可能性問題 - Wikipedia は、同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

post comment

Posted feedbacks - C++

カバレッジ稼ぎとして、上のコードを忠実に移植。

#include <iostream>
#include <stdexcept>
#include <iterator>
#include <algorithm>
#include <vector>

std::vector<bool> pack(bool x0)
{
    std::vector<bool> v(1);

    v[0] = x0;

    return v;
}

std::vector<bool> pack(bool x0, bool x1)
{
    std::vector<bool> v(2);

    v[0] = x0; v[1] = x1;

    return v;
}

void output(const std::vector<bool>& stack)
{
    std::copy(stack.rbegin(), stack.rend(), std::ostream_iterator<bool>(std::cout, " "));

    std::cout << std::endl;
}

void traverse(
    std::vector<bool>& stack,
    std::vector<std::string>::const_reverse_iterator beg,
    std::vector<std::string>::const_reverse_iterator end,
    const std::vector<bool>& values)
{
    bool invert = false;

    while (beg != end && *beg == "not")
    {
        ++beg;

        invert = !invert;
    }

#define APPEND(value, statement) stack.push_back(value ^ invert); statement; stack.pop_back();

    if (beg == end) // no expressions any more
    {
        for (std::vector<bool>::const_iterator it = values.begin(); it != values.end(); ++it)
        {
            APPEND(*it, output(stack));
        }
    }
    else // and / or
    {
        if (*beg != "and" && *beg != "or")
        {
            throw std::runtime_error("invalid expression: " + *beg);
        }

        const bool which = *beg == "and";

        for (std::vector<bool>::const_iterator it = values.begin(); it != values.end(); ++it)
        {
            if (which == *it)
            {
                APPEND(which, traverse(stack, beg + 1, end, pack(which)));
            }
            else
            {
                APPEND(which, traverse(stack, beg + 1, end, pack(!which)));

                APPEND(!which, traverse(stack, beg + 1, end, pack(!which, which)));
            }
        }
    }

#undef APPEND
}

void solve(const std::vector<std::string>& exprs)
{
    std::vector<bool> stack;

    traverse(stack, exprs.rbegin(), exprs.rend(), pack(true));
}

int main()
{
    std::boolalpha(std::cout);

    const char* exprs[] = {"and", "or", "not", "and"};

    solve(std::vector<std::string>(exprs, exprs + sizeof(exprs) / sizeof(*exprs)));
}

DouKaku?

与えた条件を満たす候補

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq