From 81710cb55dfe66fe8dae4a33c5053b0e7017a82b Mon Sep 17 00:00:00 2001
From: Neil Smith <NeilNjae@users.noreply.github.com>
Date: Wed, 25 Dec 2024 21:57:46 +0000
Subject: [PATCH] Tidy, added link to blog post
---
advent23/Main.hs | 18 +++++-------------
1 file changed, 5 insertions(+), 13 deletions(-)
diff --git a/advent23/Main.hs b/advent23/Main.hs
index 8287d07..a53c2f1 100644
--- a/advent23/Main.hs
+++ b/advent23/Main.hs
@@ -1,4 +1,5 @@
--- Writeup at https://work.njae.me.uk/2024/12/24/advent-of-code-2024-day-22/
+-- Writeup at https://work.njae.me.uk/2024/12/25/advent-of-code-2024-day-23/
+
import AoC
import Data.Text (Text)
@@ -31,21 +32,14 @@ main =
print $ part1 graph
-- print $ getMaximalCliques graph
putStrLn $ part2 graph
-
-
- -- print $ part1 codes
- -- print $ part2 codes
--- part1, part2 :: [Int] -> Int
--- part1 codes = sum $ fmap (followingSecret 2000) codes
-
--- part1 :: Graph -> Int
+part1 :: Graph -> Int
part1 graph = length $ filter couldBeHistorian $ find3Cliques graph
--- part1 graph = find3Cliques graph
+
+part2 :: Graph -> String
part2 graph = intercalate "," $ sort maxClique
where maxClique = maximumBy (compare `on` length) $ getMaximalCliques graph
-
find3Cliques :: Graph -> [[Vertex]]
find3Cliques graph = filter isClique possibles
where possibles = tuples 3 $ M.keys graph
@@ -55,7 +49,6 @@ find3Cliques graph = filter isClique possibles
couldBeHistorian :: [Vertex] -> Bool
couldBeHistorian cliques = any ((== 't') . head) cliques
-
-- Implementation from https://www.cs.columbia.edu/~sedwards/classes/2023/4995-fall/reports/MaximalClique-report.pdf
getMaximalCliques :: Graph -> [Clique]
@@ -81,7 +74,6 @@ restrictVertices graph curvertices vertex = filter ( isConnected graph vertex )
isConnected :: Graph -> Vertex -> Vertex -> Bool
isConnected graph a b = b `S.member` (graph M.! a)
-
mkGraph :: [Edge] -> Graph
mkGraph edges = M.fromListWith S.union $ fmap (\(Edge a b) -> (a, S.singleton b)) biEdges
where biEdges = edges ++ fmap (\(Edge a b) -> Edge b a) edges
--
2.43.0