day3

2 files changed, 1109 insertions, 0 deletions

diff --git a/inputs/day3 b/inputs/day3
new file mode 100644
index 0000000..39e208c
--- /dev/null
+++ b/inputs/day3
@@ -0,0 +1,1000 @@
+000011010001
+000001110100
+111100101010
+111001100111
+001010100100
+101010010001
+000001100011
+010010110101
+011001011100
+001110111000
+111101011111
+001111001011
+100110010010
+000001011001
+110001000111
+010011111110
+111011000111
+001000110111
+010011101110
+111010111000
+001101100000
+111101010111
+111000010111
+101111001011
+100000000011
+110000111100
+101110110001
+010000100011
+001100111111
+011011011100
+000001110011
+001110111011
+011110011101
+110011010010
+010111001010
+110010000100
+101111001101
+011111001101
+111110010000
+001011010011
+111111001101
+011110110000
+100001011001
+011010010010
+101001111010
+001100001010
+110000000010
+010000011001
+010010010110
+110101111111
+011001101110
+001100000111
+101111001010
+110000100000
+000111101110
+101101111011
+100110101011
+011010011000
+101000101010
+000001010100
+110101011101
+010101010100
+011010000111
+011001001001
+011101010001
+111111011110
+100010100110
+101001111110
+110010100101
+111110110011
+101101111101
+001010110000
+001111001010
+011001111010
+000111010010
+010100000001
+101000111110
+110111000011
+110111011101
+110111001000
+111111001000
+001000010110
+110000010010
+001011010001
+011000110000
+101001101001
+000101101001
+010100111100
+100001111110
+010011001100
+100010010111
+000010000000
+010110101111
+010000100010
+110111010111
+110100011010
+000111101100
+011110101000
+010000010111
+011010111101
+110111111000
+110001010101
+101011110010
+110011111001
+010111101010
+000000010000
+010010011000
+100100001110
+001101011101
+101101010100
+000011001101
+101000000001
+101000000111
+110001010011
+100001011010
+000100111101
+100011000101
+110001001000
+000110011111
+010100111001
+111111111011
+000010010100
+101001011000
+011000011010
+010011111111
+101100001101
+110101010111
+111010011001
+100010111011
+100010000000
+111001111010
+010111011110
+010010000101
+101100110110
+111101001000
+000010111011
+111010010100
+101011011110
+110110010111
+101100010011
+000110101001
+100010101111
+101001010011
+111010100101
+000011011010
+110010111001
+010100101110
+101001001101
+101110011111
+110101100010
+110100111001
+111110100111
+101101000010
+111111111000
+100001100001
+011100100010
+011100101011
+111101111111
+010011000100
+010001110111
+100101001100
+111100100110
+110001111110
+001100100110
+010011011001
+001001010011
+111000100100
+011011010111
+101011010010
+101100001111
+011111000111
+100001101000
+011101101101
+011000001010
+100101111011
+111000100001
+011101111000
+011011001011
+011010011001
+101111100011
+010001110000
+000101110010
+010100001111
+100110010001
+110011111100
+011100100100
+010011111001
+001010011011
+000111111100
+101000000010
+110101010000
+101110011101
+001110001110
+001110100111
+010111010101
+100100001111
+001111010110
+100010111010
+001010000100
+010001001100
+011111010011
+010000100110
+110011000111
+111010000100
+101101001011
+010110111001
+000110100101
+000010011000
+000111011100
+011010101100
+101100110000
+101001011001
+110011010100
+000101011000
+110010110111
+101001101101
+010100011101
+101100011010
+010111000111
+010110101001
+111000011010
+011011100101
+011111110101
+110110000000
+111111010010
+011001000000
+000100010000
+111011100110
+011100111100
+001010000110
+011110000011
+011001011101
+111001111101
+011010101111
+100011001000
+111111110100
+100101011101
+101110111111
+110100100011
+010100100111
+111011011000
+011111011001
+101111010001
+011111110010
+010000011100
+111101111110
+001010011000
+011010010011
+011011100111
+100001000110
+111111010100
+101100100001
+100101010101
+111110011110
+101001001110
+111011100001
+110111011011
+011100101100
+011000111011
+110100110101
+110000001011
+110101100001
+110011000000
+010010011011
+000110000001
+110001001111
+101010100111
+001011001100
+111100011111
+111101000101
+010110110001
+001000111110
+001110111111
+000100001001
+100101010110
+111110101101
+101111111001
+011011000101
+111011101010
+001000100001
+001111110101
+111110100000
+111011000110
+111101111010
+000100000101
+011000010110
+000000011011
+110011010011
+000101100000
+111100111111
+111110111000
+000101100011
+010000110110
+100101101011
+010101000100
+110110100011
+110001010001
+100010011100
+111101100000
+011110001100
+011101010011
+101111000111
+101000001010
+001010110010
+110000101000
+101101111111
+101000111100
+011011010010
+111101010001
+000100010010
+100010011000
+111110101000
+011101001010
+100100110001
+101010000000
+110100111101
+001101000110
+110101010010
+010101110110
+100011010011
+011011101011
+010110111011
+111001000000
+001100000101
+001101111110
+111000100110
+001010001001
+001000111100
+011110110110
+011111010110
+101010000011
+011111010100
+010100010111
+010100110001
+110100100111
+110001110100
+100101010100
+001111111010
+100111110111
+011010001000
+011101111001
+101110111010
+110011000100
+000010111010
+000011011001
+101010010011
+001110001011
+000100000100
+001001001000
+111101011010
+111110101110
+101110000100
+110101110000
+001110010110
+001001100100
+010011001111
+010011101010
+001111001000
+110001000011
+001100001111
+101100100011
+001100110011
+110111000110
+100010101000
+011110100111
+010111010001
+111100000101
+011110110010
+111010000111
+010101011110
+011101111010
+001100010100
+111000000001
+011001110111
+010000101110
+001010111111
+111100110110
+111000010010
+101011000111
+111000011101
+100111010001
+001110101000
+100111001010
+100110111000
+110001011110
+000001000100
+001100110110
+110110100001
+011101000001
+111001010111
+111000001010
+101100010100
+000110111111
+001100000001
+110011100011
+101111100110
+011010101001
+110001001100
+011111010111
+110100100010
+011100001110
+111000000010
+001010110011
+001100100011
+001010000111
+100000111010
+011011001101
+111001000110
+110011110111
+010001001000
+111010110011
+001100111011
+010000110001
+000110000111
+111100110101
+010111010110
+011100100001
+101011010000
+101010101000
+111011110110
+101100010001
+111110000010
+101010110111
+001001100000
+001110010011
+000110111110
+001001111001
+010101110000
+111001100110
+100100100101
+010001011101
+010000011110
+100001001001
+001001010100
+111100000000
+110011001110
+010101001100
+101000011111
+000010001111
+001111010001
+101010001111
+111101000011
+101000011001
+001111111100
+010110101101
+010011110110
+110000111110
+010000100100
+010011000111
+100101011110
+110100100101
+100100001000
+110110011101
+011011110100
+010001011111
+111000100000
+011100101001
+110010100100
+000001001011
+101011110001
+011011110000
+101011110101
+011011010000
+001110110001
+100010100111
+111001100100
+010011100110
+111111111100
+101110001010
+001001111111
+010100110011
+100101000000
+011101110001
+010110000111
+110100000111
+010100101100
+001000000011
+001100011110
+101100011100
+001001110000
+100110100010
+100011010111
+011101111100
+010110010000
+001111101011
+101100001110
+000010110110
+010110100110
+101110100111
+001111010011
+101110101010
+110011110001
+010001001110
+111010100110
+000001111001
+000100100001
+000000111100
+011100101111
+000001101110
+101000110101
+010011011110
+100000111101
+010010001100
+010101101010
+000001000001
+111111000100
+111111100110
+101011101000
+111100000011
+010110001111
+010011101101
+100101111010
+000001001111
+010000001111
+010111000000
+100110101110
+110101101110
+000000000110
+010001110001
+000111100001
+110101101111
+000110010111
+011010100011
+111110001101
+100000101001
+001010100110
+100001001111
+011010100000
+101010111000
+001101110111
+111001101011
+000111111001
+100010001000
+001010110110
+011001011111
+000111000101
+001111100110
+100110101001
+101111000110
+001101011111
+001111011110
+110110110100
+011001111111
+100001010101
+101101100010
+111101011110
+111110000000
+001011111100
+100100010111
+111000110001
+001110101010
+100100001100
+110100011111
+010101000111
+110111010000
+011111100011
+101110111001
+101011001000
+000011010011
+101011001110
+100101110111
+001011100011
+000110100100
+110110101010
+000011110111
+110010100010
+000111010101
+011011010110
+001001011110
+100101110100
+000110110000
+011001100100
+010010000110
+001110101110
+010000001000
+110000100010
+000010011011
+101000111011
+011001100111
+000000010100
+110101111110
+110100101101
+111111111101
+110100011110
+000001111000
+100110100111
+101010111011
+001000011101
+010001000010
+100100100010
+000111110000
+100001000010
+000110001100
+000001111010
+000101001010
+000101100100
+011000001101
+010000111000
+101111111000
+001110011101
+001010110101
+001011101000
+010110011100
+000010111101
+011001010110
+000011000000
+001000010101
+001101001000
+111100010000
+111111001111
+001011011000
+100000101000
+010101110101
+010010011010
+011001000001
+011000000000
+010101011101
+100101001000
+110101110101
+101101011001
+000101011100
+011001010100
+100010010100
+010101001011
+000001001001
+011011001100
+100001110100
+000101101110
+011011000000
+000010010011
+111111001001
+100110010111
+001011000000
+101111100101
+110100111000
+101110010000
+010000101001
+110100101110
+011000100100
+100100100001
+010101100010
+111011010101
+111001110000
+010011110010
+000011001000
+010011010011
+110110110010
+100101001111
+101011100011
+011111110111
+011000100010
+111001000111
+110001000110
+011100101000
+011100000101
+001010111010
+001101010011
+000101111101
+001101111111
+101111010111
+000011100011
+111001110101
+100101011100
+001011101011
+110001001110
+001001110001
+101011010011
+100110011101
+101001010100
+111001100000
+001011011100
+010001101101
+100100100100
+100110111100
+000101010000
+010011100000
+111101110010
+111001010100
+101100001000
+110100010110
+000010011111
+100100111001
+101011101010
+110101111010
+111011110011
+101110011011
+010101010101
+101111111111
+110011110010
+001010001100
+001001110100
+101110110010
+001010101101
+001111111101
+110110011111
+111000011001
+000010000011
+010001111100
+001001100001
+101011010111
+100111000010
+011101110011
+001110000010
+100000111111
+101101010101
+001010000011
+110101011110
+011011100110
+100101001001
+001101000001
+000001100111
+101100110111
+100000001100
+011100001111
+111000010101
+000110101110
+000101011010
+101110110100
+000001101011
+010001111001
+000000011101
+110100010101
+000101010111
+011011011110
+010010110011
+111101011011
+111100101001
+010010110100
+101001000110
+111100110011
+011100000100
+001000100111
+100001001010
+101101110101
+011010110101
+110110010011
+100110110110
+111110001111
+010111101000
+011100011110
+010110000100
+111001001011
+011010110111
+100110000111
+101110111000
+011000101001
+101010001010
+001101011010
+001010100001
+101111101011
+101111101000
+110010011101
+001010001010
+111000011100
+101011110100
+110000010001
+101010101010
+110111010110
+010100011110
+110101110100
+000101011001
+000110000000
+101110111100
+000110001011
+100010011101
+110001011011
+011010111000
+100111111000
+101011100111
+100001101011
+111110111010
+000011010010
+011010100101
+001110110101
+111110011111
+101010110001
+000011110001
+101001001011
+001100001011
+101111011101
+000110110001
+001001111110
+011001111001
+100001111101
+011110001111
+011011010100
+111101000111
+011000011110
+100011011000
+100001110011
+101010100010
+100110000110
+111010010101
+110000101101
+110111001001
+111001111100
+001000001110
+110001101001
+100111010000
+110110011001
+110100010011
+001100011001
+100111110001
+100000011111
+001000101010
+010010010100
+001010010111
+111111110110
+001011110011
+001010110111
+100100111011
+111100100011
+111111110111
+101110100000
+100001111010
+000100011100
+001011100010
+011001110110
+111010111001
+000101011101
+000011110110
+100000001010
+010110110100
+101100110010
+011010110011
+100010111001
+100101111101
+101110111011
+100001101110
+001101001111
+000011101100
+000011011101
+001001010101
+100111101011
+000111010110
+100000101100
+001011011101
+111001010110
+110000011100
+100011010100
+100110110001
+101001000000
+111111101110
+101110100100
+000101011110
+010010101100
+110011001011
+001100011111
+000000110000
+010101111101
+000111101111
+101110001100
+110101001011
+110010110010
+001110010000
+001100110100
+000001010101
+110001111100
+001101101001
+100010100101
+001010110001
+100000100010
+110010111011
+110101110011
+011111010101
+111001111110
+010000101000
+101001101100
+111010101110
+011010101000
+110011101001
+110110000101
+111011101101
+101110100110
+010010001011
+110000110110
+100001100101
+111000111101
+011000010100
+101111110110
+001100011101
+001100010000
+101110000111
+011110010000
+111101001011
+110101100100
+011100101010
+101001100111
+110110011010
+011110011010
+011101100111
+011001010001
+111111100010
+111011110001
+110111110011
+101111000100
+001000111111
+010011100011
+100110100001
+101000001110
+100010000111
+011010000010
+010100111101
+110001010000
+110011100101
+001101010000
+100011111000
+010001000001
+011011110110
+100101001011
+000011011100
+010000111001
+011111011101
+011011111001
+110010011110
+100010110100
+111010001111
+101110011100
+001111010101
+000100011001
+010111011111
+110010000010
+000010011010
+001101011100
+010000100101
+110011100001
+110100000101
+100010101110
+011010010101
+111101010010
+000111100000
+111010110101
+000100111100
+101100101011
+000100110011
+000111110111
+000101010100
+101101110011
+101011011001
+001001010111
+010011011100
+101100110011
+010101101011
+000011110100
+111111111001
+010011100101
+001001000000
+101101010000
+001111110001
+001100101000
+000000001001
+001111011101
+111110110001
+110110011000
+100000011100
+110101111000
+100010110001
+110101111100
+000001010010
+110010000001
+100101111001
+110010001101
+111011010010
+000110110011
+110000100111
+010110011010
+101111101110
+010101111010
+000011101111
+000001110010
+100100011011
+011100011011
+101010110110
+010001011010
+111110011010
+111110011000
+010110101000
+100110110000
+010100000011
+100001100011
+011101000100
+010111110001
+110111110100
+101001001001
+001001101001
+111000010100
+100010000110
+110010010100
+001001111000
+010001111101
+100111000111
+011110101111
+101110010100
+010010101000
+111011111101
+111010010110
+101000100011
+010000011000
+001011000100
+111001010010
diff --git a/src/bin/day3.rs b/src/bin/day3.rs
new file mode 100644
index 0000000..cb442ed
--- /dev/null
+++ b/src/bin/day3.rs
@@ -0,0 +1,109 @@
+fn main() {
+    let input = advent::read_lines(3);
+    println!("3a: {}", power_consumption(&input));
+    println!("3b: {}", life_support_rating(&input));
+}
+
+
+fn power_consumption<T: AsRef<str>>(input: &[T]) -> u32 {
+    let bits = count_ones(input);
+    let gamma = rate(&bits, input.len(), true);
+    let epsilon = rate(&bits, input.len(), false);
+
+    gamma * epsilon
+}
+
+fn count_ones_at_pos<T: AsRef<str>>(input: &[T], pos: usize) -> usize {
+    input.iter()
+         .filter(|&x| x.as_ref().chars().nth(pos).unwrap() == '1')
+         .count()
+}
+
+fn count_ones<T: AsRef<str>>(input: &[T]) -> Vec<usize> {
+    input[0].as_ref()
+            .chars()
+            .enumerate()
+            .map(|(i, _)| count_ones_at_pos(input, i))
+            .collect()
+}
+
+fn rate(bits: &[usize], max_count: usize, gamma: bool) -> u32 {
+    let mut result = 0;
+    let max_count = max_count;
+
+    for count in bits.iter() {
+        result <<= 1;
+        if gamma && 2 * count > max_count {
+            result += 1;
+        }
+        if !gamma && 2 * count < max_count {
+            result += 1;
+        }
+    }
+    result
+}
+
+fn life_support_rating<T: AsRef<str>>(input: &[T]) -> usize {
+    let oxygen = oxygen_rating(input);
+    let co2 = co2_rating(input);
+
+    oxygen * co2
+}
+
+fn co2_rating<T: AsRef<str>>(input: &[T]) -> usize {
+    rating(input, false)
+}
+
+fn oxygen_rating<T: AsRef<str>>(input: &[T]) -> usize {
+    rating(input, true)
+}
+
+fn rating<T: AsRef<str>>(input: &[T], oxygen: bool) -> usize {
+    let mut numbers = vec!["0"; input.len()];
+    for (i, number) in input.iter().enumerate() {
+        numbers[i] = number.as_ref();
+    }
+
+    let len = numbers[0].len();
+    for i in 0 .. len {
+        let ones = count_ones_at_pos(&numbers, i);
+        let keep = if (oxygen && 2 * ones >= numbers.len()) || (!oxygen && 2 * ones < numbers.len()) {
+            '1'
+        } else {
+            '0'
+        };
+        numbers = numbers.iter()
+                         .filter(|&x| x.chars().nth(i).unwrap() == keep)
+                         .copied()
+                         .collect();
+        if numbers.len() == 1 {
+            break;
+        }
+    }
+    usize::from_str_radix(numbers[0], 2).unwrap()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "00100",
+            "11110",
+            "10110",
+            "10111",
+            "10101",
+            "01111",
+            "00111",
+            "11100",
+            "10000",
+            "11001",
+            "00010",
+            "01010",
+        ];
+        assert_eq!(power_consumption(&input), 198);
+        assert_eq!(life_support_rating(&input), 230);
+    }
+}