[[プログラミング言語/Ruby]]
#contents
*初心者用課題 Ruby版 [#z0839d58]
問題の詳細については
[[練習問題]]を参照。
*素数判定 [#u543d3a3]
ま さ に 外 道(I)
require 'mathn.rb'
class PrimePredicater
def initialize
@prime = Prime.new
@cache = []
end
def prime?(x)
extend_cache x if @cache.empty? || x > @cache.last
@cache.include? x
end
private
def extend_cache(lim)
@prime.each do |x|
break if x > lim
@cache.push x
end
end
end
#使用例
ppred = PrimePredicater.new
[1, 10, 2, 5, 7].each do |x|
p ppred.prime?(x)
end
*素数を求める [#e48df6ac]
100までの素数を列挙する。
エラトステネスのふるい:
# limitまでの素数について繰り返しをする
def eratosthenes_sieve(limit, &block)
return enum_for(__method__, limit) unless block_given?
primes = [2]
nums = (primes.last..limit).to_a
loop do
nums.delete_if{|x| x % primes.last == 0 }
break if nums.empty?
break if nums.last < primes.last ** 2
yield(nums.first)
primes << nums.first
end
nums.each(&block)
end
puts eratosthenes_sieve(100).to_a.join(' ')
↑は2を素数と言ってくれないので、書きかえた。1,000,000まで。1.9.3p392で確認。
def eratosthenes_sieve(limit)
sq = (limit ** 0.5).to_i
is_prime = [false, false] + [true] * (limit-1)
2.upto(sq+1) { |i|
if is_prime[i]
(i*i).step(limit, i) { |j|
is_prime[j] = false
}
end
}
res = []
2.upto(limit) { |i|
res.push(i) if is_prime[i]
}
return res
end
puts eratosthenes_sieve(1e6.to_i).join(' ')
ライブラリを用いた解法
Ruby1.8.7:
require 'mathn'
puts Prime.new.enum_for(:each).take_while{|n| n <= 100 }.join(' ')
Ruby1.9:
require 'mathn'
puts Prime.each.take_while{|n| n <= 100 }.join(' ')
Ruby1.9:
require 'prime'
puts Prime.each(100).to_a
*うるう年測定 [#r3e10171]
まっとうな例:
#
# * 4の倍数であれば閏年
# * ただし、100の倍数でもある場合、
# 400の倍数でもあるならば閏年
#
def leap_year?(y)
return false unless y % 4 == 0
return true unless y % 100 == 0
y % 400 == 0
end
begin
ARGV[0] or raise 'missing year'
# Integer()は数値表現とは見えない文字列が与えられた場合、
# #to_iと違い、ArgumentErrorを発生させます。
y = Integer(ARGV[0])
y >= 0 or raise "invalid year: #{y}"
puts "#{y}: #{leap_year?(y)}"
rescue => ex
# 例外を捕まえて、エラーメッセージと使い方を喋って終わる
me = File.basename($0, '.rb')
$stderr.puts "#{me}: #{ex}"
$stderr.puts "Usage: #{me} YEAR"
end
変態な例:
LEAP_YEAR_CHART = {
# x4?
true => {
# x100?
true => {
# x400?
true => true,
false => false,
},
false => {
true => true,
false => true,
}
},
false => {
true => {
true => false,
false => false,
},
false => {
true => false,
false => false,
}
}
}
def leap_year?(y, chart)
[4, 100, 400].inject(chart){|r, i| r[y % i == 0] }
end
begin
ARGV[0] or raise 'missing year'
y = Integer(ARGV[0])
y >= 0 or raise "invalid year: #{y}"
puts "#{y}: #{leap_year?(y, LEAP_YEAR_CHART)}"
rescue => ex
me = File.basename($0, '.rb')
$stderr.puts "#{me}: #{ex}"
$stderr.puts "Usage: #{me} YEAR"
end
*ハノイの塔 [#r9efcc5f]
#Usage: ruby hanoi.rb [n number of disc]
=begin
= Hanoiクラス
「ハノイの塔」の問題を解くクラス。
== クラスメソッド
--- Hanoi.new(num, :from => "From", :to => "To", :work => "Work")
Hanoiクラスを生成する。numは積まれている円盤の枚数。
fromなどのキーワード引数(もどき)はnumの後に書く必要がある。
問題に使用する円盤を差す棒の名前。
== インスタンスメソッド
--- height
--- from
--- to
--- work
それぞれ、new時に与えた問題の設定を参照する。heightは初めにfromに
積まれている円盤の数。
--- each{|n, from, to| ... }
再帰的に問題を解いている様子を一回ずつ監視する。
nは動かす円盤の番号、それをfromからtoへと動かしている。
円盤nとはn番目に小さい円盤のこと。
=end
class Hanoi
def initialize(n, h)
@height = n
@from = h[:from] || "From"
@to = h[:to] || "To"
@work = h[:work] || "Work"
end
attr_reader :height, :from, :to, :work
def each(&block)
do_hanoi @height, @from, @to, @work, &block
end
private
def do_hanoi(n, from, to, work, &block)
if n == 1
yield n, from, to
else
do_hanoi n - 1, from, work, to, &block
yield n, from, to
do_hanoi n - 1, work, to, from, &block
end
end
end
##使用例
num = (ARGV[0] || 3).to_i
num >= 0 or raise "#{num}: Invalid Number"
hanoi = Hanoi.new(num, :from => "A", :to => "B", :work => "C")
hanoi.each do |n, from, to|
puts "#{n}: #{from} -> #{to}"
end
*転置行列 [#o1ceec0c]
require 'matrix'
def parse_matrix(src)
matrix = []
src.each do |line|
line.chomp!
next if line.empty?
matrix.push line.split(/\s+/).map{|x| x.to_i }
end
Matrix.rows(matrix)
end
m = parse_matrix(ARGF.read)
puts m.transpose.to_a.map{|v| v.join(" ") }
*数当てゲーム [#b1a863ae]
require 'readline'
def usage
puts "Usage: ruby #{File.basename($0)} DIFFICULTY[=1]"
end
def main
return usage() if ['-h', '--help'].any?{|h| ARGV.include?(h) }
srand()
difficulty = Integer(ARGV[0] || 1)
difficulty >= 1 or raise "invalid difficulty: #{difficulty} (must be >= 1)"
puts "[difficulty #{difficulty}]"
correct = rand(10 * difficulty + 1)
error_handling(true) do
times = 0
while line = Readline.readline("guess? > ", true)
return give_up() if line.strip == 'g'
try = Integer(line)
times += 1
comp = case
when correct == try then return result(try, times)
when correct > try then 'smaller'
when correct < try then 'bigger'
end
puts "#{try} is #{comp}. (put `g' to give up)"
end
end
end
def give_up
puts "give up!"
end
def result(answer, times)
puts "#{answer} is correct!"
puts "you tried to guess #{times} times."
end
def error_handling(continue = false)
yield
rescue => ex
me = continue ? '' : "#{File.basename($0, '.rb')}: "
puts "#{me}#{ex.message}"
continue ? retry : exit(1)
end
error_handling{ main }
*数当てゲーム その２(Hit&Blow) [#od23e209]
ルールの補足に合わせて改訂。
def help
warn <<-HELP
hit_and_blow.rb: play Hit & Blow game.
usage: ruby hit_and_blow.rb [-option] [DIFFICULTY]
h, --help show this help
v, --version show version
HELP
exit 0
end
def version
warn "hit_and_blow 0.0.1"
exit 0
end
require 'readline'
srand
#n桁以下の数を乱数生成
def generate_answer(col)
bottom = 10 ** (col - 1)
rand(10 ** col - bottom) + bottom
end
#答えの数の妥当性チェック(全桁の数がユニークか)
def valid_answer?(n)
n.to_s.split(//).uniq! ? false : true
end
def generate_valid_answer(col)
answer = nil
loop do
answer = generate_answer(col)
valid_answer?(answer) and break
end
answer
end
#数を桁ごとに分ける(col指定で0補完)
def num_split_cols(n, col=nil)
width = col || n.to_s.length
sprintf("%0#{width}d", n).split(//).map{|n| n.to_i }
end
def input_number(prompt)
while line = Readline.readline(prompt, true)
n = line.to_i
if n < 0
warn "do not input negative number."
else
yield n
end
end
end
ARGV.delete_if do |x|
case x
when "-h", "--help"
help
when "-v", "--version"
version
end
end
n = (ARGV[0] || 4).to_i
n > 0 or raise "#{n}: Invalid difficulty specification."
answer = generate_valid_answer(n)
answer_set = num_split_cols(answer, n)
p answer if $DEBUG
result = []
def result.clear(width)
fill(0, 0, width)
end
def result.count(n)
join.count(n.to_s)
end
result.clear(n)
input_number("try! >") do |reply|
reply_set = num_split_cols(reply, n)
#check `Hit'
reply_set.each_with_index do |r, i|
result[i] += 1 if r == answer_set[i]
end
#check `Blow'
reply_set.each_with_index do |r, i|
result[i] += 1 if answer_set.include?(r)
end
hit, blow = result.count(2), result.count(1)
print "#{hit} Hit & #{blow} Blow\n"
break if hit == n
result.clear(n)
end
*FizzBuzz [#xb9545ca]
def fizz_buzz(n)
ret = "#{["Fizz"][n % 3]}#{["Buzz"][n % 5]}"
ret.empty? ? n.to_s : ret
end
puts (1..100).collect{|n| fizz_buzz n }
*カレンダー出力 [#v8444f3a]
#使い方: コマンドラインにテキトーに日付を入れで動かす
require 'optparse'
require 'time'
require 'forwardable'
require 'stringio'
class Month
extend Forwardable
[:Sunday, :Monday, :Thuesday, :Wednesday,
:Thursday, :Friday, :Saturday].each_with_index do |const, n|
const_set const, n
end
private
def initialize(datum)
@datum = datum
@days = [nil]
load_days datum, @days
end
def load_days(datum, days)
1.upto(31) do |day|
date = Time.local(datum.year, datum.month, day)
break unless date.month == datum.month
days.push date
end
end
public
def_delegators "@datum", :year, :zone
def name(abbrev=false)
@datum.strftime(abbrev ? "%b" : "%B")
end
def_delegators "@days", :[], :first, :last
def each
@days.each{|d| yield d }
end
end
class CalenderRender
def initialize(mon)
@mon = mon
end
def run(port=$stdout)
weeks = calender_matrix(@mon)
show_calender header_render(@mon) + calender_render(weeks)
end
private
def show_calender(src, port=$stdout)
port.print src
end
def calender_matrix(mon)
weeks = []
week = Array.new(7)
1.upto(mon.last.day) do |n|
week[mon[n].wday] = mon[n].day
if mon[n].wday == Month::Saturday
weeks.push week
week = Array.new(7)
end
end
weeks.push week
weeks
end
end
class CUICalenderRender < CalenderRender
private
def calender_matrix(mon)
weeks = super
weeks.unshift %w[Sun Mon Tue Wed Thu Fri Sat]
weeks
end
def header_render(mon)
col = 3 * 7 + (7 - 1)
cap = "#{mon.name}, #{mon.year}"
padding = (col - cap.length) / 2
head = sprintf("%#{padding}s%s%#{padding}s", "", cap, "")
sprintf("%#{col}s\n", head)
end
def calender_render(weeks)
weeks.collect{|week|
if week.all?{|day| day.nil? }
""
else
week.collect{|day| sprintf("%3s", day.to_s)}.join(" ")
end
}.join("\n")
end
end
class HTMLCalenderRender < CalenderRender
def header_render(mon)
h = "#{mon.name}, #{mon.year}"
<<-HTML
<!-- generated by calender.rb -->
<?xml version="1.0" ?>
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>#{h}</title>
</head>
<body>
<table>
<tr>
<th colspan="7">#{h}</th>
</tr>
HTML
end
def calender_render(weeks)
buf = StringIO.new
weeks.each do |week|
buf.puts "\t<tr>"
week.each do |day|
buf.puts "\t\t<td>#{day}</td>" if day
end
buf.puts "\t</tr>"
end
buf.puts "</table>\n</body>\n</html>"
buf.string
end
end
class GUICalenderRender < CalenderRender
#作成中
end
render_class = CUICalenderRender
render_class_table = {
"cui" => CUICalenderRender,
"gui" => GUICalenderRender,
"html" => HTMLCalenderRender
}
op = OptionParser.new
op.on("-m MODE", "--show-mode=MODE",
"specify calender type(cui|gui|html)"){|v|
render_class = render_class_table[v.downcase] || CUICalenderRender
}
op.on("-h", "--help", "show this help"){
warn op.help
exit 0
}
op.on("-v", "--version", "show version"){
warn "calender.rb 0.0.1"
exit 0
}
op.parse!(ARGV)
if ARGV.size > 1
ARGV.replace [ARGV.join("/")]
end
datum = ARGV[0] ? Time.parse(ARGV[0]).getlocal : Time.now
mon = Month.new(datum)
render = render_class.new(mon)
render.run
*配列いじり [#d5c23dc0]
def exclude_without_first!(array)
fst = array.first.dup
fst = array.first
array.fill(0)
array[0] = fst
array
end
*Caesar暗号解読 [#h97ae94f]
総当り法による力任せ解読。
### Usage: ruby caesar.rb HINT [CODE_FILE]
module CaesarCode
class CharTable
def initialize(char_set)
@char_set = char_set
@shifted = char_set.dup
@shift_count = 0
def @shifted.rotate
temp = self.shift
self.push temp
self
end
@table = {}
init_table
end
attr_reader :shift_count
def [](key)
@table[key]
end
def shift
@shifted.rotate
init_table
@shift_count += 1
self
end
private
def init_table
@table.clear
@char_set.zip(@shifted).each do |x|
@table[x[0]] = x[1]
end
end
end
end
def convert(base, table)
base.split(//).collect{|x| table[x] or x }.join("")
end
raise ArgumentError, "hint word not given" if ARGV.empty?
hint = ARGV.shift
char_set = "abcdefghijklmnopqrstuvwxyz .,-".split(//)
table = CaesarCode::CharTable.new(char_set)
src = ARGF.read
org = src[0]
until src.include?(hint)
src = convert(src, table.shift)
raise "can't decode" if org == src[0]
end
print src
print "鍵(シフト数)は #{table.shift_count} です\n"
*ファイル読み込んで標準出力に出す [#ib80ae4e]
begin
puts IO.readlines("kadai.txt").map{|line| "[#{line.chomp}]" }
rescue => ex
warn ex.message
end
*Base64 [#q2bfc331]
require 'stringio'
def version
warn "base64.rb 0.0.1"
exit 0
end
def help
warn <<-HELP
base64.rb: Base64 encoder/decoder
usage: ruby base64.rb MODE [filenames ...]
MODE:
encode : ordinary file to Base64 format
decode : Base64 format to original file
none : print not convert one
HELP
exit 0
end
proc_tbl = {
:encode => proc{|org| [org].pack("m") },
:decode => proc{|org| org.unpack("m").first },
:none => proc{|org| org }
}
opt_mode = []
ARGV.delete_if do |x|
case x
when "encode", "decode", "none"
opt_mode.push x.intern
when "-h", "--help"
help
when "-v", "--version"
version
end
end
opt_mode.empty? and opt_mode.push :none
opt_mode.size == 1 or raise "Too many mode specification"
mode = opt_mode.first
$stdin.binmode
$stdout.binmode
def argf_imitate(argv, mode)
if argv.empty?
yield $stdin
else
argv.each do |path|
File.open(path, mode){|f| yield f }
end
end
end
argf_imitate(ARGV, 'rb') do |f|
buffer = StringIO.new(proc_tbl[mode].call(f.read))
until buffer.eof?
$stdout.print buffer.read(64)
end
end
----
*初心者用課題（汎用アルゴリズム編） Ruby版 [#re07127c]
問題の詳細については
[[練習問題(アルゴリズム編)]]を参照。
*スタック [#g581d449]
require 'readline'
require 'forwardable'
module RPCalc
class Stack
extend Forwardable
def initialize
@body = []
end
def self.load(collection)
stack = self.new
collection.each{|x| stack.push x }
stack
end
def_delegators :@body, :push, :pop, :size, :empty?
def_delegator :@body, :last, :top
def pretty_print
". " + @body.reverse.map{|x| x.to_s }.join(" ") + " ]"
end
end
module Lexer
def lex(str)
str.strip.split(/\s+/)
end
end
module Parser
def parse(tokens)
semantic_values = []
tokens.each do |token|
case token
when /\A[_a-zA-Z]\w*\Z/
semantic_values.push [token.intern, :IDENT]
when /\A\d+\.\d+\Z/, /\A\d+\Z/
semantic_values.push [token.to_f, :NUMBER]
when /\A(\+|-|\*|\/)\Z/
semantic_values.push [token.intern, :COPERATOR]
else
semantic_values.push [token.intern, :ETC]
end
end
semantic_values
end
end
module Evaluater
def evaluate(svals, stack)
svals.each do |value, type|
case type
when :COPERATOR
unless o2 = stack.pop
warn "Stack Empty."
break
end
unless o1 = stack.pop
warn "Stack Empty."
stack.push o2
break
end
stack.push o1.__send__(value, o2)
when :NUMBER
stack.push value
when :IDENT
exit if value == :exit
when :ETC
; #ignore
else
raise Exception, "unknown semantic value: #{type}"
end
end
stack.top
end
end
class Calculator
include Lexer, Parser, Evaluater
def initialize
@stack = Stack.new
end
def shell(prompt, echo=true)
while line = Readline.readline(prompt, true)
yield line
puts @stack.pretty_print if echo
end
end
def calculate(expr)
tokens = lex(expr)
svals = parse(tokens)
evaluate(svals, @stack)
end
end
end
calc = RPCalc::Calculator.new
calc.shell("> ") do |line|
puts calc.calculate(line)
end
print "\n"
