Day 25: Snowverload

import networkx


class Solver:

    def __init__(self):
        with open('input.txt', 'r', encoding='utf-8') as f:
            self.lines = [line.strip() for line in f.readlines()]
        self.data = [self.parse_line(i, line) for i, line in enumerate(self.lines)]
        self.graph = networkx.Graph()
        self.build_graph()

    def parse_line(self, i: int, line: str):
        name, children = line.split(': ')
        ret = {
            "name": name,
            "children": children.split(' ')
        }
        return ret

    def build_graph(self):
        for line in self.data:
            self.graph.add_node((line['name']))

        for line in self.data:
            for child in line['children']:
                self.graph.add_edge(line['name'], child)

    def run(self):
        total = 0
        for (a, b) in networkx.minimum_edge_cut(self.graph):
            self.graph.remove_edge(a, b)
        for c in networkx.connected_components(self.graph):
            print(len(c))

        return total


if __name__ == '__main__':
    print(Solver().run())

module Main (main) where

import qualified Data.Set as Set
import Data.Set (Set)
import qualified Data.Map as Map
import Data.Map (Map, (!))
import AOCTools (splitOn)
import Data.List (partition)

main :: IO ()
main = do
    input <- readFile "./input.txt"
    putStrLn $ "Part 1: " ++ show (solve1 $ parseInput input)

type Node = String
type Graph = Map Node (Set Node)

parseInput :: String -> Graph
parseInput str = foldr parseLine Map.empty (lines str)

parseLine :: String -> Graph -> Graph
parseLine str graph = graph' where
    (node, xs) = splitOn ": " str
    nodes = words xs
    graph' = foldr addEdge graph [(node, n) | n <- nodes]

addEdge :: (Node, Node) -> Graph -> Graph
addEdge (n1, n2) graph
    | Map.notMember n1 graph = addEdge (n1, n2) $ Map.insert n1 Set.empty graph
    | Map.notMember n2 graph = addEdge (n1, n2) $ Map.insert n2 Set.empty graph
    | otherwise = Map.adjust (Set.insert n1) n2 $ Map.adjust (Set.insert n2) n1 graph

removeEdge :: (Node, Node) -> Graph -> Graph
removeEdge (n1, n2) graph = Map.adjust (Set.delete n1) n2 $ Map.adjust (Set.delete n2) n1 graph

neighbors :: Graph -> Node -> [Node]
neighbors graph n = Set.toList $ graph ! n

solve1 :: Graph -> Int
solve1 graph = length a * (length b + 1) where
    testNode:nodes = Map.keys graph
    (a, b) = partition (\n -> maxFlow graph testNode n == 3) nodes

maxFlow :: Graph -> Node -> Node -> Int
maxFlow graph n1 n2 = case findPath graph n1 n2 of
    Nothing -> 0
    Just path -> 1 + maxFlow graph' n1 n2 where
        graph' = foldr removeEdge graph path

findPath :: Graph -> Node -> Node -> Maybe [(Node, Node)]
findPath graph n1 n2 = djikstra [n1] (Map.singleton n1 n1) where
    djikstra :: [Node] -> Map Node Node -> Maybe [(Node, Node)]
    djikstra [] _ = Nothing
    djikstra (n:queue) prev
        | n == n2 = Just $ reverse (buildPath prev n)
        | otherwise = djikstra (queue ++ neighborNodes) prev' where
            neighborNodes = filter (`Map.notMember` prev) $ neighbors graph n
            prev' = foldr (`Map.insert` n) prev neighborNodes
    buildPath :: Map Node Node -> Node -> [(Node, Node)]
    buildPath prev node
        | pNode == node = []
        | otherwise = (pNode, node) : buildPath prev pNode where
            pNode = prev ! node

# Advent of Code 2023
# Day 25: Snowverload

import networkx

graph = {}

with open("inputs/day_25.txt") as file:
    for line in file:
        component = line[:3]

        if component in graph:
            graph[component].update(set(line[5:].rstrip("\n").split(" ")))
        else:
            graph[component] = set(line[5:].rstrip("\n").split(" "))

        for other in graph[component]:
            if other not in graph:
                graph[other] = set([component])
            else:
                graph[other].add(component)

to_remove = tuple(networkx.minimum_edge_cut(networkx.from_dict_of_lists(graph)))

for edge in to_remove:
    graph[edge[0]].remove(edge[1])
    graph[edge[1]].remove(edge[0])

product = 1

for edge in to_remove[0]:
    queue = [edge]
    seen = set()

    while queue:
        current = queue.pop(0)

        for next_ in graph[current]:
            if next_ not in seen:
                queue.append(next_)
                seen.add(next_)

    product *= len(seen)

print(f"Part 1: {product}")