module Problem103 where

import Control.Monad
import Data.Function
import Data.List

main :: IO ()
main = putStrLn . concatMap show $ minimumOptimumSpecialSumSet 7

minimumOptimumSpecialSumSet :: Int -> [Int]
minimumOptimumSpecialSumSet n = reverse . head . (!! max 0 n) $ iterate
    (concatMap nextElement)
    [[]]
  where
        -- NOTE : disjointness doesn't matter since if we include elements in both then comparison
        -- remains same
    nextElement soln
        | null soln = map (: []) [1 .. 50]
        | otherwise = filter valid $ map (: soln) [1 + head soln .. 50]
    valid soln'@(x : xs) =
        -- minimum sum of any subset of size k should be greater than
        -- maximum sum of any subset of size k-1
        and (zipWith (<) (maxSums soln') (tail $ minSums soln'))
        -- sets of same size should not have unique values, so sets of size k from xs
        -- and set of size k-1 from xs and including x should be sufficient to gurantee
        -- uniqueness of sums of same size
                                                                 && and
            (zipWith
                (\oldSumsK newSumsK ->
                    null
                        [ True
                        | oldSumK <- oldSumsK
                        , newSumK <- newSumsK
                        , oldSumK == newSumK
                        ]
                )
                (tail oldSums)
                newSums
            )
      where
        newSums = map (map (+ x)) oldSums
        oldSums =
            map (map sum)
                . groupBy ((==) `on` length)
                . sortBy (compare `on` length)
                $ filterM (const [True, False]) xs
    -- set is sorted so minSums formed by greedily taking smallest elements
    minSums xs = map sum . reverse . notnull $ tails xs
    maxSums xs = map sum . notnull $ inits xs
    notnull = filter (not . null)
