module Exercise05 where

--import Debug.Trace

-- 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-}
-- While unable to proof any of these claims, we strongly believe these are true
-- 1. The complexity of this algorithm is O(d log n) whereas d is the number of dimensions and n is the size of the largest dimension
-- 2. This algorithm is correct (based on the findings of me and other CPs [Competition Participants])


--    This function takes the largest Cube it can possibly fit in and puts it in the space, initializing all the fields in the process
--    After that the other functions get recursively called
--    Short Circuit for those pesky flat or negative Cube/Hypercube/(whatever you call that stuff in the 10^14th dimension)
--    For readability we will now always refer to cubes, although we of course mean the äquivalent structure in the respective dimension

decompose :: [Integer] -> [Integer]
decompose [] = []
decompose ds =
  let miv = minimum ds
      minl = log2 miv
      mi = 2 ^ minl
      tD = length ds
   in if miv <= 0
        then []
        else reverse $ decRM (map (\x -> x - mi) ds) [mi | _ <- [1 .. tD]] minl 1 (toInteger tD) 1

--This function goes over all possible cube sizes (smaller than the init cube)
--Note: the volume always gets 2^totalDimension so it stays accurate, while allowing to not deal with large numbers for large cubes
--This ensures that the volume is always the number of cubes of the current size we can fit in our currently claimed space

decRM :: [Integer] -> [Integer] -> Integer -> Integer -> Integer -> Integer -> [Integer]
decRM _ _ (-1) _ _ _ = []
decRM rmDims crDims cszl vol tD ca =
  let (rrmDims, rcrDims, rca, rvol) = decRC rmDims crDims ca (2 ^ cszl) vol tD
   in
      rca : decRM rrmDims rcrDims (cszl -1) (rvol * (2 ^ tD)) tD 0

--This goes once trough all dimensions
--Basically it calculates how many cubes can fit into this dimension by dividing the remaining space between the outer
-- limits and the currently claimed space
--This allows us to just multiply this dimension with the currently claimed volume divided by the inspected dimension,
-- because remember our volume always accurately represents how many cubes we would be able to fit into our currently claimed space
--Also short circuit if we can not fit any cubes into this dimension

decRC :: [Integer] -> [Integer] -> Integer -> Integer -> Integer -> Integer -> ([Integer], [Integer], Integer, Integer)
decRC [] _ ca _ vol _ = ([], [], ca, vol)
decRC _ [] ca _ vol _ = ([], [], ca, vol)
decRC (rd : rmDims) (cd : crDims) ca csz vol td =
  let nac = rd `div` csz
      voldm = vol `div` (cd `div` csz)
      cuba = (voldm * nac)
      rmd = rd - (nac * csz)
      ncs = cd + (nac * csz)
      (rrmDims, rcrDims, rca, rvol) = decRC rmDims crDims (ca + cuba) csz (if nac > 0 then cuba + vol else vol) td
   in (rmd : rrmDims, ncs : rcrDims, rca, rvol)
{-TTEW-}