「ruby」タグアーカイブ

codeiq @riverplus さんの「コード・トライアスロン2」問題をrubyで解いた

作題者によるまとめはhttp://togetter.com/li/971415から。
問題解説はhttps://codeiq.jp/magazine/2016/05/40858/から。

問題の概要はこちら。

■ 1 ■
四角形ABCDについて、∠ABD=a,∠CBD=b,∠ACB=c,∠ACD=d とおきます。
∠ADB を求めることを考えましょう。
さて、a,b,c,d の値(単位は度)に対し、∠ADB の値(単位は度)を 10^6 倍したものの整数部分を F(a,b,c,d) と定義します。
F(a,b,c,d) を求めるプログラムを書いてください。

■ 2 ■
自然数 n に対し、次の性質をもつ自然数 d の総和を G(n) と定義します。
  n を d で割った余りが 1 に等しい。
G(n) を求めるプログラムを書いてください。

■ 3 ■
先頭にゼロを持たない自然数であって、逆から読んでも同じ数になる数を回文数と呼びます。
自然数 m に対し、m 以下の回文数の総和を H(m) と定義します。
例えば、H(20)=56 です。20 以下の自然数では 1~9 と 11 が回文数だからです。

H(m) を求めるプログラムを書いてください。

■ 問 ■
標準入力から、半角空白区切りで自然数 a,b,c,d(a+b+c < 180 かつ b+c+d < 180)が与えられます。
標準出力に H( G( F( a,b,c,d ) ) ) の値を出力してください。

rubyで書いて提出した回答は下記の通り。

最初に提出したものでは f の計算で数値誤差があって間違った。この手の話は久々。
下のコードでは、切り捨て前に十分小さい値として0.00001をたしている。
この手の問題は整角四角形問題というらしい。学生の頃、三角関数なしでどうやって解くんだと悩んだ記憶がある。

h の計算では、1ケタの数は別に足しておいてから、11 から順に、回文数をひたすら小さい方から生成して順にたしているだけ。数値を文字列にしてひっくり返して足して、、と、手抜きだけど通ったのでまぁいいや、という感じ。

# 正弦定理で等しい辺の長さを探してごにょごにょいじると計算できる。
def f(_a,_b,_c,_d)
  include Math
  a=_a*PI/180
  b=_b*PI/180
  c=_c*PI/180
  d=_d*PI/180
  s=sin(b)*sin(d)*sin(a+b+c)/sin(a)/sin(c)/sin(b+c+d)
  ret = atan(sin(b+c)/(s+cos(b+c)))/PI*180*(10**6) + 0.00001
  ret < 0 ? (180000000 + ret).to_i : ret.to_i
end
# ナイーブに全通り1からnまで探索すると時間切れなので、少し工夫。
# n=(n-1)/d * d + 1 なので、nをdで割った余りが1のときは、
# (n-1)/dで割った余りも1になる。
# これを使って、1 から sqrt(n)までしか探索しない。
# また、nをdで割った余りが1でないときは、d*i(i>1)で割った余りも
# 1でないということを利用して、判断する回数を減らす。
def g(n)
  res=n-1
  max=Math.sqrt(n).to_i
  arr=Array.new(1+max, false)
  (2..max).each{|d|
    next if arr[d]
    if n%d == 1
      res+=d+(n-1)/d
    else
      (1..(max/d)).each{|i| arr[d*i] = true }
    end
  }
  res
end
# 回文数を小さい方から全通り生成して、mより小さければ結果に足す。
def h(m)
  i=1
  tmp=-1
  len = m.to_s.length
  if len == 1 # 1桁のときは別処理。
    return (1..m).reduce(&:+)
  else
    res=45
  end
  while tmp != res
    tmp=res
    str=i.to_s
    if str.length * 2 == len
      wk=(str+str.reverse).to_i
      res+=wk if wk < = m
    else
      ([""] + %w(0 1 2 3 4 5 6 7 8 9)).each{|sp|
        wk=(str+sp+str.reverse).to_i
        res+=wk if wk <= m
      }
    end
    i+=1
  end
  res
end

a,b,c,d=gets.chomp.split.map(&:to_i)
puts h(g(f(a,b,c,d)))

codeiq @riverplus さんの「ディビジョン・ナイン問題」をrubyとschemeで解いた

回答まとめはこちら

問題は下記。

1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 20)が与えられます。標準出力に F(n) の値を出力するプログラムを書いてください。

