Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« 2009年12月 | トップページ | 2010年4月 »

2010年2月

2010-02-14

「いつふぉろ」リニューアル

Twitter 向けサービス「いつふぉろ」を全面的に更新しました。

もともと、新規フォロー/リムーブを DM で通知するサービス
として公開した「いつふぉろ」ですが、やっぱり DM がうざいので、
Firefox の GreaseMonkey 経由で情報を表示するサービスに変えました。

Twitter の following ページや、フォローしているユーザのプロフィールページに、
自動的に「何月何日からフォローしています」という文字列を埋め込みます。

あと、ついでにサーバプログラムを xyzzy から CGI (Perl) に変えました。
それに伴い、ホームページの URL も変更になっています。

    ⇒ 「いつふぉろ」ホームページ(新)

グリモン自体は、自分では以前から使っていたものを
今回の仕様変更に合わせて修正&改良したものなので、
たぶん安定して動作すると思います。

ちなみに、Google Chrome では動きません。
グリモン独自関数 (GM_xmlhttprequest) を使っているので・・・。


新しく生まれ変わった「いつふぉろ」を、どうぞよろしくおねがいします!

2010-02-07

TopCoder 連載第1回の問題

昨日の記事の連載「最強最強アルゴリズマー養成講座 -- ITmedia」の
バックナンバーを順に追ってみることにしました。

まずは第1回。肩慣らしですね。

  ⇒ 問題(と解答)

あっさり解けました。それでも15分かかりましたが・・・


;; TopCoder (SRM Div2Easy)
;; http://www.itmedia.co.jp/enterprise/articles/0908/01/news001_2.html

; すべての円について、以下を調べる:
;  ・始点と終点がともに円周内にある場合は円周をまたぐ必要はない。
;  ・始点と終点がともに円周外にある場合は円周をまたぐ必要はない。
;  ・片方だけが円周内にある場合は円周をまたがなければならない。


