Added ex075 Quiz 8

4 files changed, 237 insertions, 10 deletions

diff --git a/README.md b/README.md
index 3a874d2..a6792fd 100644
--- a/README.md
+++ b/README.md
@@ -117,6 +117,8 @@ the learning resource I wished for. There will be tons of room for improvement:
 
 Planned exercises:
 
+Core Language
+
 * [x] Hello world (main needs to be public)
 * [x] Importing standard library
 * [x] Assignment
@@ -142,18 +144,24 @@ Planned exercises:
 * [x] Labelled blocks and loops
 * [x] Loops as expressions
 * [x] Builtins
-* [ ] Comptime (!)
-* [ ] Inline loops
+* [x] Inline loops
+* [x] Comptime
 * [ ] Anonymous structs
 * [ ] Sentinel termination
-* [ ] Vectors
+* [ ] Suspend / Resume
+* [ ] Async / Await
+* [ ] Nosuspend
+* [ ] Async Frames, Suspend Blocks
+* [ ] Working with C?
+
+Modules and the Zig Standard Library
+
 * [ ] Imports
 * [ ] Allocators
 * [ ] Arraylist
 * [ ] Filesystem
 * [ ] Readers and Writers
 * [ ] Formatting
-* [ ] JSON
 * [ ] Random Numbers
 * [ ] Crypto
 * [ ] Threads
@@ -161,12 +169,6 @@ Planned exercises:
 * [ ] Stacks
 * [ ] Sorting
 * [ ] Iterators
-* [ ] Formatting specifiers
-* [ ] Advanced Formatting
-* [ ] Suspend / Resume
-* [ ] Async / Await
-* [ ] Nosuspend
-* [ ] Async Frames, Suspend Blocks
 
 The initial topics for these exercises were unabashedly cribbed from
 [ziglearn.org](https://ziglearn.org/). I've since moved things around
diff --git a/build.zig b/build.zig
index 9581e17..f427b98 100644
--- a/build.zig
+++ b/build.zig
@@ -370,6 +370,15 @@ const exercises = [_]Exercise{
         .main_file = "073_comptime8.zig",
         .output = "My llama value is 25.",
     },
+    .{
+        .main_file = "074_comptime9.zig",
+        .output = "My llama value is 2.",
+    },
+    .{
+        .main_file = "075_quiz8.zig",
+        .output = "Archer's Point--2->Bridge--1->Dogwood Grove--3->Cottage--2->East Pond--1->Fox Pond",
+        .hint = "Roll up those sleeves. You get to WRITE some code for this one.",
+    },
 };
 
 /// Check the zig version to make sure it can compile the examples properly.
diff --git a/exercises/075_quiz8.zig b/exercises/075_quiz8.zig
new file mode 100644
index 0000000..14fab18
--- /dev/null
+++ b/exercises/075_quiz8.zig
@@ -0,0 +1,208 @@
+//
+// 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 print(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) |*entry, i| {
+            if (i >= self.end_of_entries) break;
+            if (place == entry.*.?.place) return &entry.*.?;
+        }
+        return null;
+    }
+
+    fn checkNote(self: *HermitsNotebook, note: NotebookEntry) void {
+        var 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
+
+    // TODO: can we neaten this up????
+    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..];
+
+    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()) {
+        var 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(u8, trip.len);
+
+    while (i > 0) {
+        i -= 1;
+        if (trip[i] == null) continue;
+        trip[i].?.print();
+    }
+
+    print("\n", .{});
+}
diff --git a/patches/patches/075_quiz8.patch b/patches/patches/075_quiz8.patch
new file mode 100644
index 0000000..ce6a2d8
--- /dev/null
+++ b/patches/patches/075_quiz8.patch
@@ -0,0 +1,8 @@
+52c52,56
+< 
+---
+>     return Path{
+>         .from = from,
+>         .to = to,
+>         .dist = dist,
+>     };