bwc9876.dev
Advent of Code solutions
1use std::collections::{HashMap, HashSet};
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
5
6pub struct Day23;
7
8type Edges = HashMap<String, HashSet<String>>;
9
10fn find_self_in_3<'a>(node: &'a String, edges: &'a Edges) -> Vec<[&'a String; 3]> {
11 edges
12 .get(node)
13 .unwrap()
14 .iter()
15 .flat_map(|adj| {
16 edges.get(adj).unwrap().iter().filter_map(|sadj| {
17 if edges.get(sadj).unwrap().contains(node) {
18 let mut v = [node, adj, sadj];
19 v.sort();
20 Some(v)
21 } else {
22 None
23 }
24 })
25 })
26 .collect()
27}
28
29fn represent<'a>(
30 node: &'a String,
31 friends: HashSet<&'a String>,
32 edges: &'a Edges,
33 size: usize,
34 seen: &mut HashSet<&'a String>,
35) -> Option<HashSet<&'a String>> {
36 if friends.len() == size {
37 return Some(friends);
38 } else if friends.iter().all(|f| seen.contains(f)) {
39 return None;
40 }
41
42 seen.insert(node);
43
44 edges.get(node).unwrap().iter().find_map(|dep| {
45 if edges
46 .get(dep)
47 .is_some_and(|e| friends.iter().all(|f| e.contains(*f)))
48 {
49 let mut new_friends = friends.clone();
50 new_friends.insert(dep);
51 represent(dep, new_friends, edges, size, seen)
52 } else {
53 None
54 }
55 })
56}
57
58impl Day for Day23 {
59 day_stuff!(23, "7", "co,de,ka,ta", Edges);
60
61 fn part_1(input: Self::Input) -> Option<String> {
62 let groups = input
63 .keys()
64 .flat_map(|k| find_self_in_3(k, &input))
65 .collect::<HashSet<_>>();
66
67 let ans = groups
68 .into_iter()
69 .filter(|g| g.iter().any(|c| c.starts_with('t')))
70 .count();
71
72 Some(ans.to_string())
73 }
74
75 fn part_2(input: Self::Input) -> Option<String> {
76 let verts = input.keys().cloned().collect::<Vec<_>>();
77 let max_group_size = verts
78 .iter()
79 .map(|v| input.get(v).unwrap().len())
80 .max()
81 .unwrap()
82 + 1;
83
84 let mut group = (0..max_group_size)
85 .rev()
86 .find_map(|s| {
87 verts.par_iter().find_map_any(|node| {
88 represent(
89 node,
90 HashSet::from_iter([node]),
91 &input,
92 s,
93 &mut HashSet::with_capacity(s),
94 )
95 })
96 })
97 .unwrap()
98 .into_iter()
99 .collect::<Vec<_>>();
100
101 group.sort();
102 let len = group.len();
103 let s = ",".to_string();
104 Some(group.into_iter().intersperse(&s).fold(
105 String::with_capacity(len * 2 + (len - 1)),
106 |mut acc, computer| {
107 acc.push_str(computer.as_str());
108 acc
109 },
110 ))
111 }
112
113 fn parse_input(input: &str) -> Self::Input {
114 input
115 .lines()
116 .fold(HashMap::with_capacity(50), |mut acc, l| {
117 let (l, r) = l.split_once('-').unwrap();
118 acc.entry(l.to_string())
119 .or_insert(HashSet::new())
120 .insert(r.to_string());
121 acc.entry(r.to_string())
122 .or_insert(HashSet::new())
123 .insert(l.to_string());
124 acc
125 })
126 }
127}