Twelve Coins Problem
haskell
a month ago
15 kB
4
Indexable
Never
import Data.Maybe ( catMaybes ) import Data.List ( foldl' ) type Step = ([Int],[Int]) type Flowchart = [Step] data Result = Lighter | Equal | Heavier deriving (Eq, Show) type Scenario = (Int,Result) type IndClass = (Int,Int) type Perm = [Int] -- Prelim oppositeResult :: Result -> Result oppositeResult Lighter = Heavier oppositeResult Heavier = Lighter oppositeResult Equal = Equal weigh :: Scenario -> Step -> Result weigh (m,hl) (scaleLeft,scaleRight) | m `elem` scaleLeft = hl | m `elem` scaleRight = oppositeResult hl | otherwise = Equal applyFlowchart :: Scenario -> Flowchart -> [Result] applyFlowchart sc = map (weigh sc) allScenarios :: Int -> [Scenario] allScenarios n = [(m,hl) | m <- [1..n], hl <- [Lighter, Heavier]] -- Generation of flowcharts via IndClass method getSteps :: [IndClass] -> [(Step,[IndClass])] getSteps = filter (\((xs,ys),_) -> length xs == length ys) . getStepsFold (([],[]),[]) where getStepsFold (([],[]),_) [] = [] getStepsFold stepIc [] = [stepIc] getStepsFold (([],[]),ic') ((a,b):ic) = let m = b - a addToStep (c,d) = (([a..a-1+c], [a+c..a+c+d-1]),ic' ++ filter (uncurry (<=)) [(a,a+c-1),(a+c,a+c+d-1),(a+c+d,b)]) in concatMap (`getStepsFold` ic) [addToStep (c,d) | c <- [0..m+1], d <- [0..min c (m+1-c)]] getStepsFold ((xs,ys),ic') ((a,b):ic) = let m = b - a addToStep (c,d) = ((xs ++ [a..a-1+c], ys ++ [a+c..a+c+d-1]),ic' ++ filter (uncurry (<=)) [(a,a+c-1),(a+c,a+c+d-1),(a+c+d,b)]) in concatMap (`getStepsFold` ic) [addToStep (c,d) | c <- [0..m+1], d <- [0..m+1-c]] getFlowcharts :: Int -> Int -> [Flowchart] getFlowcharts n weighs = filter validFlowchart . map (reverse . fst) . filter (allDistinct . snd) . (!!weighs) . iterate (concatMap buildCharts) $ [([],[(1,n)])] where allDistinct = all (uncurry (==)) buildCharts ([], ic) = [([step], ic') | (step, ic') <- getSteps ic] buildCharts (prevStep:fc,ic) = [(step:prevStep:fc, ic') | (step, ic') <- getSteps ic, length (fst step) <= length (fst prevStep)] validFlowchart fc = allUnique $ map (`applyFlowchart` fc) scenarios scenarios = allScenarios n -- Rigorous isomorphism classes subsetIsomorphismProblem :: [[Int]] -> [[Int]] -> Bool subsetIsomorphismProblem xss yss = case subsetIsomorphismProblem' xss yss of Nothing -> False _ -> True subsetIsomorphismProblem' :: [[Int]] -> [[Int]] -> Maybe [(Int,Int)] subsetIsomorphismProblem' = go (Just []) where go Nothing _ _ = Nothing go currentPerm [] _ = currentPerm go (Just currentPerm) (xs:xss) (ys:yss) = if length xs /= length ys then Nothing else safeHead $ catMaybes [go nextPerm xss yss | ys' <- permsOf ys, let nextPerm = updatePerm currentPerm (zip xs ys')] updatePerm currentPerm [] = Just currentPerm updatePerm currentPerm ((x,y):ps) = case lookup x currentPerm of Nothing -> if y `elem` map snd currentPerm then Nothing else updatePerm ((x,y):currentPerm) ps Just y' -> if y /= y' then Nothing else updatePerm currentPerm ps isomorphic :: Flowchart -> Flowchart -> Bool isomorphic fc1 fc2 = any (isomorphicFixedOrder fc1) $ concatMap permsOf $ scaleFlips fc2 where scaleFlips fc = [zipWith (\b (x,y) -> if b then (y,x) else (x,y)) flips fc | flips <- cartExp [False,True] (length fc)] isomorphicFixedOrder fc1 fc2 = subsetIsomorphismProblem (concatMap (\(x,y) -> [x,y]) fc1) (concatMap (\(x,y) -> [x,y]) fc2) getIsomorphismClasses :: [Flowchart] -> [Flowchart] getIsomorphismClasses = foldl' (\classes fc -> if any (isomorphic fc) classes then classes else fc:classes) [] main :: IO () main = do n <- readLn let fcs = getFlowcharts n 3 let vcs = getIsomorphismClasses fcs print $ length fcs mapM_ print vcs print $ length vcs -- Helpers safeHead :: [a] -> Maybe a safeHead xs = if null xs then Nothing else Just $ head xs allUnique :: (Eq a) => [a] -> Bool allUnique = go [] where go _ [] = True go seen (x:xs) = x `notElem` seen && go (x:seen) xs permsOf :: (Eq a) => [a] -> [[a]] permsOf xs = getPermsFrom n [] where getPermsFrom 0 _ = [[]] getPermsFrom m used = concat [map (x:) $ getPermsFrom (m-1) (x:used) | x <- xs, x `notElem` used] n = length xs cartExp :: [a] -> Int -> [[a]] cartExp _ 0 = [[]] cartExp xs n = [x:ys | ys <- cartExp xs (n-1), x <- xs] powerset :: [a] -> [[a]] powerset [] = [[]] powerset (x:xs) = let ys = powerset xs in map (x:) ys ++ ys {- 12 coins, 3 weighings 130 algorithms generated from IndClass method [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,10,12],[3,5,8,11])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,9,10],[3,5,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,5,7,10],[3,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,5,7,12],[3,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,10],[3,5,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,12],[3,5,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,5,7],[3,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,7],[8,9,10,11]),([2,5,9,12],[3,6,8,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,7],[8,9,10,11]),([2,5,8,9],[3,6,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,7],[8,9,10,11]),([1,2,5,9],[3,6,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,8,12],[5,7,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,8,9],[5,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,5,6,8],[7,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,9,11],[4,5,7,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,9,12],[4,5,7,10])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,5,6,12],[4,7,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,5,6,9],[4,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([2,6,9,11],[3,7,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([2,6,9,12],[3,7,8,10])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([2,3,6,8],[7,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([2,3,6,12],[4,7,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([2,3,6,9],[4,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,6,9,11],[3,5,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,6,9,12],[3,5,8,10])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,5,6,12],[3,8,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,5,6,9],[3,8,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,8],[5,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,12],[4,5,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,9],[4,5,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,5,6],[4,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,6,9,11],[2,3,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,6,9,12],[2,3,8,10])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,8],[2,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,12],[2,4,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,9],[2,4,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,2,6,12],[3,8,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,2,6,9],[3,8,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,2,3,6],[4,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,8,10],[6,7,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,8,12],[6,7,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,7,8],[6,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,10,12],[4,6,7,11])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,9,10],[4,6,7,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,7,10],[4,6,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([3,5,7,12],[4,6,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,5,10,12],[3,7,8,11])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,5,9,10],[3,7,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,5,7,10],[3,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,5,7,12],[3,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,3,5,8],[7,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,3,5,10],[4,7,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,3,5,12],[4,7,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([2,3,5,7],[4,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,5,10,12],[3,6,8,11])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,5,9,10],[3,6,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,5,8],[6,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,5,10],[4,6,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,5,12],[4,6,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,9,10,12],[2,3,5,8])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,8,10],[2,5,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,8,12],[2,5,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,10,12],[2,4,5,11])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,3,9,10],[2,4,5,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,2,5,10],[3,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,2,5,12],[3,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[2,7,10,11]),([1,2,3,5],[4,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,7,9,12],[3,5,8,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,5,7,9],[3,8,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,3,7,9],[4,5,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,5,9,12],[2,3,8,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,3,8,9],[2,5,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,3,9,12],[2,4,5,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[7,9,10,11]),([1,3,5,9],[2,4,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,7,10],[5,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,7,12],[5,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,6,7],[8,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,10,12],[4,5,7,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,9,10],[4,5,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,6,10],[4,7,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,6,12],[4,7,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,6,7],[5,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,7,10],[3,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,7,12],[3,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,10,12],[3,4,7,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,6,9,10],[3,4,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,6,7],[3,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,6,7],[8,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,6,10],[4,7,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,6,12],[4,7,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,7,10,12],[2,5,8,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,7,9,10],[2,5,8,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,7,10],[2,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,7,12],[2,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,9,10,12],[2,4,5,7])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,10,12],[2,4,7,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,5,9,10],[2,4,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,10],[2,5,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,12],[2,5,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,5,7],[2,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,7,10,12],[2,3,8,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,7,9,10],[2,3,8,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,9,10,12],[2,3,4,7])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,10],[2,3,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,12],[2,3,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,7,10],[2,8,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,7,12],[2,8,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,10,12],[2,4,7,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,9,10],[2,4,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,3,4,7],[2,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[3,9,10,11]),([1,5,7,9],[6,8,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[3,9,10,11]),([1,5,9,12],[4,6,7,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[3,9,10,11]),([1,7,9,12],[3,5,8,10])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[3,9,10,11]),([1,4,7,9],[3,5,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,6],[3,9,10,11]),([1,3,5,9],[4,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,5,6,12],[3,7,9,11])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,5,6,9],[3,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,3,5,6],[7,9,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,6,9,11],[2,3,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,6,9,12],[2,3,7,10])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,3,6,12],[2,7,9,11])] [([1,2,3,4],[5,6,7,8]),([1,2,9,10],[3,4,5,11]),([1,3,6,9],[2,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,4,10,11]),([1,6,10,12],[3,5,7,11])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,4,10,11]),([1,6,9,10],[3,5,7,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,4,10,11]),([1,3,5,6],[7,9,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,4,10,11]),([1,3,6,10],[4,7,11,12])] [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,4,10,11]),([1,3,6,12],[4,7,9,10])] [([1,2,3,4],[5,6,7,8]),([1,2,3,5],[4,9,10,11]),([1,6,9,12],[2,5,7,10])] [([1,2,3,4],[5,6,7,8]),([1,2,3,5],[4,9,10,11]),([1,5,6,9],[2,7,10,12])] [([1,2,3,4],[5,6,7,8]),([1,2,3,5],[4,9,10,11]),([1,6,9,12],[2,4,7,10])] [([1,2,3,4],[5,6,7,8]),([1,2,3,5],[4,9,10,11]),([1,4,6,9],[2,7,10,12])] Example unintuitive isomorphism: [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,10],[2,3,11,12])] ~~~ [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,9,10],[3,5,8,12])] via (1 5 3 7) (2 8 4 6) (9 12 11 10) Isomorphism classes: [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,12],[4,5,9,11])] [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,9,11],[4,5,7,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,7],[8,9,10,11]),([2,5,9,12],[3,6,8,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,12],[3,5,9,10])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,10],[3,5,11,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,9,10],[3,5,8,12])] [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,10,12],[3,5,8,11])] -}