4005027531

Build Type

github

Committed by GitHub

Commit Message

Merge 74f46dcbf into 0e0e3157b

Pull Request Pull Request #19: Updated versions

Run Details

2556 of 3992 branches covered (64.03%)

Branch coverage included in aggregate %.

1560 of 1560 new or added lines in 44 files covered. (100.0%)

5981 of 6247 relevant lines covered (95.74%)

624811.64 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.8

/adv2015/src/day24.rs

use combinations::Combinations;
use std::cmp::min;

pub fn find_answer(input: &str) -> usize {
    let packages = parse_packages(input);
    let weight = packages.iter().sum::<usize>() / 3;

    find_optimal_qe(&packages, weight)
}

pub fn find_answer_better(input: &str) -> usize {
    let packages = parse_packages(input);
    let weight = packages.iter().sum::<usize>() / 4;

    find_optimal_qe(&packages, weight)
}

fn find_optimal_qe(packages: &Vec<usize>, weight: usize) -> usize {
    let mut lowest_qe = usize::MAX;
    let mut lowest_count = usize::MAX;

    let sleigh = SleighCombination::new(&packages, weight);

    for group in sleigh {
        for filtered_group in group {
            let current_qe = calc_qe(&filtered_group);
            let current_count = filtered_group.len();

            if (lowest_qe == usize::MAX && lowest_count == usize::MAX)
                || (current_count < lowest_count && current_qe < lowest_qe)
            {
                let rest_packages = subtract_vectors(packages, &filtered_group);

                if group_with_weight_exists(&rest_packages, weight) {
                    lowest_qe = min(lowest_qe, current_qe);
                    lowest_count = min(lowest_count, current_count);
                }
            }
        }

        if lowest_qe != usize::MAX {
            return lowest_qe;
        }
    }

    lowest_qe
}

fn parse_packages(input: &str) -> Vec<usize> {
    input
        .lines()
        .map(|l| l.trim())
        .filter(|l| !l.is_empty())
        .filter_map(|p| p.parse::<usize>().ok())
        .collect()
}

struct SleighCombination {
    size: usize,
    packages: Vec<usize>,
    weight: usize,
}

impl SleighCombination {
    fn new(packages: &Vec<usize>, weight: usize) -> SleighCombination {
        let copy_packages = packages.to_vec();

        SleighCombination {
            size: 0,
            weight,
            packages: copy_packages,
        }
    }
}

impl Iterator for SleighCombination {
    type Item = Box<dyn Iterator<Item = Vec<usize>>>;

    fn next(&mut self) -> Option<Self::Item> {
        self.size += 1;

        if self.size == self.packages.len() || self.packages.is_empty() {
            return None;
        }

        let copy_packages = self.packages.to_vec();
        let copy_weight = self.weight.clone();
        Some(Box::new(
            Combinations::new(copy_packages, self.size)
                .filter(move |group| group.iter().sum::<usize>() == copy_weight),
        ))
    }
}

fn group_with_weight_exists(packages: &Vec<usize>, weight: usize) -> bool {
    for size in 1..packages.len() {
        let copy_packages = packages.to_vec();

        if Combinations::new(copy_packages, size)
            .any(|packages| packages.iter().sum::<usize>() == weight)
        {
            return true;
        }
    }

    false
}

// quantum entanglement
fn calc_qe(group: &Vec<usize>) -> usize {
    group.iter().fold(1, |acc, p| acc * p)
}

fn subtract_vectors(from: &Vec<usize>, rhs: &Vec<usize>) -> Vec<usize> {
    let mut result = Vec::new();

    result.extend(from.iter().filter(|i| !rhs.contains(i)));

    result
}

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

    #[test]
    fn test_parse_packages() {
        let packages = parse_packages(
            r#"1
        2

        6"#,
        );
        assert_eq!(packages.len(), 3);
        assert_eq!(packages[0], 1);
        assert_eq!(packages[1], 2);
        assert_eq!(packages[2], 6);
    }

    #[test]
    fn test_calc_qe() {
        assert_eq!(calc_qe(&vec![11, 9]), 99);
        assert_eq!(calc_qe(&vec![10, 4, 3, 2, 1]), 240);
    }

    #[test]
    fn test_subtract_vectors() {
        let packages: Vec<usize> = vec![1, 2, 3, 4, 5, 7, 8, 9, 10, 11];
        let result = subtract_vectors(&packages, &vec![10, 4, 3, 2, 1]);
        assert_eq!(result.len(), 5);
        assert!(result.contains(&5));
        assert!(result.contains(&7));
        assert!(result.contains(&8));
        assert!(result.contains(&9));
        assert!(result.contains(&11));
    }

    #[test]
    fn test_find_optimal_qe() {
        let packages: Vec<usize> = vec![1, 2, 3, 4, 5, 7, 8, 9, 10, 11];
        assert_eq!(
            find_optimal_qe(&packages, packages.iter().sum::<usize>() / 3),
            99
        );
    }
}

