Rust code shared from the playground

playground.rs

use std::cmp::max;
use std::collections::{HashMap, HashSet};
use std::iter;

const _SAMPLE_INPUT: &str = "\
0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10\
";

const _REAL_INPUT: &str = "\
31/13
34/4
49/49
23/37
47/45
32/4
12/35
37/30
41/48
0/47
32/30
12/5
37/31
7/41
10/28
35/4
28/35
20/29
32/20
31/43
48/14
10/11
27/6
9/24
8/28
45/48
8/1
16/19
45/45
0/4
29/33
2/5
33/9
11/7
32/10
44/1
40/32
2/45
16/16
1/18
38/36
34/24
39/44
32/37
26/46
25/33
9/10
0/29
38/8
33/33
49/19
18/20
49/39
18/39
26/13
19/32\
";

const INPUT: &str = _REAL_INPUT;

type ComponentId = usize;

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct Half {
    component_id: ComponentId,
    half_id: usize, // 0 or 1
}

impl Half {
    fn opposite(self) -> Self {
        Half {
            component_id: self.component_id,
            half_id: 1 - self.half_id,
        }
    }
}

/// Returns `(length, strength)`.
fn best_from_half(
    half: Half,
    seen: &mut HashSet<ComponentId>,
    edges: &HashMap<Half, Vec<Half>>,
    components: &Vec<[u64; 2]>,
) -> (usize, u64) {
    assert!(seen.insert(half.component_id));
    
    let mut best = (0, 0);
    
    for &other_half in &edges[&half.opposite()] {
        if seen.contains(&other_half.component_id) { continue; }
        best = max(
            best,
            best_from_half(other_half, seen, edges, components),
        );
        seen.remove(&other_half.component_id);
    }
    
    /*
    let strongest_edge = edges
        .get(&half)
        .unwrap()
        .iter()
        .filter(|other_half| !seen.contains(&other_half.component_id))
        .map(|&other_half| {
            strongest_from_half(other_half, seen, edges, components)
        })
        .max()
        .unwrap_or(0);
    */
        
    (
        best.0 + 1,
        best.1 + components[half.component_id].iter().cloned().sum::<u64>(),
    )
}

fn main() {
    let components: Vec<[u64; 2]> = INPUT
        .split('\n')
        .map(|line| {
            let mut parts = line.split('/').map(|n| n.parse::<u64>().unwrap());
            [parts.next().unwrap(), parts.next().unwrap()]
        })
        .collect();
        
    let halves: Vec<(Half, u64)> = components
        .iter()
        .enumerate()
        .flat_map(|(i, neighbor)| {
            iter::once(i)
                .cycle()
                .zip(neighbor.iter().cloned().enumerate())
                .map(|(component_id, (half_id, val))| {
                    (Half { component_id, half_id }, val)
                })
        })
        .collect();
        
    let mut edges: HashMap<Half, Vec<Half>> = HashMap::new();
    
    for &(half, val) in &halves {
        let neighbors = edges.entry(half).or_insert(Vec::new());
        for &(other_half, other_val) in &halves {
            if other_half.component_id == half.component_id { continue; }
            if val == other_val {
                neighbors.push(other_half);
            }
        }
    }
    
    // println!("{:#?}", edges);
    
    let starts = halves
        .iter()
        .filter(|&&(_, val)| val == 0)
        .map(|&(half, _)| half);
        
    let strongest = starts.map(|starting_half| {
        let mut seen = HashSet::new();
        best_from_half(starting_half, &mut seen, &edges, &components)
    }).max().unwrap();
    
    println!("{:?}", strongest);
}