Problem 219

Project Euler Haskell

219 Skew-cost coding
Problem 219 - Project Euler
語頭符号と聞くと，ハフマン符号を思いつきますが，
Huffman coding - Wikipedia
今回は，単純な符号長ではなく重み付きの符号長になっているのが違うところ．
符号化が問題になっているわけではないので，大丈夫だが…
符号木を考えると分かりやすいかと．
木の葉が符号に対応．
重要なことは（自明といえば，自明だが），サイズをひとつ増やすと，重み付き符号長最小の葉がふたつに分かれること．
あと，コスト最小なら木の葉の重み付き符号長の差は高々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, 0, 0, 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']