From 38b6de1e7156ad8b92284273f544ab1b8a803b49 Mon Sep 17 00:00:00 2001 From: Dave Gauer Date: Sun, 4 Apr 2021 16:05:44 -0400 Subject: Added epic ex058 - quiz 7 --- exercises/058_quiz7.zig | 458 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 458 insertions(+) create mode 100644 exercises/058_quiz7.zig (limited to 'exercises/058_quiz7.zig') diff --git a/exercises/058_quiz7.zig b/exercises/058_quiz7.zig new file mode 100644 index 0000000..bbbe1a0 --- /dev/null +++ b/exercises/058_quiz7.zig @@ -0,0 +1,458 @@ +// +// We've absorbed a lot of information about the variations of types +// we can use in Zig. Roughly, in order we have: +// +// u8 single item +// *u8 single-item pointer +// []u8 slice (size known at runtime) +// [5]u8 array of 5 u8s +// [*]u8 many-item pointer (zero or more) +// enum {a, b} set of unique values a and b +// error {e, f} set of unique error values e and f +// struct {y: u8, z: i32} group of values y and z +// union(enum) {a: u8, b: i32} single value either u8 or i32 +// +// Values of any of the above types can be assigned as "var" or "const" +// to allow or disallow changes (mutability) via the assigned name: +// +// const a: u8 = 5; // immutable +// var b: u8 = 5; // mutable +// +// We can also make error unions or optional types from any of +// the above: +// +// var a: E!u8 = 5; // can be u8 or error from set E +// var b: ?u8 = 5; // can be u8 or null +// +// Knowing all of this, maybe we can help out a local hermit. He made +// a little Zig program to help him plan his trips through the woods, +// but it has some mistakes. +// +const print = @import("std").debug.print; + +// The grue is a nod to Zork. +const TripError = error{ Unreachable, EatenByAGrue }; + +// Let's start with the Places on the map. Each has a name and a +// distance or difficulty of travel (as judged by the hermit). +// +// Note that we declare the places as mutable (var) because we need to +// assign the paths later. And why is that? Because paths contain +// pointers to places and assigning them now would create a dependency +// loop! +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" }; + +// The hermit's hand-drawn ASCII map +// +---------------------------------------------------+ +// | * Archer's Point ~~~~ | +// | ~~~ ~~~~~~~~ | +// | ~~~| |~~~~~~~~~~~~ ~~~~~~~ | +// | Bridge ~~~~~~~~ | +// | ^ ^ ^ | +// | ^ ^ / \ | +// | ^ ^ ^ ^ |_| Cottage | +// | Dogwood Grove | +// | ^ | +// | ^ ^ ^ ^ ~~~~~~~~~~~~~ ^ ^ | +// | ^ ~~ East Pond ~~~ | +// | ^ ^ ^ ~~~~~~~~~~~~~~ | +// | ~~ ^ | +// | ^ ~~~ <-- short waterfall | +// | ^ ~~~~~ | +// | ~~~~~~~~~~~~~~~~~ | +// | ~~~~ Fox Pond ~~~~~~~ ^ ^ | +// | ^ ~~~~~~~~~~~~~~~ ^ ^ | +// | ~~~~~ | +// +---------------------------------------------------+ +// +// We'll be reserving memory in our program based on the number of +// places on the map. Note that we do not have to specify the type of +// this value because we don't actually use it in our program once +// it's compiled! (Don't worry if this doesn't make sense yet.) +const place_count = 6; + +// Now let's create all of the paths between sites. A path goes from +// one place to another and has a distance. +const Path = struct { + from: *const Place, + to: *const Place, + dist: u8, +}; + +// By the way, if the following code seems like a lot of tedious +// manual labor, you're right! One of Zig's killer features is letting +// us write code that runs at compile time to "automate" repetitive +// code (much like macros in other languages), but we haven't learned +// how to do that yet! +const a_paths = [_]Path{ + Path{ + .from = &a, // from: Archer's Point + .to = &b, // to: Bridge + .dist = 2, + }, +}; + +const b_paths = [_]Path{ + Path{ + .from = &b, // from: Bridge + .to = &a, // to: Archer's Point + .dist = 2, + }, + Path{ + .from = &b, // from: Bridge + .to = &d, // to: Dogwood Grove + .dist = 1, + }, +}; + +const c_paths = [_]Path{ + Path{ + .from = &c, // from: Cottage + .to = &d, // to: Dogwood Grove + .dist = 3, + }, + Path{ + .from = &c, // from: Cottage + .to = &e, // to: East Pond + .dist = 2, + }, +}; + +const d_paths = [_]Path{ + Path{ + .from = &d, // from: Dogwood Grove + .to = &b, // to: Bridge + .dist = 1, + }, + Path{ + .from = &d, // from: Dogwood Grove + .to = &c, // to: Cottage + .dist = 3, + }, + Path{ + .from = &d, // from: Dogwood Grove + .to = &f, // to: Fox Pond + .dist = 7, + }, +}; + +const e_paths = [_]Path{ + Path{ + .from = &e, // from: East Pond + .to = &c, // to: Cottage + .dist = 2, + }, + Path{ + .from = &e, // from: East Pond + .to = &f, // to: Fox Pond + .dist = 1, // (one-way down a short waterfall!) + }, +}; + +const f_paths = [_]Path{ + Path{ + .from = &f, // from: Fox Pond + .to = &d, // to: Dogwood Grove + .dist = 7, + }, +}; + +// Once we've plotted the best course through the woods, we'll make a +// "trip" out of it. A trip is a series of Places connected by Paths. +// We use a TripItem union to allow both Places and Paths to be in the +// same array. +const TripItem = union(enum) { + place: *const Place, + path: *const Path, + + // This is a little helper function to print the two different + // types of item correctly. Note how this "print()" is namespaced + // to the TripItem union and doesn't interfere with calling the + // "print()" from the standard library we imported at the top of + // this program. + fn print(self: TripItem) void { + switch (self) { + // Oops! The hermit forgot how to capture the union values + // in a switch statement. Please capture both values as + // 'p' so the print statements work! + .place => print("{s}", .{p.name}), + .path => print("--{}->", .{p.dist}), + } + } +}; + +// The Hermit's Notebook is where all the magic happens. A notebook +// entry is a Place discovered on the map along with the Path taken to +// get there and the distance to reach it from the start point. If we +// find a better Path to reach a Place (lower distance), we update the +// entry. Entries also serve as a "todo" list which is how we keep +// track of which paths to explore next. +const NotebookEntry = struct { + place: *const Place, + coming_from: ?*const Place, + via_path: ?*const Path, + dist_to_reach: u16, +}; + +// +------------------------------------------------+ +// | ~ Hermit's Notebook ~ | +// +---+----------------+----------------+----------+ +// | | Place | From | Distance | +// +---+----------------+----------------+----------+ +// | 0 | Archer's Point | null | 0 | +// | 1 | Bridge | Archer's Point | 2 | < next_entry +// | 2 | Dogwood Grove | Bridge | 1 | +// | 3 | | | | < end_of_entries +// | ... | +// +---+----------------+----------------+----------+ +// +const HermitsNotebook = struct { + // Remember the array repetition operator `**`? It is no mere + // novelty, it's also a great way to assign multiple items in an + // array without having to list them one by one. Here we use it to + // initialize an array with null values. + entries: [place_count]?NotebookEntry = .{null} ** place_count, + + // The next entry keeps track of where we are in our "todo" list. + next_entry: u8 = 0, + + // Mark the start of empty space in the notebook. + end_of_entries: u8 = 0, + + // We'll often want to find an entry by Place. If one is not + // found, we return null. + fn getEntry(self: *HermitsNotebook, place: *const Place) ?*NotebookEntry { + for (self.entries) |*entry, i| { + if (i >= self.end_of_entries) break; + + // Here's where the hermit got stuck. We need to return + // an optional pointer to a NotebookEntry. + // + // What we have with "entry" is the opposite: a pointer to + // an optional NotebookEntry! + // + // To get one from the other, we need to dereference + // "entry" (with .*) and get the non-null value from the + // optional (with .?) and return the address of that. The + // if statement provides some clues about how the + // dereference and optional value "unwrapping" look + // together. Remember that you return the address with the + // "&" operator. + if (place == entry.*.?.place) return entry; + // Try to make your answer this long:__________; + } + return null; + } + + // The checkNote() method is the beating heart of the magical + // notebook. Given a new note in the form of a NotebookEntry + // struct, we check to see if we already have an entry for the + // note's Place. + // + // If we DON'T, we'll add the entry to the end of the notebook + // along with the Path taken and distance. + // + // If we DO, we check to see if the path is "better" (shorter + // distance) than the one we'd noted before. If it is, we + // overwrite the old entry with the new one. + 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; + } + } + + // The next two methods allow us to use the notebook as a "todo" + // list. + fn hasNextEntry(self: *HermitsNotebook) bool { + return self.next_entry < self.end_of_entries; + } + + fn getNextEntry(self: *HermitsNotebook) *const NotebookEntry { + defer self.next_entry += 1; // Increment after getting entry + return &self.entries[self.next_entry].?; + } + + // After we've completed our search of the map, we'll have + // computed the shortest Path to every Place. To collect the + // complete trip from the start to the destination, we need to + // walk backwards from the destination's notebook entry, following + // the coming_from pointers back to the start. What we end up with + // is an array of TripItems with our trip in reverse order. + // + // We need to take the trip array as a parameter because we want + // the main() function to "own" the array memory. What do you + // suppose could happen if we allocated the array in this + // function's stack frame (the space allocated for a function's + // "local" data) and returned a pointer or slice to it? + // + // Looks like the hermit forgot something in the return value of + // this function. What could that be? + fn getTripTo(self: *HermitsNotebook, trip: []?TripItem, dest: *Place) void { + // We start at the destination entry. + const destination_entry = self.getEntry(dest); + + // This function needs to return an error if the requested + // destination was never reached. (This can't actually happen + // in our map since every Place is reachable by every other + // Place.) + if (destination_entry == null) { + return TripError.Unreachable; + } + + // Variables hold the entry we're currently examining and an + // index to keep track of where we're appending trip items. + var current_entry = destination_entry.?; + var i: u8 = 0; + + // At the end of each looping, a continue expression increments + // our index. Can you see why we need to increment by two? + while (true) : (i += 2) { + trip[i] = TripItem{ .place = current_entry.place }; + + // An entry "coming from" nowhere means we've reached the + // start, so we're done. + if (current_entry.coming_from == null) break; + + // Otherwise, entries have a path. + trip[i + 1] = TripItem{ .path = current_entry.via_path.? }; + + // Now we follow the entry we're "coming from". If we + // aren't able to find the entry we're "coming from" by + // Place, something has gone horribly wrong with our + // program! (This really shouldn't ever happen. Have you + // checked for grues?) + const previous_entry = self.getEntry(current_entry.coming_from.?); + if (previous_entry == null) return TripError.EatenByAGrue; + current_entry = previous_entry.?; + } + } +}; + +pub fn main() void { + // Here's where the hermit decides where he would like to go. Once + // you get the program working, try some different Places on the + // map! + const start = &a; // Archer's Point + const destination = &f; // Fox Pond + + // Store each Path array as a slice in each Place. As mentioned + // above, we needed to delay making these references to avoid + // creating a dependency loop when the compiler is trying to + // figure out how to allocate space for each item. + 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..]; + + // Now we create an instance of the notebook and add the first + // "start" entry. Note the null values. Read the comments for the + // checkNote() method above to see how this entry gets added to + // the notebook. + var notebook = HermitsNotebook{}; + var working_note = NotebookEntry{ + .place = start, + .coming_from = null, + .via_path = null, + .dist_to_reach = 0, + }; + notebook.checkNote(working_note); + + // Get the next entry from the notebook (the first being the + // "start" entry we just added) until we run out, at which point + // we'll have checked every reachable Place. + while (notebook.hasNextEntry()) { + var place_entry = notebook.getNextEntry(); + + // For every Path that leads FROM the current Place, create a + // new note (in the form of a NotebookEntry) with the + // destination Place and the total distance from the start to + // reach that place. Again, read the comments for the + // checkNote() method to see how this works. + 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); + } + } + + // Once the loop above is complete, we've calculated the shortest + // path to every reachable Place! What we need to do now is set + // aside memory for the trip and have the hermit's notebook fill + // in the trip from the destination back to the path. Note that + // this is the first time we've actually used the destination! + var trip = [_]?TripItem{null} ** (place_count * 2); + + notebook.getTripTo(trip[0..], destination) catch |err| { + print("Oh no! {}\n", .{err}); + return; + }; + + // Print the trip with a little helper function below. + printTrip(trip[0..]); +} + +// Remember that trips will be a series of alternating TripItems +// containing a Place or Path from the destination back to the start. +// The remaining space in the trip array will contain null values, so +// we need to loop through the items in reverse, skipping nulls, until +// we reach the destination at the front of the array. +fn printTrip(trip: []?TripItem) void { + var i: u8 = @intCast(u8, trip.len); // convert usize length + + while (i > 0) { + i -= 1; + if (trip[i] == null) continue; + trip[i].?.print(); + } + + print("\n", .{}); +} + +// Going deeper: +// +// In computer science terms, our map places are "nodes" or "vertices" and +// the paths are "edges". Together, they form a "weighted, directed +// graph". It is "weighted" because each path has a distance (also +// known as a "cost"). It is "directed" because each path goes FROM +// one place TO another place (undirected graphs allow you to travel +// on an edge in either direction). +// +// Since we append new notebook entries at the end of the list and +// then explore each sequentially from the beginning (like a "todo" +// list), we are treating the notebook as a "First In, First Out" +// (FIFO) queue. +// +// Since we examine all closest paths first before trying further ones +// (thanks to the "todo" queue), we are performing a "Breadth-First +// Search" (BFS). By tracking "lowest cost" paths, we can also say +// that we're performing a "least-cost search". +// +// Even more specifically, the Hermit's Notebook most closely +// resembles the Shortest Path Faster Algorithm (SPFA), attributed to +// Edward F. Moore. By replacing our simple FIFO queue with a +// "priority queue", we would basically have Dijkstra's algorithm. A +// priority queue retrieves items sorted by "weight" (in our case, it +// would keep the paths with the shortest distance at the front of the +// queue). Dijkstra's algorithm is more efficient because longer paths +// can be eliminated more quickly. (Work it out on paper to see why!) -- cgit v1.2.3-ZIG