与えた条件を満たす候補 in awk 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にした場合に、答えが…と色々悩みどころでした。

{
#	and or not and --> x1&x2|!x3&x4
	s = ""
	cnt = 0

	for (i=1; i<=NF; i++) {
		op = $i
		if (op ‾ /not/) {
			s = s "!"
		} else if (op ‾ /and/) {
			s = s "x" ++cnt "&"
		} else if (op ‾ /or/) {
			s = s "x" ++cnt "|"
		}
	}
	s = s "x" ++cnt

	for (i=2^cnt-1; i>0; i--) {
		expr = make_expr(s,i,x,cnt)
		if (apply_expr(expr)) show(x,cnt)
	}
}

function make_expr(s,n,x,digits, i)
{
	for (i=digits; i>=1; i--) {
		x[i] = n % 2
		sub("x"i, x[i], s)
		n = (n - x[i]) / 2
	}
	return s
}

function apply_expr(expr, n,tmp,i,result)
{
	# not を先に処理
	gsub(/!1/,"0", expr)
	gsub(/!0/,"1", expr)
	# これで and と or だけ考えればよくなる
	n = split(expr,tmp,"")
	result = tmp[1]
	for (i=2; i<=n; i+=2) {
		if (tmp[i] ‾ /&/)
			result = result && tmp[i+1]
		else
			result = result || tmp[i+1]
	}
	return result
}

function show(x,cnt, i)
{
	printf "("
	for (i=1; i<=cnt; i++) {
		printf("%s", x[i] == 1 ? "True" : "False")
		if (i < cnt) printf ", "
	}
	printf ")¥n"
}

not だけの組合せが処理できないので改訂版。

% awk -f and-or-not-2.awk
not
(False)
not not
(True)
not not not
(False)
not and not
(False, False)
not not and not
(True, False)
not or not
(True, False)
(False, True)
(False, False)

{
#    and or not and --> x1&x2|!x3&x4
    s = ""
    cnt = 0

    for (i=1; i<=NF; i++) {
        op = $i
        if (op ~ /not/) {
            s = s "!"
        } else if (op ~ /and/) {
            s = s "x" ++cnt "&"
        } else if (op ~ /or/) {
            s = s "x" ++cnt "|"
        }
    }
    s = s "x" ++cnt

#    for (i=2^cnt-1; i>0; i--) {
    for (i=2^cnt-1; i>=0; i--) { # i=0は (False,False,...,False)
        expr = make_expr(s,i,x,cnt)
        if (apply_expr(expr)) show(x,cnt)
    }
}

function make_expr(s,n,x,digits, i)
{
    for (i=digits; i>=1; i--) {
        x[i] = n % 2
        sub("x"i, x[i], s)
        n = (n - x[i]) / 2
    }
    return s
}

function apply_expr(expr, n,tmp,i,result)
{
    # not を先に処理
#    gsub(/!1/,"0", expr)
#    gsub(/!0/,"1", expr)
	r = expr
	gsub(/[^!]/,"",r) # expr の中の ! だけを抽出した文字列を得る
	for (i=length(r); i>0; i--) {
		gsub(r 1, (i + 1) % 2, expr)
		gsub(r 0, i % 2, expr)
		r = substr(r,2) # １字短縮
	}

    # これで and と or だけ考えればよくなる
    n = split(expr,tmp,"")
    result = tmp[1]
    for (i=2; i<=n; i+=2) {
        if (tmp[i] ~ /&/)
            result = result && tmp[i+1]
        else
            result = result || tmp[i+1]
    }
    return result
}

function show(x,cnt, i)
{
    printf "("
    for (i=1; i<=cnt; i++) {
        printf("%s", x[i] == 1 ? "True" : "False")
        if (i < cnt) printf ", "
    }
    printf ")\n"
}

DouKaku?

与えた条件を満たす候補

Posted feedbacks - awk

Index

Feed

Other

Link

Pathtraq