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 ds
    | or [len <= 0 | len <- ds] = []   --invalid
    | otherwise = decomposeStep base (toInteger (length base)-1) (toInteger(length ds))
    where base = decomposeBase ds
{-TTEW-}

--Filtert rekursiv die doppelten Counts von cs!!run1 aus allen niedrigeren Counts heraus
--2 Steps: [56,12,2] => [24,4,2] => [8,4,2]
decomposeStep :: [Integer] -> Integer -> Integer -> [Integer]
decomposeStep cs 0 _ = cs
decomposeStep cs run1 dim = decomposeStep step (run1 -1) dim
    where step = [if toInteger run2 >= run1 then cs!!run2   --bereits aus Aktionsbereich raus
                        --AnzahlKlein - AnzahlGroß * 2^(Positiondifferenz * Dimension)
                    else cs!!run2 - ((cs!!fromIntegral run1) * 2^((run1-toInteger run2)*dim)) 
                    | run2 <- [0..(length cs -1)]]

--tests how often cuboids with length(2^run) fit in our system
--since we dont care about other run levels, this base step returns an unfiltered version of the solution
decomposeBase :: [Integer] -> [Integer]
decomposeBase ds = [numSquaresFit ds (2^run) | run <- [0..log2 zBase]]
    where zBase = nextExpo (minimum ds)

--wie viele cuboids mit BaseSeitenlänge bl passen in den Bereich
--(wie viele Squares mit BaseSeitenlänge bl passen in das Feld)
numSquaresFit :: [Integer] -> Integer -> Integer
numSquaresFit feld bl
    | or [feld!!pos < bl | pos <- [0..(length feld -1)]] = 0 --invalid, trifft eig nicht ein
    | otherwise = product [l `div` bl | l <- feld]

--redundant, nur als reminder übrig :)
--gibt an wie oft BaseLength bl in tatsächliche Length l passt
fitLength :: Integer -> Integer -> Integer
fitLength bl l = l `div` bl

--gibt maximales enthaltenes Vielfaches zurück (n * base b <= value x)
nextViel :: Integer -> Integer -> Integer
nextViel b x = maximum [n * b | n <- [1..x], n * b <= x]

--gibt nächst kleineres Vielfaches von 2 zurück, zB 80 -> 64
nextExpo :: Integer -> Integer
nextExpo x = 2^(y-1)
    where y = head [yrun | yrun <- [1..], 2^yrun > x]