The obvious solution is to generate all candidates satisfying the first two constraints and perform filtering on
constraint3. After having a base implementation, it’s not that hard to come up with the “precise” solution.

Interestingly, the ending result is the Catalan Number.

Another occurrence is matched-parenthesis: the number of expressions containing n pairs of parentheses which are
correctly matched. The “precise” solution is actually easier to reason, surprisingly.

{-# LANGUAGE RecordWildCards #-} {-# LANGUAGE TemplateHaskell #-}

import Data.List importqualified Data.Set as Set

import Hedgehog import Hedgehog.Internal.Property (TestLimit(..), ShrinkLimit(..)) importqualified Hedgehog.Gen as Gen importqualified Hedgehog.Range as Range import Control.Monad (ap)

-- Problem 1: #array gen_and_prune :: Int -> [[Int]] gen_and_prune = filter constraint3 . all_list where all_list :: Int -> [[Int]] all_list n = rec n n where rec sum 1 = [[sum]] rec sum len = do x <- [0..sum] xs <- rec (sum-x) (len-1) return $ x:xs

constraint3 :: [Int] -> Bool constraint3 list = rec list 10 where rec [] _ _ = True rec (x:xs) i sum = x + sum <= i && rec xs (i+1) (x+sum)

precise_gen :: Int -> [[Int]] precise_gen n = rec n n where rec sum 1 = [[sum]] rec sum len = do -- future len-1 are unavailable yet x <- [0 .. sum - (len-1)] xs <- rec (sum-x) (len-1) return $ x:xs

prop_eq :: Property prop_eq = withTests (TestLimit5) . property $ do n <- forAll . Gen.integral $ Range.constant 110 collect n let l1 = gen_and_prune n let l2 = precise_gen n assert $ Set.fromList l1 == Set.fromList l2

-- Problem 2: Matched parentheses dataState = State { unmatched :: Int, list :: [Char] } deriving (Show, Eq)

pair_p :: Int -> [[Char]] pair_p n = map get_list $ recState{unmatched=0, list=[]} (2*n) where get_list = reverse . list

rec :: State -> Int -> [State] rec s 0 = [s] rec s@State{..} i | unmatched == 0 = rec left i' | unmatched == i = rec right i' | otherwise = rec left i' ++ rec right i' where left = State{unmatched = unmatched+1, list = '(':list} right = State{unmatched = unmatched-1, list = ')':list} i' = i - 1

prop_matched :: Property prop_matched = withTests (TestLimit5) . property $ do n <- forAll . Gen.integral $ Range.constant 110 collect n assert $ all is_pair_matched $ pair_p n where is_pair_matched :: [Char] -> Bool is_pair_matched l = rec l 0 where rec [] acc = acc == 0 rec ('(':xs) acc = rec xs $ acc+1 rec (')':xs) acc = rec xs $ acc-1