Day 23: LAN Party

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • eco_game@discuss.tchncs.de
    link
    fedilink
    arrow-up
    2
    ·
    3 hours ago

    Kotlin

    Part1 was pretty simple, just check all neighbors of a node for overlap, then filter out triples which don’t have nodes beginning with ‘t’.

    For part2, I seem to have picked a completely different strategy to everyone else. I was a bit lost, then just boldly assumed, that if I take overlap of all triples with 1 equal node, I might be able to find the answer that way. To my surprise, this worked for my input. I’d be very curious to know if I just got lucky or if the puzzle is designed to work with this approach.

    The full code is also on GitHub.

    Solution
    class Day23 : Puzzle {
    
        private val connections = ArrayList<Pair<String, String>>()
    
        private val tripleCache = HashSet<Triple<String, String, String>>()
    
        override fun readFile() {
            val input = readInputFromFile("src/main/resources/day23.txt")
            for (line in input.lines()) {
                val parts = line.split("-")
                connections.add(Pair(parts[0], parts[1]))
            }
        }
    
        override fun solvePartOne(): String {
            val triples = getConnectionTriples(connections)
            tripleCache.addAll(triples) // for part 2
            val res = triples.count { it.first.startsWith("t") || it.second.startsWith("t") || it.third.startsWith("t") }
            return res.toString()
        }
    
        private fun getConnectionTriples(connectionList: List<Pair<String, String>>): List<Triple<String, String, String>> {
            val triples = ArrayList<Triple<String, String, String>>()
            for (connection in connectionList) {
                val connectionListTemp = getAllConnections(connection.first, connectionList)
                for (i in connectionListTemp.indices) {
                    for (j in i + 1 until connectionListTemp.size) {
                        val con1 = connectionListTemp[i]
                        val con2 = connectionListTemp[j]
                        if (Pair(con1, con2) in connectionList || Pair(con2, con1) in connectionList) {
                            val tripleList = mutableListOf(connection.first, con1, con2)
                            tripleList.sort()
                            triples.add(Triple(tripleList[0], tripleList[1], tripleList[2]))
                        }
                    }
                }
            }
            return triples.distinct()
        }
    
        private fun getAllConnections(connection: String, connectionList: List<Pair<String, String>>): List<String> {
            val res = HashSet<String>()
            for (entry in connectionList) {
                when (connection) {
                    entry.first -> res.add(entry.second)
                    entry.second -> res.add(entry.first)
                }
            }
            return res.toList()
        }
    
        override fun solvePartTwo(): String {
            val pools = getPools(connections)
            println(pools)
            val res = pools.maxByOrNull { it.size }!!
            return res.joinToString(",")
        }
    
        // will get all pools with a minimum size of 4
        // this method makes some naive assumptions, but works for the example and my puzzle input
        private fun getPools(connectionList: List<Pair<String, String>>): List<List<String>> {
            val pools = ArrayList<List<String>>()
            val triples = tripleCache
            val nodes = connectionList.map { listOf(it.first, it.second) }.flatten().toHashSet()
    
            for (node in nodes) {
                val contenders = triples.filter { it.first == node || it.second == node || it.third == node }
                if (contenders.size < 2) continue // expect the minimum result to be 4, for efficiency
    
                // if *all* nodes within *all* triples are interconnected, add to pool
                // this may not work for all inputs!
                val contenderList = contenders.map { listOf(it.first, it.second, it.third) }.flatten().distinct()
                if (checkAllConnections(contenderList, connectionList)) {
                    pools.add(contenderList.sorted())
                }
            }
    
            return pools.distinct()
        }
    
        private fun checkAllConnections(pool: List<String>, connectionList: List<Pair<String, String>>): Boolean {
            for (i in pool.indices) {
                for (j in i + 1 until pool.size) {
                    val con1 = pool[i]
                    val con2 = pool[j]
                    if (Pair(con1, con2) !in connectionList && Pair(con2, con1) !in connectionList) {
                        return false
                    }
                }
            }
            return true
        }
    }
    
    • lwhjp@lemmy.sdf.org
      link
      fedilink
      arrow-up
      1
      ·
      2 hours ago

      That’s a fun approach. The largest totally connected group will of course contain overlapping triples, so I think you’re effectively doing the same thing as checking a node at a time, just more efficiently.

  • VegOwOtenks@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    6 hours ago

    Haskell

    The solution for part two could now be used for part one as well but then I would have to rewrite part 1 .-.

    import Control.Arrow
    
    import Data.Ord (comparing)
    
    import qualified Data.List as List
    import qualified Data.Map as Map
    import qualified Data.Set as Set
    
    parse = Map.fromListWith Set.union . List.map (second Set.singleton) . uncurry (++) . (id &&& List.map (uncurry (flip (,)))) . map (break (== '-') >>> second (drop 1)) . takeWhile (/= "") . lines
    
    depthSearch connections ps
            | length ps == 4 && head ps == last ps = [ps]
            | length ps == 4 = []
            | otherwise  = head
                    >>> (connections Map.!)
                    >>> Set.toList
                    >>> List.map (:ps)
                    >>> List.concatMap (depthSearch connections)
                    $ ps
    
    interconnections (computer, connections) = depthSearch connections [computer]
    
    part1 = (Map.assocs &&& repeat)
            >>> first (List.map (uncurry Set.insert))
            >>> first (Set.toList . Set.unions)
            >>> uncurry zip
            >>> List.concatMap interconnections
            >>> List.map (Set.fromList . take 3)
            >>> List.filter (Set.fold (List.head >>> (== 't') >>> (||)) False)
            >>> Set.fromList
            >>> Set.size
    
    getLANParty computer connections = (connections Map.!)
            >>> findLanPartyComponent connections [computer]
            $ computer
    
    filterCandidates connections participants candidates = List.map (connections Map.!)
            >>> List.foldl Set.intersection candidates
            >>> Set.filter ((connections Map.!) >>> \ s -> List.all (flip Set.member s) participants)
            $ participants
    
    findLanPartyComponent connections participants candidates
            | Set.null validParticipants = participants
            | otherwise = findLanPartyComponent connections (nextParticipant : participants) (Set.delete nextParticipant candidates)
            where
                    nextParticipant = Set.findMin validParticipants
                    validParticipants = filterCandidates connections participants candidates
    
    part2 = (Map.keys &&& repeat)
            >>> uncurry zip
            >>> List.map ((uncurry getLANParty) >>> List.sort)
            >>> List.nub
            >>> List.maximumBy (comparing List.length)
            >>> List.intercalate ","
    
    main = getContents
            >>= print
            . (part1 &&& part2)
            . parse
    
    • lwhjp@lemmy.sdf.org
      link
      fedilink
      arrow-up
      2
      ·
      5 hours ago

      The solution for part two could now be used for part one as well but then I would have to rewrite part 1 .-.

      I initially thought that, but now I reconsider I’m not so sure. Isn’t it possible to have a 3-member clique overlapping two larger ones? In other words, there could be more than one way to partition the graph into completely connected components. Which means my solution to part 2 is technically incorrect. Bummer.

      • VegOwOtenks@lemmy.world
        link
        fedilink
        arrow-up
        1
        ·
        46 minutes ago

        There probably are multiple ways to partition the graph. I haven’t applied any optimizations and my program checks members of already detected groups again, would that yield all possible partitions because I choose all the possible starting points for a k-clique?

  • Gobbel2000
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    7 hours ago

    Rust

    Finding cliques in a graph, which is actually NP-comlete. For part two I did look up how to do it and implemented the Bron-Kerbosch algorithm. Adding the pivoting optimization improved the runtime from 134ms to 7.4ms, so that is definitely worth it (in some sense, of course I already had the correct answer without pivoting).

    Solution
    use rustc_hash::{FxHashMap, FxHashSet};
    
    fn parse(input: &str) -> (Vec<Vec<usize>>, FxHashMap<&str, usize>) {
        let mut graph = Vec::new();
        let mut names: FxHashMap<&str, usize> = FxHashMap::default();
        for l in input.lines() {
            let (vs, ws) = l.split_once('-').unwrap();
            let v = *names.entry(vs).or_insert_with(|| {
                graph.push(vec![]);
                graph.len() - 1
            });
            let w = *names.entry(ws).or_insert_with(|| {
                graph.push(vec![]);
                graph.len() - 1
            });
            graph[v].push(w);
            graph[w].push(v);
        }
        (graph, names)
    }
    
    fn part1(input: String) {
        let (graph, names) = parse(&input);
        let mut triples: FxHashSet<[usize; 3]> = FxHashSet::default();
        for (_, &v) in names.iter().filter(|(name, _)| name.starts_with('t')) {
            for (i, &u) in graph[v].iter().enumerate().skip(1) {
                for w in graph[v].iter().take(i) {
                    if graph[u].contains(w) {
                        let mut triple = [u, v, *w];
                        triple.sort();
                        triples.insert(triple);
                    }
                }
            }
        }
        println!("{}", triples.len());
    }
    
    // Bron-Kerbosch algorithm for finding all maximal cliques in a graph
    fn bron_kerbosch(
        graph: &[Vec<usize>],
        r: &mut Vec<usize>,
        mut p: FxHashSet<usize>,
        mut x: FxHashSet<usize>,
    ) -> Vec<Vec<usize>> {
        if p.is_empty() && x.is_empty() {
            return vec![r.to_vec()];
        }
        let mut maximal_cliques = Vec::new();
        let Some(&u) = p.iter().next() else {
            return maximal_cliques;
        };
        let mut p_pivot = p.clone();
        for w in &graph[u] {
            p_pivot.remove(w);
        }
        for v in p_pivot {
            let pn = graph[v].iter().filter(|w| p.contains(w)).copied().collect();
            let xn = graph[v].iter().filter(|w| x.contains(w)).copied().collect();
            r.push(v);
            let new_cliques = bron_kerbosch(graph, r, pn, xn);
            r.pop();
            maximal_cliques.extend(new_cliques);
            p.remove(&v);
            x.insert(v);
        }
        maximal_cliques
    }
    
    fn part2(input: String) {
        let (graph, names) = parse(&input);
        let p = (0..graph.len()).collect();
        let mut r = Vec::new();
        let maximal_cliques = bron_kerbosch(&graph, &mut r, p, FxHashSet::default());
        let maximum_clique = maximal_cliques
            .iter()
            .max_by_key(|clique| clique.len())
            .unwrap();
        let mut lan_names: Vec<&str> = names
            .iter()
            .filter(|(_, v)| maximum_clique.contains(v))
            .map(|(name, _)| *name)
            .collect();
        lan_names.sort_unstable();
        println!("{}", lan_names.join(","));
    }
    
    util::aoc_main!();
    

    Also on github

  • lwhjp@lemmy.sdf.org
    link
    fedilink
    arrow-up
    2
    arrow-down
    1
    ·
    7 hours ago

    Haskell

    I was expecting a very difficult graph theory problem at first glance, but this one was actually pretty easy too!

    import Data.Bifunctor
    import Data.List
    import Data.Ord
    import Data.Set qualified as Set
    
    views :: [a] -> [(a, [a])]
    views [] = []
    views (x : xs) = (x, xs) : (second (x :) <$> views xs)
    
    choose :: Int -> [a] -> [[a]]
    choose 0 _ = [[]]
    choose _ [] = []
    choose n (x : xs) = ((x :) <$> choose (n - 1) xs) ++ choose n xs
    
    removeConnectedGroup connected = fmap (uncurry go . first Set.singleton) . Set.minView
      where
        go group hosts =
          maybe
            (group, hosts)
            (\h -> go (Set.insert h group) (Set.delete h hosts))
            $ find (flip all group . connected) hosts
    
    main = do
      net <- Set.fromList . map (second tail . break (== '-')) . lines <$> readFile "input23"
      let hosts = Set.fromList $ [fst, snd] <*> Set.elems net
          connected a b = any (`Set.member` net) [(a, b), (b, a)]
          complete = all (uncurry $ all . connected) . views
      print
        . length
        . filter complete
        . filter (any ((== 't') . head))
        $ choose 3 (Set.elems hosts)
      putStrLn
        . (intercalate "," . Set.toAscList)
        . maximumBy (comparing Set.size)
        . unfoldr (removeConnectedGroup connected)
        $ hosts
    ``