Hatena::Grouprubyist

krystal: プログラミング超初心者(文系)

2008-12-15 (Mon)たのしいRuby練習問題

OrderedHashを定義してみよう

20:25

  • 順番を保存するハッシュクラスを定義する
  • 以下のような動きをすることとする
oh = OrderedHash.new
oh["one"] = 1
oh["two"] = 2
oh["three"] = 3
oh["two"] = 4
p oh.keys    #=> ["one", "two", "three"]
p oh.values  #=> [1, 4, 3]
class OrderedHash < Hash
  def initialize
    @index1 = []          #配列にする
    @index2 = []
  end
  
  def []=(key,value)      #[]= をオーバーライドしている
    @index1.delete(key)   #重複を避ける
    @index1.push(key)     #keyを配列に入れる
    @index2.delete(value) #重複を避ける
    @index2.push(value)
    super(key,value)      #superは現在のメソッドがオーバーライドしているメソッドを呼び出す
  end

  def keys
    @index1.each{|key|
      ary1 = Array.new << key
    }
  end
  
  def values
    @index2.each{|value|
      ary2 = Array.new << value
    }
  end
end
oh = OrderedHash.new
p oh                       #=>  {}
oh["puppy"] = 1            
oh["kitty"] = 2             
oh["snoopy"] = 3             
oh["daisy"] = 4              
oh["aho"] = "ahoaho"         
oh["kitty"] = 3              
p oh                       #=>  {"snoopy"=>3, "kitty"=>3, "aho"=>"ahoaho", "daisy"=>4, "puppy"=>1}
p oh.keys                  #=>  ["puppy", "snoopy", "daisy", "aho", "kitty"]
p oh.values                #=>  [1, 2, 4, "ahoaho", 3]

配列にして取り出そうと考えたが、うまくできず。結局他人が書いたものを参考にしたが、全部理解できなくて、自分なりに変更して書いてみたけど、はやり問題が要求している動きはしていない。→ keyとvalueは関連付けされてないみたい。

2008-12-10 (Wed)Ruby練習問題

ゼロをカウント[Part Ⅱ]

19:43

  • 今回は 0~1000万までカウント
require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{

#1~10万まで
a = (1..1e5).to_a.join.count("0")       

#10万1~20万まで
b = (100001..2e5).to_a.join.count("0")  

#0~100万まで
c = 1 + a.to_i + (b.to_i * 9) + 1       

#100万1から200万まで
d = (1000001..2e6).to_a.join.count("0") 

#0~1000万まで
p c + (d.to_i * 9) + 1   #=> 5888897 
}            
      user     system      total        real
5888897
  5.844000   0.000000   5.844000 (  5.234000)

(0..1e7).to_a.join.count("0")だと物凄く時間かかるから、分けて数えたほうが少し速くなるのかなって思って。

1 + (1~100000) + (100001~200000)*9 + 1 + (1000001~2000000)*9 + 1


違うやり方について、ヒントもらったので今書いてる最中。

たぶん↑よりもっともっと速くなるはず。たぶん


Stringクラスを使わずに計算してみる

require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{
def zerocount_from_zero_to(num)
  n = 10                 #10からゼロを数える
  count = 1              #↑は10からだから、10以内の場合は0がひとつしかないので、最初から一回カウント
  
  while n <= num  
    a,b = n.divmod(10)  
    while a >= 1         #商は1以上、つまりnは10以上の場合
      if b == 0          #余りは0であれば10の倍数ということで0で終わってる数字のはず
        count += 1       #なので、0を一つカウント
      end 
      a,b = a.divmod(10) #さらに10で割って判断する
    end
    n += 1               #nを一つずつ試していく。ここが効率悪い?
  end
  return count
end

p zerocount_from_zero_to(1e6)
}
      user     system      total        real
488896
  7.563000   0.000000   7.563000 (  6.782000)

これは100万まででもかなり時間かかってた。一つずつ試していくから効率が悪い。


↑二つの方法を合体してみる

require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{

def zerocount(n,num) #nもnumと同じように渡す

  count = 0
  
  while n <= num  
    a,b = n.divmod(10)  
    while a >= 1         #商は1以上、つまりnは10以上の場合
      if b == 0          #余りは0であれば10の倍数ということで0で終わってる数字のはず
        count += 1       #なので、0を一つカウント
      end 
      a,b = a.divmod(10) #さらに10で割って判断する
    end
    n += 1               
  end
  return count
end

a = zerocount(0,1e5)                    # 0から10万まで 
b = zerocount(100001,2e5)               # 10万1から20万まで
c = zerocount(1000001,1100000)          # 100万1から110万まで
p 1 + a + b*9 + 1 + (c + b*9 + 1)*9 + 1 # 足りないゼロの数は自分で追加しないとダメ...
}

      user     system      total        real
