K.Sasada's Home Page

こめんとのついか

こめんとこめんと!

message

please add long comment :).

_12(Mon)

タクシーかけご飯が昨日から頭から離れず、眠れないのでちょこちょこと。

問題の定義を明確にしておくと、a,b,c,d は自然数で、a<c<d<b とする。で、x = a**3 + b**3 == c**3 + d**3 となる x を、小さい順に求める。また、x を作る a,b,c,d も同時に答える。ということにしておく。

とりあえず ruby でこちょこちょと。

def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if sumcube(a) == sumcube(b)
      a,b = b,a if a[0] > b[0]
      puts "#{a.inspect} , #{b.inspect} => #{sumcube(a)}"
      found += 1
    end
    b = a
  end
end

queue = [[9,[1,2]]]

taxi_nums(30){
  r = queue.shift
  queue << [r[0],r[1]+1]
  queue << [r[0]+1,r[1]] if r[0]+1 < r[1]
  
  queue.sort!{|a,b|
    sumcube(a) <=> sumcube(b)
  }
  queue.uniq!
  r
}

うーん、まだまだ長いし非効率だ。セミコロンつかってるのは卑怯かなぁ。

というか、状態を持つってこと自体、これをそのままschemeに落としたらまずい気がする。

・・・queue を引数で渡してしまえばいいんかな。


def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if a[0] == b[0]
      a,b = b,a if a[1][0] > b[1][0]
      puts "#{a.inspect} , #{b.inspect} => #{a[0]}"
      found += 1
    end
    b = a
  end
end

queue = [[1,2]]

taxi_nums(30){
  r = queue.shift
  a = r[1][0]
  b = r[1][1]
  c = [a,b+1]
  queue << [sumcube(c),c]
  if a+1 < b
    c = [a+1,b]
    queue << [sumcube(c),c]
  end
  
  queue.sort!{|a,b|
    a[0] <=> b[0]
  }
  queue.uniq!
  r
}

22秒から3秒。って、これは前がひどかっただけな気が・・・。uniq 外せれば速くなるんだろうけどなぁ。

def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if a[0] == b[0]
      a,b = b,a if a[1][0] > b[1][0]
      puts "#{a[1].inspect} , #{b[1].inspect} => #{a[0]}"
      found += 1
    end
    b = a
  end
end

queue = [[9,[1,2]]]

taxi_nums(30){
  r = queue.shift
  a = r[1][0]
  b = r[1][1]
  c = [a,b+1]
  queue << [sumcube(c),c]
  if a+1 == b
    c = [a+1,b]
    queue << [sumcube(c),c]
  end
  
  queue.sort!{|a,b|
    a[0] <=> b[0]
  }
  r
}

