Jump to content

Wikigolf bruteforcer


Freak
 Share

Recommended Posts

I found myself playing Wikigolf with some friends the other day. If you don't know, the game involves trying to get from a specified staring Wikipedia page to a specified ending page by only clicking links to other Wikipedia pages in as few clicks as possible (like golf). For example, if you were tasked to get from "Apple" to "Banana" then your route might be (Apple -> Fruit -> Banana) which would get you a score of 2.

An inherent problem with this game is that you have no real way of knowing if your score is any good. Perhaps it took you 7 clicks to get from Jeffrey Dahmer to McDonald's. That may seem like a decent score considering that the two topics are seemingly very divorced from each other, but how can you be sure? What is the lowest possible number of clicks that you could have gotten?

Worry not! I have written a program which can tell you just that! (Interestingly enough, you can get from Jeffrey Dahmer to McDonald's in only 2 clicks).

#!/usr/bin/perl -w
use strict;
use LWP::Simple;
my(@arr1, @arr2, @pages, $start, $end, $contents, $valid, $url);

do{
	$valid = 1;
	print "Enter the starting page (Eg. \"apple\"): ";
	chomp($start = lc(<stdin>));
	print "Enter the ending page: ";
	chomp($end = lc(<stdin>));

	$contents = get("https://en.wikipedia.org/wiki/".$start);
	if(!(defined $contents)){
		print "\nError: ".$start." is not a valid wikipedia page.\n";
		$valid = 0;
	}
	$contents = get("https://en.wikipedia.org/wiki/".$end);
	if(!(defined $contents)){
		print "\nError: ".$end." is not a valid wikipedia page.\n";
		$valid = 0;
	}
}while($valid == 0);
@pages = ($start);
@arr1 = ($start);

for(my $hits = 1;; $hits++){
	for(my $i=0; $i<scalar(@arr1); $i++){
		$contents = get("https://en.wikipedia.org/wiki/".$arr1[$i]);

		if(!(defined $contents)){
			next;
		}
		while($contents =~ /href=\"(.*?)\"/g){
			$url = lc($1);
			if(substr($url,0,6) eq "/wiki/"){
				$url = substr($url,6);
				if( $url =~ /file\:/ or 	#Exclusions
				    $url =~ /special\:/ or
				    $url =~ /talk\:/ or
				    $url =~ /wikipedia\:/ or
				    $url =~ /category\:/ or
				    $url =~ /help\:/ or
				    $url =~ /portal\:/ or
				    $url =~ /template\:/ or
				    $url =~ /main_page/ or
				    grep( /^\Q$url\E$/, @pages)){ #If we've already seen that page.
					next;
				}
				if($url eq $end){
					print "The minimum number of hits is: ".($hits);
					exit(0);
				}
				push(@pages, $url);			
				push(@arr2, $url);
			}
		}
	}
	@arr1 = @arr2;
	@arr2 = ();
}

Unfortunately a limitation of this program is that while it does tell you the minimum number of clicks, it does not tell you what those clicks are exactly. This is because it lumps all pages together based on what level they are on irrespective of what page led to them. This image should demonstrate what I mean:

pEjTnKd.png

 

Be warned! The program is slow. This is because many Wikipedia pages link to 500+ other wikipedia pages. Therefore even for cases where only 2 clicks are necessary, the program may still look at the contents of over 250,000 unique wikipedia pages.

  • I Like This! 1
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...