adventofcode

commit

3737ee934b89de91b97c9ea60c8530e717edab78

parent

43a7385bb73991fa3f0f169ba515678f250af0a1

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-12-13 08:12

2022-12-12

Diffstat

3 files changed, 127 insertions, 0 deletions

diff --git a/2022/12/input.txt b/2022/12/input.txt

@@ -0,0 +1,41 @@
   -1     1 abcccccccccaaaaaaaaaaccccccccccccaaaaaaaaccaaccccccccccccccccccccccccccccccccccccccccccccaaaaaa
   -1     2 abccccccccccaaaaaaaaaccccccccccccaaaaaaaaaaaacccccccccccaacccacccccccccccccccccccccccccccaaaaaa
   -1     3 abcccccccccccaaaaaaacccccccccccccaaaaaaaaaaaaaacccccccccaaacaacccccccccaaaccccccccccccccccaaaaa
   -1     4 abccccccccccaaaaaaccccccccccccccaaaaaaaaaaaaaaaccccccccccaaaaaccccccccccaaacccccccccccccccccaaa
   -1     5 abccccccccccaaaaaaaccccccccccccaaaaaaaaaaaaaacccccccccccaaaaaacccccccccaaaacccccccccccccccccaac
   -1     6 abaaccaaccccaaccaaaccccccccaaaaaaaaaaaaaaacaaccccccccccaaaaaaaacccccccccaaalcccccccccccccccaaac
   -1     7 abaaaaaacccccccccaaccccccccaaaaaacccaaaacccaaccccccccccaaaaaaaaccccccccalllllllcccccccccccccccc
   -1     8 abaaaaaacccccccaaacccccccccaaaaccccccaaaccccaaaaacccccccccaacccccccaaaakllllllllcccccccaacccccc
   -1     9 abaaaaaacccccccaaaacccccccccaacccccccaaaccccaaaaacccccccccaacccccccaakkklllpllllccccacaaacccccc
   -1    10 abaaaaaaaccccccaaaaccccaaccccccccccccccccccaaaaaaccccccccccccccccccckkkkpppppplllcccaaaaaaacccc
   -1    11 abaaaaaaacaaaccaaaaccaaaaaaccccccccccccccccaaaaaacccccccaaaccccckkkkkkkpppppppplllcddaaaaaacccc
   -1    12 abcaaaacccaacccccccccaaaaaacccccaaaccccccccaaaaaacccccccaaaaccjkkkkkkkpppppuppplmmdddddaaaccccc
   -1    13 abccaaaaaaaaaccccccccaaaaaaccccaaaaaacccccccaaacccccccccaaaajjjkkkkkrpppuuuuupppmmmdddddacccccc
   -1    14 abccccaaaaaaaacccccccaaaaacccccaaaaaacccccccccccccccccccaaacjjjjrrrrrrppuuuuupqqmmmmmddddaccccc
   -1    15 abccccaaaaaaaaacccccccaaaacccccaaaaaaccccccccccccccccccccccjjjrrrrrrrrpuuuxuvvqqqmmmmmddddccccc
   -1    16 abccccaaaaaaaaacccccccccccccccccaaaaaccccaacccaccccccccaaccjjjrrrruuuuuuuxxyvvqqqqqmmmmmdddcccc
   -1    17 abccccaaaaaaaacccccccccaaaccccccaacaaccccaaacaacccaaacaaaccjjjrrrtuuuuuuuxxyvvvqqqqqmmmmdddcccc
   -1    18 abccaaaaaaaacccccccccccaaaaaccccccccccccccaaaaacccaaaaaaaccjjjrrttttxxxxxxyyvvvvvqqqqmmmmdeeccc
   -1    19 abccaaaccaaaccccccccaacaaaaacccccccccccccaaaaaacccaaaaaacccjjjrrtttxxxxxxxyyvvvvvvvqqqmmmeeeccc
   -1    20 abaaaaaaaaaacccaaaccaaaaaaaaaaaccaaaccccaaaaaaaacccaaaaaaaajjjqqrttxxxxxxxyyyyyyvvvqqqnnneeeccc
   -1    21 SbaaaaaaaaccccaaaaccaaaaaaaaaaaaaaaaacccaaaaaaaaccaaaaaaaaacjjjqqtttxxxxEzzyyyyvvvvqqqnnneeeccc
   -1    22 abcaaaaaacccccaaaaccccaaaaaaaccaaaaaaccccccaaccccaaaaaaaaaaciiiqqqtttxxxyyyyyyvvvvrrrnnneeecccc
   -1    23 abcaaaaaacccccaaaacccaaaaaaaaccaaaaaaccccccaaccccaaacaaacccciiiqqqqttxxyyyyyywvvvrrrnnneeeecccc
   -1    24 abcaaaaaaccccccccccccaaaaaaaaacaaaaacccccccccccccccccaaaccccciiiqqtttxxyyyyyywwrrrrnnnneeeccccc
   -1    25 abcaaacaacccccaacccccaaaaaaaaacaaaaacccccccccccccccccaaaccccciiiqqttxxxywwyyywwrrrnnnneeecccccc
   -1    26 abccccccccaaacaaccccccccccacccccccccccccccccccccccccccccccccciiqqqttxxwwwwwwywwrrrnnneeeccccccc
   -1    27 abccaacccccaaaaaccccccccccccccccccccccccccccccccccccccccaacaaiiqqqttwwwwsswwwwwrrrnnfffeccccccc
   -1    28 abaaaaccccccaaaaaacccccccccccccccccccccccccccccaaaccccccaaaaaiiqqqttssssssswwwwrrronfffaccccccc
   -1    29 abaaaaaacccaaaaaaacccccccccccccccccccccccccccaaaaaacccccaaaaaiiqqqssssssssssswrrrooofffaaaacccc
   -1    30 abaaaaaaccaaaaaacccccccccccccccccccccccccccccaaaaaacccccaaaaaiiqqqppssspppssssrrrooofffaaaacccc
   -1    31 abaaaaaaccaacaaacccccccccccccccccccccccccccccaaaaaacccccaaaaaiihpppppppppppossrrooofffaaaaacccc
   -1    32 abaaaaccccccccaacccccccccccccccccccccccccccccaaaaaccccccccaaahhhhppppppppppoooooooofffaaaaccccc
   -1    33 abaaaaccccccccccaacccccccccccccccccaaacccccccaaaaacccccccccccchhhhhhhhhhggpoooooooffffaaaaccccc
   -1    34 abccaacccccccacaaaccccccccccccccccaaaaacccccccccccccccccccccccchhhhhhhhhggggoooooffffaacaaacccc
   -1    35 abccccccccccaaaaacaaccccccccccccccaaaaaccccccccccccccccccccccccchhhhhhhhggggggggggffcaacccccccc
   -1    36 abccccccccccaaaaaaaaccccccccccccccaaaacccaacccccccccccaccccccccccccccaaaaaggggggggfcccccccccccc
   -1    37 abccccccccccccaaaaaccccaacccccccccaaaacaaaaccccccccaaaaccccccccccccccaaaacaaagggggcccccccccaccc
   -1    38 abcccccccccccaaaaacccccaacccccccccaaaaaaaaaccccccccaaaaaaccccccccccccaaaccaaaacccccccccccccaaac
   -1    39 abcccccccccccaacaaccaaaaaaaacccaaaaaaaaaaaccccccccccaaaaccccccccccccccaccccaaacccccccccccccaaaa
   -1    40 abccccccccccccccaaccaaaaaaaaccaaaaaaaaaaaccccccccccaaaaacccccccccccccccccccccacccccccccccccaaaa
   -1    41 abccccccccccccccccccccaaaaacccaaaaaaaaaaaacccccccccaacaacccccccccccccccccccccccccccccccccaaaaaa

