LuisFadini
diff --git a/‎2024/day20/Cargo.toml
Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions b/‎2024/day20/Cargo.toml
Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
diff --git a/‎2024/day20/day20.rs
Copy file name to clipboard
+91Lines changed: 91 additions & 0 deletions b/‎2024/day20/day20.rs
Copy file name to clipboard
+91Lines changed: 91 additions & 0 deletions
diff --git a/‎2024/libs/utils/src/coordinates.rs
Copy file name to clipboardExpand all lines: 2024/libs/utils/src/coordinates.rs
+28Lines changed: 28 additions & 0 deletions b/‎2024/libs/utils/src/coordinates.rs
Copy file name to clipboardExpand all lines: 2024/libs/utils/src/coordinates.rs
+28Lines changed: 28 additions & 0 deletions
diff --git a/‎readme.md
Copy file name to clipboardExpand all lines: readme.md
+1Lines changed: 1 addition & 0 deletions b/‎readme.md
Copy file name to clipboardExpand all lines: readme.md
+1Lines changed: 1 addition & 0 deletions
@@ -0,0 +1,11 @@
+[package]
+name = "day20"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+utils = { workspace = true }
+
+[[bin]]
+name = "day20"
+path = "day20.rs"
@@ -0,0 +1,91 @@
+use std::collections::HashSet;
+
+use utils::{
+    self,
+    coordinates::{Direction, Point},
+};
+
+fn get_track(map: Vec<&str>, size: i32) -> Vec<Point<i32>> {
+    let mut walls = HashSet::<Point<i32>>::new();
+    let mut end_pos = Point { x: 0, y: 0 };
+    let mut track = vec![];
+
+    for (y, line) in (0..size).zip(map.iter().skip(1)) {
+        for (x, tile) in (0..size).zip(line.bytes().skip(1)) {
+            let point = Point {
+                x: x as i32,
+                y: y as i32,
+            };
+
+            match tile {
+                b'S' => {
+                    track.push(point);
+                }
+                b'E' => end_pos = point,
+                b'#' => {
+                    walls.insert(point);
+                }
+                _ => {}
+            };
+        }
+    }
+
+    while let Some(next_point) = Direction::CARDINAL
+        .iter()
+        .filter_map(|&dir| next_move(dir, *track.last().unwrap(), size))
+        .find(|&next| !walls.contains(&next) && (track.len() < 2 || track[track.len() - 2] != next))
+    {
+        track.push(next_point);
+
+        if next_point == end_pos {
+            break;
+        }
+    }
+
+    track
+}
+
+fn next_move(direction: Point<i32>, start: Point<i32>, size: i32) -> Option<Point<i32>> {
+    let next = start + direction;
+
+    match direction {
+        Direction::UP if start.y > 0 => Some(next),
+        Direction::RIGHT if start.x + 1 < size => Some(next),
+        Direction::DOWN if start.y + 1 < size => Some(next),
+        Direction::LEFT if start.x > 0 => Some(next),
+        _ => None,
+    }
+}
+
+fn find_cheats(track: Vec<Point<i32>>, min_saving: usize, max_cheat_time: usize) -> usize {
+    let mut res = 0;
+
+    for start in 0..track.len() {
+        for end in (start + min_saving)..track.len() {
+            let distance = track.get(start).unwrap().distance(track.get(end).unwrap());
+            if distance <= max_cheat_time && distance <= (end - start - min_saving) as usize {
+                res += 1;
+            }
+        }
+    }
+
+    res
+}
+
+fn part1(input: String) -> i32 {
+    let size = input.lines().count() - 1;
+    let track = get_track(input.lines().collect(), size as i32);
+
+    find_cheats(track, 100, 2) as i32
+}
+
+fn part2(input: String) -> i32 {
+    let size = input.lines().count() - 1;
+    let track = get_track(input.lines().collect(), size as i32);
+
+    find_cheats(track, 100, 20) as i32
+}
+
+fn main() {
+    utils::run(20, vec!["input.txt"], &part1, &part2);
+}
@@ -9,6 +9,16 @@ pub struct Point<T> {
     pub y: T,
 }
 
+impl<T: Sub<Output = T>+Copy>  Point<T>
+{
+    pub fn distance(&self, other: &Point<T>) -> usize
+    where
+        T: Into<i64>,
+    {
+        ((self.x - other.x).into().abs() + (self.y - other.y).into().abs()).try_into().unwrap()
+    }
+}
+
 impl<T: Add<Output = T> + Copy> Add for Point<T> {
     type Output = Point<T>;
     fn add(self, rhs: Point<T>) -> Point<T> {
@@ -99,4 +109,22 @@ impl Direction {
     pub const DOWN_LEFT: Point<i32> = Point { y: 1, x: -1 };
     pub const LEFT: Point<i32> = Point { y: 0, x: -1 };
     pub const NONE: Point<i32> = Point { y: 0, x: 0 };
+
+    pub const ALL: [Point<i32>; 8] = [
+        self::Direction::UP_LEFT,
+        self::Direction::UP,
+        self::Direction::UP_RIGHT,
+        self::Direction::RIGHT,
+        self::Direction::DOWN_RIGHT,
+        self::Direction::DOWN,
+        self::Direction::DOWN_LEFT,
+        self::Direction::LEFT,
+    ];
+
+    pub const CARDINAL: [Point<i32>; 4] = [
+        self::Direction::UP,
+        self::Direction::RIGHT,
+        self::Direction::DOWN,
+        self::Direction::LEFT,
+    ];
 }
@@ -29,6 +29,7 @@ Para esta edição, planejo usar três linguagens de programação: Rust, C e Ja
 | Dia 17 | [Rust](./2024/day17/day17.rs)                            |
 | Dia 18 | [Rust](./2024/day18/day18.rs)                            |
 | Dia 19 | [Rust](./2024/day19/day19.rs)                            |
+| Dia 20 | [Rust](./2024/day20/day20.rs)                            |
 
 ### 2023