commit 64a06bb1a558b554dad8fa38487537b2df128bbc
parent 44e82d70e523a6b1b9daa3e6977fadae9af2f914
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Fri, 3 Dec 2021 20:49:15 -0600
Add 2021 day 03
Diffstat:
| A | 2021/day03/input.txt | | | 1000 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day03/main.rs | | | 79 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 1079 insertions(+), 0 deletions(-)
diff --git a/2021/day03/input.txt b/2021/day03/input.txt
@@ -0,0 +1,1000 @@
+100100110110
+101110110110
+010100010100
+011001110000
+000000000111
+000010110001
+001111000001
+100010000001
+010100110011
+010000010110
+010000000011
+010101001000
+011011101100
+011100110111
+011011000000
+001010010010
+011011111010
+011110110110
+000000100010
+111111010101
+011100010011
+001110110100
+110110010100
+100000001011
+100100010011
+011011010001
+111000101110
+101100001111
+110101010101
+011010001001
+101111011000
+011111111011
+110000100101
+011101101101
+011010011001
+111100100001
+100000010000
+111010001010
+111110010001
+110110001101
+000001000001
+000101011000
+111101100100
+110011001001
+100010100011
+011011100010
+011000101101
+110101101011
+111110101000
+010111110100
+010010101011
+100001001000
+101011101011
+110111000001
+011100011110
+011001101101
+010100001111
+001111011000
+100111111010
+110110000100
+000010101100
+111010111011
+110110110110
+110111011000
+100001011001
+110010011111
+100000000101
+110000101100
+110100010110
+101001101100
+111000100011
+011001001101
+000111100111
+001000111110
+110100100010
+000110011100
+010011101111
+010101000111
+101100100001
+100110000010
+001110100101
+010100100100
+001110010110
+000010111010
+101011101001
+101111101010
+101011100110
+011001111010
+100110101010
+101111101110
+100000100011
+000101001011
+000110110000
+110111101111
+111110010110
+100010010111
+011100000101
+101010011010
+010111110010
+000011111101
+000001101000
+000111001001
+101000001011
+011001101000
+010110101110
+000111101000
+101100100011
+011010010011
+110101111110
+101011110001
+111000011101
+111110011100
+100110110001
+110111110011
+000000011010
+000100001110
+011100001111
+010110010111
+011000100110
+011000111000
+010001000111
+100010101110
+011001111011
+010111100001
+011101101110
+101100010110
+100010101011
+110101000010
+111010001101
+111001100111
+101001110111
+011000110010
+011001111100
+010001000110
+011011100101
+101111010001
+100110001011
+001011000010
+010100011111
+101111100110
+011100000010
+011001000010
+010011011111
+001101000010
+110110010110
+001000101001
+101100011000
+000111000110
+000001001101
+000100100111
+110111011100
+010100101001
+010101110000
+110000001110
+010011010000
+011101110000
+001111100000
+010011000011
+010011010011
+101110010000
+101100000110
+110011101101
+010011111101
+101011010110
+001011011100
+111111011001
+011011111000
+011101110011
+010011001101
+100011001000
+011010111011
+111101000110
+100110001101
+101001101011
+100000111100
+111101001011
+010111010111
+101110000000
+010010111111
+100010110010
+101111110100
+111101110111
+111111110010
+110110001100
+101010101111
+000110101000
+100110110100
+100101011010
+001001011000
+111010001011
+000000110100
+111000010010
+101010011101
+010110000010
+011111110111
+101011111101
+011010100111
+100011011101
+110110011110
+101111100111
+001100001111
+011111101011
+100101000100
+100101010010
+011110111010
+010110001001
+010101101010
+001111000101
+010001001100
+001010000010
+010000001101
+110000100110
+111100001101
+101010001001
+110011111111
+010111011001
+000111101111
+111110000011
+011111000011
+011110011011
+100011010100
+000011000110
+011100101000
+010101001111
+010110010110
+111111000111
+101011001001
+011100010111
+000000001100
+011001001000
+110101101111
+101101011001
+000111011000
+000010001111
+111110011011
+010111011111
+011101110100
+001011100001
+001001011100
+110100111011
+100101011111
+000111001101
+011110100101
+111100011010
+111000110100
+010001010101
+100001000100
+000000101110
+011011001110
+111010100111
+100110110000
+110110110001
+001110001001
+110010111111
+000111001011
+011001011111
+000010001011
+100010101001
+100101100101
+010110011001
+101101011110
+101011100101
+101110110101
+111001100001
+001000101010
+101011010011
+110011101100
+101100001101
+101111101001
+111100000010
+100111000000
+010010000100
+001001001001
+000110111110
+011010001110
+100011110000
+110111101000
+110000010101
+011011101011
+101000010001
+110110110010
+100000000001
+011011010101
+000111111101
+100001111011
+100100000110
+001111100010
+110010000011
+101101111001
+110011010110
+010001011011
+010010011010
+001110011110
+100111010010
+110011011010
+111100010011
+111011011101
+100001010110
+101011001111
+001001000000
+101011100010
+010000110011
+100111110000
+010010101110
+110000110011
+110100010111
+001011110010
+101011000111
+000101110011
+010001111011
+000010011011
+011000001011
+000000100100
+001101111001
+011000000101
+100100001101
+101001000011
+111100100111
+111000111111
+011000110011
+101011011110
+101110000100
+010101000001
+110111111100
+100000011011
+101001011010
+111011000110
+110111101011
+011000101100
+100001111111
+111011100101
+110111110101
+101011111010
+010001101100
+111000111001
+110001000011
+100000110100
+010110100010
+100011011111
+001111111001
+101101011011
+011101011000
+100000111000
+101000000110
+010110011101
+110010101101
+011110000010
+100011011010
+110010110101
+110111100011
+110100110000
+101010011100
+001010010110
+100110011110
+101100100010
+110101111001
+111110000000
+011000111111
+100100100000
+111111101111
+001011110101
+101110000001
+101111011110
+011010111001
+011111010111
+000111000101
+000100010001
+111100100101
+100110000100
+001000001111
+001001100100
+001000000110
+110010100100
+111110110101
+010010111001
+110111000110
+011101000000
+100001101100
+111101000111
+000101111111
+001111010100
+101001100100
+111111110001
+010010010001
+111011101010
+001110101000
+111101100001
+100001000001
+111001111010
+100101000011
+000001110011
+000111100001
+110010011110
+111111101011
+000101001001
+000101111101
+011101011001
+100100000111
+110000001011
+001111100110
+110010001101
+011101011011
+011100111111
+000001010000
+011001010101
+001111001010
+010111000000
+001101101101
+011111000111
+000111011101
+100100111100
+011101011111
+111000000111
+100111101101
+001001111001
+010001100101
+101111100001
+000010101101
+010001011111
+000111101010
+011101111101
+111111110101
+011111001101
+110101001100
+011110001110
+001001010000
+010001010001
+011000010010
+100010000100
+100100100001
+011101101111
+111000101111
+001101110110
+110011110000
+000111011111
+011100110010
+001101101110
+101010100010
+111110110010
+111101000100
+001010101000
+001100101001
+111010101000
+010110000100
+110111001000
+111100000110
+001110001011
+011111111100
+110011100000
+001010011100
+110011001000
+001001110101
+001010110110
+110010100101
+100000111111
+110010000100
+110110100100
+001011101101
+000110000010
+001100000111
+010011100110
+001010101011
+111001101000
+110111010010
+110111001100
+010000111100
+010111100110
+001111111111
+011010111010
+100111011100
+011011011010
+001000001110
+111010100101
+100001011000
+011001110011
+100111011000
+111111101000
+010111011010
+111011111000
+001010101110
+000010010111
+110011000010
+100000111010
+110000001111
+011110111101
+101011011001
+011110011111
+100001111010
+111001010110
+100001010000
+011000100000
+111001011000
+000100110011
+010110111101
+010111000100
+100111011101
+100000011010
+010110111001
+010101001110
+110001001001
+111100010001
+111010110011
+100100010100
+000100100000
+100100110010
+111011100000
+111010110010
+110110100110
+001001010001
+010110100111
+111001101100
+000111111001
+011100000110
+011011010010
+001010111000
+001100000010
+100001110001
+011101110111
+010101010100
+111100111001
+010000010101
+011110011110
+000011110100
+000111100100
+100100011000
+101000011011
+111010000100
+000001000111
+111111011111
+000111010101
+000111100101
+000000001101
+000011100001
+101000100111
+100111010001
+001110101010
+101101110001
+101000111001
+001101100011
+101110000111
+100111110010
+010001111111
+100111000010
+100111101111
+111011110110
+100111000100
+000011111110
+001010000101
+111011111110
+010010101111
+010011001110
+110100000001
+110101110001
+000010001101
+000110001010
+101111110010
+111111001000
+001001100001
+110001110100
+110111111011
+000010000101
+111100111000
+010000000010
+001110111001
+111000110111
+000010000001
+111111010010
+010010001010
+001110010111
+000111111110
+100101000001
+000001110111
+101000010000
+100011011001
+010000101101
+011101000110
+110011001011
+110100011010
+100111000101
+011000000100
+110010101110
+001000101110
+100010111111
+100011111011
+001101010001
+111000100100
+100101100100
+001000100001
+000011000101
+001000110001
+110110011011
+100110010111
+110000011101
+000010000010
+011111001111
+000100111000
+100001011011
+110010000000
+000100010100
+011000101001
+100111011011
+110000101101
+111000110011
+101100010111
+101001100110
+110011111011
+100110100110
+100111111111
+100100101010
+001000011111
+000110101101
+110111100001
+100111000110
+100111110110
+111111100000
+100010001011
+100000000010
+110001001000
+101101001110
+111101110011
+010111001111
+011111010100
+110111000101
+010010001110
+010111100010
+111110010011
+001100011011
+100000110111
+010111110110
+001100011101
+010010010111
+110011001101
+000111101110
+011000001111
+010100000000
+110001101001
+101101010111
+110111010100
+101010010111
+001110111110
+101001000111
+011010010110
+010000101100
+110000111111
+011101010000
+010110001101
+010101000101
+101101001000
+100010110001
+101000110101
+111101010101
+010011111100
+100010100110
+011001111001
+000110001001
+101100000101
+000101011010
+100100011110
+100000110011
+100011000101
+110001011010
+111100000111
+001100110111
+011010110000
+011000000111
+111101101011
+011101110101
+010100011110
+010101100011
+000100010000
+010111001011
+101110100001
+110110110101
+000010100111
+001011000110
+110110101100
+010001100010
+011110110111
+110100001100
+000110001100
+001101001100
+101010111011
+000001101100
+011110101101
+110100000000
+011011100111
+000010101001
+100111110101
+000101000101
+010011010111
+111101010100
+110110101101
+110011011100
+110011011001
+000111010111
+110100011110
+000110011010
+110110100000
+111110101101
+001100111000
+101111000110
+011011000010
+000000001001
+010100111110
+100010000110
+001110111101
+010001011100
+101001111101
+110101110000
+001111101111
+100101111101
+110100111101
+000100001000
+111011110101
+001011001000
+011101010111
+101000000101
+011111111001
+111001011011
+010001110001
+010001110011
+001100111001
+100101110010
+100010100010
+110011111001
+111011101011
+001101110011
+000011011010
+101000010111
+000011010001
+101000010010
+000011101111
+011100001100
+110110011001
+011101000001
+010011011001
+111010010011
+001011000111
+010111100101
+101001111011
+101111011011
+011011001100
+010100110000
+000111100011
+010111111011
+100101101010
+010001100000
+111110100011
+100101011101
+011011011011
+111101011001
+001000011101
+101111110011
+100100100110
+010111100111
+110000001101
+000001010011
+100001010100
+101101000100
+110100101101
+110001100011
+110000111010
+101111011010
+011011100000
+100101100110
+010110010001
+101000011000
+011001110100
+001110001100
+100100110100
+001110101011
+000110000100
+101000110001
+101101110010
+011100001110
+111011010011
+011001110001
+110101100000
+110000010011
+010111101111
+101111101111
+010110100000
+111111011011
+100110000110
+011000111100
+110010111110
+001000001101
+011101011010
+001010110101
+100110001100
+101000000011
+110001010011
+100001011111
+000001101001
+100001101101
+011100100000
+011011000110
+001110111011
+100111100101
+001110000000
+110101001101
+101100101100
+001110000001
+110000011010
+101100110010
+011010100010
+111101111010
+110001111100
+011110101000
+110011011000
+110100000111
+100000000111
+101100101110
+011001000011
+011011100110
+101001000001
+001100100101
+011011110011
+110110001011
+000101011110
+010011110101
+110101001010
+111110101010
+110111010001
+010111001101
+001101011000
+011001011011
+011101000010
+101010111110
+010010000101
+100100010010
+110010000010
+000000001110
+100110011100
+000110100111
+000000011011
+111011010000
+100001111000
+000010010011
+110010000101
+011001101111
+010010000110
+101000110100
+010111010110
+011010110010
+001101110001
+001101000100
+001001101011
+010111110101
+100100110101
+000101011011
+110110000111
+000100110001
+111111110011
+111010110000
+000000110001
+010011101001
+111110011101
+101011100100
+001010100101
+010111111100
+010101100100
+011010000000
+010111111111
+111001100011
+111001011110
+010011111010
+001010101100
+110001100101
+011000011110
+001111010010
+010110001110
+011101011110
+101100011010
+000000001000
+000000000000
+100000011000
+101000001111
+101101010010
+001010110010
+101111001001
+111000000001
+010011001010
+110000000101
+101101101000
+110011110111
+111101010110
+111011011011
+100011101100
+101100011011
+000011010110
+111100111101
+110000100100
+001111110111
+011110011101
+010001010110
+101000001110
+101010101110
+010110000011
+100001100000
+000001000011
+110011100010
+000101000110
+010010110110
+100111100011
+000110100100
+110100101110
+001101100101
+110000100000
+110001100110
+110010000001
+010010011011
+101111001010
+101010010110
+001001001100
+011001110010
+111010100100
+000001000100
+010101101001
+101001100011
+010010100100
+010111001010
+101000000100
+011001010100
+101110000110
+011010000111
+101001110001
+111000011110
+010011000111
+111000100111
+010101010011
+010010101010
+011110011001
+110010011101
+110100001001
+011111001001
+011110100011
+100100001111
+000010100101
+110010010111
+111111000101
+000001010100
+001000011110
+011101001110
+111001100101
+111110011110
+000110111100
+110001001110
+011001010111
+101100011101
+010000001001
+100100011101
+101001101000
+100011110101
+100110101101
+000001111001
+011110010001
+001001011001
+110111100111
+100000010111
+011110010010
+000011110000
+111011110111
+101110110010
+000111010100
+010010101001
+000011010010
+101010001011
+111100101100
+111101101111
+101001011111
+101110001010
+010101011110
+101001001101
+100010111100
+011110111001
+110100111110
+001101000011
+000111100010
+100111110011
+010111011011
+101010111100
+100111111110
+001111001011
+000101110001
+001000001010
+010001101101
+101101001101
+111100010000
+011110000110
+100011101110
+111100001110
+101000100010
+101010100101
+110011010111
+110010101010
+110110111111
+010010110011
+000111110010
+111100110011
diff --git a/2021/day03/main.rs b/2021/day03/main.rs
@@ -0,0 +1,79 @@
+fn main() {
+ let mut width = 0;
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|x| {
+ width = x.len();
+ i32::from_str_radix(x, 2).unwrap()
+ })
+ .collect::<Vec<_>>();
+ // 2003336
+ println!("Part 1 : {}", part_1(&input, width));
+ // 1877139
+ println!("Part 2 : {}", part_2(&input, width));
+}
+
+fn part_1(input: &Vec<i32>, width: usize) -> i32 {
+ let mut gamma = 0;
+ let mut epsilon = 0;
+
+ for i in (0..width).rev() {
+ let mask = 1 << i;
+ let one_count = input.iter().fold(0, |acc, x| acc + (x & mask != 0) as i32);
+ let zero_count = input.len() as i32 - one_count;
+ // ties go to 1
+ if one_count >= zero_count {
+ gamma |= mask;
+ } else {
+ epsilon |= mask;
+ }
+ }
+
+ gamma * epsilon
+}
+
+fn part_2(input: &Vec<i32>, width: usize) -> i32 {
+ let mut gamma = 0;
+ let mut epsilon = 0;
+
+ let mut o2_candidate = input.clone();
+ let mut co2_candidate = input.clone();
+
+ for i in (0..width).rev() {
+ let mask = 1 << i;
+
+ if o2_candidate.len() > 1 {
+ let gamma_one_count = o2_candidate
+ .iter()
+ .fold(0, |acc, x| acc + (x & mask != 0) as i32);
+ let gamma_zero_count = o2_candidate.len() as i32 - gamma_one_count;
+ // ties go to 1
+ if gamma_one_count >= gamma_zero_count {
+ gamma |= mask;
+ }
+ o2_candidate = o2_candidate
+ .into_iter()
+ .filter(|&x| x >> i == gamma >> i)
+ .collect();
+ }
+
+ if co2_candidate.len() > 1 {
+ let epsilon_one_count = co2_candidate
+ .iter()
+ .fold(0, |acc, x| acc + (x & mask != 0) as i32);
+ let epsilon_zero_count = co2_candidate.len() as i32 - epsilon_one_count;
+ // ties go to 0
+ if epsilon_one_count < epsilon_zero_count {
+ epsilon |= mask;
+ }
+ co2_candidate = co2_candidate
+ .into_iter()
+ .filter(|&x| x >> i == epsilon >> i)
+ .collect();
+ }
+ }
+
+ o2_candidate[0] * co2_candidate[0]
+}