Wikigolf bruteforcer

[Freak]

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:

 

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.

[cwade12c]

I love it! I've never heard of Wikigolf before, but it's already at the top of e-sports on my list. This is a very cool concept. Nice work.