Ancestors

Toot

Written by CameronDev@programming.dev on 2024-12-23 at 05:24

💻 - 2024 DAY 23 SOLUTIONS -💻

https://programming.dev/post/23198319

=> More informations about this toot | More toots from CameronDev@programming.dev

Descendants

Written by CameronDev@programming.dev on 2024-12-23 at 22:59

Rust

Part2 works, and is fast enough, but still feels kinda gross. No idea if this is a known algorithm or not.

mod tests {

use std::collections::HashMap;

#[test]

fn day23_part1_test() {

    let input = std::fs::read_to_string("src/input/day_23.txt").unwrap();

    let links = input

        .lines()

        .map(|l| l.split_once('-').unwrap())

        .collect::<Vec<(&str, &str)>>();

    let mut peer_map = HashMap::new();

    for pair in links {

        peer_map.entry(pair.0).or_insert(Vec::new()).push(pair.1);

        peer_map.entry(pair.1).or_insert(Vec::new()).push(pair.0);

    }

    let mut rings = vec![];

    for (pc, peers) in &peer_map {

        if !pc.starts_with('t') {

            continue;

        }

        for (i, first) in peers.iter().enumerate() {

            for second in peers[i..].iter() {

                if first == second {

                    continue;

                }

                if !peer_map.get(first).unwrap().contains(second) {

                    continue;

                }

                let mut set = vec![pc, second, first];

                set.sort();

                if !rings.contains(&set) {

                    rings.push(set);

                }

            }

        }

    }

    println!("{}", rings.len());

}

#[test]

fn day23_part2_test() {

    let input = std::fs::read_to_string("src/input/day_23.txt").unwrap();

    let links = input

        .lines()

        .map(|l| l.split_once('-').unwrap())

        .collect::<Vec<(&str, &str)>>();

    let mut peer_map = HashMap::new();

    for pair in links {

        let p1 = peer_map.entry(pair.0).or_insert(Vec::new());

        if !p1.contains(&pair.1) {

            p1.push(pair.1);

        }

        let p2 = peer_map.entry(pair.1).or_insert(Vec::new());

        if !p2.contains(&pair.0) {

            p2.push(pair.0);

        }

    }

    let mut biggest_network = String::new();

    for (pc, peers) in &peer_map {

        let mut network = HashMap::new();

        network.insert(pc, peers.len());

        for first in peers {

            let mut total = 1;

            for second in peers.iter() {

                if first == second {

                    continue;

                }

                if peer_map.get(first).unwrap().contains(second) {

                    total += 1;

                }

            }

            network.insert(first, total);

        }

        let mut network_size = peers.len();

        loop {

            if network_size == 0 {

                break;

            }

            let mut out = network

                .iter()

                .filter_map(|(k, v)| {

                    if v >= &network_size {

                        return Some(**k);

                    }

                    None

                })

                .collect::<Vec<_>>();

            if out.len() == network_size + 1 {

                out.sort();

                let pw = out.join(",");

                // println!("{}", pw);

                if pw.len() > biggest_network.len() {

                    biggest_network = pw;

                }

                break;

            }

            network_size -= 1;

        }

    }

    println!("{}", biggest_network);

}

}

=> More informations about this toot | More toots from CameronDev@programming.dev

Written by lwhjp on 2024-12-23 at 06:28

Haskell

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

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