1 files changed, 120 insertions, 0 deletions
diff --git a/12/src/part-1.rs b/12/src/part-1.rs
new file mode 100644
index 0000000..2e70ef9
--- /dev/null
+++ b/12/src/part-1.rs
@@ -0,0 +1,120 @@
+mod tensor;
+
+use std::collections::{BinaryHeap};
+use std::io::{BufRead};
+
+use tensor::{Index, Shape, Tensor};
+
+#[derive(Debug)]
+struct Node {
+    idx: [usize; 2],
+    cost: usize
+}
+
+impl Node {
+    fn new(idx: [usize; 2], cost: usize) -> Self {
+        Self {
+            idx: idx,
+            cost: cost
+        }
+    }
+}
+
+impl PartialEq for Node {
+    fn ne(self: & Self, other: & Self) -> bool {
+        self.cost != other.cost
+    }
+    fn eq(self: & Self, other: & Self) -> bool {
+        self.cost == other.cost
+    }
+}
+
+impl Eq for Node {
+}
+
+impl PartialOrd for Node {
+    fn partial_cmp(self: & Self, other: & Self) -> Option<std::cmp::Ordering> {
+        other.cost.partial_cmp(& self.cost)
+    }
+}
+
+impl Ord for Node {
+    fn cmp(self: & Self, other: & Self) -> std::cmp::Ordering {
+        other.cost.cmp(& self.cost)
+    }
+}
+
+fn main() {
+    let stdin = std::io::stdin();
+    let mut handle = stdin.lock();
+
+    let mut buf: Vec<u8> = Vec::new();
+
+    let mut tmp: Vec<(u8, bool)> = Vec::new();
+    let mut m: usize = 0;
+    let mut n: usize = 0;
+    let mut n_check: usize = 0;
+
+    loop {
+        let buf = handle.fill_buf().expect("IO error");
+        let bytes_read = buf.len();
+        if bytes_read == 0 { break; }
+
+        for & b in buf.into_iter() {
+            if b == b'\n' {
+                m += 1;
+                assert_eq!(n_check, n);
+                n_check = 0;
+            }
+            else {
+                tmp.push((b, false));
+                if m == 0 {
+                    n += 1;
+                }
+                n_check += 1;
+            }
+        }
+
+        handle.consume(bytes_read);
+    }
+    let mut terrain: Tensor<(u8, bool), 2> = Tensor::new_from([m, n], tmp);
+
+    let mut unvisited: BinaryHeap<Node> = BinaryHeap::new();
+    let mut done: bool = false;
+    let mut res: usize = usize::MAX;
+
+    for i in 0..m {
+        for j in 0..n {
+            if terrain[[i, j]].0 == b'S' {
+                unvisited.push(Node::new([i, j], 0));
+            }
+        }
+    }
+
+    while let Some(node) = unvisited.pop() {
+        let idx = node.idx;
+        if !terrain[idx].1 {
+            let elev = terrain[idx].0;
+            let neighbor_idxs = [[idx[0].wrapping_sub(1), idx[1]                ],
+                                 [idx[0] + 1            , idx[1]                ],
+                                 [idx[0]                , idx[1].wrapping_sub(1)],
+                                 [idx[0]                , idx[1] + 1            ]];
+            for neighbor_idx in neighbor_idxs.into_iter() {
+                if let Some(& (x, v)) = terrain.el(& neighbor_idx) {
+                    if x == b'E' && (elev == b'y' || elev == b'z') { // The end node has elevation z.
+                        res = node.cost + 1;
+                        done = true;
+                        break;
+                    }
+                    if !v && (x < elev || x - elev <= 1 || elev == b'S') {
+                        unvisited.push(Node::new(neighbor_idx.clone(), node.cost + 1));
+                    }
+                }
+            }
+            terrain[idx].1 = true;
+        }
+        if done { break; }
+    }
+
+    println!("{}", res);
+}