1	use combinations::Combinations;
2	use std::cmp::min;
3
4	pub fn find_answer(input: &str) -> usize {	1✔
5	let packages = parse_packages(input);	1✔
6	let weight = packages.iter().sum::<usize>() / 3;	1✔
7
8	find_optimal_qe(&packages, weight)	1✔
9	}	1✔
10
11	pub fn find_answer_better(input: &str) -> usize {	1✔
12	let packages = parse_packages(input);	1✔
13	let weight = packages.iter().sum::<usize>() / 4;	1✔
14
15	find_optimal_qe(&packages, weight)	1✔
16	}	1✔
17
18	fn find_optimal_qe(packages: &Vec<usize>, weight: usize) -> usize {	3✔
19	let mut lowest_qe = usize::MAX;	3✔
20	let mut lowest_count = usize::MAX;	3✔
21
22	let sleigh = SleighCombination::new(&packages, weight);	3✔
23
24	for group in sleigh {	5✔
25	for filtered_group in group {	3✔
26	let current_qe = calc_qe(&filtered_group);	1✔
27	let current_count = filtered_group.len();	1✔
28
29	if (lowest_qe == usize::MAX && lowest_count == usize::MAX)	1!
30	\|\| (current_count < lowest_count && current_qe < lowest_qe)	×
31	{
32	let rest_packages = subtract_vectors(packages, &filtered_group);	1✔
33
34	if group_with_weight_exists(&rest_packages, weight) {	1!
35	lowest_qe = min(lowest_qe, current_qe);	1✔
36	lowest_count = min(lowest_count, current_count);	1✔
37	}
38	}	1✔
39	}	1✔
40
41	if lowest_qe != usize::MAX {	2✔
42	return lowest_qe;	1✔
43	}
44	}
45
46	lowest_qe	2✔
47	}	3✔
48
49	fn parse_packages(input: &str) -> Vec<usize> {	3✔
50	input	3✔
51	.lines()
52	.map(\|l\| l.trim())	4✔
53	.filter(\|l\| !l.is_empty())	4✔
54	.filter_map(\|p\| p.parse::<usize>().ok())	3✔
55	.collect()
56	}	3✔
57
58	struct SleighCombination {
59	size: usize,
60	packages: Vec<usize>,
61	weight: usize,
62	}
63
64	impl SleighCombination {
65	fn new(packages: &Vec<usize>, weight: usize) -> SleighCombination {	3✔
66	let copy_packages = packages.to_vec();	3✔
67
68	SleighCombination {	3✔
69	size: 0,
70	weight,
71	packages: copy_packages,	3✔
72	}
73	}	3✔
74	}
75
76	impl Iterator for SleighCombination {
77	type Item = Box<dyn Iterator<Item = Vec<usize>>>;
78
79	fn next(&mut self) -> Option<Self::Item> {	4✔
80	self.size += 1;	4✔
81
82	if self.size == self.packages.len() \|\| self.packages.is_empty() {	4!
83	return None;	2✔
84	}
85
86	let copy_packages = self.packages.to_vec();	2✔
87	let copy_weight = self.weight.clone();	2✔
88	Some(Box::new(	2✔
89	Combinations::new(copy_packages, self.size)	4✔
90	.filter(move \|group\| group.iter().sum::<usize>() == copy_weight),	57✔
91	))
92	}	4✔
93	}
94
95	fn group_with_weight_exists(packages: &Vec<usize>, weight: usize) -> bool {	1✔
96	for size in 1..packages.len() {	3!
97	let copy_packages = packages.to_vec();	3✔
98
99	if Combinations::new(copy_packages, size)	9✔
100	.any(\|packages\| packages.iter().sum::<usize>() == weight)	78✔
101	{
102	return true;	1✔
103	}
104	}
105
106	false	×
107	}	1✔
108
109	// quantum entanglement
110	fn calc_qe(group: &Vec<usize>) -> usize {	3✔
111	group.iter().fold(1, \|acc, p\| acc * p)	12✔
112	}	3✔
113
114	fn subtract_vectors(from: &Vec<usize>, rhs: &Vec<usize>) -> Vec<usize> {	2✔
115	let mut result = Vec::new();	2✔
116
117	result.extend(from.iter().filter(\|i\| !rhs.contains(i)));	22✔
118
119	result
120	}	2✔
121
122	#[cfg(test)]
123	mod tests {
124	use super::*;
125
126	#[test]
127	fn test_parse_packages() {	2✔
128	let packages = parse_packages(	1✔
129	r#"1
130	2
131
132	6"#,
133	);
134	assert_eq!(packages.len(), 3);	1!
135	assert_eq!(packages[0], 1);	1!
136	assert_eq!(packages[1], 2);	1!
137	assert_eq!(packages[2], 6);	1!
138	}	2✔
139
140	#[test]
141	fn test_calc_qe() {	2✔
142	assert_eq!(calc_qe(&vec![11, 9]), 99);	1!
143	assert_eq!(calc_qe(&vec![10, 4, 3, 2, 1]), 240);	1!
144	}	2✔
145
146	#[test]
147	fn test_subtract_vectors() {	2✔
148	let packages: Vec<usize> = vec![1, 2, 3, 4, 5, 7, 8, 9, 10, 11];	1✔
149	let result = subtract_vectors(&packages, &vec![10, 4, 3, 2, 1]);	1✔
150	assert_eq!(result.len(), 5);	1!
151	assert!(result.contains(&5));	1!
152	assert!(result.contains(&7));	1!
153	assert!(result.contains(&8));	1!
154	assert!(result.contains(&9));	1!
155	assert!(result.contains(&11));	1!
156	}	2✔
157
158	#[test]
159	fn test_find_optimal_qe() {	2✔
160	let packages: Vec<usize> = vec![1, 2, 3, 4, 5, 7, 8, 9, 10, 11];	1✔
161	assert_eq!(	1✔
162	find_optimal_qe(&packages, packages.iter().sum::<usize>() / 3),	1!
163	99
164	);
165	}	2✔
166	}

Vest / aoc-rust / 4005027531

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous