切符問題

アルゴリズム Ruby Scala

某プログラム勉強会で、お題が出たので解いてみる。



いくつかの正の整数と加算・減算・乗算 の3つの演算子（そして、括弧）を使って、ある別の正の整数を生成する方法を探し出すプログラムを書け。

例えば。{2,5,6,8}から10を生成する方法は、例えば (2+8)*(6-5) があるので、これを出力すればよい。

なお：

・解がない場合は、その旨を出力すること

・解が複数ある場合でも、ひとつだけ出力すればよい

・オーバーフローは考慮しなくてもよい

・不正な入力（負の数がある、など）への対処は不要

・括弧は無駄にたくさんついていてもよい。

・ヒント：再帰
遠い昔に似た問題のソルバーを作ったことがある。
「切符問題」といわれていたけれど、与えられた４つの数字を加減乗除して指定された数字にする、という問題。
切符に数字が４つ書かれていて、その数字を使ったのが起源だったようだが。
見かけた車のナンバーを加減乗除して10を作るのは、いい暇つぶし。

で、出題者が再帰での回答を期待しているようなので、あえて再帰をしない方法で。

require "mathn"
class Ticket
  def initialize(val, elem)
    @val = val
    @elem = elem
  end

  def calc_rpn(rpn)
    stack = []
    rpn.each do |e|
      stack.push e.class == Fixnum ? e : "(#{stack.pop}#{e}#{stack.pop})"
    end
    return nil unless stack.size == 1
    val = eval(stack.first) rescue val = nil
    return nil unless val == @val
    return stack.first
  end

  def solve
    %w(+ - * /).map{|e| [e]*(@elem.size - 1)}.flatten.combination(@elem.size - 1).to_a.uniq.each do |e|
      (@elem + e).permutation do |rpn|
        if ans = calc_rpn(rpn)
          return ans
        end
      end
    end
    "解なし"
  end
end
val, *elem = ARGV.map(&:to_i)
puts Ticket.new(val, elem).solve

与えられた数から、逆ポーランド記法のパターンを生成して指定された数になるかチェックしています。
かなり強引な方法で無駄が多いので、与える数の個数は４個が限界でしょうか。
普通に再帰を使うとこんな感じ。

require "mathn"
class Ticket
  def initialize(val, elem)
    @val = val
    @elem = elem
  end

  def gen_exp(elem,&block)
    if elem.size == 1
      yield elem.first
    else
      0.upto(elem.size-2) do |i1|
        e1 = elem[i1]
        (i1+1).upto(elem.size-1) do |i2|
          e2 = elem[i2]
          elem_next = []
          elem.each_with_index{|e,i| elem_next.push(e) unless i == i1 or i == i2}
          gen_exp(elem_next+["(#{e1}+#{e2})"],&block)
          gen_exp(elem_next+["(#{e1}-#{e2})"],&block)
          gen_exp(elem_next+["(#{e1}*#{e2})"],&block)
          gen_exp(elem_next+["(#{e1}/#{e2})"],&block)
          gen_exp(elem_next+["(#{e2}-#{e1})"],&block)
          gen_exp(elem_next+["(#{e2}/#{e1})"],&block)
        end
      end
    end
  end

  def solve
    gen_exp(@elem) do |exp|
      val = eval(exp) rescue val = nil
      return exp if val == @val
    end
    "解なし"
  end
end
val, *elem = ARGV.map(&:to_i)
puts Ticket.new(val, elem).solve

ここで、出題をよく読むと「加減乗除」の「除」は使わなくて良いらしい。
有理数クラスが無いので見送っていたscalaの出番（scalaなら有理数クラスの実装も簡単なんだけれどね）。

object Ticket {
  import scala.collection.mutable.Stack
  def main(args: Array[String]) {
    args.map(_.toInt).toList match {
      case x::xs => if (!solve(x, xs, List())) println("No answer")
      case _ => println("Argument error")
    }
  }

  def calcRpn(rpn:List[Any]):Int = {
    var st = new Stack[Int]
    rpn.foreach {
      _ match {
        case "+" => st.push(st.pop+st.pop)
        case "-" => st.push(-st.pop+st.pop)
        case "*" => st.push(st.pop*st.pop)
        case n:Int => st.push(n)
      }
    }
    st.pop
  }

  def solve(ans:Int, nums:List[Int], pn:List[Any]):Boolean = {
    var c1, c2 = 0
    pn.foreach {_ match{case n:Int => c1+=1; case _ => c2+=1}}
    if (nums.size == 0) {
      if (c1 == c2 + 1) {
        if (calcRpn(pn.reverse) == ans) {
          println(pn.reverse)
          return true
        }
        return false
      }
    } else {
      for (i <- 1 to nums.size) {
        var (n1,n2) = nums.splitAt(i)
        if (solve(ans, n1.take(n1.size-1):::n2, n1.last::pn)) return true
      }
    }
    if (c1 > c2 + 1) {
      List("+", "-", "*").foreach {op =>
        if (solve(ans, nums, op::pn)) return true
      }
    }
    false
  }
}