From 3b877bf4cc667eb8bcc787d145203600a4dba2d2 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sat, 25 Feb 2023 11:41:27 +0100
Subject: Initial commit

---
 d13/Cargo.toml  |  6 +++++
 d13/src/main.rs | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 85 insertions(+)
 create mode 100644 d13/Cargo.toml
 create mode 100644 d13/src/main.rs

(limited to 'd13')

diff --git a/d13/Cargo.toml b/d13/Cargo.toml
new file mode 100644
index 0000000..2bab20e
--- /dev/null
+++ b/d13/Cargo.toml
@@ -0,0 +1,6 @@
+[package]
+name = "d13"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
diff --git a/d13/src/main.rs b/d13/src/main.rs
new file mode 100644
index 0000000..52ef4ce
--- /dev/null
+++ b/d13/src/main.rs
@@ -0,0 +1,79 @@
+use std::collections::VecDeque;
+
+fn is_space(seed: usize, (x, y): (usize, usize)) -> bool {
+    let sum = x*x + 3*x + 2*x*y + y + y*y + seed;
+    let bin = format!("{:#b}", sum);
+    bin.matches('1').count() % 2 == 0
+}
+
+fn solve_puzzle(seed: usize, part1_goal: (usize, usize), part2_limit: usize) -> (usize, usize) {
+    let mut part1_found = false;
+    let mut part1_depth = 0;
+    let mut part2_count = 1;
+
+    // Breadth-first search of the maze
+    let start = (1, 1);
+    let mut visited = vec![start];
+    let mut queue = VecDeque::from([(start, 0)]);
+    loop {
+        let (pos, depth) = queue.pop_front().unwrap();
+
+        // Is this the shortest path to `part1_goal'?
+        if pos == part1_goal && !part1_found {
+            part1_found = true;
+            part1_depth = depth;
+        }
+        // Have we found all the information we want?
+        if depth > part2_limit && part1_found {
+            return (part1_depth, part2_count);
+        }
+
+        // The grid extends infinitely far in the positive directions
+        let mut adjacents = vec![
+            (pos.0 + 1, pos.1),
+            (pos.0, pos.1 + 1),
+        ];
+        if pos.0 > 0 {
+            adjacents.push((pos.0 - 1, pos.1));
+        }
+        if pos.1 > 0 {
+            adjacents.push((pos.0, pos.1 - 1));
+        }
+
+        for adj in adjacents {
+            // Is this a valid move to a space we haven't visited before?
+            if is_space(seed, adj) && !visited.contains(&adj) {
+                visited.push(adj);
+                queue.push_back((adj, depth + 1));
+
+                // Count locations reachable in at most `part2_limit' steps
+                if depth < part2_limit {
+                    part2_count += 1;
+                }
+            }
+        }
+    }
+}
+
+fn main() {
+    // My personal puzzle input
+    let seed = 1358;
+
+    let (part1, part2) = solve_puzzle(seed, (31, 39), 50);
+
+    // Part 1 gives 96 for me
+    println!("Part 1 solution: {}", part1);
+
+    // Part 2 gives 141 for me
+    println!("Part 2 solution: {}", part2);
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1_example1() {
+        assert_eq!(solve_puzzle(10, (7, 4), 42).0, 11);
+    }
+}
-- 
cgit v1.2.3