結城浩さん (id:hyuki) 出題のリンゴ問題に挑戦した

vim codeiq

ベストリンゴ賞もらえた. 回答は C 言語で書いた. ハフマン符号を使わない回答だったので, 勉強のため vim script で書いてみた. こういうアルゴリズム問題は vim 力なくても書けるから練習に良い気がする.

" http://www.hyuki.com/codeiq/
" https://codeiq.jp/ace/yuki_hiroshi/q279
" りんごの圧縮問題
" 結城浩さんの解答をみながら実装
"
" type : leaf if 0
"      : leaf-dummy if -1
"      : node if 1
let s:sorted_list = [
\	{'count' : 1194, 'char':  'E', 'type' : 0},
\	{'count' : 1001, 'char':  'T', 'type' : 0},
\	{'count' :  805, 'char':  'A', 'type' : 0},
\	{'count' :  694, 'char':  'I', 'type' : 0},
\	{'count' :  662, 'char':  'O', 'type' : 0},
\	{'count' :  653, 'char':  'H', 'type' : 0},
\	{'count' :  581, 'char':  'N', 'type' : 0},
\	{'count' :  572, 'char':  'S', 'type' : 0},
\	{'count' :  460, 'char':  'R', 'type' : 0},
\	{'count' :  410, 'char':  'D', 'type' : 0},
\	{'count' :  398, 'char':  'L', 'type' : 0},
\	{'count' :  295, 'char':  'U', 'type' : 0},
\	{'count' :  246, 'char':  'W', 'type' : 0},
\	{'count' :  226, 'char':  'Y', 'type' : 0},
\	{'count' :  209, 'char':  'C', 'type' : 0},
\	{'count' :  201, 'char':  'M', 'type' : 0},
\	{'count' :  199, 'char':  'G', 'type' : 0},
\	{'count' :  123, 'char':  'K', 'type' : 0},
\	{'count' :  121, 'char':  'F', 'type' : 0},
\	{'count' :  110, 'char':  'P', 'type' : 0},
\	{'count' :  107, 'char':  'B', 'type' : 0},
\	{'count' :   74, 'char':  'V', 'type' : 0},
\	{'count' :   11, 'char':  'J', 'type' : 0},
\	{'count' :    9, 'char':  'Q', 'type' : 0},
\	{'count' :    5, 'char':  'Z', 'type' : 0},
\	{'count' :    5, 'char':  'X', 'type' : 0},
\	]


" ???
while len(s:sorted_list) % 3 != 0
	call add(s:sorted_list, {'count' : 0, 'type' : -1})
endwhile


while len(s:sorted_list) > 2 
	let a = remove(s:sorted_list, -1)
	let b = remove(s:sorted_list, -1)
	let c = remove(s:sorted_list, -1)
	let d = {
\		'count' : a.count + b.count + c.count, 
\		'type' : 1,
\		'child' : [a,b,c]}
	let i = len(s:sorted_list) 
	while i > 0
		let elm = s:sorted_list[i-1]
		if elm.count > d.count
			break
		endif
		let i = i - 1
	endwhile
	call insert(s:sorted_list, d, i)
endwhile

function! s:get_result(l, d, v)
	if a:l.type == 0
		let a:l.depth = a:d
		echo a:l.char . ':' . a:v
		return a:d * a:l.count
	elseif a:l.type == 1
		let c = a:l.child
		let c1 = s:get_result(c[0], a:d+1, a:v . "r")
		let c2 = s:get_result(c[1], a:d+1, a:v . "g")
		let c3 = s:get_result(c[2], a:d+1, a:v . "b")
		return c1+c2+c3
	else
		return 0
	endif
endfunction

echo s:get_result(s:sorted_list[0], 0, "")


note:

  • ハフマン符号が最適になる理由が理解できていないので, 3 の倍数にするためにダミーを追加している部分(??? のところ)の正しさがわかっていない.
  • 以下の部分は for in range() にしたかったけど, len(s:sorted_list)=0 の場合に対する例外処理が必要で悲しくなったので while 文にした. 恰好よくかけないのかな.
    let i = len(s:sorted_list)
    while i > 0
        ....
        let i = i - 1
    endwhile