■ 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 だとリスト自体から値が湧いて出てくる感じがします。
■ ただただし [古くなった何かを食べて、負けたのかと思ってましたよ]
■ あおき [そう毎日毎日賞味期限切れの食料を食べてるわけにもまいりません (^^;;]