THINK FIRST·CODE LATER

← All labs

A tiny web crawler: the visited set

Problem

A crawler starts from one page, follows its links, then the links of those pages, and so on — and must never visit a page twice, even though pages link to each other in circles.

The first line gives the start page and the maximum number of pages to visit. Each following line describes a page of a pretend web: page: link1 link2 ….

Write MiniCrawler with:

  • a Map<String, List<String>> for the web;
  • a queue of pages waiting to be visited;
  • a set of the pages already seen (visited or waiting) — a link is queued only if seen.add(link) returns true.

A link to a page that has no line is a broken link. Print the pages in the order visited, the number of links examined, the pages still waiting when the limit stopped the crawl, the broken links and the pages never reached (the last two in alphabetical order). For the input

home 10
home: news sports about
news: home world tech
sports: home scores
about: home contact
world: news
tech: news gadgets ai
scores: sports
ai: tech home
archive: home old

the program prints

Visited (8): [home, news, sports, about, world, tech, scores, ai]
Links examined: 17
Still waiting: []
Broken links: [contact, gadgets]
Pages never reached: [archive]

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d5-8-data-1.txt

home 10
home: news sports about
news: home world tech
sports: home scores
about: home contact
world: news
tech: news gadgets ai
scores: sports
ai: tech home
archive: home old
What your program must print for d5-8-data-1.txt
Visited (8): [home, news, sports, about, world, tech, scores, ai]
Links examined: 17
Still waiting: []
Broken links: [contact, gadgets]
Pages never reached: [archive]

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d5-8-data-1.txt

Windows PowerShell does not understand <:

Get-Content d5-8-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.