青木日記

■ ruby

ARGF が stdin 待ちになって止まるバグが再発してるようだ。 再現条件がよくわからない。

追記： バグではなく、EOF の後で gets しているのが原因でした。

■ みこみこ

「みこみこみこみこみこみこみこみこみこ」を変換すると落ちる件ですが。 みなさんそんなに「みこみこ」が気になりますか！ (笑)

「らしい」とか書きましたが、メモ帳が落ちるのは確認しておりました。 ネタ元はここ。

• http://pc.2ch.net/test/read.cgi/prog/1053860856/n91-

このスレッドの情報によれば、 発生条件は「みこ」 9 回を変換すること。 こちらで追試してみたところ、8 回までは何も起きず、9 回にすると落ちました。 バグが確認されているプラットフォームは Windows 98 と 2000。 IME は MS IME 2000 ver7.0.1。

繰り返し実行すると OS ごと固まるという話もありましたが 家では 5、6 回やっても大丈夫でした。

■ 切符の数字で 10 を作れ

ついでにもう一個 2ch ネタ。

• http://pc2.2ch.net/test/read.cgi/tech/1052999322/l50

切符に書いてある 4 つの数字を足したり引いたりして 10 にするっていう問題がありますよね。 あれをプログラムで解こうというスレです。

4 桁固定だと力技のループで解けてしまうので、 任意桁数で解くプログラムを考えました。 条件は以下の通り。

• 0〜9 の数 n 個から 10 を作る。
• 使ってよい演算子は + - * /
• 数字の並び順は変えてもよい。
• 割り算は分数を生成するものとする。
• このとき、答えが 10 になる式をすべて表示せよ。
• ただし出力する式が重複してはならない。重複の定義は以下の通り。
• 文字列表現が一致する式は重複とみなす
• 任意の可換な演算子 @ について、a@b と b@a は重複とみなす
• 任意の可換な演算子 @ について、(a@b)@c と a@(b@c) は重複とみなす

a とか b は任意の式です。 例えば (1+2)*(3+4) と (3+4)*(1+2) は重複です。

スレにはもうちょっと詳細な条件が載ってるんですが、 実装が面倒になったのでぼくはこのへんにしときます。 意外に長い。

#
# kippu.rb
#
　
require 'mathn'
　
OPERATORS = [:+, :-, :*, :/]
　
def main
  if ARGV.empty?
    $stderr.puts "no arguments"
    exit 1
  end
  nums = ARGV.map {|a| a.to_i }
  nums.each do |n|
    unless (0..9).include?(n)
      $stderr.puts "wrong value given; use 0-9 (#{n})"
      exit 1
    end
  end
　
  results = {}
  each_valid(nums, OPERATORS, 10) do |tree|
    str = tree.to_s
    if results[str]
      $stderr.puts "\# #{tree.inspect}" if $DEBUG
      next
    end
    results[str] = true
    puts str[1..-2]
  end
end
　
def each_valid( numbers, operators, expect )
  i = 0
  precedences = (0...numbers.length-1).to_a
  each_nPn(numbers) do |nums|
    each_nPr(operators, numbers.length-1) do |ops|
      each_nPn(precedences) do |precs|
        i += 1
        begin
          tree = Tree.build(nums, ops, precs)
          yield tree if tree.evaluate == expect
        rescue NoMethodError => err
          unless /undefined method `<<'/ === err.message
            p nums
            p ops
            p precs
            p tree
            raise
          end
        rescue ZeroDivisionError
          ;
        end
      end
    end
  end
  $stderr.puts "#{i} cases tested" if $DEBUG
end
　
def each_nPn( list )
  generate_combinations(list.length, list.length) do |idxes|
    next unless idxes.length == idxes.uniq.length
    yield idxes.inject([]) {|result, idx| result.push list[idx]; result }
  end
end
　
def each_nPr( list, r )
  generate_combinations(r, list.length) do |idxes|
    yield idxes.inject([]) {|result, idx| result.push list[idx]; result }
  end
end
　
def generate_combinations( len, upper )
  cur = Array.new(len, 0)
  fin = Array.new(len, upper-1)
  while true
    yield cur
    break if cur == fin
    # Increment a set (cur)
    0.upto(cur.length - 1) do |i|
      cur[i] += 1
      break if cur[i] < upper
      cur[i] = 0
    end
  end
end
　
module Tree
  def Tree.build( nums, ops, precs )
    trees = nums.map {|n| LiteralNode.new(n) }
    ops = ops.dup
    precs = precs.dup
　
    cur_prec = precs.length - 1
    while cur_prec >= 0
      idx = precs.index(cur_prec)
      precs.delete(cur_prec)
      rhs, lhs = trees.slice(idx, 2)
      op = ops.delete_at(idx)
      trees[idx, 2] = OpNode.new(rhs, op, lhs)
      cur_prec -= 1
    end
    raise "must not happen: #{tree.inspect}" unless trees.length == 1
    trees[0]
  end
end
　
class OpNode
  def initialize( lhs, op, rhs )
    @lhs = lhs
    @op = op
    @rhs = rhs
  end
　
  def inspect
    "(#{@lhs.inspect}#{@op}#{@rhs.inspect})"
  end
　
  def evaluate
    @lhs.evaluate.__send__(@op, @rhs.evaluate)
  end
　
  COMMUTATIVE_OP = [:+, :*]
　
  def to_s
    if COMMUTATIVE_OP.include?(@op)
      l, r = sort_tree(@lhs, @rhs)
      "(#{l}#{@op}#{r})"
    else
      "(#{@lhs}#{@op}#{@rhs})"
    end
  end
　
  def sort_tree( lhs, rhs )
    if lhs.terminal? and rhs.terminal?
      [lhs, rhs].sort_by {|t| t.value }
    elsif lhs.terminal?
      [lhs, rhs]
    elsif rhs.terminal?
      [rhs, lhs]
    else
      [lhs.to_s, rhs.to_s].sort_by {|s| [-s.length, s] }
    end
  end
  private :sort_tree
　
  def terminal?
    false
  end
end
　
class LiteralNode
  def initialize( val )
    @value = val
  end
　
  attr_reader :value
　
  def inspect
    @value.to_s
  end
　
  def evaluate
    @value
  end
　
  def to_s
    @value.to_s
  end
　
  def terminal?
    true
  end
end
　
main

戦略は単純な総当たりです。 each_nPn とか generate_combinations のあたりは Haskell のほうが簡単に書けそう。

と言うか、Haskell のリストを念頭に置いてイテレータに落としました。 イテレータと遅延評価のリストは非常に感覚が似てますね。 イテレータはメソッドから値が湧いてくるけど、 Haskell だとリスト自体から値が湧いて出てくる感じがします。