26
\$\begingroup\$

As many geeks may know most pages (95% i think) on wikipedia eventually lead to Philosophy like this:

Click on the first non-italic or in parentheses link that is to another normal article: (i.e. not File: or Special:, but things like Wikipedia: are OK) and repeat on that one until you hit philosophy.

The script must:

  • Take a first page as input
  • Print the name of each article it gets to
  • And print how many articles it took to get to Philosophy, and if it didn't say so.

You start with 1000 points, and lose one for each character in the code, Bonus points for:

Detecting looping articles and stopping: +50

Detecting looping articles and requesting if the user should go to the next link on the article: +170

Allowing for a default on the former check as a command-line arg or similar: +140

Highest score wins.

\$\endgroup\$
  • 7
    \$\begingroup\$ +1, great challenge! This parenthesis detection is hard :P \$\endgroup\$ – Doorknob Jan 16 '14 at 22:38
  • 1
    \$\begingroup\$ I get the feeling this could use some better definition, but I'm not sure exactly how so just yet. \$\endgroup\$ – Iszi Jan 16 '14 at 22:39
  • 3
    \$\begingroup\$ Lose one point for each character typed. Hmm. Great, I got it, I'll just copy-paste the characters! No points lost! \$\endgroup\$ – Justin Jan 16 '14 at 22:52
  • 5
    \$\begingroup\$ Please don't change the rules after answers have already been posted; that's quite rude and generally frowned upon in the community here... \$\endgroup\$ – Doorknob Jan 16 '14 at 23:10
  • 2
    \$\begingroup\$ xefer.com/wikipedia \$\endgroup\$ – Charlie Jan 17 '14 at 13:29
8
\$\begingroup\$

Ruby, 1000 - 303 299 337 - 50 373 - 170 382 - 170 - 140 379 - 170 - 140 chars = 697 701 713 797 928 931

I'm sure there are many improvements to be made.

(This requires Nokogiri)

require'open-uri'
require'nokogiri'
x="/wiki/"+gets.chomp
r=[n=i=0]
until x=~/\/Philosophy/
d=Nokogiri.HTML open"http://en.wikipedia.org#{x}"
x=d.css('p a').select{|a|t=a.xpath('preceding::text()').map(&:text)*'';t.count('(')==t.count(')')&&a.attr('href')=~/^.wiki[^:]+$/}[i].attr'href'
i=0
puts r.index(x)?"#{$><<'i=';i=($*[0]||gets).to_i;''}": r.push(x)[-1][6..-1]
n+=1
end
p n

Example run:

c:\a\ruby>wikipedia_crawl_philosophy
Latin (note: this is my input)
Classical_antiquity
History
Umbrella_term
Terminology
Word
Linguistics
Science
Knowledge
Fact
Proof_(truth)
Argument
Logic
Reasoning
Consciousness
Quality_(philosophy)
Property_(philosophy)
Modern_philosophy
Philosophy
18

Sample one where I had to go to a different link

c:\a\ruby>wikipedia_crawl_philosophy
Snow
Precipitation_(meteorology)
Meteorology
Atmospheric_physics
Synoptic_scale_meteorology
i=2 // I put the 0-indexed number of the link I wanted to go to (so, the third link)

Weather
Atmosphere
Gas
State_of_matter#The_four_fundamental_states
Physics
Natural_science
Sciences
Knowledge
Fact
Proof_(truth)
Argument
Logic
Reasoning
Consciousness
Quality_(philosophy)
Property_(philosophy)
Modern_philosophy
Philosophy
25

Tricks I used:

  • I used the selector p a to only get non-italic links, because all links in the actual article that are not italics are always in paragraph elements in Wikipedia.
