与えた条件を満たす候補 in JavaScript 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 - JavaScript

身も蓋も無し。

function doukaku43(){
	var exp = "", result = [], x = 0, X, i, j, l;
	for(i = 0, l = arguments.length; i < l; i++) switch(arguments[i]){
	case "and": exp = "("+ exp + "X["+ x++ +"]) && "; break;
	case "or" : exp = "("+ exp + "X["+ x++ +"]) || "; break;
	case "not": exp += "!"; break;
	}
	exp += "X["+ x++ +"]";
	for(i = 0, l = 1 << x; i < l; i++){
		for(j = x, X = []; j--;) X.push(!!(i >> j & 1));
		if(eval(exp)) result.push(X);
	}
	return result;
}
(function(){
	for(var r, s = "", i = 0, j; i < arguments.length; i++){
		r = doukaku43.apply(this, arguments[i]);
		s += arguments[i].join(" ") +" :\n";
		for(j = 0; j < r.length; j++) s += "  "+ r[j] + "\n";
	}
	this.WSH ? WSH.echo(s) : alert(s);
})(['and', 'or', 'not', 'and'], ['not', 'or', 'and'], ['not', 'not']);

DouKaku?

与えた条件を満たす候補

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq