adventofcode

commit

10a3f14f9ce5cd83e849c9868fbe88b7a76fad42

parent

d94a3b4129af946d8981c9031efee339de9454c0

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2024-12-21 10:22

2024-12-21

Diffstat

3 files changed, 144 insertions, 0 deletions

diff --git a/2024/21/input.txt b/2024/21/input.txt

@@ -0,0 +1,5 @@
   -1     1 208A
   -1     2 586A
   -1     3 341A
   -1     4 463A
   -1     5 593A

diff --git a/2024/21/solution.rs b/2024/21/solution.rs

@@ -0,0 +1,134 @@
   -1     1 use std::collections::HashMap;
   -1     2 
   -1     3 #[path = "../lib.rs"]
   -1     4 mod lib;
   -1     5 
   -1     6 #[derive(Eq, Hash, PartialEq, Clone, Copy)]
   -1     7 enum Dir {
   -1     8     Left,
   -1     9     Down,
   -1    10     Right,
   -1    11     Up,
   -1    12     A,
   -1    13 }
   -1    14 
   -1    15 fn get_pos_dir(v: Dir) -> (usize, usize) {
   -1    16     return match v {
   -1    17         Dir::Left => (0, 0),
   -1    18         Dir::Down => (1, 0),
   -1    19         Dir::Right => (2, 0),
   -1    20         Dir::Up => (1, 1),
   -1    21         Dir::A => (2, 1),
   -1    22     };
   -1    23 }
   -1    24 
   -1    25 fn get_pos_numeric(v: u8) -> (usize, usize) {
   -1    26     return match v {
   -1    27         b'0' => (1, 1),
   -1    28         b'A' => (2, 1),
   -1    29         b'1' => (0, 2),
   -1    30         b'2' => (1, 2),
   -1    31         b'3' => (2, 2),
   -1    32         b'4' => (0, 3),
   -1    33         b'5' => (1, 3),
   -1    34         b'6' => (2, 3),
   -1    35         b'7' => (0, 4),
   -1    36         b'8' => (1, 4),
   -1    37         b'9' => (2, 4),
   -1    38         _ => unreachable!(),
   -1    39     };
   -1    40 }
   -1    41 
   -1    42 fn press(x1: usize, y1: usize, x2: usize, y2: usize, steps: usize, cache: &mut HashMap<(Dir, Dir, usize), usize>) -> usize {
   -1    43     let mut count1 = 0;
   -1    44     let mut count2 = 0;
   -1    45 
   -1    46     if x2 == 0 && y1 == 1 {
   -1    47         count1 = usize::MAX;
   -1    48     } else {
   -1    49         let mut pos = Dir::A;
   -1    50         for _ in x1..x2 {
   -1    51             count1 += press_dir(Dir::Right, pos, steps - 1, cache);
   -1    52             pos = Dir::Right;
   -1    53         }
   -1    54         for _ in x2..x1 {
   -1    55             count1 += press_dir(Dir::Left, pos, steps - 1, cache);
   -1    56             pos = Dir::Left;
   -1    57         }
   -1    58         for _ in y1..y2 {
   -1    59             count1 += press_dir(Dir::Up, pos, steps - 1, cache);
   -1    60             pos = Dir::Up;
   -1    61         }
   -1    62         for _ in y2..y1 {
   -1    63             count1 += press_dir(Dir::Down, pos, steps - 1, cache);
   -1    64             pos = Dir::Down;
   -1    65         }
   -1    66         count1 += press_dir(Dir::A, pos, steps - 1, cache);
   -1    67     }
   -1    68 
   -1    69     if x1 == 0 && y2 == 1 {
   -1    70         count2 = usize::MAX;
   -1    71     } else {
   -1    72         let mut pos = Dir::A;
   -1    73         for _ in y1..y2 {
   -1    74             count2 += press_dir(Dir::Up, pos, steps - 1, cache);
   -1    75             pos = Dir::Up;
   -1    76         }
   -1    77         for _ in y2..y1 {
   -1    78             count2 += press_dir(Dir::Down, pos, steps - 1, cache);
   -1    79             pos = Dir::Down;
   -1    80         }
   -1    81         for _ in x1..x2 {
   -1    82             count2 += press_dir(Dir::Right, pos, steps - 1, cache);
   -1    83             pos = Dir::Right;
   -1    84         }
   -1    85         for _ in x2..x1 {
   -1    86             count2 += press_dir(Dir::Left, pos, steps - 1, cache);
   -1    87             pos = Dir::Left;
   -1    88         }
   -1    89         count2 += press_dir(Dir::A, pos, steps - 1, cache);
   -1    90     }
   -1    91 
   -1    92     return count1.min(count2);
   -1    93 }
   -1    94 
   -1    95 fn press_dir(button: Dir, prev: Dir, steps: usize, cache: &mut HashMap<(Dir, Dir, usize), usize>) -> usize {
   -1    96     if steps == 0 {
   -1    97         return 1;
   -1    98     } else if let Some(count) = cache.get(&(button, prev, steps)) {
   -1    99         return *count;
   -1   100     } else {
   -1   101         let (x1, y1) = get_pos_dir(prev);
   -1   102         let (x2, y2) = get_pos_dir(button);
   -1   103         let count = press(x1, y1, x2, y2, steps, cache);
   -1   104         cache.insert((button, prev, steps), count);
   -1   105         return count;
   -1   106     }
   -1   107 }
   -1   108 
   -1   109 fn get_sequence(code: &str, steps: usize, cache: &mut HashMap<(Dir, Dir, usize), usize>) -> usize {
   -1   110     let mut pos = b'A';
   -1   111     let mut count = 0;
   -1   112     for b in code.bytes() {
   -1   113         let (x1, y1) = get_pos_numeric(pos);
   -1   114         let (x2, y2) = get_pos_numeric(b);
   -1   115         count += press(x1, y1, x2, y2, steps, cache);
   -1   116         pos = b;
   -1   117     }
   -1   118     return count;
   -1   119 }
   -1   120 
   -1   121 fn main() {
   -1   122     let mut sum1 = 0;
   -1   123     let mut sum2 = 0;
   -1   124     let mut cache = HashMap::new();
   -1   125 
   -1   126     for line in lib::iter_input() {
   -1   127         let value = line[..line.len() - 1].parse::<usize>().unwrap();
   -1   128         sum1 += get_sequence(&line, 2 + 1, &mut cache) * value;
   -1   129         sum2 += get_sequence(&line, 25 + 1, &mut cache) * value;
   -1   130     }
   -1   131 
   -1   132     println!("part1: {}", sum1);
   -1   133     println!("part2: {}", sum2);
   -1   134 }

diff --git a/2024/21/test.txt b/2024/21/test.txt

@@ -0,0 +1,5 @@
   -1     1 029A
   -1     2 980A
   -1     3 179A
   -1     4 456A
   -1     5 379A