Two problems with ex. 58

[arbrk1]

Unfortunately, the algorithm shown in the exercise is wrong: it doesn't work e.g. for

A -----------10-------------> B --1--> F
|                             |
\--1-- C --1-- D --1-- E --1--/

because it visits each node not more than once (and doesn't update neighbors of the nodes updated with new information).

It can easily be fixed e.g. by returning an ?u8 from getEntry instead of a ?*NotebookEntry and updating the notebook next_entry field with it in checkNote (choosing the minimum of the current value and the updated entry index).

The second problem is much less severe: the figure with the notebook lists wrong distance for the B->D entry. The distance must be greater than distance for the A->B entry.

[ratfactor]

Ha, go figure. Thanks the attention to detail! If anybody is able to verify and PR a fix for this, that'd be great. It might be a while before I can.

...Or replace this exercise with something else entirely - see #198 and #125.

[ZoloZithro]

@arbrk1 can you provide output that is incorrect?

The example you provided works fine and produces the output:

Archer's Point--1->Cottage--1->Dogwood Grove--1->East Pond--1->Bridge--1->Fox Pond

Additionally, the algorithm is correct exhaustively, for all start and end points, for the hermits map.

It also updates as appropriate; in the main function, the while loop will visit every node and the inner for loop will update each of the nodes neighbours.

This may help, the following is a digraph of the hermits map:

digraph hermit_map {
  a [label = "Archer's Point"];
  b [label = "Bridge"];
  c [label = "Cottage"];
  d [label = "Dogwood Grove"];
  e [label = "East Pond"];
  f [label = "Fox Pond"];

  a -> b [label = "2"];

  b -> a [label = "2"];
  b -> d [label = "1"];

  c -> d [label = "3"];
  c -> e [label = "2"];

  d -> b [label = "1"];
  d -> c [label = "3"];
  d -> f [label = "7"];

  e -> c [label = "2"];
  e -> f [label = "1"];

  f -> d [label = "7"];
}

Save the map as hermit_map.dot and generate the map with dot by running the following command on the command-line:

cat hermit_map.dot | dot -Tpng -o hermit_map.png

You can run the exercise and compare.

@ratfactor I really like this example! It is fun and a great refresher to graph algorithms.

[ZoloZithro]

Update: Unfortunately, the algorithm is incorrect. After my last update, I kept having a nagging feeling; I remembered I thought it was really neat that you could use the hermit's notebook both to hold the locations and as the queue for the algorithm. This is actually the problem.

While the neighbours get updated correctly, they are supposed to go back into the queue after that; otherwise, their neighbours and neighbours' neighbours etc.. won't get updated.

@arbrk1's suggested fix is also incorrect as the notebook's next_entry field can be overwritten before it is even used in that case.

The only efficient way is to have a data structure hold nodes we need to check; queue for breath-first search, stack for depth-first search, or something else.

If you want to just get this algorithm to work then we can wrap the while loop in main with another while loop with a condition like a was_updated variable which is set to true depending on the return value from checkNote (when it updates a distance or adds a new entry). I've tested and this works:

var was_updated = true;
while (was_updated) {
    notebook.next_entry = 0;
    was_updated = false;
    while (notebook.hasNextEntry()) {
        ...
        for (place_entry.place.paths) |*path| {
        ...
            if (notebook.checkNote(working_note)) {
                was_updated = true;
            }
        }
    }
}

@ratfactor If you want to do this, I could do a pull request in a couple days; but it may be better for you to do it and integrate it with the rest of the comments/story [maybe something about the hermit updating his notebook so that when he goes on future trips the path will be better :-) ]. Or you could modify it after I do a pull request.

Failure Example of Current Algorithm

It is pretty difficult to get it to fail on a small graph, especially because it is sensitive to how you order the paths, but I finally got an example of it failing after adding two new locations. The following graph will still give the original answer when there is shorter path available.

digraph hermit_map {
  a [label = "Archer's Point"];
  b [label = "Bridge"];
  c [label = "Cottage"];
  d [label = "Dogwood Grove"];
  e [label = "East Pond"];
  f [label = "Fox Pond"];
  g [label = "Gorge"];
  h [label = "Haunted Forest"];

  a -> b [label = "2"];

  b -> g [label = "10"];
  b -> a [label = "2"];
  b -> d [label = "1"];

  c -> d [label = "3"];
  c -> e [label = "2"];

  d -> b [label = "1"];
  d -> c [label = "3"];
  d -> f [label = "7"];
  d -> g [label = "2"];

  e -> c [label = "2"];
  e -> f [label = "1"];

  f -> d [label = "7"];

  g -> b [label = "10"];
  g -> d [label = "2"];
  g -> h [label = "1"];

  h -> f [label = "1"];
}