\$\endgroup\$
  • \$\begingroup\$ hmmm... maybe i should disallow any but librarys that come with the language... \$\endgroup\$ – AlphaModder Jan 16 '14 at 23:07
  • \$\begingroup\$ @user1825860 It's not actually a library that comes with the language; it's a gem. I edited my answer. But really, you want to take this already hard challenge and force us to not use HTML parsing libraries too? :P \$\endgroup\$ – Doorknob Jan 16 '14 at 23:08
  • \$\begingroup\$ i'm not disallowing it but you lose points :P \$\endgroup\$ – AlphaModder Jan 16 '14 at 23:10
  • \$\begingroup\$ You should reread the first post and edit accordingly :P \$\endgroup\$ – AlphaModder Jan 16 '14 at 23:10
  • 2
    \$\begingroup\$ @user1825860 Please don't change the rules after answers have already been posted; that's quite rude... \$\endgroup\$ – Doorknob Jan 16 '14 at 23:11
5
\$\begingroup\$

"BASH" – (If not mistaken: 1000 - 397 + 170 + 140 = 913 points)
"BASH" – (If not mistaken: 1000 - 386 + 170 + 140 = 924 points)

"BASH" – (If not mistaken: 1000 - 381 + 170 + 140 = 929 points)

BASH is in quotes on purpose as this is a mix of tools used in *nix shells but wrapped in a bash script.

Edit 1:

  • Removed http:// as curl defaults to this.
  • Changed href= match on anchors to f= as <a> does not have any other normal attributes ending in f. (It is a possibility of custom tags. Have not seen any so far.)
  • Set exit message on not found to !Phil instead of NoPhil. This one is a bit quirky as One could also say e.g. !, 0, N, !P or similar.
  • Quirk two: -s on curl could be removed to reduce by three more bytes, but that would yield a messy output. Not sure if that is an issue.
  • Updated help on this page.

Using quirks, code would end up at 379 bytes, 931 points.

I could also implement @plannapus usage of matching (hopefully) navigation box by adding (p|ul).*?<(\1) adding six bytes (subtracting six points).

Edit 2:

