From c58ada44f42811ac6f74ccc30822d8adc71214fd Mon Sep 17 00:00:00 2001 From: =?utf8?q?Gr=C3=A9gory=20Burri?= Date: Wed, 18 Dec 2019 09:47:35 +0100 Subject: [PATCH] Day 16 & day 17 part 1 --- data/day16.input | 1 + data/day17.input | 1 + day17.txt | 43 ++++++++++++++++++++ src/day16.rs | 104 +++++++++++++++++++++++++++++++++++++++++++++++ src/day17.rs | 74 +++++++++++++++++++++++++++++++++ src/main.rs | 19 +++++++++ 6 files changed, 242 insertions(+) create mode 100644 data/day16.input create mode 100644 data/day17.input create mode 100644 day17.txt create mode 100644 src/day16.rs create mode 100644 src/day17.rs diff --git a/data/day16.input b/data/day16.input new file mode 100644 index 0000000..4db7059 --- /dev/null +++ b/data/day16.input @@ -0,0 +1 @@ +59764635797473718052486376718142408346357676818478503599633670059885748195966091103097769012608550645686932996546030476521264521211192035231303791868456877717957482002303790897587593845163033589025995509264282936119874431944634114034231860653524971772670684133884675724918425789232716494769777580613065860450960426147822968107966020797566015799032373298777368974345143861776639554900206816815180398947497976797052359051851907518938864559670396616664893641990595511306542705720282494028966984911349389079744726360038030937356245125498836945495984280140199805250151145858084911362487953389949062108285035318964376799823425466027816115616249496434133896 \ No newline at end of file diff --git a/data/day17.input b/data/day17.input new file mode 100644 index 0000000..e58ec75 --- /dev/null +++ b/data/day17.input @@ -0,0 +1 @@ +1,330,331,332,109,3546,1101,1182,0,15,1101,1439,0,24,1002,0,1,570,1006,570,36,1001,571,0,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,15,1,15,1008,15,1439,570,1006,570,14,21101,0,58,0,1105,1,786,1006,332,62,99,21102,1,333,1,21102,73,1,0,1106,0,579,1101,0,0,572,1101,0,0,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,1001,574,0,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1105,1,81,21102,340,1,1,1105,1,177,21101,0,477,1,1106,0,177,21102,514,1,1,21101,0,176,0,1105,1,579,99,21101,184,0,0,1106,0,579,4,574,104,10,99,1007,573,22,570,1006,570,165,102,1,572,1182,21102,375,1,1,21101,0,211,0,1106,0,579,21101,1182,11,1,21101,0,222,0,1106,0,979,21101,0,388,1,21102,233,1,0,1105,1,579,21101,1182,22,1,21101,244,0,0,1105,1,979,21102,1,401,1,21101,0,255,0,1106,0,579,21101,1182,33,1,21102,266,1,0,1106,0,979,21102,414,1,1,21102,1,277,0,1105,1,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21101,0,1182,1,21102,1,313,0,1106,0,622,1005,575,327,1101,1,0,575,21101,327,0,0,1106,0,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,22,42,0,109,4,1201,-3,0,587,20101,0,0,-1,22101,1,-3,-3,21102,1,0,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1105,1,597,109,-4,2106,0,0,109,5,2101,0,-4,629,21002,0,1,-2,22101,1,-4,-4,21101,0,0,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,652,21002,0,1,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21102,1,702,0,1105,1,786,21201,-1,-1,-1,1105,1,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21102,731,1,0,1106,0,786,1105,1,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,756,0,0,1105,1,786,1105,1,774,21202,-1,-11,1,22101,1182,1,1,21102,1,774,0,1106,0,622,21201,-3,1,-3,1105,1,640,109,-5,2106,0,0,109,7,1005,575,802,21002,576,1,-6,21002,577,1,-5,1106,0,814,21102,1,0,-1,21101,0,0,-5,21102,0,1,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,49,-3,22201,-6,-3,-3,22101,1439,-3,-3,1201,-3,0,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21101,0,1,-1,1105,1,924,1205,-2,873,21102,1,35,-4,1105,1,924,2102,1,-3,878,1008,0,1,570,1006,570,916,1001,374,1,374,2102,1,-3,895,1102,2,1,0,1201,-3,0,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,921,21001,0,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,49,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,43,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1102,1,1,575,21101,0,973,0,1105,1,786,99,109,-7,2106,0,0,109,6,21101,0,0,-4,21102,0,1,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1106,0,1041,21102,1,-4,-2,1106,0,1041,21102,1,-5,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,1202,-2,1,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,2102,1,-2,0,1106,0,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1105,1,989,21102,1,439,1,1106,0,1150,21101,477,0,1,1106,0,1150,21101,0,514,1,21101,0,1149,0,1106,0,579,99,21101,1157,0,0,1105,1,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,2102,1,-5,1176,2102,1,-4,0,109,-6,2105,1,0,26,5,44,1,3,1,44,1,3,1,44,1,3,1,44,1,3,1,44,1,3,1,44,7,46,1,1,1,44,11,38,1,1,1,1,1,5,1,28,13,1,1,5,1,28,1,9,1,3,1,5,1,28,1,9,7,3,1,28,1,13,1,1,1,3,1,28,1,13,1,1,1,3,1,28,1,13,1,1,1,3,1,16,13,13,1,1,1,3,1,16,1,25,1,1,1,3,1,10,11,21,7,10,1,5,1,3,1,23,1,14,1,5,1,3,1,23,1,3,7,4,1,5,1,3,1,23,1,3,1,5,1,4,7,3,1,23,1,3,1,5,1,14,1,23,1,3,1,5,1,14,1,23,11,14,1,27,1,20,1,27,1,3,7,10,1,27,1,3,1,5,1,10,1,25,5,1,1,5,1,10,1,25,1,1,1,1,1,1,1,5,1,10,7,19,1,1,11,16,1,19,1,3,1,1,1,22,1,13,13,22,1,13,1,5,1,3,1,24,1,13,1,5,1,3,1,24,1,13,1,9,1,24,1,13,1,9,1,24,1,13,1,9,1,24,1,13,11,24,1,48,1,48,1,48,7,26 \ No newline at end of file diff --git a/day17.txt b/day17.txt new file mode 100644 index 0000000..396303c --- /dev/null +++ b/day17.txt @@ -0,0 +1,43 @@ +..........................#####.................. +..........................#...#.................. +..........................#...#.................. +..........................#...#.................. +..........................#...#.................. +..........................#...#.................. +..........................#######................ +..............................#.#................ +............................###########.......... +............................#.#.#.....#.......... +..................#############.#.....#.......... +..................#.........#...#.....#.......... +..................#.........#######...#.......... +..................#.............#.#...#.......... +..................#.............#.#...#.......... +..................#.............#.#...#.......... +......#############.............#.#...#.......... +......#.........................#.#...#.......... +###########.....................#######.......... +#.....#...#.......................#.............. +#.....#...#.......................#...#######.... +#.....#...#.......................#...#.....#.... +#######...#.......................#...#.....#.... +..........#.......................#...#.....#.... +..........#.......................###########.... +..........#...........................#.......... +..........#...........................#...####### +..........#...........................#...#.....# +..........#.........................#####.#.....# +..........#.........................#.#.#.#.....# +..........#######...................#.########### +................#...................#...#.#...... +................#.............#############...... +................#.............#.....#...#........ +................#.............#.....#...#........ +................#.............#.........#........ +................#.............#.........#........ +................#.............#.........#........ +................#.............###########........ +................#................................ +................#................................ +................#................................ +................######^.......................... \ No newline at end of file diff --git a/src/day16.rs b/src/day16.rs new file mode 100644 index 0000000..2112c0e --- /dev/null +++ b/src/day16.rs @@ -0,0 +1,104 @@ +use std::iter::FromIterator; + +pub fn parse(input: &str) -> Vec { + input.chars().map(|c| c.to_digit(10).unwrap() as i32).collect() +} + +pub fn fft(signal: &[i32], pattern: &[i32], nb_phases: i32, offset: usize, length: usize, nb_signal_repeated: usize) -> Vec { + + let l = signal.len(); + let pattern_l = pattern.len(); + + let mut output = Vec::from_iter(signal.iter().cycle().take(l * nb_signal_repeated).copied()); + + for _ in 0 .. nb_phases { + let cloned_output = output.clone(); + for i in 0 .. output.len() { + output[i] = + cloned_output.iter().enumerate().fold( + 0, + |sum, (j, value)| { + sum + value * pattern[(j + 1) / (i + 1) % pattern_l] + } + ).abs() % 10; + } + } + + Vec::from(&output[offset .. offset + length]) +} + +pub fn digits_as_string(signal: &[i32]) -> String { + signal.iter().fold(String::new(), |result, digit| result + &digit.to_string()) +} + +// Part 2 is from 'https://github.com/mkeeter/advent-of-code/blob/master/2019/16/src/main.rs'. + +fn cumsum(input: &[i32]) -> Vec { + let mut output = vec![0; input.len() + 1]; + for (i, v) in input.iter().enumerate() { + output[i + 1] = output[i] + v; + } + output +} + +fn dft(scale: usize, csum: &[i32]) -> i32 { + use std::cmp::min; + + assert!(scale > 0); + let mut i = scale; + let mut sign = true; + let mut out = 0; + while i < csum.len() { + let d = csum[min(csum.len() - 1, i + scale - 1)] - csum[i - 1]; + if sign { + out += d; + } else { + out -= d; + } + sign = !sign; + i += scale * 2; + } + out.abs() % 10 +} + +pub fn part2(input: &[i32]) -> Vec { + let size = input.len(); + let mut input = Vec::from_iter(input.iter().cycle().take(size * 10_000).copied()); + + let offset = input[..7].iter().fold(0, |acc, i| acc * 10 + i) as usize; + + for _ in 0..100 { + let csum = cumsum(&input); + input = (0..input.len()) + .map(|i| dft(i + 1, &csum)) + .collect::>(); + } + + Vec::from(&input[offset..(offset + 8)]) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn part1_sample_1() { + let signal = parse("80871224585914546619083218645595"); + let output = fft(&signal, &[0, 1, 0, -1], 100, 0, 8, 1); + assert_eq!(digits_as_string(&output), "24176176"); + } + + #[test] + fn part1_sample_2() { + let signal = parse("19617804207202209144916044189917"); + let output = fft(&signal, &[0, 1, 0, -1], 100, 0, 8, 1); + assert_eq!(digits_as_string(&output), "73745418"); + } + + #[test] + fn part1_sample_3() { + let signal = parse("69317163492948606335995924319873"); + let output = fft(&signal, &[0, 1, 0, -1], 100, 0, 8, 1); + assert_eq!(digits_as_string(&output), "52432133"); + } +} \ No newline at end of file diff --git a/src/day17.rs b/src/day17.rs new file mode 100644 index 0000000..15bd825 --- /dev/null +++ b/src/day17.rs @@ -0,0 +1,74 @@ +use super::intcode; +use std::collections::HashSet; + +pub fn scaffold_intersections(code: &[i64]) -> i32 { + let output = intcode::execute_op_code(code, &[]); + let mut board = Vec::>::new(); + let mut current_line = Vec::::new(); + + let (mut x, mut y) = (0i32, 0i32); + let mut dir = '^'; + + let mut current_x = 0; + for c in output { + if c == 10 { + board.push(current_line); + current_line = Vec::::new(); + current_x = 0; + //println!(""); + } else { + let c = (c as u8) as char; + if let '^' | '<' | 'v' | '>' = c { + x = current_x; + y = board.len() as i32; + dir = c; + } + //print!("{}", c); + current_line.push(c); + current_x += 1; + } + } + + let get = |x: i32, y: i32| -> Option { + if x < board[0].len() as i32 && x >= 0 && y < board.len() as i32 && y >= 0 { + Some(board[y as usize][x as usize]) + } else { + None + } + }; + + let mut visited_locations = HashSet::<(i32, i32)>::new(); + let mut crosses = Vec::<(i32, i32)>::new(); + visited_locations.insert((x, y)); + + 'main: loop { + let positions = [('^', (x, y - 1)), ('<', (x - 1, y)), ('>', (x + 1, y)), ('v', (x, y + 1))]; + + let next_position = positions.iter().find(|(d, _)| *d == dir).unwrap().1; + //match dir { '^' => positions[0], '<' => positions[1], '>' => positions[2], 'v' | _ => positions[3] }; + + // If the robot can continue straightforward. + if get(next_position.0, next_position.1) == Some('#') { + if !visited_locations.insert(next_position) { + crosses.push(next_position); + } + x = next_position.0; + y = next_position.1; + continue; + } + + for (d, p) in &positions { + if get(p.0, p.1) == Some('#') && !visited_locations.contains(p) { + visited_locations.insert(*p); + dir = *d; + x = p.0; + y = p.1; + continue 'main; + } + } + + break; + } + + crosses.iter().fold(0, |sum, cross| sum + cross.0 * cross.1) +} \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 491ee5c..4788102 100644 --- a/src/main.rs +++ b/src/main.rs @@ -16,6 +16,8 @@ mod day12; mod day13; mod day14; mod day15; +mod day16; +mod day17; fn day01() -> String { let masses = common::read_list_of_numbers("data/day01.input", "\n"); @@ -117,6 +119,21 @@ fn day15() -> String { format!("part1: {}, part2: {}", n, day15::time_to_flood_the_area(&dts)) } +fn day16() -> String { + let signal_raw = fs::read_to_string("data/day16.input").unwrap(); + let signal = day16::parse(&signal_raw); + let output_part_1 = day16::fft(&signal, &[0, 1, 0, -1], 100, 0, 8, 1); + //let output_part_2 = day16::part2(&signal); + format!("part1: {}, part2: {}", day16::digits_as_string(&output_part_1), /*day16::digits_as_string(&output_part_2)*/ "") +} + +fn day17() -> String { + let code = common::read_list_of_numbers("data/day17.input", ","); + let n = day17::scaffold_intersections(&code); + format!("part1: {}, part2: {}", n, "") + +} + fn format_micros(t: u128) -> String { if t < 10_000 { format!("{} μs", t) @@ -151,6 +168,8 @@ fn main() { day13, day14, day15, + day16, + day17, ); let args: Vec = env::args().skip(1).collect(); -- 2.45.2