AOJ0052 Factorial II

問題

例によってRubyで書いた。

末尾に0がつく===10が掛かっている===2と5がかかっている、だから
素因数の2と5の少ない方が0の個数になる、という方針で解いた。

以下ソースと、テスト。

# encoding: utf-8
class ZeroCounter
  attr_accessor:num
  attr_accessor:num_zero
  def initialize(i)
    @num = i
    @num_zero = [count_num_of_primes(2), count_num_of_primes(5)].min
    p @num_zero
 end

  def count_num_of_primes(prime)
    num_pf = 0
    i = prime
    while @num / i > 0 do
      num_pf += @num / i
      i = i * prime
    end
    return num_pf
  end
end

while (line = gets) do
  if line.to_i != 0 then
    ZeroCounter.new(line.to_i)
  end
end
#encoding: utf-8
require 'rspec'
require './a'

describe ZeroCounter do
  it "should return the num of prime factor 2" do
    zc = ZeroCounter.new(19)
    zc.count_num_of_primes(2).should == 16
  end
  it "should return the num of zeros of factorial" do
    zc = ZeroCounter.new(19)
    zc.num_zero.should == 3
  end
  it "should return the num of zeros of factorial" do
    zc = ZeroCounter.new(45)
    zc.num_zero.should == 10
  end
  it "should return the num of zeros of factorial" do
    zc = ZeroCounter.new(50)
    zc.num_zero.should == 12
  end
end

AOJ0067 The Number of Island

問題
ほとんどこれと同じコードで通るんじゃないかとおもって
入力部分とneighbor返すところだけ少し手直ししたら通った。

入力部分がなんか汚いのはご愛嬌。
最後に空行があるのかないのかわからなかったので両方いけるようにした。

 class IslandCounter
  attr_accessor :map
  def initialize(map)
    @map = map
  end

  def neighbors(y, x)
    w = map[0].length
    h = map.length
    neighbor_list =[[y-1, x], [y, x-1], [y, x+1], [y+1, x]]
    return neighbor_list.select{|i| i[0] >= 0 && i[0]<h && i[1] >=0 && i[1]<w }.select{|i| @map[i[0]][i[1]] == 1 }
  end

  def num_island_color
    @map.flatten.sort.uniq.select{|i|i!=0}.length
  end

  def explorer_all_islands
    num_islands = 0
    while (coord = find_new_island) != nil do
      num_islands += 1
      explorer_in_an_island(coord[0], coord[1])
    end
    return num_islands
  end

  def explorer_in_an_island(y, x)
    @map[y][x] = 0
    neighbors(y, x).each{|coords|
      explorer_in_an_island(coords[0], coords[1])
    }
  end

  def find_new_island
    if @map.flatten.include?(1) then
       h = @map.length
       w = @map[0].length
       place = @map.flatten.index(1)
       return [place / w, place % w]
    else
       return nil
    end
  end
end

current_map = Array.new
while (line = gets) do
line = line.chomp
  if line != "" then
    current_map.push line.split("").map{|i| i.to_i}
  else
    if current_map.size > 1 then
    ic = IslandCounter.new(current_map)
    p ic.explorer_all_islands
    current_map = Array.new
    end
  end
end
if current_map.size > 1 then
  ic = IslandCounter.new(current_map)
  p ic.explorer_all_islands
end

AOJ1160 How Many Islands?

問題リンク

Rubyで書いてみた。

class IslandCounter
attr_accessor :map
def initialize(map)
@map = map
end
def neighbors(y, x)
w = map[0].length
h = map.length
neighbor_list =[[y-1, x-1], [y-1, x], [y-1, x+1], [y, x-1], [y, x+1], [y+1, x-1], [y+1, x], [y+1, x+1]]
return neighbor_list.select{|i| i[0] >= 0 && i[0]=0 && i[1]

Inputに対するOutputは正しそうな感じなんだけれども、
50*50で1を敷き詰めるInputをあたえたら、stack level too deep (SystemStackError)だった。
アウトプットするとあと一行かそこらで数え切れそうなんだけど惜しい感じ。
もうちょっと効率化したらRubyでもいけそうなんだけど…

というわけで上記コードは未Acceptです。

Rubyの再帰の限界を調べてみる

深さ優先探索の問題（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160）を
解いていたら手元のサンプルインプットではうまく動くのだけど、
Online Judgeに投げ込むとうまく動かない。（Runtime Errorとのこと）

ためしに問題の上限サイズで入力例を作ったら、
a.rb:11: stack level too deep (SystemStackError)
みたいなエラーがでたので再帰が深すぎてエラーに成ってるのではないか。

興味が出たのでRubyの再帰について調べてみる。

def func(n)
if n == 1 then
return "hoge"
elsif n > 1
#p n
func(n-1)
end
end
p func ARGV[0].to_i

っていうスクリプトを作っていろいろ引数を変えて動かしてみる。

ruby --version
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux]

# ruby stacktest.rb 8735

だと

stacktest.rb:2: stack level too deep (SystemStackError)

# ruby stacktest.rb 8734

だと

"hoge"

と表示されるので、このコード・環境での再帰の限界は8734回までということになる。

ruby --version
ruby 1.8.7 (2012-06-29 patchlevel 370) [x86_64-linux]

に切り替えると、

# ruby stacktest.rb 5727
"hoge"
# ruby stacktest.rb 5728
stacktest.rb:6:in `func': stack level too deep (SystemStackError)
from stacktest.rb:6:in `func'
from stacktest.rb:9

になるので、5727回まで。

また1.9.3に戻して、

