use std::{
    cmp::PartialEq,
    iter::Sum,
    ops::{Add, Sub},
};

pub fn brutal<T>(arr: &[T]) -> Option<usize>
where
    T: for<'a> Sum<&'a T>
        + for<'a> Sub<&'a T, Output = T>
        + for<'a> Add<&'a T, Output = T>
        + PartialEq
        + Copy,
{
    let sum: T = arr.iter().sum();

    let x = arr
        .iter()
        .enumerate()
        .try_fold((sum - &sum, sum), |(left, right), (idx, x)| {
            if left == right - x {
                Err(idx)
            } else {
                Ok((left + x, right - x))
            }
        });

    x.err()
}

#[cfg(test)]
mod tests {
    use super::*;
    use test_case::test_case;

    #[test_case(&[1, 1, 1, 2],  2)]
    #[test_case(&[1, 2, 3, 6, 3, 3],  3)]
    #[test_case(&[0, 1, 0],  1)]
    #[test_case(&[0, 0, 0],  0)]
    #[test_case(&[4, 1000, 1, 1, 1, 1],  1)]
    fn test_some(arr: &[usize], expected_idx: usize) {
        let idx = brutal(arr);

        assert_eq!(idx, Some(expected_idx));
    }

    #[test_case(&[4, 1000, 1, 10, 1, 1])]
    #[test_case(&[1, 2, 3, 4, 5])]
    fn test_none(arr: &[u32]) {
        let idx = brutal(arr);

        assert_eq!(idx, None);
    }
}