「みこみこみこみこみこみこみこみこみこ」を変換すると落ちる件ですが。 みなさんそんなに「みこみこ」が気になりますか! (笑)
「らしい」とか書きましたが、メモ帳が落ちるのは確認しておりました。 ネタ元はここ。
このスレッドの情報によれば、 発生条件は「みこ」 9 回を変換すること。 こちらで追試してみたところ、8 回までは何も起きず、9 回にすると落ちました。 バグが確認されているプラットフォームは Windows 98 と 2000。 IME は MS IME 2000 ver7.0.1。
繰り返し実行すると OS ごと固まるという話もありましたが 家では 5、6 回やっても大丈夫でした。
ついでにもう一個 2ch ネタ。
切符に書いてある 4 つの数字を足したり引いたりして 10 にするっていう問題がありますよね。 あれをプログラムで解こうというスレです。
4 桁固定だと力技のループで解けてしまうので、 任意桁数で解くプログラムを考えました。 条件は以下の通り。
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 だとリスト自体から値が湧いて出てくる感じがします。
昔書いたこれは任意桁数に容易に拡張できますが、
重複を除くのは厄介かもしれません。
http://www.lava.net/~shiro/Private/diary/0112.html (12/11)
なつかしい、お題だったりします。「切符問題」
そのときの発端は、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
でも、このときは、全解ではなかったなぁ。
2001年にもう流行って(?)たんですね…。
読書会でも話が出ましたけど、式の同値判定
まで考えるのは結構面倒ですね。