Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

20. Chapter 20 Solutions
Written by Jonathan Sande & Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

Solution to Challenge 1

This solution uses the AdjacencyList API you built in this chapter. You can use any non-null weight, but a good default is 1.

final graph = AdjacencyList<String>();

final megan = graph.createVertex('Megan');
final sandra = graph.createVertex('Sandra');
final pablo = graph.createVertex('Pablo');
final edith = graph.createVertex('Edith');
final ray = graph.createVertex('Ray');
final luke = graph.createVertex('Luke');
final manda = graph.createVertex('Manda');
final vicki = graph.createVertex('Vicki');

graph.addEdge(megan, sandra, weight: 1);
graph.addEdge(megan, pablo, weight: 1);
graph.addEdge(megan, edith, weight: 1);
graph.addEdge(pablo, ray, weight: 1);
graph.addEdge(pablo, luke, weight: 1);
graph.addEdge(edith, manda, weight: 1);
graph.addEdge(edith, vicki, weight: 1);
graph.addEdge(manda, pablo, weight: 1);
graph.addEdge(manda, megan, weight: 1);

print(graph);

You can simply look at the graph to find the common friend:

Megan --> Sandra, Pablo, Edith, Manda
Sandra --> Megan
Pablo --> Megan, Ray, Luke, Manda
Edith --> Megan, Manda, Vicki
Ray --> Pablo
Luke --> Pablo
Manda --> Edith, Pablo, Megan
Vicki --> Edith

Turns out to be Manda, which was stated pretty directly in the question. :]

If you want to solve it programmatically, you can find the intersection of the set of Megan’s friends with the set of Pablo’s friends.

final megansFriends = Set.of(
  graph.edges(megan).map((edge) {
    return edge.destination.data;
  }),
);

final pablosFriends = Set.of(
  graph.edges(pablo).map((edge) {
    return edge.destination.data;
  }),
);

final mutualFriends = megansFriends.intersection(pablosFriends);
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now