adventofcode

commit

579058de161dc8383f62df63e3193bc5c815ef26

parent

d11f75e5744512cf0d41774c9e66a74d4efc7016

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2024-12-23 10:58

perf: restrict search to neighbors

for some reason using the neighbors of a single stack entry was faster
than intersecting the neighbors of all stack entries.

Diffstat

1 files changed, 25 insertions, 12 deletions

diff --git a/2024/23/solution.rs b/2024/23/solution.rs

@@ -21,8 +21,11 @@ fn parse_input() -> (Vec<String>, Vec<HashSet<usize>>) {
   21    21         let (name1, name2) = line.split_once('-').unwrap();
   22    22         let i1 = insert_node(name1, &mut names, &mut connections);
   23    23         let i2 = insert_node(name2, &mut names, &mut connections);
   24    -1         connections[i1].insert(i2);
   25    -1         connections[i2].insert(i1);
   -1    24         if i1 < i2 {
   -1    25             connections[i1].insert(i2);
   -1    26         } else {
   -1    27             connections[i2].insert(i1);
   -1    28         }
   26    29     }
   27    30 
   28    31     return (names, connections);
@@ -31,21 +34,31 @@ fn parse_input() -> (Vec<String>, Vec<HashSet<usize>>) {
   31    34 fn visit(stack: &mut Vec<usize>, names: &Vec<String>, connections: &Vec<HashSet<usize>>) -> (usize, Vec<usize>) {
   32    35     let mut part1 = 0;
   33    36     let mut part2 = stack.clone();
   -1    37 
   34    38     if stack.len() == 3 && stack.iter().any(|j| names[*j].starts_with('t')) {
   35    39         part1 += 1;
   36    40     }
   37    -1     let start = *stack.last().unwrap_or(&0);
   38    -1     for i in start..connections.len() {
   39    -1         if stack.iter().all(|j| connections[i].contains(j)) {
   40    -1             stack.push(i);
   41    -1             let (tmp1, tmp2) = visit(stack, names, connections);
   42    -1             part1 += tmp1;
   43    -1             if tmp2.len() > part2.len() {
   44    -1                 part2 = tmp2;
   45    -1             }
   46    -1             stack.pop();
   -1    41 
   -1    42     let mut potential: Vec<usize> = vec![];
   -1    43     if let Some(&l) = stack.last() {
   -1    44         potential.extend(&connections[l]);
   -1    45     } else {
   -1    46         potential.extend(0..connections.len());
   -1    47     };
   -1    48     for i in potential {
   -1    49         if !stack.iter().all(|j| connections[*j].contains(&i)) {
   -1    50             continue;
   47    51         }
   -1    52 
   -1    53         stack.push(i);
   -1    54         let (tmp1, tmp2) = visit(stack, names, connections);
   -1    55         part1 += tmp1;
   -1    56         if tmp2.len() > part2.len() {
   -1    57             part2 = tmp2;
   -1    58         }
   -1    59         stack.pop();
   48    60     }
   -1    61 
   49    62     return (part1, part2);
   50    63 }
   51    64