# Twelve Coins Problem

unknown
a year ago
15 kB
15
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
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])]
-}```