blob: 1584fc3f3a7fe471b7ff92e7f35551cf58862e60 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
use std::fs;
use std::path::Path;
use std::collections::BinaryHeap;
struct Cave {
width: usize,
layout: Vec<u32>
}
impl Cave {
fn astar(&self, start: usize, goal: usize) -> u32 {
let mut heap = BinaryHeap::new();
heap.push(start);
let mut prec = vec![0;self.layout.len()];
let mut cost = vec![u32::MAX;self.layout.len()];
cost[start] = 0;
while let Some(curr) = heap.pop() {
for neighbor in self.neighbors(curr) {
let newcost = cost[curr] + self.layout[neighbor];
if newcost < cost[neighbor] {
prec[neighbor] = curr;
cost[neighbor] = newcost;
if heap.iter().find(|&&n| n == neighbor).is_none() {
heap.push(neighbor);
}
}
}
}
cost[goal]
}
fn neighbors(&self, pos: usize) -> Vec<usize> {
let mut nbs = vec![];
if (pos+1) % self.width > 0 {
nbs.push(pos+1);
}
if pos % self.width > 0 {
nbs.push(pos-1);
}
if (pos+self.width) < self.layout.len() {
nbs.push(pos+self.width);
}
if pos >= self.width {
nbs.push(pos-self.width);
}
nbs
}
}
fn main() {
let input = Path::new("resources").join("input.txt");
let content = fs::read_to_string(input).expect("Unable to read input file");
let cave = parse_input(&content);
println!("Ex1: the result is {}", cave.astar(0,cave.layout.len()-1))
}
fn parse_input(input: &str) -> Cave {
let width = input.lines().next().unwrap().len();
let layout = input.lines().flat_map(|l| l.bytes().map(|b| (b-b'0') as u32)).collect();
Cave { width, layout }
}
#[cfg(test)]
mod tests {
use super::*;
const INPUT: &str = "1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581";
#[test]
fn example() {
let cave = parse_input(INPUT);
assert_eq!(40, cave.astar(0,cave.layout.len()-1));
}
}
|
