Have you ever heard of the Wikirace? It's a popular way to pass time by using links to travel from one Wikipedia page to another.
Basically, one of the best parts about using Wikipedia is how vast it is...you could look up one topic, and in trying to understand that topic have to learn about a half a dozen other topics within Wikipedia. This is all done through Wikilinks, or the internal links that connect topics. The premise of the Wikirace is to see really how vast Wikipedia actually is, and try to connect two completely unrelated topics to each other in as few 'clicks' as possible. You can play the game yourself, or you could build a bot to do it for you as quickly as possible.
It's especially fun to build this kind of bot if you like to nerd out on data structures, because it's essentially a breadth-first search algorthim. A breadth-first search algorithm is effective for searching tree or graph data structures - it explores all of the neighbor nodes at the immediate depth level before viewing any node on the next depth level.
Building a Wikirace bot on a microcontroller seems like a fun challenge, so let's see how the build goes!
The Build
This kind of bot can be built through Python, and I'm a mega fan of Python due to its ease of use and endless libraries. So naturally, the easiest conversion to build this out on a microcontroller is to use MicroPython, which has most of the great features of Python through a small subset of the Python standard library.
Plus, I want to use a display to count the number of Wikilinks visited throughout the race and what they are. It seems to be an prime opportunity to utilize the brand new RP2040 MicroMod Processor and the Input and Display Carrier board. As with all MicroMod projects, the hardware hookup is super simple - it just takes inserting the special keyed M.2 connector of the processor board into the carrier board and gently screwing it in.
The Code
I had to import some libraries directly into the MicroPython to access the Wikipedia pages. Otherwise, the code takes a root and target page, and completes breadth-first search to go through Wikipedia to connect the two.
import os, sys, wikipedia
def print_path(data):
if data['parent']:
print_path(data['parent'])
print(' => ', end='')
print(data['title'], end='')
def get_page(selection):
page = None
while not page:
try:
entry = input('%s page title: ' % selection)
page = wikipedia.page(entry)
except wikipedia.exceptions.DisambiguationError as e:
print('\nDisambiguation Selection (Choose one of these or use another term)')
for option in e.options:
print('\t' + option)
print()
except wikipedia.exceptions.PageError as e:
print('Page error, try again.')
except KeyboardInterrupt:
print('Exiting')
sys.exit()
return page
def wikipedia_game():
# Clears up the screen on start.
os.system('cls' if os.name == 'nt' else 'clear')
print('Wikipedia Game\n\n')
root_page = get_page('Root')
target_page = get_page('Target')
G = {}
G[root_page.title] = {
'title': root_page.title,
'distance': 0,
'parent': None
}
Q = [G[root_page.title]]
print('\nFinding the shortest path between the %s and %s pages...' % (root_page.title, target_page.title))
while Q:
current = Q[0]
Q = Q[1:]
try:
current_page = wikipedia.page(current['title'])
print('\t%s' % current_page.title)
for link in current_page.links:
if link not in G:
G[link] = {
'title': link,
'distance': current['distance'] + 1,
'parent': current
}
if link == target_page.title:
print('\n%s found!' % link)
print('Path: ', end='')
print_path(G[link])
print()
sys.exit()
Q.append(G[link])
except wikipedia.exceptions.DisambiguationError as e:
# Disambiguation Page
G[e.title] = {
'title': e.title,
'distance': current['distance'] + 1,
'parent': current
}
# Adds every link on disambiguation page to queue
for option in e.options:
if option not in G:
G[option] = {
'title': option,
'distance': current['distance'] + 2,
'parent': G[e.title]
}
if option == target_page.title:
print('\n%s found!' % option)
print('Path: ', end='')
print_path(G[option])
print()
sys.exit()
Q.append(G[option])
except wikipedia.exceptions.PageError as e:
# Skips over the item in the queue if it results in a page error.
print('\tSkipping %s...\n\t\t%s' % (current['title'], e))
except KeyboardInterrupt:
print('Exiting')
sys.exit()
wikipedia_game()
Obviously, there's an immediate issue with this code running on the RP2040 - I need Wifi to access Wikipedia in the first place. But it's okay that I wrote this up in MicroPython, because the ESP32 Processor board also works with MicroPython and has WiFi capabilities. So I can swap it out real quick and run it through a different processor board.
The End Result
The end result is that I can provide the bot a starting and ending Wikipedia page, and it can count how many Wikilinks it visited and what they were and display it on the Input and Display Carrier board. I looked up a random page on Wikipedia (Montesarchio), and ran it to see if I could get to tree. These were the following steps it took: Montesarchio, Western Roman Empire, Africa, Oil Lamp, Walnuts, Tree. I suppose the next step is to race the bot itself...
No comments:
Post a Comment