module Exercise05 where

import Data.List
import Data.Ord

-- May or may not be useful: computes the logarithm base 2 (rounded down) of the given number.
-- You don't have to move this into the WETT tags if you want to use it.
log2 :: (Integral a, Num b) => a -> b
log2 = let go acc n = if n <= 1 then acc else go (acc + 1) (n `div` 2) in go 0

{-WETT-}
decompose1 :: Integer -> [Integer]
decompose1 0 = []
decompose1 x = r : decompose1 q where (q, r) = quotRem x 2

decompose2 :: Integer -> Integer -> Integer -> [Integer]
decompose2 0 _ _ = []
decompose2 x 1 _ = [x]
decompose2 x p d = p * r : decompose2 q (p `div` d) d where (q, r) = quotRem x 2

madd :: Integer -> [Integer] -> [Integer] -> [Integer]
madd _ [] ys = ys
madd m xs [] = [m * x | x <- xs]
madd m (x:xs) (y:ys) = (m * x + y) : madd m xs ys

merge :: Integer -> Integer -> Integer -> [Integer] -> [Integer]
merge _ _ _ [] = []
merge _ _ y _ | y <= 0 = []
merge p d y (x:xs) = madd x (decompose2 y p d) (merge (p * d) d y xs)

decompose :: [Integer] -> [Integer]
decompose [] = []
decompose [x] = decompose1 x
decompose (x:xs) = merge 1 (2 ^ length xs) x (decompose xs)
{-TTEW-}