「code」タグアーカイブ

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)

codeiq @riverplus さんの「ロング・ロング・ストリング問題」を解いた

https://codeiq.jp/q/2683

作者による解説は
https://codeiq.jp/magazine/2016/03/38398/ (Wayback Machine 経由)

回答は
http://togetter.com/li/947393
でまとめられている。

問題はだいたいこんな感じ

自然数 n に対して、関数 F(n) を、n**n(n の n 乗)を 10 進数で表したときの桁数と定義します。
さらに、2 以上の自然数 m に対して、F(n) = m となる n の値を G(m) と定義します。
もしそのような n が存在しない場合は、G(m) = -1 と定義します。

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

rubyで書いたニュートン法の提出コードはこちら。
四捨五入しているところはちょっと怪しいと思ったけど、
テストケースが全部通ったので、とりあえずは深く考えずにそのままにしている。
自然対数じゃない対数の微分とか、高校以来かもしれない。

 m=gets.chomp.to_i
# 入力mに対して、10**m=n**n、すなわち n*log10(n)-m = 0 を満たす 
# 実数nを、ニュートン法で求める。
i = m
tmp = (i*Math.log10(i) - m )/(Math.log10(i) + 1/ Math.log(10))
while tmp.abs > 0.01
  i-=tmp
  tmp = (i*Math.log10(i) - m )/(Math.log10(i) + 1/ Math.log(10))
end
i=i.round # ここは大丈夫かな? # -1 になる条件をチェックしつつ出力。
puts (i*Math.log10(i)).ceil == m ? i : -1 

codeiq @riverplus さんの「プラス・マイナス・ゼロ問題」を解いた。

問題&解法はこちら。
https://codeiq.jp/magazine/2016/02/37963/

問題は、大体下記のような感じ。

自然数 n に対して、次の等式を考えます。

    □1□2□3□4…□n = 0

四角の部分には、プラス(+)またはマイナス(-)の記号が入ります。

自然数 n に対し、等式を成立させる記号の入れ方の数を F(n) と定義します。

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

提出コードはruby。(コメントだけ追加しました。)
基本的には、ひとつひとつ+-していったときの値を、まとめて勘定しているだけ。
一番最初に全通り数え上げてみるのを書いてみた後、それではとてもとても無理ということで書き直した感じ。

def solve(n)
  # 1..j の数字について処理した結果の値をキーに、そのキーの値になる
  # +-の組み合わせの数を値として持つ連想配列を考える。
  # (Arrayだとインデックスが負にならないような小細工が必要で面倒)
  ret = {1 => 1} # -1から始まるものは、対称性から最後に2倍してすます
  (2..n).each{|j|
    tmp = Hash.new{|h,k| h[k] = 0}
    # j番目のHashは、j-1 番目のHashの各要素{k=>v}について、
    # k+j, k-j の値にvを足していくことで得られる。
    ret.each{|k,v|
      tmp[k+j] += v
      tmp[k-j] += v
    }
    ret = tmp
  }
  ret[0] * 2
end
while str = STDIN.gets
  n = str.chomp.to_i
  puts solve(n)
end

codeiq @riverplusさんの 「スロット・マシン問題」を解いた。

解きました。フィードバックは大変なんでしょうね~。
最初に書いたコードでは、F(12)までとてもとてもまともな時間で計算できなかった。
想定時間30分で12のときまで解くのは結構ハードだと思う。

恥ずかしながら半日~1日くらい??

【問題】

n 個のリール(数字が描かれている部分です)を持つスロットマシンを回します。

各リールには、0 から 9 のいずれかの数字がランダムに出ます。

このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。

例えば n = 6 のスロットマシンを考えましょう。

各リールに、左から順に 7 7 5 1 0 7 という数字が出たとします。

このとき、7 の数字が最も多く 3 回出現していますので、賞金は 3 ドルです。

リールの数字が 0 2 0 9 2 6 のとき、賞金は 2 ドルです。

リールの数字が 1 2 3 4 5 6 のとき、賞金は 1 ドルです。

リールの数字が 8 8 8 8 8 8 のとき、賞金は 6 ドルです。

このスロットマシンを 1 回まわしたときの賞金の期待値を F(n) とします。

例えば F(1) = 1,F(2) = 1.1,F(3) = 1.29 となることが確かめられます。

■ 第1問 (Normal)

F(6) の値を求めて下さい(四捨五入は不要です)。

■ 第2問 (Hard)

F(12) の値を求めて下さい(四捨五入は不要です)。

【方針】
○ nをn以下で10個までの自然数の和に分割する方法が何通りあるかを計算する。
(このとき、同時に賞金ごとに分類しておく)
○ 上で計算した分割方法ごとに、リールの数字が何通りあるかを計算し、期待値を求める。
○ たとえば、n=6で4点のときは、[4, 1, 1], [4, 2] の2通りの分割があり、
それぞれ、 (10*9*8)*(6!/4!)/2!, (10*9)*(6!/4!/2!)/1!通りの組み合わせになる。
配列の長さmについて、(10からmとる順列)*(並べ方の数)/(配列中に同じ数字があれば割引く)通り。(うーん、我ながらわかりにくいか。)

