25
\$\begingroup\$

Introduction

Recently, I was skyping with a bunch of friends and we got bored and had nothing to do, so we "invented" a "game" (some people in the comments pointed out that this game is playable online and very popular, so we definetely didn't invent it, although I hadn't seen it before). The reason I put the word "game" in quotation marks is because it's not an actual computer game, but it's played on Wikipedia.

It's really easy to play: Someone chooses some Wikipedia article as the goal. Let's assume Code Golf for this example. All the players then have to start from a random article (by pressing Random Article in the sidebar or going to this URL) and have to get to the "goal" as quick as possible using only linked articles of the article you are currently at. Rules include:

  • The search function is not allowed (obviously)
  • You may only click links in the article's main text (specifically all text inside <div id="bodyContent">)
  • If your random page or any other page you encounter has no valid links (dead links, loops, etc) or no links at all you may roll again.

The challenge

Here's where you come in: unfortunately I'm pretty bad at this game, but I'm also a dirty cheater. So I want you to implement this bot for me. I'm also a programmer, so naturally my hard disk is full of stuff like code, libraries and such and I only have a few bytes of memory to spare. Therefore this challenge is Code Golf, the answer with the least bytes wins.

Implementation Details:

  • Of course you don't have to implement an intelligent bot that knows connections between topics and automatically detects the optimal route. Brute forcing is more than enough for the purpose of this challenge
  • In the actual game, time counts. Your program shouldn't take longer than 1 hour to find the article (this is to avoid loopholes like random searchers that will "eventually" find the goal)
  • If no path to the goal can be found (e.g. dead links or a loop) you can choose what to do from the list below:
    • Quit (score remains the same)
    • Get another random article and try again and do nothing on loops (score -= 10)
    • Get another random article on a dead link or a loop (detect loops automatically) (score -= 50)
    • (By "score" I mean your byte count here)
  • Another 20 bonus bytes will be subtracted if you "trace" the route, so you print the title of every individual page you visit.
  • Standard network libraries may be used (to avoid loopholes like "I crafted my own network library which crawls wikipedia articles")
    • The only thing network-related your program should do is send a HTTP request to download a wikipedia page
  • If your program finds the page, it should quit, but somehow signalize that it finished (printing the character "f" or the title of the page is enough)
  • Standard loopholes are to be avoided

Have fun golfing!

(This is my first question here, so please point out obvious loopholes and caveats in the comments before exploiting them - thanks :D)

\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting enough for a challenge, but not enough reason for me to flood a site with requests. \$\endgroup\$ – manatwork Jul 17 '14 at 11:13
  • 2
    \$\begingroup\$ @manatwork I'm fairly certain Wikipedia has sufficient bandwith to handle "attacks" like this \$\endgroup\$ – Christoph Böhmwalder Jul 17 '14 at 11:17
  • 1
    \$\begingroup\$ Not exactly a loophole but I would look out for people complaining that this is just a graph search question that doesn't bring many new ideas to the table. I however think its fine, this site needs more questions. (Though you definitely didn't invent this "game" :P.) \$\endgroup\$ – Calvin's Hobbies Jul 17 '14 at 11:24
  • 1
    \$\begingroup\$ This is basically codegolf.stackexchange.com/q/18665/194 + codegolf.stackexchange.com/q/26031/194 \$\endgroup\$ – Peter Taylor Jul 17 '14 at 13:09
  • 1
    \$\begingroup\$ This could have been good as a koth challenge taking the average number of hops out of 50 runs with each bot. Would give more incentive to build a more intelligent bot. \$\endgroup\$ – rdans Jul 17 '14 at 19:48
12
\$\begingroup\$

Python 373 -> 303

It reads the Wikipedia destination from input() (user input) and should be in the format of /wiki/dest. So, something like /wiki/Code_golf or /wiki/United_States. It also uses one space for the indents and http://enwp.org instead of Wikipedia's full URL to save bytes.

  • -50 because if it finds a broken URL it gets a new random URL.
  • -20 because it prints the title of each URL visited (could change title -> URL, but title is cleaner and actually makes my source larger).

It hangs every once and a while, and I can't figure out why. Perhaps because of Wikipedia rate limits?

I found the Boston Red Sox Wikipedia page in 9 minutes 20 seconds, and the United States page in under 10 seconds, so it shouldn't take too long to find Code Golf...

from mechanize import*;from lxml.html import*;from random import*;a=Browser();a.set_handle_robots(0);i='http://enwp.org/Special:Random';t=input();d={};k=a.open
def f(o):
 if o!=i:d[o]=o
 if o in d:f(i)
 try:v=fromstring(k(o).read()).xpath('//div[@id="content"]//a/@href')
 except:f(i)
 print a.title()
 if t in v:k(t);print 'f';exit()
 else:f(choice(v)) if v else f(i)
f(i)
\$\endgroup\$
  • \$\begingroup\$ I don't know a lot of python, but this looks nice \$\endgroup\$ – Christoph Böhmwalder Jul 18 '14 at 4:41
  • \$\begingroup\$ Does it detect loops though? If it doesn't, that's 10 bonus points instead of 50 \$\endgroup\$ – Christoph Böhmwalder Jul 18 '14 at 4:44
  • \$\begingroup\$ @HackerCow yeah it won't visit the same url twice except for the /wiki/Special:Random url. Consequently, after visiting many urls it'll eat up your entire RAM. \$\endgroup\$ – Eric Lagergren Jul 18 '14 at 5:56
  • \$\begingroup\$ I'll just say this: from ... import*. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jul 18 '14 at 10:42
  • 1
    \$\begingroup\$ @DevanLoper oh shoot, misread your comment. Yes, I am. Originally I was using import mechanize as m and the assigning m.Browser() to a so when I call a.open() I'm in effect calling mechanize.Browser().open() now I'm just importing all of mechanize and get to skip the ... as m part. \$\endgroup\$ – Eric Lagergren Jul 19 '14 at 8:26

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.