1111…から4444…まで全通り生成して数えていては終わらないので、9の剰余で分類します。すなわち、1から4の数字を使って作るn桁の数字のうち、9で割ったあまりがrになるものの個数をF(n,r) とすると、
 \displaystyle F(n+1,r) = \sum^4_{i=1}F(n,r-i)
の漸化式になります。

これをrubyで計算し、F(n,0)を出力するコードが下記。Hashの引数が9で割ったあまりになっています。

n=gets.to_i
h={}
h[1]=h[2]=h[3]=h[4]=1
(1...n).each{|m|
  tmp=Hash.new{|h,k| h[k]=0 }
  h.each{|k,v|
    (1..4).each{|i|
      tmp[(i+k)%9]+=v
    }
  }
  h=tmp
}
puts h[0]

最近始めたschemeで書いたのはこちら、末尾再帰といえば聞こえはいいけど、ループを再帰にして、状態を関数の引数で覚えている、というだけ。もっとスマートに書けると思うんだけど、引数10個くらいだしまぁいいよね、ということで。

(use-modules (ice-9 rdelim))
(define (solve i a0 a1 a2 a3 a4 a5 a6 a7 a8)
    (if (= i 1)
        a0
        (+ (solve (- i 1)
                  (+ a5 a6 a7 a8)
                  (+ a6 a7 a8 a0)
                  (+ a7 a8 a0 a1)
                  (+ a8 a0 a1 a2)
                  (+ a0 a1 a2 a3)
                  (+ a1 a2 a3 a4)
                  (+ a2 a3 a4 a5)
                  (+ a3 a4 a5 a6)
                  (+ a4 a5 a6 a7)))))
(display (solve (string->number (read-line)) 0 1 1 1 1 0 0 0 0))
(newline)

set_trace_func を使うことで Ruby on Rails のデバッグが超はかどったという話。

最近、 rails で開発しているときに、set_trace_funcでエラー行を表示させるのが便利だったので、メモ。 gem で使っているライブラリも疑っていろいろ見ないといけないので、結構便利だ。

rails側では controllerか何かで適当に
require_relative "hogehoge" if Rails.env.development?
しておいて、hogehoge.rbには下に書いた感じで書くと、はかどった。

実際には、if文の条件をもっといろいろ追加して、余計な出力を出さないようにするが、大筋ではこんな感じ。
eventでc-callやらc-returnを指定すれば、cで書いたメソッドの呼び出しと戻りも表示できる、ということで、いろいろできそうだ。

require 'pp'
set_trace_func lambda{|event, file, line, id, binding, klass|
  if event == "raise"
    # raise 例外が発生したファイル名と行番号を表示。
    print "#{event} at #{klass}:#{id} #{file}:#{line}"

    # 例外が発生した場所でのローカル変数一覧を表示。
    # railsではインスタンス変数やselfを表示させようとすると
    # 表示結果が多すぎて煩雑になる。
    binding.eval(local_variables.map{|v|[v.to_s, eval(v)]})
      .each{|name, val| print "#{name} = #{val.pretty_inspect}" }
  end
}

sinatra で、サーバ側で作成した画像を直接表示

バイナリで送って、javascriptでbase64でencode、、、とか最初は考えたけど、探したらhttp://qiita.com/haruboh/items/b90fcf763295b56b0915を見つけられたので、そのままやった。

まぁ、よくよく考えてみれば当たり前。転送量だってそんなにたいした画像を書くわけでもないので、気にするほどでもなかった。
なお、元記事にある改行コードの削除は、strict_encode64メソッドでエンコードすればOK。

だいたいこんな感じ。
画像作成はgnuplot(と、ruby_gnuplot)を利用。 set output を指定しなければ、ruby変数に処理結果を格納できる。

require 'base64'
require 'gnuplot'
get '/plot' do
  img = Gnuplot.open do |gp|
    # 適当なpng作成処理
  end
  base64 = Base64.strict_encode64(img)
  "<img src='data:image/png;base64,#{base64}'>"
end

で、よくよく確かめたら、今どきのgnuplotは set ternminal svg でsvgをそのまま吐けるので、エンコードとかややこしいことを考えずとも、そのままHTMLにはればよかった。
これだと、gnuplotの日本語fontなど色々ケアしなくてもよいので楽だった。(IE8,9対策に、pngでも描画できないとだめだけども、、、。)

require 'base64'
require 'gnuplot'
get '/plot' do
  img = Gnuplot.open do |gp|
    # 適当なsvg作成処理
  end
  img # svgは普通のXML文字列なので、そのままでOK
end