RubyでPalindromic Rangesを解く-CodeEval

またまた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

RubyでFollowing Integerを解く-CodeEval

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

RubyでUgly Numbersを解く-CodeEval

って、まだ解けてません^ ^;

下のコードだと一応解答は得られるんだけど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

RubyでString Listを解く-CodeEval

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

RubyでMessage Decodingを解く-CodeEval

まず問題を解読するのが大変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

blog comments powered by Disqus

100円〜で好評発売中！
M'ELBORNE BOOKS