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

type bool = Boolean
type f2   = Function2[bool,bool,bool]

class Solver(lst:List[String]) {
  val fs = {
    def factory(t:String, f:bool=>bool)(v1:bool, v2:bool) = t match {
      case "and" => v1&&f(v2)
      case "or" =>  v1||f(v2)
    }
    def it(lst:List[String]):List[f2] = lst match {
      case n::"not"::xs => factory(n, !_) _::it(xs)
      case n::xs    =>     factory(n, x=>x) _::it(xs)
      case Nil      =>     Nil
    }
    it(lst)
  }

  def solve() = {
    val eachv = List(true, false).foreach _
    def apply(v1:bool, fs:List[f2], res:List[bool]):unit = fs match {
      case Nil if v1 => println(res.reverse)
      case f::fs   => eachv(x=> apply(f(v1,x),fs, x::res))
      case _ => ()
    }
    eachv(x=> apply(x,fs,List(x)))
  }
}

new Solver(List("and", "or", "not", "and")) solve

盆休みで生活リズム乱れまくり。

["not","not","not"]みたいなケースに対応してみた。

type bool = Boolean
type f2   = Function2[bool,bool,bool]
type pred = Function1[bool,bool]
type tokens = List[String]
class Solver(lst:tokens) {

  val nlst = { 
    def it(lst:tokens,i:int):tokens = lst match {
      case "not"::xs => it(xs, i+1)
      case n::xs     => it(xs, 0):::List(n, if(i%2==0){""}else{"not"})
      case Nil       => (if(i%2==0){""}else{"not"})::Nil
    }
    it(lst, 0).reverse.filter(_!="")
  }

  val fs = {
    def factory(t:String, f1:pred, f2:pred)(v1:bool, v2:bool) = t match {
      case "and" => f1(v1)&&f2(v2)
      case "or" =>  f1(v1)||f2(v2)
    }
    def it(lst:tokens, f:pred):List[f2] = lst match {
      case "not"::xs => it(xs, !_)
      case n::"not"::xs => factory(n, f, !_) _::it(xs, x=>x)
      case n::xs    =>     factory(n, f, x=>x) _::it(xs, x=>x)
      case Nil      =>     Nil
    }
    it(nlst, x=>x)
  }

  def solve() = nlst.length match{
    case 0 => println(List(true))
    case 1 if nlst.head == "not" => println(List(false))
    case _ => 
      val eachv = List(true, false).foreach _
      def apply(v1:bool, fs:List[f2], res:List[bool]):unit = fs match {
        case Nil if v1 => println(res.reverse)
        case f::fs   => eachv(x=> apply(f(v1,x),fs, x::res))
        case _ => ()
      }
      eachv(x=> apply(x,fs,List(x)))
  }
}

new Solver(List("and", "or","not", "and")) solve

DouKaku?

与えた条件を満たす候補

Posted feedbacks - Scala

Index

Feed

Other

Link

Pathtraq