トップ «前の日記(2006-11-13 (Mon)) 最新 次の日記(2006-11-16 (Thu))» 編集

uDiary

海野秀之(うんのひでゆき)の外部記憶

Twitter (twilog) / RSS / アンテナ / ぶくま

2006|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|08|
2010|01|02|03|05|06|07|10|11|
2011|03|08|
2012|02|04|07|08|10|
2013|01|02|03|05|06|08|11|12|
2014|01|02|05|06|07|08|09|12|
2015|01|02|03|04|

2006-11-15 (Wed)

[Web] Google の SEO 対策(?)と不安定

このところ Google の検索結果にでなくなってしまっている 「水からの伝言」を信じないでください の冒頭に、以下のような文が追加されていた。

11 月 11 日前後から、このページが Google の検索にかからなくなっています。 これは、最近頻出している Google の技術的トラブルの可能性が高いとの ご指摘をご専門の方からいただきました。 要は、Google に頼りすぎてはいけないということでしょうね (11月14日)。

そういえば、最上嗣生さんがGoogle に ad-hoc なアルゴリズムを導入することで不安定になると言っていた のを思いだした。

(蛇足) 私は google の試行錯誤的なシステムが改変がいけないことだとは思っていません。 さっきの局所最適解と次の局所最適解の間は不安定でしょうから。 (←しまった、最上さんの主張をまったく理解していないように見えるなぁ。)

[Ruby] 切符問題そるば

似たような出題を二回目撃してしまったため、 スルー力(するー・りょく)及ばず、変なフラグが立ってしまった。

いずれも 24 をターゲットにしているのは、切符問題にはなにか僕の知らない流儀でも?? さらに、解いてみると(と書くとさくっと解いたように聞こえるかも知れませんが、恥ずかしながら、 そんなことはありません *1) 、いずれの答えも同じ形の構文木になります。

むむー、この形が人間にとっては思いつきにくいということかな。

まだお二人のコードをきちんと読んでいませんが、 おそらく、それらとくらべて断然素人臭いと思われますが、拙作を以下に (ticket.rb)。

いやね、There is more than one way to do it が言い訳モットーでして。

次は scheme で書いてみよう。Shiro Kawai さんのコードを詳しくしらべるのはそれから。 (ざっと見た感じ、あんなコードは僕からは出てきそうにもない。非決定性なんちゃらって何だ? *2

#!/usr/local/bin/ruby
=begin
ticket.rb
  いわゆる切符問題をときます。
  「1, 3, 4, 6 の 4 つの数字(順序は入れ替えてよい)と四則演算をもちいて
    24 をつくれ」
  だったら、
  ./ticket.rb 24 1 3 4 6
  になります。
=end

require 'rational'

=begin
== each_tree_permutaion(array) {|a| ... }
  配列をうけとって、構文木の候補を生成します。
  たとえば、[a, b, c] からは
     [[a, b], c], [[b, a], c], [c, [a, b]], ...
  が次々に生成されブロックに渡されます。
=end
def each_tree_permutation(ary)
  pr = Proc.new

  if ary.size > 2
    0.upto(ary.size - 1) do |i0|
      a = ary.dup
      x = a.delete_at(i0)

      0.upto(a.size - 1) do |i1|
        b = a.dup
        y = b.delete_at(i1)

        0.upto(b.size) do |j|
          each_tree_permutation(b.dup.insert(j, [x, y]), &pr)
        end
      end
    end
  else
    pr.call(ary)
  end
end

=begin
== each_operations(ary){|a| ... }
  each_tree_permutation で生成された木の各ノード [x, y] に
  可能な四則演算をはめこんでブロックに渡します。
  [x, y] は、['+', x, y], ['-', x, y], ['*', x, y], ['/', x, y]
  になります。y が 0 でないか等の検査はしない。
  (eval まかせ)
=end
OPS=['+', '-', '*', '/']

def each_operations(ary)
  x,y, = ary

  def unexpanded?(a)
    a.class == Array and a.size != 3
  end

  if unexpanded? x
    each_operations(x) do |a|
      if unexpanded? y
        each_operations(y) do |b|
          OPS.each do |op|
            yield([op, a, b])
          end
        end
      else
          OPS.each do |op|
            yield([op, a, y])
          end
      end
    end
  else
      if unexpanded? y
        each_operations(y) do |b|
          OPS.each do |op|
            yield([op, x, b])
          end
        end
      else
          OPS.each do |op|
            yield([op, x, y])
          end
      end
  end
end

=begin
== eval(expr) => [value, string]
  each_operation が返す形式を受け取って、
  値を評価します。
  評価値と式の表現(文字列)の組を返します。
=end
def eval(expr)
  op, x, y, = expr

  def v_and_s(a)
    if a.class == Array
      eval(a)
    else
      [a, a.to_s]
    end
  end

  x_val, x_str = v_and_s(x)
  y_val, y_str = v_and_s(y)

  ret_val = nil
  if x_val and y_val
    case(op)
    when '+'
      ret_val = x_val + y_val
    when '-'
      ret_val = x_val - y_val
    when '*'
      ret_val = x_val * y_val
    when '/'
      if y_val != 0
        ret_val = x_val / y_val
      else
        ret_val = nil
      end
    end
  end

  ret_str = "(#{x_str} #{op} #{y_str})"

  [ret_val, ret_str]
end

# ======== main ========

target = ARGV.shift.to_i

n = []
ARGV.each do |a|
  n << Rational(a.to_i, 1)
end

hash = {}

each_tree_permutation(n) do |tree|
  each_operations(tree) do |expr|
    v,s = eval(expr)
    if v == target
      puts s unless hash[s]
      hash[s] = true
    end
  end
end

書いてみて:

  • 関数内ローカル関数をはじめて書いてみた。
  • ['+', a, b] とか schemer っぽい?
  • 自分にわたされたブロックをうけとる方法が Proc.new とは意外でした。
  • っていうか、いくらなんでも eval をあっさり隠す度胸ってどうなの?>自分

どれも、今回の問題とはあんまり関係ないうえに、「だから何?」的な。

しまったぁ、 Enumerable::each_with_index (昨日 tdiary のソースをみてて知った) 使えばよかった。(自分で書きながらも、0.upto(a.size - 1) はないだろうと)

追記

案の定、あとから見ると恥ずかしいところがぞろぞろですね。

とりあえず、each operations なんで複数なのか、とか。コメントが……とか。 でも、書き直すんだったら一年後(←なぜ?

*1 ついでに白状しとくと、ここに載せたコードの前に、ちゃんと答えを見つけられない失敗作がいっこありました。えへ。

*2 や、非決定性オートマトンなら学校でならったかな。決定性に書き直せとかいわれたりして。

Schemer っぽい?

PostScript の言語仕様を読んでいて。 オペレータが後置なのと、括弧がないのが気持ち悪くて仕方がない。

これって、ちょっと Schemer っぽい?(うれしい)


2006|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|08|
2010|01|02|03|05|06|07|10|11|
2011|03|08|
2012|02|04|07|08|10|
2013|01|02|03|05|06|08|11|12|
2014|01|02|05|06|07|08|09|12|
2015|01|02|03|04|
Categories 3imp | Card | Cutter | Dalvik | Euler | Football | GAE/J | Hand | Haskell | Re:View | Ruby | Scheme | TQD | Tiger | TigerBook読 | UikiTeXi | Verilog | Violin | Web | parconc | tDiary | お勉強 | エントロピー | ツン読 | | 将棋 | 政治について | | 模写してみよう | 確率論 | 設定など | 雑文 | 音声