CodeIQ 「ロンリー・ルーク」問題の解答コード公開
久々の投稿になります。
今回はCodeIQの問題の解答コードを公開します。
問題
今回の問題の概要です。
方針
F(n, k)について、k=1~mまでの和を求めるので、F(n,k)の値の求め方を考えます。
- k=1の場合、「はぐれルーク」は1個なので期待値は1
- k > n-1の2乗+1の場合、どう配置しても「はぐれルーク」は無いので期待値は0
- kの値が上記以外の場合について、全配置の組み合わせについて「はぐれルーク」の個数を計算
まあ、要はしらみつぶしというやつですww
解答
以下が、提出したコード。n×n の盤面を1次元配列で表現しているのが多少の工夫といえば工夫かも。
def func(n, k) return 1.0 if k == 1 return 0.0 if ((n - 1) ** 2 ) + 1 < k numOfLonelyLuke = 0 numOfCombination = 0 (0..(n**2 - 1)).to_a.combination(k) do |array| numOfCombination += 1 array.each do |x| isLonely = true array.each do |y| next if x == y if (x / n == y / n) || (x % n == y % n) isLonely = false break; end end numOfLonelyLuke += 1 if isLonely end end numOfLonelyLuke / numOfCombination.to_f end (n, m) = gets.split.map(&:to_i) num = 0.0 (1..m).each do |k| num += func(n, k) end puts (num *1000).to_i
感想
今までもCodeIQの問題は解いてましたが、公開するのは今回が初めてです。
また、この機会に他の方の解答コードを見てみましたが、エレガントな解法で実装されてる方が結構いらっしゃったので驚きでした。
次はもう少し綺麗な解き方を目指すようにしないとなー。
ま、自分もまだまだ精進が必要だなーと感じ入りました。ほんと。(´Д`)
2017年5月の目標
どうも、パイソンです。
本日から5月。先月に引き続き月間の目標でも立ててみようかなーと思います。
とはいえ、先月は毎日更新を目指すとか息巻いてみたものの結局挫折したんで、今月は普通に達成出来る感じのものにしようかと。(^^;
というわけで、立ててみた5月の目標。
1.rubyでなんか作る
先月来からrubyの勉強を進めているが、やはりcuiのプログラムだけ作ってても退屈なもんです。
なので、今月はrubyを使って少し規模の大きなソフトを書いてみようかと思います。何作るかは検討中ですが、早い内に決めて、ブログに作成過程なんかを残して行こうかと思います。
2.記事更新は10記事程度を目処に
1カ月ブログやってきて、さすがに毎日更新はしんどいと実感したので、今月は少し控えめな目標にしてみましたw
とはいえ、数値目標を立てて置かないと更新しないまま放置になるので、一応少なすぎるという事は無い程度の規模感で。
というわけで、5月はマイペースで更新していきます。
ブログ開始から1カ月経過しました
どうも、パイソンです。
ブログ開始からちょうど1カ月経過しましたので、これまでの振り返りをしてみようと思います。
月初の目標
一応、今月の初めに2点ほど目標を立てておりました。
1.毎日更新を目指す事
2.rubyの勉強を頑張る事。
んで、1の目標ですが、結局毎日更新はできませんでした。(´・ω・`)
理由としては、飲み会があって帰りが遅くなった日があったり、そもそもネタが全然浮かばなかったりというのがありますが、まあ、これらのことは言訳にしかなりません。(^^;
つか、毎日更新とかキツイわ。本当、毎日更新してるブロガーのひとは凄いと思います。
次に、2の目標。
rubyのほうは、ブログ続けてきた効果か、大分理解が深まったかなーと個人的には思います。やはり、わからない事を調べつつ、その内容をブログにアウトプットしていくことで、学んだ事が頭に定着しているという実感はあります。
とはいえ、まだまだ基本的な部分しか理解出来てないという自覚があるので、来月以降も継続して勉強は続けていこうかと思います。
まとめ
というわけで、
1.毎日更新は無理ゲーだった
2.今後も勉強した事はブログに残して行こう
以上が今月の感想です。
5月もブログは継続していきます。
Rubyにはインクリメント演算子(++)が無い
Rubyを書いてて、いつも疑問に思ってた事項なので自分用にメモ。
CやJava、またはPerl等のプログラム言語では、整数の値に1を加算する時にインクリメント演算子++
を使用します。しかし、Rubyではインクリメント演算子を使うことは出来ません。
インクリメント演算子が無い理由
Rubyの開発者であるMatzさんが、過去この件について言及されておりました。
3) 記号的な記法
これは単なる私の趣味ですが, 単項インクリメントとかがたまに欲しく
なります. i += 1 でいいわけですが. i++ と書いて怒られる (^^;
すんません.この件は以前から指摘されているのですが(演算子はC
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/5323
に似ているのに++と--は対応する演算子が無い),++の動作が本質
的に「変数を操作する」ものであるため,変数がオブジェクトでな
いRubyでは導入できないでいます.++や--の「オブジェクト指向的
意味」がRubyの他の部分と整合性を保ったまま定義できれば採用し
たいのですが….
以下、自分なりの解釈。
Rubyでは整数値はオブジェクトであるためインクリメント演算子を実現しようとすれば変数が参照しているオブジェクトそのものに作用する必要がありますが、++
演算子が変数に対して作用するものであるため実現が困難であるということですかねぇ。
また、RubyのFixnumクラスはimmutableですので、さらに実現は困難ですね。
Ruby の Fixnum クラスは immutable です。 つまり、オブジェクト自体を破壊的に変更することはできません。 Bignum も同様です。
https://docs.ruby-lang.org/ja/latest/class/Fixnum.html
インクリメントメソッド
尚、Fixnumクラスにはnext
やsucc
という値に+1するメソッドはあります。しかし、前述の通りFixnum自体がimmutableである為、
num=10
num.next
としてもnumの値は変化しません。
結論
Rubyでは、整数をインクリメントする場合はおとなしく+=1
を使いましょう。
Rubyで乱数生成
Rubyの乱数生成メモです。
rand関数
Rubyで乱数生成をするにはrandメソッドを使います。
10.times do puts rand(1000) end
このプログラムは、0~999までの範囲の乱数を10回出力します。
ただ、この乱数は擬似乱数と呼ばれるものであり、乱数生成に使われる種(シード)を元に算出されている数になりますので、純粋にランダムな数が生成されているわけではないということに注意が必要です。
擬似乱数の偏りについて説明しだすと長くなりすぎるので詳細はWikipediaのほうを参照。
因みに、srandメソッドを使うことで乱数の種を明示的に与える事が可能です。
srand(3) 10.times do puts rand(1000) end
実行結果
874 664 249 643 952 968 256 789 659 714
種を指定した方のプログラムは何回実行しても同じ結果を返します。
Rubyで書式付き出力を行う
Rubyの書式付き出力に関するメモ。
Rubyの書式付き出力
C言語なんかでもみるsprintf
メソッドを使うやり方と、%
演算子を使うやり方があります。先ずは%
演算子を使う例を見てみます。
プログラム
(1..10).each do |n| puts "%03d" % n end
実行結果
001 002 003 004 005 006 007 008 009 010
このプログラムの"%03d" % n
は、sprintf("%03d", n)
と同じ意味になります。
個人的には、%
の演算というと、どうも剰余を求めている様な感じがするので違和感ありまくりでしたが、演算子が文字列にかかっているか、数値にかかっているかの違いと理解すれば良いのでしょうか。
因みに、複数の書式を一度に扱う例は以下の通り。
puts "100 to bin ->%b ,oct->%o ,hex->%X" % [100,100,100] #=>100 to bin ->1100100 ,oct->144 ,hex->64 puts sprintf("100 to bin ->%b ,oct->%o ,hex->%X", 100,100,100) #=>100 to bin ->1100100 ,oct->144 ,hex->64
Rubyのsortメモ
Rubyのsortに関するメモです。
sortメソッド
配列をソートするには、sort(もしくはsort!)メソッドを使います。後ろにブロック処理を記述することで、比較方法を定義する事が出来ます。ここでは昇順でソートする方法と降順でソートする方法を記載します。
p [5,3,7,4,9,0,1,8,2,6].sort #=>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] p [5,3,7,4,9,0,1,8,2,6].sort{|a, b| a <=> b } #=>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] p [5,3,7,4,9,0,1,8,2,6].sort.reverse #=>[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] p [5,3,7,4,9,0,1,8,2,6].sort{|a, b| b <=> a } #=>[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
因みに、ブロックの中で出てきた<=>
は比較演算子と呼ばれるもので、左右の項の大小関係により、0,1,-1が返却されます。
p 1 <=> 1 #=> 0 p 1 <=> 0 #=> 1 p 0 <=> 1 #=> -1 p 2 <=> 0 #=> 1 p 0 <=> 2 #=> -1
sort_byメソッド
ブロック処理の戻り値を元にソートすることを前提としたのがsort_byメソッドです。以下の例のように、アルファベット順でなく、文字数でソートしたい時などに使えます。
langs = ["Java", "C", "Python", "C++", "Ruby", "Basic"] p langs.sort_by{|s| s } #=>["Basic", "C", "C++", "Java", "Python", "Ruby"] p langs.sort_by{|s| s.size } #=>["C", "C++", "Java", "Ruby", "Basic", "Python"]