ショートな課題でジャムプログラミングの問題を解いてみました
第22回 Ruby/Rails勉強会＠関西のセッションでやった問題を僕も解いてみました。問題はこちらです。
課題1 配列をシャッフルする
sort_byを使うのは簡単なのですが、先頭にくる要素がどれになるか、選ばれる確率がそれぞれの要素について公平ではないと思いますので、ナイーブなアルゴリズムで実装しています。mapラブ。
def shuffle(ary) tmpary = ary.dup ary.map { tmpary.slice!(rand(tmpary.size)) } end ary = ['A', 'B', 'C', 'D', 'E'] p shuffle(ary) # => ["D", "A", "E", "C", "B"] p ary # => ["A", "B", "C", "D", "E"]
selfを省略しています。少しシンプルになりました。
class Array def shuffle tmpary = dup map { tmpary.slice!(rand(tmpary.size)) } end end ary = ['A', 'B', 'C', 'D', 'E'] p ary.shuffle # => ["D", "A", "E", "C", "B"] p ary # => ["A", "B", "C", "D", "E"]
課題2 グラフを実装する
matrixライブラリを使おうか迷った末に、普通に配列で実装しました。この問題では入力ファイルを全部読み込むまで配列のサイズは決定できません。いびつな配列にしながら計算を進めて最後に0で埋める方法もありますが、ここでは以下では2パスで配列のサイズを先に求めています。
入力ファイル
1 - 2 - 3 - 4 - 5 - 1 1 - 6 - 3 5 - 6 2 - 7
require 'pp' def parse(lines) lines.inject([]) do |a, line| ns = line.strip.split(/\s*-\s*/).map {|s| s.to_i } a += (0 .. ns.size - 2).map {|i| [ns[i], ns[i + 1]] } end end def mkgraph(conns) size = conns.map {|ary| ary.max }.max + 1 Array.new(size) { Array.new(size, 0) } end def setconns(graph, conns) conns.each {|from, to| graph[from][to] = graph[to][from] = 1 } end conns = parse(ARGF.readlines) graph = mkgraph(conns) setconns(graph, conns) pp graph # => [[0, 0, 0, 0, 0, 0, 0, 0], # [0, 0, 1, 0, 0, 1, 1, 0], # [0, 1, 0, 1, 0, 0, 0, 1], # [0, 0, 1, 0, 1, 0, 1, 0], # [0, 0, 0, 1, 0, 1, 0, 0], # [0, 1, 0, 0, 1, 0, 1, 0], # [0, 1, 0, 1, 0, 1, 0, 0], # [0, 0, 1, 0, 0, 0, 0, 0]]
課題3 アナグラム作り支援プログラム
アナグラムの文字をArrayにするかStringにするか悩みましたが、以下ではArrayで実装しています。それ以外に特筆すべきとことはあまりないです。副作用ばりばりでバグりそうな怖いプログラムです。
require 'readline' class Array def shuffle tmpary = dup map { tmpary.slice!(rand(tmpary.size)) } end end def prompt(rests, fixed) puts "rests:`#{rests.join}' -> fixed:`#{fixed.join}'" end rests = 'NFLNUOEOIBYR'.split(//) fixed = [] prompt(rests, fixed) while buf = Readline.readline('> ', false) break if buf == 'BYE' buf.gsub(/\s/, '').split(//).each do |s| pos = rests.index(s) if pos fixed += rests.slice!(pos, 1) if rests.empty? puts 'おめでとう！' break end else puts "不正な文字です。`#{s}'" end end prompt(rests, fixed) end puts fixed.join + rests.shuffle.join
課題4 しりとりゲーム
関数型言語っぽいデータの変換を繰り返すアプローチで解いてみました。Enumerableの高階関数ラブ。
入力ファイル
ねずみ,うし,とら,うさぎ,りゅう,へび,うま ひつじ,さる,とり,いぬ,いのしし,すずめ はと,からす,うぐいす,めじろ,つばめ,かっこう ほととぎす,にわとり,ちゃぼ,かるがも,きじ だちょう,くじゃく,しちめんちょう,がちょう はくちょう,わし,たか,とんび,かもめ,ふくろう みみずく,きつつき,うずら,しじゅうから,つぐみ ひよどり,きつね,たぬき,ねこ,ろば かえる,かっぱ,とかげ,やもり,いもり,しか りす,いたち,もぐら,こうもり,かもしか むささび,ももんが,こあら,らっこ,ぞう,かば らくだ,さい,おおかみ,くじら,いるか,しゃち おっとせい,せいうち,あざらし
require 'csv' def read_words(input) CSV::IOReader.new(ARGF).inject([]) do |ws, row| ws + row.reject {|w| w.nil? }.map {|w| w.split(//) } end end def shiritori(ret, acc, words) nexts = words.select {|word| word.first == acc.last.last } if nexts.empty? ret << acc else nexts.each {|word| shiritori(ret, acc + [word], words - [word]) } end ret end words = read_words(ARGF) seqs = words.inject([]) do |ss, start| ss + shiritori([], [start], words - [start]) end max, ans = seqs.inject([0, []]) do |(max, ans), seq| case seq.size <=> max when 0 then [max, ans + [seq]] when 1 then [seq.size, [seq]] else [max, ans] end end ans.each do |seq| puts seq.map{|word| word.join }.join(' - ') end # => たぬき - きつつき - きつね - ねずみ - みみずく - くじゃく - くじら - らっこ - こうもり - りゅう - うし - しか - かもしか - かるがも - ももんが - がちょう - うずら - らくだ - だちょう - うぐいす - すずめ - めじろ - ろば # たぬき - きつつき - きつね - ねずみ - みみずく - くじゃく - くじら - らっこ - こうもり - りゅう - うずら - らくだ - だちょう - うし - しか - かもしか - かるがも - ももんが - がちょう - うぐいす - すずめ - めじろ - ろば # たぬき - きつつき - きつね - ねずみ - みみずく - くじゃく - くじら - らくだ - だちょう - うし - しか - かもしか - かるがも - ももんが - がちょう - うずら - らっこ - こうもり - りゅう - うぐいす - すずめ - めじろ - ろば # たぬき - きつつき - きつね - ねずみ - みみずく - くじゃく - くじら - らくだ - だちょう - うずら - らっこ - こうもり - りゅう - うし - しか - かもしか - かるがも - ももんが - がちょう - うぐいす - すずめ - めじろ - ろば
