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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
//
// Quiz Time!
//
// Let's revisit the Hermit's Map from Quiz 7.
//
// Oh, don't worry, it's not nearly as big without all the
// explanatory comments. And we're only going to change one part
// of it.
//
const print = @import("std").debug.print;
const TripError = error{ Unreachable, EatenByAGrue };
const Place = struct {
name: []const u8,
paths: []const Path = undefined,
};
var a = Place{ .name = "Archer's Point" };
var b = Place{ .name = "Bridge" };
var c = Place{ .name = "Cottage" };
var d = Place{ .name = "Dogwood Grove" };
var e = Place{ .name = "East Pond" };
var f = Place{ .name = "Fox Pond" };
// Remember how we didn't have to declare the numeric type of the
// place_count because it is only used at compile time? That
// probably makes a lot more sense now. :-)
const place_count = 6;
const Path = struct {
from: *const Place,
to: *const Place,
dist: u8,
};
// Okay, so as you may recall, we had to create each Path struct
// by hand and each one took 5 lines of code to define:
//
// Path{
// .from = &a, // from: Archer's Point
// .to = &b, // to: Bridge
// .dist = 2,
// },
//
// Well, armed with the knowledge that we can run code at compile
// time, we can perhaps shorten this a bit with a simple function
// instead.
//
// Please fill in the body of this function!
fn makePath(from: *Place, to: *Place, dist: u8) Path {
}
// Using our new function, these path definitions take up considerably less
// space in our program now!
const a_paths = [_]Path{makePath(&a, &b, 2)};
const b_paths = [_]Path{ makePath(&b, &a, 2), makePath(&b, &d, 1) };
const c_paths = [_]Path{ makePath(&c, &d, 3), makePath(&c, &e, 2) };
const d_paths = [_]Path{ makePath(&d, &b, 1), makePath(&d, &c, 3), makePath(&d, &f, 7) };
const e_paths = [_]Path{ makePath(&e, &c, 2), makePath(&e, &f, 1) };
const f_paths = [_]Path{makePath(&f, &d, 7)};
//
// But is it more readable? That could be argued either way.
//
// We've seen that it is possible to parse strings at compile
// time, so the sky's really the limit on how fancy we could get
// with this.
//
// For example, we could create our own "path language" and
// create Paths from that. Something like this, perhaps:
//
// a -> (b[2])
// b -> (a[2] d[1])
// c -> (d[3] e[2])
// ...
//
// Feel free to implement something like that as a SUPER BONUS EXERCISE!
const TripItem = union(enum) {
place: *const Place,
path: *const Path,
fn printMe(self: TripItem) void {
switch (self) {
.place => |p| print("{s}", .{p.name}),
.path => |p| print("--{}->", .{p.dist}),
}
}
};
const NotebookEntry = struct {
place: *const Place,
coming_from: ?*const Place,
via_path: ?*const Path,
dist_to_reach: u16,
};
const HermitsNotebook = struct {
entries: [place_count]?NotebookEntry = .{null} ** place_count,
next_entry: u8 = 0,
end_of_entries: u8 = 0,
fn getEntry(self: *HermitsNotebook, place: *const Place) ?*NotebookEntry {
for (&self.entries, 0..) |*entry, i| {
if (i >= self.end_of_entries) break;
if (place == entry.*.?.place) return &entry.*.?;
}
return null;
}
fn checkNote(self: *HermitsNotebook, note: NotebookEntry) void {
const existing_entry = self.getEntry(note.place);
if (existing_entry == null) {
self.entries[self.end_of_entries] = note;
self.end_of_entries += 1;
} else if (note.dist_to_reach < existing_entry.?.dist_to_reach) {
existing_entry.?.* = note;
}
}
fn hasNextEntry(self: *HermitsNotebook) bool {
return self.next_entry < self.end_of_entries;
}
fn getNextEntry(self: *HermitsNotebook) *const NotebookEntry {
defer self.next_entry += 1;
return &self.entries[self.next_entry].?;
}
fn getTripTo(self: *HermitsNotebook, trip: []?TripItem, dest: *Place) TripError!void {
const destination_entry = self.getEntry(dest);
if (destination_entry == null) {
return TripError.Unreachable;
}
var current_entry = destination_entry.?;
var i: u8 = 0;
while (true) : (i += 2) {
trip[i] = TripItem{ .place = current_entry.place };
if (current_entry.coming_from == null) break;
trip[i + 1] = TripItem{ .path = current_entry.via_path.? };
const previous_entry = self.getEntry(current_entry.coming_from.?);
if (previous_entry == null) return TripError.EatenByAGrue;
current_entry = previous_entry.?;
}
}
};
pub fn main() void {
const start = &a; // Archer's Point
const destination = &f; // Fox Pond
// We could either have this:
//
// a.paths = a_paths[0..];
// b.paths = b_paths[0..];
// c.paths = c_paths[0..];
// d.paths = d_paths[0..];
// e.paths = e_paths[0..];
// f.paths = f_paths[0..];
//
// or this comptime wizardry:
//
const letters = [_][]const u8{ "a", "b", "c", "d", "e", "f" };
inline for (letters) |letter| {
@field(@This(), letter).paths = @field(@This(), letter ++ "_paths")[0..];
}
var notebook = HermitsNotebook{};
var working_note = NotebookEntry{
.place = start,
.coming_from = null,
.via_path = null,
.dist_to_reach = 0,
};
notebook.checkNote(working_note);
while (notebook.hasNextEntry()) {
const place_entry = notebook.getNextEntry();
for (place_entry.place.paths) |*path| {
working_note = NotebookEntry{
.place = path.to,
.coming_from = place_entry.place,
.via_path = path,
.dist_to_reach = place_entry.dist_to_reach + path.dist,
};
notebook.checkNote(working_note);
}
}
var trip = [_]?TripItem{null} ** (place_count * 2);
notebook.getTripTo(trip[0..], destination) catch |err| {
print("Oh no! {}\n", .{err});
return;
};
printTrip(trip[0..]);
}
fn printTrip(trip: []?TripItem) void {
var i: u8 = @intCast(trip.len);
while (i > 0) {
i -= 1;
if (trip[i] == null) continue;
trip[i].?.printMe();
}
print("\n", .{});
}
|
