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

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
class Program
{
  static void Main()
  {
    Show(new string[] { "and", "or", "not", "and" });
  }
  static void Show(string[] ss)
  {
    List<string> l = new List<string>();
    // 全組合わせ作成
    Get(ss, 0, "", l);
    foreach (string s in l) if (Check(s)) Show(s);
  }
  static string Rev(char c) { return c != 'F' ? "F" : "T"; }
  static bool Check(string s)
  {
    Match m;
    Regex r1 = new Regex("![TF]", RegexOptions.Compiled);
    Regex r2 = new Regex("^[TF]&[TF]", RegexOptions.Compiled);
    Regex r3 = new Regex("^[TF]|[TF]", RegexOptions.Compiled);
    while (s.Length > 1)
    {
      if ((m = r1.Match(s)).Success)
        s = s.Substring(0, m.Index) + Rev(m.Value[1]) + s.Substring(m.Index + 2);
      else if ((m = r2.Match(s)).Success)
        s = (s.StartsWith("T&T") ? "T" : "F") + s.Substring(3);
      else if ((m = r3.Match(s)).Success)
        s = (s.StartsWith("F|F") ? "F" : "T") + s.Substring(3);
    }
    return s != "F";
  }
  static void Show(string s)
  {
    Console.Write("(");
    bool bFirst = true;
    foreach (char c in s)
    {
      if ("&|!".IndexOf(c) >= 0) continue;
      if (!bFirst) Console.Write(", ");
      bFirst = false;
      Console.Write(c != 'F');
    }
    Console.WriteLine(")");
  }
  static void Get(string[] ss, int pos, string cur, List<string> l)
  {
    if (pos == ss.Length)
    {
      l.Add(cur + "T");
      l.Add(cur + "F");
      return;
    }
    switch (ss[pos])
    {
      case "and":
        Get(ss, pos + 1, cur + "T&", l);
        Get(ss, pos + 1, cur + "F&", l);
        break;
      case "or":
        Get(ss, pos + 1, cur + "T|", l);
        Get(ss, pos + 1, cur + "F|", l);
        break;
      case "not":
        Get(ss, pos + 1, cur + "!", l);
        break;
    }
  }
}

DouKaku?

与えた条件を満たす候補

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq