219 Skew-cost coding

Problem 219 – Project Euler

語頭符号と聞くと，ハフマン符号を思いつきますが，

Huffman coding – Wikipedia, the free encyclopedia

今回は，単純な符号長ではなく重み付きの符号長になっているのが違うところ．

符号化が問題になっているわけではないので，大丈夫だが…

符号木を考えると分かりやすいかと．

木の葉が符号に対応．

重要なことは（自明といえば，自明だが），サイズをひとつ増やすと，重み付き符号長最小の葉がふたつに分かれること．

あと，コスト最小なら木の葉の重み付き符号長の差は高々4． 

import Data.List (findIndex)
nexts :: (Integer, [Integer]) -> (Integer, [Integer])
nexts (n, c1: c2: cs) = (n+c1, (c1+c2): cs ++ [c1])
p219 :: Integer -> Integer
p219 n = sum $ zipWith (*) [toInteger m..] cs
where ss = iterate nexts (2, [1, , , 1])
Just m = findIndex ((>n).fst) ss
(n', [c1, c2, c3, c4]) = ss !! (m-1)
cs = [c1-n+n', c2+n-n', c3, c4, n-n']