0
\$\begingroup\$

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:

  1. http://www.abc.com links to ->
  2. http://www.widgets.com links to ->
  3. http://www.gadgets.net links to ->
  4. http://www.techcrunch.com links to ->
  5. https://twitter.com/techcrunch links to ->
  6. 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.
\$\endgroup\$

closed as unclear what you're asking by Peter Taylor, Gareth, squeamish ossifrage, ProgramFOX, Justin Jan 27 '14 at 20:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ If anyone thinks this would be better as some other type of competition other than code golf, please comment. \$\endgroup\$ – Ben Paton Jan 27 '14 at 8:20
  • \$\begingroup\$ Determining whether two sites are on the same domain or not is hard. Browsers have long lists of special cases to deal with it. In order to make this a fair contest, I think you should provide a spec for whether two FQDNs should be considered to be from the same domain or not for the purposes of this question. \$\endgroup\$ – Peter Taylor Jan 27 '14 at 8:31
  • 1
    \$\begingroup\$ @BenPaton You may want to use the sandbox, especially if you are unsure about your puzzle. \$\endgroup\$ – Howard Jan 27 '14 at 8:33
  • 3
    \$\begingroup\$ Does example.co.uk count as the same domain as example2.co.uk. If not, can you specify why? \$\endgroup\$ – John Dvorak Jan 27 '14 at 8:34
  • 1
    \$\begingroup\$ @BenPaton, some TLDs allow registration of yourdomain.tld (these include the com, org, net, and some CCTLDs; I suspect that mil and gov are also in this category, but that might be debatable); others have their own second level domains and allow registration of third level domains (e.g. the uk CCTLD). And IIRC it's not even that simple. See also publicsuffix.org/list \$\endgroup\$ – Peter Taylor Jan 27 '14 at 12:36
1
\$\begingroup\$

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<String, String> entities = new HashMap<>();
    private static HashMap<String, ArrayList<String>> robotstxts = new HashMap<>();

    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 < 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<a href=\"\\E");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
        for (int i = 1; i < 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://") && !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<String> ar = new ArrayList<>();
                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<String> 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<String, String> getEntitiesFromEnt(String url) throws Exception {
        HashMap<String, String> e = new HashMap<>();
        String ent = downloadString(url);
        while (ent.contains("  ")) ent = ent.replace("  ", " ");
        String[] lines = ent.split("\n");
        for (String line : lines) {
            if (line.startsWith("<!ENTITY")) {
                String[] f = line.split(" ");
                e.put("&" + 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<String, String> e : entities.entrySet())
            html = html.replace(e.getKey(), e.getValue());
        Pattern ep = Pattern.compile("&#(\\d+);");
        Matcher m = ep.matcher(html);
        while (m.find()) {
            if (!m.group(1).equals("38"))
                html = html.replace("&#" + m.group(1) + ";", String.valueOf((char)Integer.parseInt(m.group(1))));
        }
        Pattern ep1 = Pattern.compile("&(x|X)([\\da-fA-F]+);");
        Matcher m2 = ep1.matcher(html);
        while (m2.find()) {
            if (!m.group(1).equals("26")) {
                html = html.replace("&x" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
                html = html.replace("&X" + m2.group(2) + ";", String.valueOf((char)Integer.parseInt(m2.group(2), 16)));
            }
        }
        html = html.replace("&#38;", "\0").replace("&x26;", "\0").replace("&X26;", "\0").replace("\0", "&");
        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<String> domains = new ArrayList<>();
        public ArrayList<String> links = new ArrayList<>();
        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; &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

\$\endgroup\$
  • \$\begingroup\$ Thanks for having a go at this challenge your code and output certainly seem valid. Well done! I'm always pleased to see someone take some time on a challenge i set. Thanks :) \$\endgroup\$ – Ben Paton Jan 27 '14 at 21:33
  • 2
    \$\begingroup\$ @BenPaton Thank you! Just trying my best to help out. It's not perfect, but it works to a certain degree. For some reason my 700 lines of "URL failed: Banned by robots.txt" didn't make it in. Oh well. \$\endgroup\$ – bilde2910 Jan 27 '14 at 22:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.