5888897
  2.219000   0.000000   2.219000 (  1.984000)

速くなったが、やっぱりややこしい。

2008-12-08 (Mon)

P244 - str2hashを定義しよう

19:15

  • ハッシュには配列の%wのようなものがありません
  • 空白(/\s+/)で区切られた文字列をハッシュに変換するメソッドを定義しよう
def str2hash(string)
  ary = string.split(/\s+/)
  Hash[*ary]   #多重代入
end

p str2hash("blue 青 white 白\nred 赤")                           #=> {"white"=>"白", "blue"=>"青", "red"=>"赤"}
p str2hash("movie 死神の精度 book ハリーポッター music ロック")  #=> {"music"=>"ロック", "movie"=>"死神の精度", "book"=>"ハリーポッター"}

メモ:配列の多重代入

文字列の最初は空白だとエラーが出るので、まず前後の空白を取る

def str2hash(string)
  ary = string.strip.split(/\s+/)
  Hash[*ary]   #多重代入
end

p str2hash("blue 青 white 白\nred 赤")                           #=> {"white"=>"白", "blue"=>"青", "red"=>"赤"}
p str2hash("movie 死神の精度 book ハリーポッター music ロック")  #=> {"music"=>"ロック", "movie"=>"死神の精度", "book"=>"ハリーポッター"}
p str2hash(" black 黒      green 緑\ngold 金  ")                 #=> {"black"=>"黒", "gold"=>"金", "green"=>"緑"}

holysugarholysugar2008/12/10 16:48p str2hash(" blue 青 white 白\nred 赤") と、最初に空白を入れるとエラーになります。想定通り?

krystalkrystal2008/12/10 17:05>holysugarさん
コメントありがとうございます。
最初の空白ですか!?想定していなかったです。
stripを使って前後の空白を取るようにしました。

holysugarholysugar2008/12/10 21:04ストレートに聞くと、String#split のマニュアルは読みましたか?

krystalkrystal2008/12/15 20:06>holysugarさん
「1 バイトの空白 ' 'か $; が使用される場合でその値が nil: 先頭の空白を除いて空白で分割する。」と書いてあります。
ということは、ary = string.split にすればエラーがなくなります。

2008-12-05 (Fri)Ruby練習問題

send more money

11:40

  • send + more = money を満たすそれぞれ異なる 0 以上 9以下の数 s, e, n, d, m, o, r, y を求めよ。(ただし s, m は 0 でない)

8重forで解いてみる

for s in 1..9
  for e in 0..9
    next if s == e
    for n in 0..9
      next if s == n or e == n
      for d in 0..9
        next if s == d or e == d or n == d
        for m in 1..9
          next if s == m or e == m or n == m or d == m
          for o in 0..9
            next if s == o or e == o or n == o or d == o or m == o
            for r in 0..9
              next if s == r or e == r or n == r or d == r or m == r or o == r
              for y in 0..9
                next if s == y or e == y or n == y or d == y or m == y or o == y or r == y
                send = s * 1000 + e * 100 + n * 10 + d
                more = m * 1000 + o * 100 + r * 10 + e
                money = m * 10000 + o * 1000 + n * 100 + e * 10 + y
                if send + more == money
                  p send.to_s + "+" + more.to_s + "=" + money.to_s  #=> "9567+1085=10652"
                end
              end
            end
          end
        end
      end
    end
  end
end

9秒くらいかかった。

Prinyさんは Array#permutation で解いてみたようです。

http://rubyist.g.hatena.ne.jp/priny/20081208

ufcppufcpp2008/12/05 20:23next ifの行の下、インデント一段下げる必要ないと思います。

cuziccuzic2008/12/07 12:21制約緩和法を使うのが基本だと思うな。

krystalkrystal2008/12/08 17:02>ufcppさん
ご指摘ありがとうございます。
修正しました。

>cuzicさん
コメントありがとうございます。
「制約緩和法」は初耳です。かなりハイレベルのアルゴリズムだそうですね。

rubikitchrubikitch2008/12/09 21:11ここにも答えのコード置いてます。手で解くのも不可能ではない。
http://d.hatena.ne.jp/rubikitch/20081209/1228823996

krystalkrystal2008/12/10 17:18>rubikitchさん
答えのコード、ありがとうございます。
やはり皆さんpermutationを使ってますね。

ShikamaruShikamaru2012/10/16 01:08This has made my day. I wish all positgns were this good.

bamjoihbamjoih2012/10/16 21:14bL3WVc <a href="http://oervgeigtetf.com/">oervgeigtetf</a>

