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
|
//! A small graph and a breadth-first search over it. `dist` and `queue` are
//! exported globals, so a tracer finds them by name and watches them fill.
//! Exits with the sum of the distances from node 0 (18).
const n = 8;
const unreached = 0xff;
const edges = [_][2]u8{ .{ 0, 1 }, .{ 0, 2 }, .{ 1, 3 }, .{ 2, 3 }, .{ 3, 4 }, .{ 4, 5 }, .{ 5, 6 }, .{ 2, 7 } };
/// Aligned so that it is one machine word to a watcher.
export var dist: [n]u8 align(8) = @splat(unreached);
export var queue: [n]u8 = @splat(0);
fn linked(a: u8, b: u8) bool {
for (edges) |e| {
if ((e[0] == a and e[1] == b) or (e[0] == b and e[1] == a)) return true;
}
return false;
}
fn bfs(start: u8) void {
var head: usize = 0;
var tail: usize = 1;
queue[0] = start;
dist[start] = 0;
while (head < tail) : (head += 1) {
const at = queue[head];
for (0..n) |next| {
if (dist[next] != unreached or !linked(at, @intCast(next))) continue;
dist[next] = dist[at] + 1;
queue[tail] = @intCast(next);
tail += 1;
}
}
}
pub fn main() u8 {
bfs(0);
var sum: u8 = 0;
for (dist) |d| sum += d;
return sum;
}
|