【rubyの提出コード】

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
BASE=10 # スロットが10進数で回る。
def solve(n)
  score_sum=0 # スコアの総和
  count_sum=0 # (デバッグ用)スロットの並び方の総和
  make_array(n).each{|score, arrays|
    arrays.each{|arr| # nと賞金で決まる配列ごとにループ
      # 対称性を考慮して、並べ方の数を数える。
      # 配列の中の同じ数字があるかどうか。
      sym=(1..n).map{|i| arr.count(i)>1 ? arr.count(i) : nil }
        .compact.map{|i| facto(i)}.reduce(&:*) || 1
      # 上の対称性も考慮した、並べ方の数。
      part = facto(n)/arr.map{|i| facto(i)}.reduce(&:*) / sym
      # 配列の中の数字にそれぞれ0-9の数字を当てはめる
      count = permu(arr.length) * part
      count_sum += count
      score_sum += score*count
    }
  }
  #  print "count(#{n}) = #{count_sum}\n"
  score_sum.to_f / BASE**n
end
# 普通の階乗計算
def facto(n)
  $facto||=[1]
  $facto[n]||=n*facto(n-1)
end
# BASE個の中からn個とる順列
def permu(n)
  ((BASE + 1 -n)..BASE).reduce(&:*)
end
# nをBASE個までの整数の和に分割し、賞金ごとに分けたHashに配列の配列として格納。
# たとえば n=3 のとき、{1=>[[1, 1, 1]], 2=>[[2, 1]], 3=>[[3]]}を返す。
def make_array(n)
  ret = Hash.new{|h,k| h[k]=[] }
  min = 1 + (n-1)/BASE
  (min..n).map{|sc|
    tmp = rec(sc,n).reject{|arr| arr.length > BASE }
    ret[sc].push(*tmp)
  }
  ret
end
# nと賞金が決まった時の、可能な自然数への分割を配列の配列で返す。
def rec(sc,n,ret=[],all=[])
  sum = ret.reduce(&:+) || 0
  num = n-sum
  if n == sum
    all << ret
  elsif num == sc
    ret << sc
    all << ret
  elsif sc == 1
    num.times{ ret << 1 }
    all << ret
  elsif num > 0 && num >= sc
    ret << sc
    (1..[sc,n-sc].min).each{|_sc|
      rec(_sc,n,ret.dup,all) # 次の数は直前に格納した数字と同じか少ない。
    }
  else
    nil
  end
  all
end

(1..20).each{|i|
  print "F(#{i}) = #{solve(i)}\n"
}

codeiq 「カット・アンド・スクエア問題」

問題はこちら
http://riverplus.net/codeiq/CutAndSquare.pdf

かいつまんで言うと、
[偶数 n に対して、先頭にゼロを持たない n 桁の整数で上 n/2 桁と下 n/2 桁とに分け、それぞれを 2 乗して和をとると、元の数に戻るような数で、n=6, n=10の場合を求めよ。]という感じ。
色々と回答があるようで、参考になったな~。

で、Rubyで書いた提出コードが下記。
sqrtの結果を整数に丸めるあたりが怪しい気がするが、まぁ、当たりでないときは外れるはずだからOKのはず。

ideone.comにも置きました。便利だね。
http://ideone.com/eMPnrv

【方針】
求めるN桁の数をnとし、 n = a * 10**(N/2) + b とする。
n = a**2 + b**2 (b>0, a>10**(N/2 – 1)) の条件を満たす整数a,bを見つける方針でとく。
1. n = a**2 + b**2 の1桁目に注目すると、aの1桁目の数字は0,2,8のみとなる。
   (Excelで100通りをすべてチェックしましたが、a,bの下1桁の値の組み合わせは8通りしかありません。)
2. 条件の式からbについて解くことができるので、各aについて、bが条件を満たす整数かどうかをチェックする。
   (bについてはループしなくて済む。)

N=10
Base2=10**(N/2)

result = []
((Base2/10)...Base2).select{|a| # aの下1桁を0, 2, 8に絞る。
  tmp = a%10
  tmp == 0 or tmp == 2 or tmp ==8
}.each{|a| # aについてのループ。
  # bは、aについて解いておく。(b>0なので、一意にさだまる。)
  b=(1 + Math.sqrt(1+4*Base2*a -4*a*a)).round/2
  n = a*Base2 + b
  result << n if a*a + b*b == n # 条件を満たすかどうかをチェック。
}
p result
p result.reduce(&:+)

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

フィルタースクリプトなシェルスクリプト

今日はじめて気付いたので、忘れないうちにメモ。

bashとかでフィルターのスクリプトを書くとき、
cat $@ | hoge | huga
とか書くと便利なことを今日知った。
スクリプトの引数がなければ$@が無視されるので(man bash参照のこと)、catが標準入力を読む。つまり、スクリプトに渡された標準入力に対して動作する。
スクリプトに引数としてファイル名をいくつか与えると、$@にすべての引数が入るので、普通に引数を処理する。
別にcatじゃなくても、sedでもawkでもgrepでもいけると思う。

例えば、 
nkf $@ | less
というスクリプトを(たとえばnkflessと言う名前で)用意しておけば、 nkfless text でも cat text | nkfless でも両方使える。
ちなみに、bashでなくdashでも使えたので、たぶんshでもいけるかも。
(でも、lessのこんなことは、LESSOPEN=”|nkf %s” みたいな環境変数で本当はできるんですけどね、、、。)

引数の個数を判断して、while read line (場合によってはcat – | と書いてた)と、
for i in $* を分ける必要はなかったという話。
while read がどうしても必要なら、
 cat $@ | while read line ; do hoge;done| huga
とか、好きにかける。
そもそも、複雑なフィルターならシェルスクリプトで書くなって話もあるけど、、、。