(defun solve (x1 y1 x2 y2 circles)
  (labels ((second-power (x) (* x x))
           (distance (p0 p1)
             (+ (second-power (- (car p0) (car p1)))
                (second-power (- (cadr p0) (cadr p1)))))
           (is-inside (p circle)
             (< (distance p circle) (second-power (caddr circle)))))
    (count-if #'(lambda (c) (xor (is-inside (list x1 y1) c) (is-inside (list x2 y2) c))) circles)))

;====================

(solve 0 0 10 10 '((0 0 2) (5 5 2) (10 10 2)))  ; = 2
(solve 0 0 10 10 '((0 0 20) (5 5 2) (10 10 2))) ; = 1
途中、count-if 関数を手書きしそうになりましたが、 考え直して xyzzy refwiki で検索して count-if を発見。 まぁ、無いわけ無いですよね・・・

TopCoder の「探索」

土曜日の朝、Twitter を眺めていると、@chokudai さんが
TopCoder の記事を書かれたというお話をされていました。


  ⇒ トップクラスだけが知る「このアルゴリズムがすごい」
    --  探索」基礎最速マスター
     --  最強最強アルゴリズマー養成講座
      --  ITmedia


さっそく記事を開いてみると、TopCoder の問題が掲載されてます。


  ⇒ 問題 (SRM456 Div1Medium/Div2Hard)



一見しただけだと難しさがわからなかったのですが、
ちょっと考えてみると、

 ・cut の回数が膨大 (~1,000,000,000) なので、
  できた切片をそのままリストとかで保持すると爆発。

 ・というか、この回数でバックトラック探索とかしたら
  いつまでたっても終わらない。

というわけで、なかなか奥が深そう。




で、気がつけばお昼・・・。なんと4時間もかかりました><

いろいろ試行錯誤した結果、なんとか自力で解けました。

書いてみた Common Lisp のコードは以下のとおり:


;; TopCorder (SRM456 Div1Medium/Div2Hard)
;; http://www.itmedia.co.jp/enterprise/articles/1002/06/news001_3.html
; 
; ※ "k" は 問題より1小さいモノとする(問題は「1ベース」だが「0ベース」で解く)。
;
; 0~k番目までのすべての棒が同じ長さであるのが最適解。それに近づけることを目指す。
; 計算過程において、k>=n のときは「長さ0の棒」があると仮定して処理すればよい。
; 計算過程において、cは十分大きいと仮定して良い(期待より小さいときに打ち切られてもそれが最善解である)。
; 計算過程において、k番目以降の棒の存在は無視してよい。
;
; カットした部分はすべて同じ長さ。それ以外の長さのモノは高々50本しかない。
; よって「カウンタ」と「リスト」で別々に管理する。
;

(defun insert-stick (elem list)
  (if (null list)
      (list elem)
      (let ((pos (position elem list :test #'>=)))
        (cond
         ((null pos) (append list (list elem)))
         ((= pos 0) (cons elem list))
         (t (append (subseq list 0 pos) (cons elem (nthcdr pos list))))))))

(defun cut-stick (length sticks)
  (if (or (null sticks) (< (car sticks) length))
      (values sticks nil)
      (values
       (cond ((< (car sticks) length) sticks)
             ((= (car sticks) length) (cdr sticks))
             ((> (car sticks) (* 2 length))
              (insert-stick (+ length (mod (car sticks) length)) (cdr sticks)))
             (t (insert-stick (- (car sticks) length) (cdr sticks))))
       t)))

(defun try-cut (length sticks) ; ある長さ以上の棒が何本作れるか
  (reduce #'(lambda (acc sample)
              (+ acc (floor (/ sample length))))
          (cons 0 sticks)))

(defun trial (k sticks)
  (labels ((rec (upper-bound lower-bound)
;             (format t "~A ~A~%" upper-bound lower-bound) ; for debug
             (if (= (- upper-bound lower-bound) 1)
                 lower-bound
                 (let* ((length (+ lower-bound (ceiling (/ (- upper-bound lower-bound) 2))))
                        (num (try-cut length sticks)))
                   (if (<= num k)
                       (rec length lower-bound)
                       (rec upper-bound length))))))
    (rec (1+ (car sticks)) 1))) ; ←ほんとは初期値は「最初の k 本の平均」とかにすべき

(defun div2hard (k c sticks)
  (let ((n (length sticks)))
    (cond
     ((= c 0) (nth k sticks))
     ((= k 0) (div2hard k (1- c) sticks))
     (t
      (let* ((length (trial k sticks))
             (count (min c (try-cut length sticks))))
        (block cutting
          (dotimes (i c i)
            (multiple-value-bind (s cont) (cut-stick length sticks)
              (if (not cont)
                  (return-from cutting nil))
              (setf sticks s))))
        (let ((pos (position length sticks :test #'>=)))
;          (format t "~A ~A ~A~%" sticks count k) ; for debug
          (if (null pos)
              (if (< k count)
                  length
                  (or (nth (- k count) sticks) 0))
              (cond
               ((< k pos) (nth k sticks))
               ((< k (+ pos count)) length)
               (t (or (nth (- k count) sticks) 0))))))))))

(defun sample-test (list c k)
  (div2hard (1- k) c (sort list #'>)))
とりあえず Cygwin 上の clisp.exe に喰わせれば動きます。 ちなみに、「棒の長さは整数」と思いこんで解いてしまったので、 記事の回答とは微妙に動作が違っています^^; この問題、最初から「ちからわざ」で探索しようとしても破綻してしまい、 ちょっと気がつけばキレイに解ける、という、良い問題だと思いました。 さすがは TopCoder です。 でも、手強かった・・・。 この連載の他の回でも TopCoder の問題が紹介されてるみたいなので、 時間があるときにトライしてみようと思います~

2010-02-04

ぐりもん on Google Chrome

数日前、Google Chrome がグリモン (GreaseMonkey) に対応した、
とのニュースが流れました。

    
    Google ChromeがGreasemonkeyスクリプトをネイティブサポート
     - INTERNET Watch
    http://internet.watch.impress.co.jp/docs/news/20100202_346437.html


ネイティブ対応なので、プラグイン不要なのがうれしいところです。
JavaScript の動作速度に定評のある Chrome なので、高速化も期待大。

「15~25% のスクリプトが Google Chrome で動作しないと予測している」
らしいので、さっそく自作ぐりもんの動作確認・・・・

 ・・・

 ・・・・・

 ・・・・・・・・・



Seaoak の自作ぐりもんは6個あるのですが、
そのうち1個しかまともに動いてくれませんでした orz

動かない率 83%。




調べてみると、グリモン独自関数(GM_getValue() などの GM_* 系の関数)が
ちゃんと動いてくれていないみたいです。

しかも、それらの関数を typeof すると、ちゃんと "function" が返ります。

つまり、「実装しているフリだけして実は実装してない」という最悪のパターン・・・。




しかたがないので、グリモン独自関数の代わりに HTML5 の新機能を使うことにしました。

GM_getValue() / GM_setValue() については、HTML5 の Local Storage という新機能で
同等のこと(サイトごとのデータの永続化)が可能になるみたいです。
で、Firefox も Google Chrome も Local Storage をサポートしているらしいので、
とりあえず置換してみたところ、一部のスクリプトが期待通りに動作するようになりました。

    ⇒ Google Chrome に対応した「AddFooterIntoTweet」


HTML5 の Local Storage については次のサイトを参考にさせていただきました↓

    ⇒ CONIT Labs.: コニットブログ::HTML5で遊んでみる その2 Web Storage


GM_xmlhttpRequest() についても、HTML5 の Web Socket という新機能で置換できれば
Google Chrome でも動くようになるかもしれないので、ちょっと調べてみます。
これが動かないとグリモンの一番面白い特長が生かせないので・・・

« 2009年12月 | トップページ | 2010年4月 »