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 accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now