Six degrees of web separation Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world.

Your challenge here is to write a program which crawls to find out what is exactly 6 links away but connected back to the starting URL through a series of links.

For example if your program is given a starting url of http://vimeo.com it would then potentially (this is a made up example) crawl to:


http://www.abc.com links to ->
http://www.widgets.com links to ->
http://www.gadgets.net links to ->
http://www.techcrunch.com links to ->
https://twitter.com/techcrunch links to ->
http://www.youtube.com/user/techcrunch (finish as we are now 6 links away from the starting URL.)


Rules:


You can choose your own starting URL.
Any programming language can be used.
You most obey sites robots.txt files and not crawl any areas sites disallow.
Each step must be a new URL from the one you are currently on.
URLS should only be visited once per crawl.
You must output the starting URL and each link followed in sequence. 


Winner:


This is a popularity contest so the solution with the most up-votes wins.
Java, 8623 bytes

It isn't perfect. It has some issues connecting to some URLs and fails to parse the robots.txt properly. However, it's a start.

package info.varden.codegolf.sixdegreeslink;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URI;
import java.net.URISyntaxException;
import java.net.URL;
import java.net.URLConnection;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    private static HashMap&lt;String, String&gt; entities = new HashMap&lt;&gt;();
    private static HashMap&lt;String, ArrayList&lt;String&gt;&gt; robotstxts = new HashMap&lt;&gt;();

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        String init = "";
        for (String s : args) {
            init += s + "%20";
        }
        init = init.substring(0, init.length() - 3);
        try {
            System.out.println("Resolving entites (step 1 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLlat1.ent"));
            System.out.println("Resolving entites (step 2 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLsymbol.ent"));
            System.out.println("Resolving entites (step 3 of 3)...");
            entities.putAll(getEntitiesFromEnt("http://www.w3.org/TR/html4/HTMLspecial.ent"));
            System.out.println(entities.size() + " entites resolved.\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println("Starting search from: " + init + "\n");
        IterationInfo initInfo = new IterationInfo();
        IterationInfo info = initInfo;
        try {
            initInfo.scanLink = init;
            initInfo.links.add(init);
            initInfo.domains.add(getDomain(init));
            info = getSixStepsRecursive(initInfo);
        } catch (URISyntaxException e) {
            e.printStackTrace();
        }

        long diffTime = System.currentTimeMillis() - startTime;
        long second = (diffTime / 1000) % 60;
        long minute = (diffTime / (1000 * 60)) % 60;
        long hour = (diffTime / (1000 * 60 * 60)) % 24;
        diffTime = diffTime % 1000;

        String time = String.format("%02d:%02d:%02d.%d", hour, minute, second, diffTime);
        System.out.println("\nCompleted in " + time);
        System.out.println("\nRESULTS:");
        if (info.success) {
            for (int i = 0; i &lt; info.links.size(); i++) {
                System.out.println(info.links.get(i));
            }
        } else {
            System.out.println("Can't find six degrees step separation!");
        }
    }

    private static IterationInfo getSixStepsRecursive(IterationInfo info) {
        IterationInfo returnInfo = info;
        String[] urls = new String[0];
        try {
            String content = downloadString(info.scanLink);
            content = content.replace("\t", " ").replace("\r", " ").replace("\n", " ");
            while (content.contains("  ")) content = content.replace("  ", " ");
            urls = content.split("\\Q&lt;a href=\"\\E");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        for (int i = 1; i &lt; urls.length; i++) {
            try {
                if (info.iteration == 6) {
                    returnInfo.success = true;
                    return returnInfo;
                }
                returnInfo = info;
                urls[i] = stripHTMLEntities(urls[i].split("\"")[0]);
                if (urls[i].startsWith("//"))
                    urls[i] = "http:" + urls[i];
                if (!urls[i].startsWith("http://") &amp;&amp; !urls[i].startsWith("https://")) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Relative or non-HTTP link (" + urls[i] + ")");
                    continue;
                }
                if (!canGetRobotsTxt(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Blocked by robots.txt (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.links.contains(urls[i])) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Exact link already passed (" + urls[i] + ")");
                    continue;
                }
                if (returnInfo.domains.contains(getDomain(urls[i]))) {
                    System.out.println("Iter " + info.iteration + " - URL failed: Domain already passed (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                    continue;
                }

                System.out.println("Iter " + info.iteration + " - URL valid: Distict domain (" + getDomain(urls[i]) + ") (" + urls[i] + ")");
                returnInfo.links.add(urls[i]);
                returnInfo.domains.add(getDomain(urls[i]));
                returnInfo.iteration = info.iteration + 1;
                returnInfo.scanLink = urls[i];

                returnInfo = getSixStepsRecursive(returnInfo);
                if (returnInfo.success) {
                    return returnInfo;
                }
            } catch (Exception ex) {
            }
        }
        return returnInfo;

    }

    private static boolean canGetRobotsTxt(String url) {
        try {
            URI cur = new URI(url);
            if (!robotstxts.containsKey(cur.getHost())) {
                String rtxt = downloadString("http://" + cur.getHost() + "/robots.txt");
                String[] lines = rtxt.split("\n");
                ArrayList&lt;String&gt; ar = new ArrayList&lt;&gt;();
                for (String line : lines) {
                    if (line.endsWith("\r"))
                        line = line.substring(0, line.length() - 1);
                    if (line.toLowerCase().startsWith("disallow: ")) {
                        line = line.substring(10);
                        ar.add(line);
                    } else if (line.toLowerCase().startsWith("allow: ")) {
                        line = line.substring(7);
                        ar.remove(line);
                    }
                }
                robotstxts.put(cur.getHost(), ar);
            }
            ArrayList&lt;String&gt; a = robotstxts.get(cur.getHost());
            for (String s : a) {
                String[] sw = s.split("\\Q*\\E");
                String s2 = "^i";
                for (String s3 : sw) {
                    s2 += "\\Q" + s3 + "\\E(.+)";
                }
                s2 = s2.substring(0, s2.length() - 4);
                Pattern p = Pattern.compile(s2);
                Matcher m = p.matcher(cur.getPath());
                if (m.find()) {
                    return false;
                }
            }
            return true;
        } catch (Exception e) {
            return true;
        }
    }

    private static HashMap&lt;String, String&gt; getEntitiesFromEnt(String url) throws Exception {
        HashMap&lt;String, String&gt; e = new HashMap&lt;&gt;();
        String ent = downloadString(url);
        while (ent.contains("  ")) ent = ent.replace("  ", " ");
        String[] lines = ent.split("\n");
        for (String line : lines) {
            if (line.startsWith("&lt;!ENTITY")) {
                String[] f = line.split(" ");
                e.put("&amp;" + f[1] + ";", f[3].substring(1, f[3].length() - 1));
            }
        }
        return e;
    }

    private static String downloadString(String url) throws Exception {
        URL cur = new URL(url);
        URLConnection conn = cur.openConnection();
        conn.setRequestProperty("User-Agent", "URLConnection/1.7 (Any system) VardenCG/3.0");
        BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
        String content = "", line;
        while ((line = in.readLine()) != null) content += line + "\n";
        in.close();
        return content;
    }

    private static String stripHTMLEntities(String html) {
        for (Entry&lt;String, String&gt; e : entities.entrySet())
            html = html.replace(e.getKey(), e.getValue());
        Pattern ep = Pattern.compile("&amp;#(\\d+);");
        Matcher m = ep.matcher(html);
        while (m.find()) {
            if (!m.group(1).equals("38"))
                html = html.replace("&amp;#" + m.group(1) + ";", String.valueOf((char)Integer.parseInt(m.group(1))));
        }
        Pattern ep1 = Pattern.compile("&amp;(x|X)([\\da-fA-F]+);");
        Matcher m2 = ep1.matcher(html);
        while (m2.find()) {
            if (!m.group(1).equals("26")) {
                html = html.replace("&amp;x" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
                html = html.replace("&amp;X" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
            }
        }
        html = html.replace("&amp;#38;", "\0").replace("&amp;x26;", "\0").replace("&amp;X26;", "\0").replace("\0", "&amp;");
        return html;
    }

    private static String getDomain(String url) throws URISyntaxException {
        URI uri = new URI(url);
        String host = uri.getHost().toLowerCase();
        String[] subDomainTree = host.split("\\.");
        String[] commonSLs = {"ac", "co", "com", "gov", "ltd", "me", "net", "org"};
        boolean isCommonSL = false;
        try {
            String secondLevel = subDomainTree[subDomainTree.length - 2];
            for (String sl : commonSLs) {
                if (sl.equals(secondLevel)) {
                    isCommonSL = true;
                }
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return host;
        }
        try {
            if (isCommonSL) {
                return subDomainTree[subDomainTree.length - 3] + "." +
                        subDomainTree[subDomainTree.length - 2] + "." + 
                        subDomainTree[subDomainTree.length - 1];
            } else {
                return subDomainTree[subDomainTree.length - 2] + "." + 
                        subDomainTree[subDomainTree.length - 1];
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            return subDomainTree[subDomainTree.length - 2] + "." + 
                    subDomainTree[subDomainTree.length - 1];
        }
    }

    private static class IterationInfo {
        public ArrayList&lt;String&gt; domains = new ArrayList&lt;&gt;();
        public ArrayList&lt;String&gt; links = new ArrayList&lt;&gt;();
        public String scanLink = "";
        public int iteration = 1;
        public boolean success = false;
    }

}


Parameter used: http://codegolf.stackexchange.com/

Output: http://pastebin.no/34cd (Had to post on other site because it was too big for codegolf)

There's a lot of stuff going on here.

First of all, I have to parse HTML entities like &em; &amp;39; and &x2F;. The named entities have to be translated, I do that by downloading the definitions from W3C.

I also need to figure out the host of the URL, taking into account common second level domains like co, edu etc. (.co.uk, .edu.uk, ...)

Then I need to parse robots.txt.

I don't have time to write more now, but oh well, there's my contribution.

-- bilde2910