qrrefzszrcqrrefzszrc2012/10/19 13:32SqXEYS , [url=http://gyieiiutwzlt.com/]gyieiiutwzlt[/url], [link=http://eevaidttpegq.com/]eevaidttpegq[/link], http://ezfsffemznil.com/

xjvyudvpxjvyudvp2012/10/20 01:02xmT2IA <a href="http://adrczmmvgrse.com/">adrczmmvgrse</a>

2008-12-01 (Mon)たのしいRuby練習問題

P230 - クラスStringIOを定義しよう

17:53

  • 与えられた文字列に対して、IOクラスのようにgetsreadができるオブジェクトのクラスStringIOを定義しよう
  • このクラスは以下のような使い方を想定している
sio = StringIO.new("密林\n嘘\n赤と黒\n罠\n罪")
p sio.gets  #=> "密林\n"
p sio.gets  #=> "嘘\n"
p sio.gets  #=> "赤と黒\n"
sio.rewind  
p sio.gets  #=> "密林\n"

このように定義した

class StringIO
  def StringIO.gets(string)
    ary = string.split("\n")
    string_length = string.split("\n").size
    string_length.times{|x|ary.shift
    }
  end
  
  def StringIO.rewind
    return string
  end

end
sio = StringIO.new("密林\n\n赤と黒\n\n")
p sio.gets  #=> "密林\n"
p sio.gets  #=> "嘘\n"
p sio.gets  #=> "赤と黒\n"
sio.rewind  
p sio.gets  #=> "密林\n"

修正

  • ↑の書き方だと既存のStringIOクラスのメソッドをそのまま使ってるだけ
  • いろんな方に質問したり、正解を参考にしたりした
class MyIO
  def initialize(string = "")
    @string = string
    @position = 0
  end
  
  def read(num)
    if num < 0
      return false
    end

    show = @string[@position, num]
    @position += num 
    if @position > @string.size
      @position = @string.size
    end
      
    show
  end
  
  def gets
    if @position >= @string.size
      return nil
    end

    pos = @string.index("\n", @position)
    if pos == nil
      @string.size
    end
      ret = @string[@position..pos]
      @position = pos + 1
      return ret
  end

  def rewind
    @position = 0
  end
  
end

mio = MyIO.new("密林\n\n赤と黒\n\n")
p mio.gets      #=> "密林\n"
p mio.gets      #=> "嘘\n"
p mio.gets      #=> "赤と黒\n"
p mio.gets      #=> "罠\n"
p mio.read(5)   #=> "罪"
p mio.read(3)   #=> ""
mio.rewind 
p mio.read(2)   #=>"密"

あとこういうのも書いた

  • splitshiftを使って書いたもの
  • 質問の意図はこれじゃないけど、せっかく書いたからアップ
class MyIO
  def initialize(string)
    @string = string
    @ary = @string.split("\n")
  end
  
  def get_word
    @ary.shift
  end
  
  def rewind
    @ary = @string.split("\n")
  end
end

mio = MyIO.new("密林\n\n赤と黒\n\n")

p mio.get_word   #=>  "密林"
p mio.get_word   #=>  "嘘"
p mio.get_word   #=>  "赤と黒"
mio.rewind
p mio.get_word   #=>  "密林"

えぬえぬ2008/12/01 21:01毎回、配列に split して shift すると遅くならないの?

entottoentotto2008/12/02 18:16上のクラスを irb で試したら、エラーになりました。

irb(main):014:0> sio = StringIO.new("aa\nbb\ncc\ndd\nss")
ArgumentError: wrong number of arguments (1 for 0)
from (irb):14:in `initialize'
from (irb):14:in `new'
from (irb):14
from :0

あと、仕様では gets に引数を渡してないのに、コードでは引数を取るメソッドなのも気になります。

krystalkrystal2008/12/02 20:30>えぬさん
コメントありがとうございます。
スピードのことまったく考慮していませんでした..
早くなる方法のヒントをいただければと思います。

>entottoさん
エラーですか!?
確かにgetsに引数を渡してしまってます。
修正します。

holysugarholysugar2008/12/03 00:11というか、StringIO.gets を定義したのに、StringIO#gets を呼んでもできたことにならないのでは。
標準ライブラリの StringIO のメソッドを呼んでいるだけですよね?

とりあえず StringIO のマニュアルを読んだあとに、練習に必要なら、StringIO とは別のクラスを定義してみてはいかがでしょうか。

krystalkrystal2008/12/04 20:54>holysugarさん
コメントありがとうございます。
実は既存のものをそのまま使ってしまったということですね。
修正しました。ご指摘ありがとうございます。