def func(n)
if n == 1 then
return "hoge"
elsif n > 1
arr = Array.new [" "]
return func(n-1)
end
end
p func ARGV[0].to_i

っていう形で関数が余計なarrを保持するようにすると、8188回までで打ち止め。
arrを削ったら8734回まで行けるようになった。

というわけで、

  • 呼び出し元メソッドが確保している変数などの領域を増やすと

スタック呼び出し可能な深さが減る

  • RubyのVersionによってもスタック呼び出し可能な深さが減る

ということは分かった...けど直接的に呼び出し可能回数をもっと増やすにはどうしたらいいかは
よくわからないままです（オチなし）

        • -

追記: コメントでRuby2.0以降では、環境変数にRUBY_THREAD_VM_STACK_SIZEを設定することでスタックサイズが設定できると情報をいただきました。

謝辞

元データは青空文庫様にお借りしました。
青空文庫・作家別ページ「石川啄木」
青空文庫トップページ
Rubyのコミュニティの皆様、Rubyとても便利です。これからも使わせていただきます。
また、Botのアイコンには日本文学館様の『一握の砂 他』の端正な印象の書影をお借りしております。
そして素晴らしく心に刺さる数々の詩を残してくださった石川啄木さん(1886 - 1912)に感謝します。

石川啄木のTwitterBotを作った

mizti2009-02-14

Twitter上で石川啄木の詩を呟くBotをRubyの習作がてら作ってみました。
http://twitter.com/takuboku_

  • 仕様

・ときどき（今は/2h）、石川啄木の詩を呟く。
・元データは『一握の砂』『悲しき玩具』の2冊
・Followは返しません。
・Replyへの反応もしません

  • 動機

石川啄木の詩があまりにも他人に思えず、またTwitterの風土に馴染みそうと感じていました。
これをTwitter上でちょくちょく読めたら嬉しいな、と思い作りました。

  • 製作

Rubyの手習いも兼ねているので、Ruby環境の導入から開始しました。

TwitterのAPIはTwitter4r（Ruby用TwitterAPIライブラリ）を使ったのですが、
最初Windowsでgemを動かすのに難渋、最終的にはMac上で作業をしました。
Macってデフォルトでruby入ってるんですね･･･

元のBookデータを適当にパースしてXML化、ランダムに読み込んで表示させています。

最初は普通に立ち上げっぱなしのデスクトップで走らせればよいかとも思ったのですが、
自由に使えるサーバがあったことを思い出したのでそちらでデーモン化して動かしています。
RubyのWebrickだとデーモン化も3行程度で済みました…。

  • 命名

「たくぼっと」と名づけようかとも思いましたが、故人に失礼かな、と思いid:takuboku_、名前:石川啄木になっています。
ただ、だんだん普通のついったったーさんにしか思えない瞬間が増えてきたので変えないとは限りません。

  • 所感

元は三行詩の作品なので、そのリズムを殺さないようにどうすればいいのか悩みました。
新聞などで標準となっている＼による分かち書きは個人的に目障りに感じてしまって好きでないので
今のところは改行を全角スペースで置き換えることで対処しています。
良いお知恵がありましたらお貸しいただけるとうれしいです。

「TWAINソースが選択できません」の解決

mizti2009-01-11

Canonのスキャナ（うちの場合はLiDE40）で「TWAINソースが選択できません」というエラーに時々出くわしていました。

今回本格的に困ったのでいろいろ踏ん張っていたところ、
「悟茶辞苑ッ」さんのところのエントリに救われました。

以下引用です

Canoscan 9950F ドライバの問題：回避方法

以下不具合報告の手短なレポ。システムの環境変数PATHに値を追加するようなアプリケーションが多数インストールされている場合、スキャナドライバが正常に動作しない。

PATHの長さ制限は2,000文字程度だけれど、CanoScanドライバは700文字を超えたあたりで不具合が起きる。

スキャン時には一時的にPATHの値を短くしてやる必要がありそう。

私にはどうもキヤノンがこの問題を深刻なものとして取り扱っているようには思えない。問題を報告して数年が経過したにもかかわらず、この問題は未だに修正されていない（ナレッジベースにも掲載されていない）。それに、どうも9950Fに限らずいろいろなモデルのスキャナで起こるっぽい。

もし（明らかにそれがあるにも関わらず）「rmslantc.dll」が見つからないというエラーメッセージが出て、ドライバを再インストールするよう勧められたなら、このバグのせいだ。

アプリケーションによってはDLLが欠けているとは告げず、単純にスキャナが利用可能でないと報告するかと思う。

役立つ回避方法としては、PATHをシステムのものとユーザ別のもので分けてしまうこと。必須ではない（システム関連ではない）値はユーザ別のPATH変数に入れる。

ユーザ別のPATHは値の内容を損なうことなく、その場で直接編集によって一時的に名前を変更することができる（再ログインが必要　※訳者注：私の場合、システムのPATHを短くして問題の解決を確認したんだけど、特に再ログインの類も必要なかったです。ただ、スキャナを使うアプリケーションの再起動は必要かも）。

このさらに元の記述はこちら。


PATHを削る、だけで解決するとは思いませんでした。
（XPの場合、PATHをいじるには、「マイコンピュータ」を右クリックー＞プロパティー＞「詳細設定」タブー＞「環境変数」ボタン
ー＞「システム環境変数」囲み内の“PATH”を選択して編集でいけます。
どれが必要かわからなければ、とりあえず全部メモ帳あたりにコピーして、設定してスキャン。後で書き込みなおせばよいと思います。）

gochaさま、元記事を書いたreviewerさまありがとうございました。