またまたArray#permutationのお世話に..
与えられた2数を最小値と最大値とする数字の並びにおける並びの組を考える。回文数が偶数個の組の数を答える。
#!/usr/bin/env ruby
def count_even_palindrome(l, r)
range = [*l..r]
(range.size.times).inject(0) do |cnt, w|
x = range.each_cons(w+1).select do |set|
set.count { |n| palindrome? n }.even?
end
cnt += x.size
end
end
def palindrome?(num)
"#{num}" == "#{num}".reverse
end
ARGF.lines do |line|
l, r = line.split(/\s+/).map(&:to_i)
p count_even_palindrome(l, r)
end
Array#permutationを使って力技!
与えられた数の各桁の並び替えの組合せを、昇順に並べたとき与えられた数の次ぎに来る数を答える。但し各数には任意個数の0を挟める。
#!/usr/bin/env ruby
def build_combination(nums)
nums.permutation(nums.size).sort.uniq.map(&:join).reject { |e| e[0] == '0' }
end
def next_number(num)
nums_wo_zero = num.to_s.chars.map(&:to_i).reject(&:zero?)
zeros = num.to_s.count('0')
nums = nums_wo_zero + [0]*zeros
set = build_combination(nums)
unless next_num = set[set.index(num.to_s)+1]
next_num = build_combination(nums+[0]).min
end
next_num.to_i
end
ARGF.lines do |line|
num = line.to_i
puts next_number(num)
end
って、まだ解けてません^ ^;
下のコードだと一応解答は得られるんだけど5秒以上掛かるってことで0点です..
気にせず先に..
一桁の素数(2,3,5,7)で割れる数をUgly Numberという。D桁の数字の桁の間に+か-を挟むと3^D-1 個の数字ができる。Ugly Numberの個数を求める。
#!/usr/bin/env ruby
def count_uglys(num)
exps = all_expressions(num)
exps.map { |exp| eval exp }
.inject(0) { |cnt, n| ugly?(n) ? cnt + 1 : cnt }
end
def all_expressions(num)
op = ['+', '-', '']
top, *remains, _ = num.chars.inject([]) { |arr, n| arr << [n] << op }
top.product(*remains).map { |arr| oct2dec arr.join }
end
# avoid evaluating as oct number
def oct2dec(str)
str.gsub(/0+(\d)/, '1円')
end
def ugly?(num)
[2,3,5,7].any? { |i| (num%i).zero? }
end
ARGF.lines do |line|
number = line.chomp
puts count_uglys(number)
end
Array#repeated_permutationで^ ^;
文字列中の文字の全順列。
#!/usr/bin/env ruby
def possible_ways(set, n)
set.repeated_permutation(n).map { |e| e.join }.uniq.sort
end
ARGF.lines do |line|
n, str = line.split(',').map(&:chomp)
puts possible_ways(str.split(//), n.to_i).join(',')
end
まず問題を解読するのが大変orz..
どう見てもエレガントな解法じゃない..
特にheaderのsequenceを作る方法がヒドイ。どなたかスマートな解法を教えて下さい。
文字列からなるheaderを使って01からなるmessageを解読する。headerの各文字はその位置にマッピングされた01からなるkeyに対応付けられている。messageは複数のkeyを含む複数のsegmentからできていて、各segmentの最初の3桁がそのsegment内のkeyの長さを表す。
#!/usr/bin/env ruby
def message_decode(header, message)
keys = extract_keys(message)
table = build_table(header)
decode(keys, table)
end
def extract_keys(message, default_keysize=3)
key_size = default_keysize
go_next_segment = true
keys = []
while key = message.slice!(/.{#{key_size}}/)
if go_next_segment
key_size = key.to_i(2)
go_next_segment = false
else
next unless key.size == key_size
if key.chars.any? { |chr| chr == '0' }
keys << key
else
go_next_segment = true
key_size = default_keysize
end
end
end
keys
end
def build_table(header)
digit_sequence = digit_sequence_gen
header.chars.inject({}) { |h, v| h[digit_sequence.next] = v; h }
end
def digit_sequence_gen
digit_counter_gen = Enumerator.new { |y| n = 1; loop { y << 2**n-1; n+=1 } }
Enumerator.new do |y|
digit_counter = digit_counter_gen
digits, cnt, n = 0, 0, 0
loop do
if cnt.zero?
cnt = digit_counter.next
n = 0
digits += 1
end
y << format("%0#{digits}d", n.to_s(2)).tap { cnt -= 1; n += 1 }
end
end
end
def decode(keys, table)
keys.inject("") { |mem, code| mem + table[code] }
end
ARGF.lines do |line|
header, message = line.match(/\d+/) { |m| [m.pre_match, m.to_s] }
puts message_decode(header, message)
end