2.3 kB · 61 lines · Created 10mo ago
Haskell
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import Data.List (find, sortBy)import Data.List.Split (splitOn)import Data.Ord (comparing)import qualified Data.Set as S
parse = map (map read . splitOn ",") . lines
dist [x, y, z] [x', y', z'] = sqrt $ (x - x') ^ 2 + (y - y') ^ 2 + (z - z') ^ 2
pairwise ls = sortBy (comparing snd) [((i, i'), dist p p') | (i, p) <- zip [0 ..] ls, (i', p') <- zip [0 ..] ls, i' > i]
circuits ls limit = foldl insert [] ordered where ordered = map fst . take limit $ pairwise ls insert (c : cs) (i, i') = if any (`S.member` c) [i, i'] then mergeSets ((c `S.union` S.fromList [i, i']) : cs) else c : insert cs (i, i') insert [] (i, i') = [S.fromList [i, i']]
circuits2 ls = (ls !! p, ls !! p') where Just ((p, p'), _) = find (\(pt, res) -> length ls == maximum (map S.size res)) $ tail $ scanl insert ((0, 0), []) ordered ordered = map fst $ pairwise ls insert :: ((Int, Int), [S.Set Int]) -> (Int, Int) -> ((Int, Int), [S.Set Int]) insert (_, (c : cs)) (i, i') = if any (`S.member` c) [i, i'] then let merged = mergeSets ((c `S.union` S.fromList [i, i']) : cs) pt = if (maximum $ map S.size merged) == length ls then (i, i') else (0, 0) in (pt, merged) else ((0, 0), c : snd (insert ((0, 0), cs) (i, i'))) insert (_, []) (i, i') = ((0, 0), [S.fromList [i, i']])
mergeSets [] = []mergeSets (s : ss) = mergeSets' [s] ss where mergeSets' acc [] = acc mergeSets' acc (x : xs) = case findIntersecting x acc of Nothing -> mergeSets' (x : acc) xs Just (intersecting, rest) -> mergeSets' (S.unions (x : intersecting) : rest) xs findIntersecting x sets = let (intersecting, disjoint) = partition (not . S.null . S.intersection x) sets in if null intersecting then Nothing else Just (intersecting, disjoint)
partition :: (a -> Bool) -> [a] -> ([a], [a])partition p xs = foldr select ([], []) xs where select x (ts, fs) | p x = (x : ts, fs) | otherwise = (ts, x : fs)
p1 n = product $ take 3 $ map S.size $ reverse $ sortBy (comparing S.size) $ circuits n 1000
p2 = circuits2
main = do n <- parse <$> getContents print $ p1 n print $ p2 n