Using ${#c[@]} to print degrees of separation instead of $i counter.

Using quirks, code would end up at 374 bytes, 936 points.


I summon Cthulhu and go for a regexp + bash/shell/*nix solution.

Stolen:

Implemented:

  • Detect loop and ask if next link should be taken.
  • Optionally select next link on duplicate as option.

Requirements:

  • bash v.?
  • grep with -P (PCRE) support.
  • sed
  • curl
  • cut

Usage:

script PATH [OPTIONS]

Print separation of article from ``PATH'' to ``Philosophy'' on Wikipedia.
Degrees of separation, if found, is printed as last line. 
If not found last line yields ``!Phil''.

PATH    
     Absolute path to starting article, e.g: /wiki/Word 
OPTIONS
     y   Automatically select next link if already visited.
     n   (Or other) Quit if next link already visited.
BUGS
     1. On previous visit; "next link" is not checked. Thus if next link
     has already been visited we get eternal loop. Not sure if this
     disqualify +170 points.
     2. Sure there are.

Inline code. Copy to file. chmod +x filename. Run by ./script /wiki/… from bash shell.

u=($1);c=($1);while ! [[ "$u" =~ /Philosophy$ ]];do echo "$u";u=($(curl -s "en.wikipedia.org$u"|tr '\n' ' '|grep -Po '<p>.*?</p>'|sed 's/>[^<]*([^)]*)//g'|grep -o '<a [^>]*f="/wiki/[^":]*"'|cut -d\" -f2));for x in "${c[@]}";do if [ "$x" = "$u" ];then [ $2 ] &&s=$2||read -p "${u[0]}?" s;[ $s = y ] &&u[0]=${u[1]}||{ echo "!Phil";exit;} fi;done;c=("${c[@]}" "$u");done;echo ${#c[@]};

Expanded and explained code:

u=($1); # Array of paths.
c=($1); # Array of visited paths.
# While $u != /Philosophy, ugly trick is to use $u instead of ${u[0]}.
while ! [[ "$u" =~ /Philosophy$ ]];do   
        echo "$u";      # Print current page.
        # curl   : prints retreived page to stdout. "-s" could be skipped.
        # tr     : replace all newline with space. This is a ®sanity thing when it comes to 
        #          twidling with html using regex.
        # grep 1 : match <p> tags. Using -P's ungreedy *?.
        # sed    : remove all occurences of "(" something ")".
        # grep 2 : match links where "href" attribute starts with /wiki/ and is not e.g. File:
        # cut    : match actual href value.
        # Result is added to array ``u''.
        u=($(curl -s "en.wikipedia.org$u" |
                tr '\n' ' ' | 
                grep -Po '<p>.*?</p>' | 
                sed 's/>[^<]*([^)]*)//g' | 
                grep -o '<a [^>]*f="/wiki/[^":]*"' | 
                cut -d\" -f2));

        # For previously visited pages as x.
        for x in "${c[@]}"; do 
                # If x equals to first page ...
                if [ "$x" = "$u" ]; then        
                        # Use option or ask.
                        [ $2 ] && s=$2 || read -p "${u[0]}?" s; 
                        # If response is "y" use next link, else exit with status.
                        [ $s = y ] && u[0]=${u[1]} || { 
                                echo "!Phil"; 
                                exit;
                        } 
                fi;
        done;
        # Append current link to "visited"
        c=("${c[@]}" "$u"); 
done;
# Print number of visited pages.
echo ${#c[@]}
\$\endgroup\$
  • \$\begingroup\$ Darn it, you beat me by one point! :P I'm going to have to golf my solution more \$\endgroup\$ – Doorknob Jan 17 '14 at 21:47
  • \$\begingroup\$ Ye ;), but not sure this is valid code. Using tools this way. \$\endgroup\$ – Runium Jan 18 '14 at 13:48
5
\$\begingroup\$

JavaScript 726 (444 chars [556] + 170)

Now I appreciate that this might not be valid as a bookmarklet, but I've enjoyed tinkering with it anyway.

Usage: Navigate to the page you'd like to start from and run the following in the console:

(function(a){c=0,o="";$(u="html")[u](f=$('<iframe src="'+location+'?">').on("load",function(){$=f.contentWindow.$;p=f.contentDocument.title[s="split"](" - ")[0];c++;p=="Philosophy"?document.write("<pre>"+o+p+"\n"+c):(i=RegExp("^"+p+"$","m").test(o)?a||confirm("Loop, try next?")?2:0:1)&&(f.src=$("p>a").filter(function(){return(t=$(this).parent()[u]()[s](this.outerHTML)[0])[s]("(").length==t[s](")").length})[--i].href);o+=p+"\n"})[0])})(true)

For JavaScript the output is the following:

JavaScript
Interpreter (computing)
Computer science
Science
Knowledge
Fact
Proof (truth)
Argument
Logic
Reason
Consciousness
Quality (philosophy)
Property (philosophy)
Modern philosophy
Philosophy
15

This solution will assume you want to jump to the next link on a loop being detected, but if you change the true at the end to false it'll pop up a confirmation box instead (quite annoying...) not sure if that qualifies for the secondary bonus or not. I'll assume not.

Indented:

(function(l){
    c=0,o='';
    $(u='html')[u](f=$('<iframe src="'+location+'?">').on('load',function(){ // Firefox needs the ? to properly load the frame
        $=f.contentWindow.$; // reference repeated calls as strings to save more bytes
        p=f.contentDocument.title[s='split'](' - ')[0]; // get the title

        c++;
        p=='Philosophy'?
            document.write('<pre>'+o+p+'\n'+c): // pre for nice formatting
            (i=RegExp('^'+p+'$','m').test(o)?
                l||confirm('Loop, try next?')?
                    2: // desired index + 1 so we can use as a boolean
                    0
                :
                1)&&
            (f.src=$('p>a').filter(function(){
                return (t=$(this).parent()[u]()[s](this.outerHTML)[0])[s]('(').length == t[s](')').length // shorter, but still not overly happy with this...
            })[--i].href);
            o+=p+'\n' // update output
    })[0])
})(true) // change this to show confirm box when loop detected

So I originally missed the part about ignoring items in parens, adding that made it a lot more wordy, so I'm hoping to golf that filter function down (or hopefully replace it entirely).

Working in both Chrome and Firefox (tested in Firefox 26)

\$\endgroup\$
  • 2
    \$\begingroup\$ Looks awesome, but fails in Firefox 20. \$\endgroup\$ – boothby Jan 17 '14 at 18:38
  • \$\begingroup\$ Argghh! I only tested Chrome. I'll look into it! \$\endgroup\$ – Dom Hastings Jan 17 '14 at 19:12
  • \$\begingroup\$ @boothby Should be working in Firefox now... Still want to work on the links I'm choosing though! \$\endgroup\$ – Dom Hastings Jan 17 '14 at 20:40
5
\$\begingroup\$

C# - 813 chars

Score: 1000-813+50+170+140 = 547 :(

No external libraries. Loop detection.

First argument is the Source Article, second is the Target Article.

Golfed version:

class Program
{
    static void Main(string[] a)
    {
        Func<XmlDocument,IList<string>> G=delegate(XmlDocument xd){return xd.SelectNodes("//p//a[starts-with(@href,'/wiki/') and not(contains(@href,':'))]").Cast<XmlNode>().Select(n=>n.Attributes["href"].InnerText).ToList();};Action<string> W=delegate(string s){Console.WriteLine(s);};var h=new HashSet<string>();var c=new WebClient();var x=new XmlDocument();var t=c.DownloadString(@"http://wikipedia.org/wiki/"+a[0]);int i=0,C=0;
    GO:
        x.LoadXml(t);var ns=G(x);
    COL:
        var f=ns[i];if(f.Equals("/wiki/"+a[1],StringComparison.OrdinalIgnoreCase)){goto END;}if(h.Contains(f)){W("loop: "+f);i++;goto COL;}else{h.Add(f);i=0;C++;}W(f);t=c.DownloadString(@"http://wikipedia.org"+f);goto GO;
    END:
        W("Found in "+C);
    }
}

Intelligible version:

class Program
{
    // arg[0] source article. arg[1] target article
    static void Main(string[] arg)
    {
        Func<XmlDocument, IList<string>> G = delegate(XmlDocument xd)
        {
            return xd.SelectNodes("//p//a[starts-with(@href,'/wiki/') and not(contains(@href,':'))]").Cast<XmlNode>().Select(n => n.Attributes["href"].InnerText).ToList();
        };
        Action<string> W = delegate(string s) { Console.WriteLine(s); };
        var h = new HashSet<string>(); var c = new WebClient(); var x = new XmlDocument();
        var allText = c.DownloadString(@"http://wikipedia.org/wiki/" + arg[0]);
        int i = 0; int C = 0;
    GO:
        x.LoadXml(allText);
        var ns = G(x);
    COL:
        var f = ns[i];
        if (f.Equals("/wiki/" + arg[1], StringComparison.OrdinalIgnoreCase))
        {
            goto END;
        }
        if (h.Contains(f))
        {
            W("loop: " + f); i++; goto COL;
        }
        else
        {
            h.Add(f); i = 0; C++;
        }
        W(f);
        allText = c.DownloadString(@"http://wikipedia.org" + f);
        goto GO;
    END:
        W("Found in " + C);
    }
}

Example run, from "Sky" to "Philosophy":

C:\>wiki.exe Sky Philosophy

/wiki/Earth
/wiki/Geometric_albedo
/wiki/Phase_angle_(astronomy)
/wiki/Observational_astronomy
/wiki/Astronomy
/wiki/Natural_science
/wiki/Sciences
/wiki/Latin_language
/wiki/Classical_antiquity
/wiki/History
/wiki/Ancient_Greek
/wiki/Greek_language
/wiki/Modern_Greek
loop: /wiki/Greek_language
/wiki/Colloquialism
/wiki/Word
/wiki/Linguistics
/wiki/Science
loop: /wiki/Latin_language
/wiki/Knowledge
/wiki/Fact
/wiki/Latin
loop: /wiki/Classical_antiquity
/wiki/Italic_languages
/wiki/Indo-European_languages
/wiki/Language_family
/wiki/Language
/wiki/Human
/wiki/Extinct
/wiki/Biology
loop: /wiki/Natural_science
/wiki/Life
loop: /wiki/Earth
/wiki/Physical_body
/wiki/Physics
loop: /wiki/Greek_language
loop: /wiki/Natural_science
/wiki/Matter
/wiki/Rest_mass
/wiki/Center_of_momentum_frame
loop: /wiki/Physics
/wiki/Inertial_frame
loop: /wiki/Physics
/wiki/Frame_of_reference
loop: /wiki/Physics
/wiki/Coordinate_system
/wiki/Geometry
loop: /wiki/Ancient_Greek
/wiki/Mathematics
/wiki/Quantity
/wiki/Property_(philosophy)
/wiki/Modern_philosophy
Found in 41

C:\>
\$\endgroup\$
5
\$\begingroup\$

Scala (294 chars => 1000-294+140 = 846 points)

The updated solution which automatically takes the next link if one has already been consumed. Thanks for the 140 bonus points.

Logic: Pick up the first "/wiki" link that doesn't have a ":" in it (so it ignores "File:" links). Rinse and repeat with recursion returning the count + 1 every time. I keep a list of all previous outputs handy so the program doesn't go into an infinite loop.

Regular Expression: I have 2 forms of the regular expression.

  • "<p>.*?\"/wiki/([^:]*?)\".*?/p>" which finds links within the <p> tags
  • "p>.*?/wiki/([^:]*?)\"" which is a slightly more experimental tag that has proven to work but provide different results because it, at times, picks up links from the right side info bar. These are regular articles so I believe it is still valid. If it's adjudged to not be, the OP (or someone else) can leave me a comment and I can update my solution to a better reg-ex.

I'm going to be using the second regular expression until I find a test case where it doesn't work or the OP mentions picking up links from the side bar aren't allowed (in my opinion, the info bars are still part of the actual article itself; more of a summary).


Minified Source:

object W extends App{print(x(Seq(args(0))));def x(s:Seq[Any]):Int={val? =s.last;println(?);?match{case "Philosophy"=>1;case _=>x(s:+"p>.*?/wiki/([^:]*?)\".*?/p>".r.findAllMatchIn(io.Source.fromURL("http://en.wikipedia.org/wiki/"+ ?).getLines.mkString).map(_ group 1).filter(!s.contains(_)).next)+1}}}

Readable Source:

object W extends App {
  print(x(Seq(args(0))))

  def x(s: Seq[Any]): Int = {
    val ? = s.last
    println(?)
    ? match {
      case "Philosophy" => 1
      case _ => x(s :+ "p>.*?/wiki/([^:]*?)\"".r.findAllMatchIn(io.Source.fromURL("http://en.wikipedia.org/wiki/" + ?).getLines.mkString).map(_ group 1).filter(!s.contains(_)).next) + 1
    }
  }
}

Sample Output:

Input

Space_toilet

Output

Space_toilet
Weightlessness
G-force
Weight
Force
SI_unit
French_language
Second_language
Language_acquisition
Word
Linguistics
Science
Latin_language
Pontifical_Academy_for_Latin
Pope_Benedict_XVI
Pope_Benedict_(disambiguation)
Regnal_name#Catholic_Church
Monarch
State_(polity)
Community
Commutative_property
Mathematics
Quantity
Property_(philosophy)
Modern_philosophy
Philosophy
26
\$\endgroup\$
  • 1
    \$\begingroup\$ Scala doesn't require a main object or method. You can run it with the interpreter as "scala <filename> [args..]". Use args(0) to get the first argument, get rid of your object and main definitions, and I think you can remove the :Int too. pastebin.com/YqywKcG8 \$\endgroup\$ – KChaloux Jan 17 '14 at 20:11
  • \$\begingroup\$ Turns out you can't remove the : Int. Didn't realize you were doing a recursive call. Also my pastebin was taken from your old Readable Source, but the same concepts apply. \$\endgroup\$ – KChaloux Jan 17 '14 at 20:13
  • \$\begingroup\$ I'll try out getting rid of the main method. And yeah, recursive calls made me add the :Int there. Later today, I'll also add a readable form of the 333 char solution I have. Thanks for the suggestions @KChaloux \$\endgroup\$ – javatarz Jan 18 '14 at 5:45
  • 1
    \$\begingroup\$ Like I said, the reference to object Q extends App { ... } is totally unnecessary if you run the code with the interpreter rather than compiling with scalac. Just run with scala <filename> [args..] \$\endgroup\$ – KChaloux Jan 21 '14 at 13:44
4
\$\begingroup\$

R, 379 characters; 1000-379+170=791 points

Version that ask users how to proceed when looping detected

library(XML);w="http://en.wikipedia.org";W="/wiki/";n=1;A=c(scan(,""));while(A[n]!="Philosophy"){a=paste0(w,W,A[n]);d=sapply(strsplit(grep(W,sapply(xpathApply(xmlParse(readLines(a)),"//p/a[@href]|//ul/li/a[@href]",xmlAttrs),`[`,'href'),v=T),"/"),`[`,3);B=d[-grep(":",d)];n=n+1;if(B[1]%in%A)if(readline("Loop!2nd link?")=="n")break;A[n]=head(B[!B%in%A],1);cat(A[n],"\n")};cat(n-1)

With indentations and comments:

library(XML) #Uses package XML
w="http://en.wikipedia.org"
W="/wiki/"
n=1
A=c(scan(,"")) #Stdin + makes it a vector so we can store each iteration
while(A[n]!="Philosophy"){
    a=paste0(w,W,A[n])
    d=sapply(strsplit(grep(W,sapply( #The heart of the program
             xpathApply(xmlParse(readLines(a)),"//p/a[@href]|//ul/li/a[@href]",xmlAttrs),
             `[`,'href'),v=T),"/"),`[`,3)
    B=d[-grep(":",d)] #get rid of Templates, Files ,etc...
    n=n+1
    #Ask user if should proceed when loop encountered 
    #(any answer other than "n" is considered agreement):
    if(B[1]%in%A)if(readline("Loop!2nd link?")=="n")break
    A[n]=head(B[!B%in%A],1) #Take the first link that is not redundant
    cat(A[n],"\n")
    }
cat(n-1)

Example run:

> library(XML);w="http://en.wikipedia.org";W="/wiki/";n=1;A=c(scan(,""));while(A[n]!="Philosophy"){a=paste(w,W,A[n],sep="");d=sapply(strsplit(grep(W,sapply(xpathApply(xmlParse(readLines(a)),"//p/a[@href]|//ul/li/a[@href]",xmlAttrs),`[`,'href'),v=T),"/"),`[`,3);B=d[-grep(":",d)];n=n+1;if(B[1]%in%A)if(readline("Loop!2nd link?")=="n")break;A[n]=head(B[!B%in%A],1);cat(A[n],"\n")};cat(n-1)
1: Extended_ASCII
2: 
Read 1 item
Eight-bit 
Computer_architecture 
Computer_science 
Science 
Logic 
List_of_aestheticians 
Art 
Human_behavior 
Behavior 
Organism 
Biology 
Loop!2nd link?y
Mathematics 
Quantity 
Property_(philosophy) 
Modern_philosophy 
Philosophy 
16

R, 325 characters; ??? points

Version that, by default takes first non-redundant link (i. e. non-looping).

library(XML);w="http://en.wikipedia.org";W="/wiki/";n=1;A=c(scan(,""));while(A[n]!="Philosophy"){a=paste0(w,W,A[n]);d=sapply(strsplit(grep(W,sapply(xpathApply(xmlParse(readLines(a)),"//p/a[@href]|//ul/li/a[@href]",xmlAttrs),`[`,'href'),v=T),"/"),`[`,3);B=d[-grep(":",d)];n=n+1;A[n]=head(B[!B%in%A],1);cat(A[n],"\n")};cat(n-1)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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