module Exercise05 where

-- 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-}
decompose :: [Integer] -> [Integer]
decompose [] = []
decompose ds
    | 0 `elem` ds = []
    | otherwise   = reverse $ map snd $ merge 0 (length ds) $ cubes (2 ^ log2 (minimum ds))
    where
        -- For each possible cube size, calculate cube amount if volume would be filled with same-sized cubes.
        cubes :: Integer -> [(Integer, Integer)]
        cubes 0 = []
        cubes a = (a, product (map (`div` a) ds)) : cubes (a `div` 2)

        -- Smaller cubes are merged into larger ones
        merge :: Integer -> Int -> [(Integer, Integer)] -> [(Integer, Integer)]
        merge _ _ []                        = []
        merge _ _ [x]                       = [x]
        merge acc n ((x, a) : (y, b) : xs)  = let nAcc = acc + (x ^ n) * a in (x, a) : merge nAcc n ((y, (y ^ n * b - nAcc) `div` (y ^ n)) : xs)
{-TTEW-}