history

青木日記 RSS

<前の日 | この月 | 次の日>

2003-06-27

ruby

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

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

みこみこ

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

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

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

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

切符の数字で 10 を作れ

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

切符に書いてある 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 だとリスト自体から値が湧いて出てくる感じがします。

本日のツッコミ(全4件) [ツッコミを入れる]
shiro (2003-06-27 17:47)

昔書いたこれは任意桁数に容易に拡張できますが、
重複を除くのは厄介かもしれません。
http://www.lava.net/~shiro/Private/diary/0112.html (12/11)

nobsun (2003-06-27 18:08)

なつかしい、お題だったりします。「切符問題」
そのときの発端は、http://www.lava.net/~shiro/Private/diary/0112.html
で、拡がったのは
http://namazu.org/~satoru/diary/?date=20011211#p03
からかなぁ。で、そのときのHaskell版は
http://www.sampou.org/nobsun/journal/?200112b&to=200112160#200112160

nobsun (2003-06-27 18:16)

でも、このときは、全解ではなかったなぁ。

あおき (2003-06-29 03:04)

2001年にもう流行って(?)たんですね…。
読書会でも話が出ましたけど、式の同値判定
まで考えるのは結構面倒ですね。

名前
メールアドレス

<前の日 | この月 | 次の日>
2002|04|05|06|07|08|09|10|11|12|
2003|01|02|03|04|05|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|04|05|06|09|10|
2009|07|
2010|09|

Copyright (c) 2002-2007 青木峰郎 / Minero Aoki. All rights reserved. LIRS