//! 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; }