2013-01-10

2012年12月第4回granpark.rb 「山本山の野望」

12月の勉強会で出した課題と回答。

1問目は(1)回文判定と、(2)与えられた文に+αして最短の回文にするっていう内容。
(2)をいろいろな書き方をする人が多くて面白かった。

2問目は与えられたマップから島（コロニー）の数を数える、という問題。
勉強会の時間内では1問目でタイムアップのチームが多かったけど、
勉強会時間外のタイミングで解いてきてくれた人もいました。
解答例はDFS（深さ優先探索）です。

2012-11-18

2012/11/16 第2回granpark.rb 「ポーの惑星」

社内勉強会で、ペアプログラミングでアルゴリズムの問題を解いてみよう！っていう
試みがあったのでこんな問題を作った。

解答例はこちら

見る人が見ればすぐわかるように、（逆じゃない）ポーランド記法を
処理しましょう、って旨。
上記のように、逆から読んでいってスタックで処理する...を
想定してたんだけど制限時間内に構文解析をちゃんと書いてきたチームが複数あって
びっくりした。

作問する側としても想定外の解き方が出てきて面白いので、
次週以降も続けたいところ。

2012-11-18

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

2012-11-18

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

2012-11-17

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です。

2012-11-13

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を設定することでスタックサイズが設定できると情報をいただきました。

2009-02-14

謝辞

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