diff --git a/2022/12/solution.rs b/2022/12/solution.rs

@@ -0,0 +1,81 @@
   -1     1 #[path = "../lib.rs"] mod lib;
   -1     2 
   -1     3 fn get_map() -> (Vec<Vec<u8>>, (usize, usize), (usize, usize)) {
   -1     4     let mut heights = vec![];
   -1     5     let mut start = (0, 0);
   -1     6     let mut end = (0, 0);
   -1     7 
   -1     8     for line in lib::iter_input() {
   -1     9         let mut row = vec![];
   -1    10         for b in line.bytes() {
   -1    11             match b {
   -1    12                 b'S' => {
   -1    13                     start = (row.len(), heights.len());
   -1    14                     row.push(b'a');
   -1    15                 },
   -1    16                 b'E' => {
   -1    17                     end = (row.len(), heights.len());
   -1    18                     row.push(b'z');
   -1    19                 },
   -1    20                 x => {
   -1    21                     row.push(x);
   -1    22                 },
   -1    23             }
   -1    24         }
   -1    25         heights.push(row);
   -1    26     }
   -1    27 
   -1    28     return (heights, start, end);
   -1    29 }
   -1    30 
   -1    31 fn get_siblings(x: usize, y: usize, rows: usize, cols: usize) -> Vec<(usize, usize)> {
   -1    32     let mut result = vec![];
   -1    33     if x > 0 {
   -1    34         result.push((x - 1, y));
   -1    35     }
   -1    36     if x + 1 < cols {
   -1    37         result.push((x + 1, y));
   -1    38     }
   -1    39     if y > 0 {
   -1    40         result.push((x, y - 1));
   -1    41     }
   -1    42     if y + 1 < rows {
   -1    43         result.push((x, y + 1));
   -1    44     }
   -1    45     return result;
   -1    46 }
   -1    47 
   -1    48 fn main() {
   -1    49     let (heights, start, end) = get_map();
   -1    50     let rows = heights.len();
   -1    51     let cols = heights[0].len();
   -1    52 
   -1    53     let mut queue = vec![end];
   -1    54     let mut m: Vec<Vec<u64>> = heights.iter().map(|row|
   -1    55         row.iter().map(|_| u64::MAX - 1).collect()
   -1    56     ).collect();
   -1    57 
   -1    58     m[end.1][end.0] = 0;
   -1    59 
   -1    60     while let Some((x, y)) = queue.pop() {
   -1    61         for (x1, y1) in get_siblings(x, y, rows, cols).into_iter() {
   -1    62             if heights[y1][x1] + 1 >= heights[y][x] && m[y1][x1] > m[y][x] + 1 {
   -1    63                 m[y1][x1] = m[y][x] + 1;
   -1    64                 queue.push((x1, y1));
   -1    65             }
   -1    66         }
   -1    67     }
   -1    68 
   -1    69     println!("part1: {}", m[start.1][start.0]);
   -1    70 
   -1    71     let mut min_a_distance = u64::MAX;
   -1    72     for y in 0..rows {
   -1    73         for x in 0..cols {
   -1    74             if heights[y][x] == b'a' && m[y][x] < min_a_distance {
   -1    75                 min_a_distance = m[y][x];
   -1    76             }
   -1    77         }
   -1    78     }
   -1    79 
   -1    80     println!("part2: {}", min_a_distance);
   -1    81 }

diff --git a/2022/12/test.txt b/2022/12/test.txt

@@ -0,0 +1,5 @@
   -1     1 Sabqponm
   -1     2 abcryxxl
   -1     3 accszExk
   -1     4 acctuvwj
   -1     5 abdefghi