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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
use std::mem::swap;
use std::collections::VecDeque;
#[derive(PartialEq, Clone)]
struct Board {
arr: Vec<Vec<u32>>,
zero: (usize, usize),
}
impl Board {
fn find_zero(board: &Vec<Vec<u32>>) -> (usize, usize) {
for i in 0..board.len() {
for j in 0..board[i].len() {
if board[i][j] == 0 {
return (i, j);
}
}
}
panic!("Couldn't find a zero inside {:?}", board);
}
fn new(board: Vec<Vec<u32>>) -> Board {
Board {
zero: Self::find_zero(&board),
arr: board,
}
}
fn can_move_zero(&self, direction: u32) -> bool {
match direction {
0 => self.zero.1 > 0,
1 => self.zero.1 < self.arr[self.zero.0].len() - 1,
2 => self.zero.0 > 0,
3 => self.zero.0 < self.arr.len() - 1,
_ => panic!("Unknown direction {}", direction),
}
}
fn dir_to_str(direction: u32) -> String {
match direction {
0 => "left".to_string(),
1 => "right".to_string(),
2 => "up".to_string(),
3 => "down".to_string(),
_ => panic!("Unknown direction {}", direction),
}
}
fn move_zero(&mut self, direction: u32) {
match direction {
0 => {
let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1);
swap(&mut left[self.zero.1 - 1], &mut right[0]);
self.zero.1 -= 1;
},
1 => {
let (left, right) = self.arr[self.zero.0].split_at_mut(self.zero.1 + 1);
swap(&mut left[self.zero.1 - 1], &mut right[0]);
self.zero.1 += 1;
},
2 => {
let (top, bottom) = self.arr.split_at_mut(self.zero.0);
swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
self.zero.0 -= 1;
},
3 => {
let (top, bottom) = self.arr.split_at_mut(self.zero.0 + 1);
swap(&mut top[self.zero.0 - 1][self.zero.1], &mut bottom[0][self.zero.1]);
self.zero.0 += 1;
},
_ => panic!("Unknown direction {}", direction),
}
}
}
#[derive(Clone)]
struct GraphNode {
board: Board,
adj: Vec<GraphNode>,
dist: u32,
path: Vec<String>,
}
impl PartialEq for GraphNode {
fn eq(&self, other: &Self) -> bool {
self.board == other.board
}
}
impl Eq for GraphNode {}
impl GraphNode {
fn new(board: Vec<Vec<u32>>, dist: u32, path: Vec<String>) -> GraphNode {
GraphNode {
board: Board::new(board),
adj: Vec::new(),
dist: dist,
path: path
}
}
}
pub struct Graph {
root: GraphNode,
}
impl Graph {
pub fn new(root_board: Vec<Vec<u32>>, goal: u32) -> Graph {
let mut G = Graph { root: GraphNode::new(root_board, 0, Vec::new()) };
let mut queue: VecDeque<&mut GraphNode> = VecDeque::new();
queue.push_back(&mut G.root);
let mut all_nodes: Vec<&GraphNode> = Vec::new();
while !queue.is_empty() {
let curr: &mut GraphNode = queue.pop_front().unwrap();
for direction in 0..4 {
if ! curr.board.can_move_zero(direction) { continue; }
let mut newnode: GraphNode = curr.clone().to_owned();
newnode.board.move_zero(direction);
newnode.path.push(Board::dir_to_str(direction));
// TODO: update distance
if all_nodes.iter().any(|&x| *x == newnode) { continue; }
curr.adj.push(newnode);
queue.push_back(curr.adj.last_mut().unwrap());
// all_nodes.push(curr.adj.last().unwrap());
}
}
G
}
}
|
