last updated: Aug. 18, 2006.

그냥 재미로 오랜만에;;

문제는 http://orbi7.com/bbs/zboard.php?id=pls_amu_imported&no=20076에. 풀다보니 어느새 루비로 코딩하고 있던 자신을 발견함;; 그래서 풀이는 루비.

#!/usr/bin/ruby -w

numbers = [49, 49, 50, 52, 49, 47, 47, 46, 44, 42, \
42, 38, 38, 38, 36, 34, 33, 33, 33, 32, \
34, 38, 42, 41, 42, 42, 40, 41, 40, 38, \
38, 37, 37, 39, 41, 40, 40, 40, 40, 42, \
45, 47, 47, 46, 46, 46, 47, 47, 47, 47, \
46, 44, 43, 39, 36, 34, 34, 32, 30, 29, \
30, 31, 31, 31, 30, 28, 25, 23, 24, 22, \
22, 25, 25, 27, 31, 33, 35, 37, 38, 39, \
39, 40, 40, 41, 40, 40, 40, 40, 39, 38, \
37, 35, 35, 34, 33, 32, 31, 30, 30, 29, \
29, 28, 27, 27, 28, 27, 25, 26, 0, 0, \
90, 90, 90, 90, 90, 91, 90, 88, 87, 84, \
80, 78, 83, 89, 91, 90, 89, 92]

# Average value of given numbers
def average(nums)
nums.inject(0.0) { |tot, i| tot + i } / nums.size
end

def error_sum(nums)
rmse(nums, [encode(nums)]) ** 2 * nums.size
end

# Split numbers into every possible split point, and find out the split
# point where the difference of averages of left partition and the right
# one is the biggest.
def best_split_point(nums)
left_sum = nums[0]
right_sum = nums[1..-1].inject(0) { |tot, i| tot + i }

min_dif = error_sum(nums[0..0]) + error_sum(nums[1..-1])
min_dif_idx = 0

for i in (1..nums.size – 2)
cur_dif = error_sum(nums[0..i]) + error_sum(nums[i+1..-1])

if min_dif > cur_dif
min_dif_idx = i
min_dif = cur_dif
end
end

min_dif_idx
end

# Compute rmse value
def rmse(nums, encoding)
inflated = encoding.inject([]) do |memo, i|
memo << [i[0]] * i[1] end.flatten squared_sum = nums.zip(inflated).inject(0.0) do |tot, i| tot += (i[0] - i[1]) ** 2 end Math.sqrt(squared_sum / nums.size) end # Encode numbers. This is simply done by returning # [average of numbers, # of numbers] def encode(nums) [(nums.inject(0.0) { |tot, i| tot += i } / nums.size).round, nums.size] end # Split nums into two partition where rmse is expected to be minimized most. def split(nums) split_point = best_split_point(nums) num_partition = [nums[0..split_point], nums[split_point+1..-1]] [num_partition, [encode(num_partition[0]), encode(num_partition[1])]] end # Find out best run length encoding (RLE) based on rmse def find_best_encoding(nums, max_encoding_len) num_partition, encoding = split(nums) while encoding.size < max_encoding_len # Find the worst split worst_rmse = nil worst_rmse_idx = -1 num_partition.zip(encoding).inject(0) do |idx, (n, e)| if worst_rmse_idx == -1 || (rmse(n, [e]) ** 2 * n.size) > worst_rmse
worst_rmse = rmse(n, [e]) ** 2 * n.size
worst_rmse_idx = idx
end
idx + 1
end

# Split the bad guy
num_partition[worst_rmse_idx], encoding[worst_rmse_idx] = split(num_partition[worst_rmse_idx])

# Flatten – WTF! Do I really have to do this? I’m so stupid.
tmp_num_partition = []
num_partition.each do |v|
if v[0].kind_of?(Array)
v.each do |i|
tmp_num_partition << i end else tmp_num_partition << v end end num_partition = tmp_num_partition tmp_encoding = [] encoding.each do |v| if v[0].kind_of?(Array) v.each do |i| tmp_encoding << i end else tmp_encoding << v end end encoding = tmp_encoding end [num_partition, encoding] end num_parition, encoding = find_best_encoding(numbers, 16) puts "Number partitions=#{num_parition.inspect}" puts puts "RLE=#{encoding.inspect}" puts puts "RMSE=#{rmse(numbers, encoding)}" [/code] 음 일단 비효율성은 신경안쓰더라도 아직 1.89 [code] mkseo@mkseo:~/tmp$ ./rmse.rb Number partitions=[[49, 49, 50, 52, 49, 47, 47, 46], [44, 42, 42], [38, 38, 38, 36, 34, 33, 33, 33, 32, 34, 38], [42, 41, 42, 42, 40, 41, 40, 38, 38, 37, 37, 39, 41, 40, 40, 40, 40], [42, 45, 47, 47, 46, 46, 46, 47, 47, 47, 47, 46, 44], [43, 39], [36, 34, 34, 32, 30, 29, 30, 31, 31, 31, 30], [28, 25, 23, 24, 22, 22, 25, 25, 27, 31], [33, 35, 37, 38, 39, 39, 40, 40, 41, 40, 40, 40, 40, 39, 38, 37], [35, 35, 34], [33, 32, 31, 30, 30, 29, 29, 28, 27, 27, 28, 27, 25, 26], [0, 0], [90, 90, 90, 90, 90, 91, 90], [88, 87, 84], [80, 78, 83], [89, 91, 90, 89, 92]] RLE=[[49, 8], [43, 3], [35, 11], [40, 17], [46, 13], [41, 2], [32, 11], [25, 10], [39, 16], [35, 3], [29, 14], [0, 2], [90, 7], [86, 3], [80, 3], [90, 5]] RMSE=1.89571886101289 [/code] 아직까지 greedy인데, greedy로 하면 안되는건지 버그인지; 다시 수정 예정입니다.