2秒。あとはsortが速くなることを期待するだけ(ぉ。rubyの組み込みソートが何使ってるか知らんけど。priority queue を作ろうかと思ったけど血迷ってるよなぁ、と考えて辞め。

記念(何の)に、100個答え。を書いていたのだけど、あまり面白くないので削除。


児玉さんの priority queue for Ruby. を利用したら、30個を0.5秒。100個を2秒。ハヤ。

GHC だともっと速かったりするのかしらん。


[ruby-math:00851] Ramanujan Number。お、たいむりー?

if a+1 == b じゃなくて a+2 だなぁ・・・。


priority queue 利用版も書いておこうっと。

def sumcube e
  e[0]**3+e[1]**3
end

def taxi_nums n
  b = yield ; found = 0
  while found < n
    a = yield
    #puts "#{a.inspect} => #{sumcube a}"
    if a[0] == b[0]
      a,b = b,a if a[1][0] > b[1][0]
      puts "#{a[1].inspect} , #{b[1].inspect} => #{a[0]}"
      found += 1
    end
    b = a
  end
end

require 'pqueue'
queue = PQueue.new lambda{|x,y|
  x[0] < y[0]
}
queue.push [9,[1,2]]

taxi_nums(30){
  r = queue.pop
  a = r[1][0]
  b = r[1][1]
  c = [a,b+1]
  queue.push [sumcube(c),c]
  if a+2 == b
    c = [a+1,b]
    queue.push [sumcube(c),c]
  end
  r
}

pqueue.rb内、微妙に loop をつかうと遅いっぽいので、while true ; ... ; end に書き換えた。


今TA(さすがにTerminalAdapterはできないですが。2台あるんだけど、今売っても捨て値だよなぁ・・・)やってるんですが、Javaの実験で。いやー、なんかソースが書ける、わかるって凄いなぁ。


ruby-math に投稿してみようかとか思ったけどなんかネタ晴らしになりそうなのでやめとこう。


で、ですねぇ。RHG飲み会をさぼったのは(金が無いのと)ケースを買いに行くためだったんですよ。

というわけで、ケースを買いました。自宅サーバ用ケース。今までは電源込みで5000円。店頭で投売りのアレです。

今度はちゃんとしたやつを買いました。3.5インチベイが6個も入ります。電源も別々に買いました。ケースファンについても、初めてその存在を知りました。しかも、前面にも着けられるらしいです。というわけで、着けました。

・・・前面ファンうるせー。夏まで止めとこう。

金が無いのでSICP飲み会も微妙な感じが。うーん、どうしようかな。飲み会に行かない代わりに K本さんに言語処理系の講義をしてもらったりなかったり。


編集追加、っと。


scheme版がやっと出来た。

; ((sum-of-cube a . b) ...)
(define (taxi-numbers)
  (define (sumcube a b) (+ (expt a 3) (expt b 3)))
  (define (insert lst e)
    (if (or (null? lst) (>= (caar lst) (car e)))
        (cons e lst)
        (cons (car lst) (insert (cdr lst) e))))
  ; next list
  (define (next lst e)
    (let ((a (car e)) (b (cdr e)))
      (insert (if (= (+ a 2) b)
                  (insert lst (cons (sumcube (+ a 1) b) (cons (+ a 1) b))) ; then
                  lst) ; else
              (cons (sumcube a (+ b 1)) (cons a (+ b 1))))))
  (define (iter lst b)
    (let ((a (car lst)))
      (if (= (car a) (car b))
          (cons (cons (cdr a) (cdr b)) (lambda () (iter (next (cdr lst) (cdr a)) a)))
          (iter (next (cdr lst) (cdr a)) a))))
  (iter '((28 1 . 3)) '(9 1 . 2)))

(define (display-taxi-nums max)
  (define (iter lst m)
    (if (= 0 m)
        #t
        (begin
          (display (car lst)) (newline)
          (iter ((cdr lst)) (- m 1)))))
    (iter (taxi-numbers) max)
  )

(display-taxi-nums 1000)

なんか、根本から考え方が間違えてる気がしなくもない。自分でも全然よみずらすぎるし。


NArray って、ウワ・・・それは卑怯じゃ。しかし、こんなのがあるんですね。今度使おうっと。

なんつうか、数学の理論屋さんと、代数屋さんの違いなんだろうか。

_nobsun(Mon May 12 17:04:34 JST 2003)

 GHCしても速くならんでしょうなぁ。hugs よりは速いという程度でしょう

_笹川 賢一(Mon May 12 19:05:17 JST 2003)

 SICP第2章の写像の入れ子がタクシーの雰囲気に似てますね。

_はら(Mon May 12 19:25:32 JST 2003)

 ぜひ ruby-math に送ってください。複数パターンで。明日ならもういいでしょう。(^^

_はら(Mon May 12 19:26:43 JST 2003)

 笹田さんのこのページ、ウチの大学からアクセスできません。もしかして、*.ac.jpをはねてる?(^^;

_ささだ(Mon May 12 19:42:20 JST 2003)

いや、そんな素敵な設定はしてないはずなんですが。というか、これCGIじゃなくてHTMLなので、弾くならサーバ側でしか無理です(.htaccessも置いてないし)。当研究室のトップページからも、弾かれますでしょうか?

_ささだ(Mon May 12 19:54:49 JST 2003)

 というか、*.ac.jp禁止にしたら、自分のところから見れません(笑)


好きなだけ長いコメントをどうぞ。

お名前


back

tton 記述が使えます。YukiWikiな記述してりゃ問題ありません。

「行頭に#code」 と、「行頭に#end」 で挟むと、その間の行は pre で囲まれます。プログラムのソースを書くときに使ってください。

例:

#code

(なんかプログラム書く)

#end

リンクは

[[なまえ|http://www.example.org]]

とか

[[http://www.example.org]]

で貼れます。

$Date: 2003/04/28 10:27:51 $