28 replies to this topic

[Neoquest]

Inspired by this topic, I decided to write a program that solves the Mystery Pic using database queries. It was pretty fun, and the end result was a program that is capable of solving the MPIC in <1 second.
Please excuse any gross looking code that you may encounter in this topic, these are scripts that I only planned on running a few times, and I didn't take much care when crafting them.

Tools

• Python (Pillow, pymongo)
• MongoDB
• Time

Step 1: The Images

 

Well, I could hardly download every neopets image every time I wanted to solve an mpic, so I started with that. There were about 130,000 in the end, I'm sure that I'm still missing many.
I used a combination of Dr. Sloth and the JN item DB to obtain these images.

This script scrapes every image url from Dr. Sloth:

Spoiler

import urllib
import time
import multiprocessing.pool
import json

class DoIt():
    def __init__(self):
        self.urls = []

    def getUntil(self, string, sub, char):
        total_length = len(string)
        place = string.find(sub) + len(sub)
        toreturn = ""
        while 1:
            if place > total_length:
                return ''
            scan = string[place:place + 1]
            if scan == char:
                return toreturn
                break
            else:
                toreturn = toreturn + scan
                place = place + 1

    def getUntils(self, string, sub, char):
        to_return = []
        while sub in string:
            res = self.getUntil(string, sub, char)
            to_return.append(res)
            string = string.replace(sub, '', 1)
        return to_return

    def safeOpen(self, url):
        try:
            src = urllib.urlopen(url).read()
        except Exception:
            print "Error encountered with" + url
            time.sleep(1)
            src = self.safeOpen(url)
        return src

    def scrapePage(self, page):
        src = self.safeOpen("http://www.drsloth.com/search/?start=" + str((page * 40)))
        images = ["http://images.neopets.com" + x for x in self.getUntils(src, '<img src="http://images.neopets.com', '"')]
        self.urls += images
        print page

doit = DoIt()

x = xrange(3218)
pool = multiprocessing.pool.ThreadPool(50)
pool.map(doit.scrapePage, x)
fi = open("out.json", "w")
fi.write(json.dumps(doit.urls))
fi.close()

 

I coupled this with a few lines on the command line to get a list of all item images and misc images. The JN item DB will happily display all items at once, making the item URLs very easy to scrape.

I then used this script to download all the images, this process wasn't as lengthy as you might think:

Spoiler

import json
import ast
import urllib
import time
import os
import multiprocessing.pool
import threading

all_images = ast.literal_eval(open("item_urls.json").read())
already_downloaded = os.listdir("images")

def safeDownload(url):
	if url.split("/")[-1] not in already_downloaded:
		try:
			urllib.urlretrieve(url, "images/" + url.split("/")[-1])
		except Exception:
			print "Error encountered with " + url
			time.sleep(1)
			safeDownload(url)

pool = multiprocessing.pool.ThreadPool(50)
pool.map(safeDownload, all_images) 

After all was said and done, I had a directory with 130,000 images in it, this was the longest and most annoying part by far.

Step 2: The Documents
I needed a way to quickly search the database for images, so for each image, I generated a BSON document that contained a list of all the colors contained in the image. The plan was to match images that contained the same colors as the MPIC.

Here is the script that I used to generate the docs from images, and upload the generated docs to MongoDB:

Spoiler

import pymongo
import os
from PIL import Image

def rgb2hex(t):
    r, g, b = t
    return '#{:02X}{:02X}{:02X}'.format(r, g, b)

def getDoc(path):
    doc = {}
    try:
        colors = Image.open("images/" + path).convert("RGB").getcolors()
    except Exception:
        return False
    if colors:
        colors = [rgb2hex(color[1]) for color in colors]
        doc["name"] = path.split("/")[-1]
        for color in colors:
            doc[color] = True
        return doc
    else:
        return False

client = pymongo.MongoClient()

all_images = os.listdir("images")

docs = []
count = 0
for index, image_path in enumerate(all_images):
    new_doc = getDoc(image_path)
    if new_doc:
        docs.append(new_doc)
    count += 1
    if count % 100 == 0:
        print count

client.image.images.insert_many(docs)
 

These generated documents take up about a gig across 3 files, which is pretty manageable compared to the 130,000 images from before.

Step 3: The Profit

The final script I had to write is short and sweet. Download the MPIC hint from the supplied URL, get a list of the colors that it uses, and query the database for any images that contain the same colors:

Spoiler

import urllib
import pymongo
import time
from PIL import Image

MPIC_URL = "http://images.neopets.com/games/mysterypic/1377_39479.gif"

def rgb2hex(t):
    r, g, b = t
    return '#{:02X}{:02X}{:02X}'.format(r, g, b)

def getDoc(path):
    doc = {}
    colors = Image.open(path).convert("RGB").getcolors()
    if colors:
        colors = [rgb2hex(color[1]) for color in colors]
        for color in colors:
            doc[color] = True
        return doc
    else:
        return False

client = pymongo.MongoClient()

coll = client.image.images
pic_name = MPIC_URL.split("/")[-1]
urllib.urlretrieve(MPIC_URL, pic_name)
pic_doc = getDoc(pic_name)

t = time.time()
cursor = coll.find(pic_doc, {"name": 1})
for result in cursor:
    print result
print "Found in %s seconds" % (time.time() - t) 

 

Which results in a short and sweet final output:

{u'_id': ObjectId('55a58719292f980c548598d4'), u'name': u'plush_kyrii_mutant.gif'}
Found in 0.832999944687 seconds

[Swar]

Well this is wonderful now the fight will be over who can access the mystery pic page first after a new round starts

[Strategist]

Nice work mate. There goes Wasers claim to fame

[Michaelhex]

+rep for this. Sooo *I'm gonna sound so noobish here* I need to install:

• Python (Pillow, pymongo)
• MongoDB
• Time

first. Then run the script on any browser ? Is that how it goes?

Edited by michaelhex, 14 July 2015 - 05:10 PM.

[karlwithak]

Nice work.  I'm a bit surprised how quickly your query was able to get the correct answer.

[Florg]

Well, now all those who have no idea how to properly do this themselves can say goodbye to ever winning this competition again xD

[Waser Lave]

That's pretty much how I did my first version. It's all well and good until they give you one to solve with very few colours or where the colours have changed slightly.

[anewvision]

Wow, amazing work! Now I'll (almost) always get the item!

 

Waser can still have my rep even though he doesn't need it. In fact, I'll give him some right now.

[Nano]

Is step one mean to stop and hang here:

 

[Neoquest]

This wasn't meant to be a full working product, you will still need programming knowledge to put all these pieces together and get a queryable DB.

[Nano]

I only want to download the images.

 

I have no interest in working out the MPic.

[Neoquest]

Well then you may have to restart the process to get it to go all the way through. Why it would hang completely, I don't know. At least some of the threads should be free.

[Nano]

Restarted it a few times. And sniffed the network, it just stops requesting from drsloth.

[Neoquest]

You can try ripping out the parsing method I used and write a regex for getting the URLs, because the current one is really bad and I could imagine it causing a problem like that. But I had the code lying around and was too lazy to write a regex.

[Kway]

You can try ripping out the parsing method I used and write a regex for getting the URLs, because the current one is really bad and I could imagine it causing a problem like that. But I had the code lying around and was too lazy to write a regex.

(zip(*re.compile("(?P['\"])(http://images\.neopets\.com/.+?)(?P=quote)").findall(pageSource)) or {1:[]})[1]

[Neoquest]

(zip(*re.compile("(?P['\"])(http://images\.neopets\.com/.+?)(?P=quote)").findall(pageSource)) or {1:[]})[1]

Yes, I know that it's easy. I'm just saying that I was too lazy.

[MariahPapaya]

How ingenious! this will make it 100000 times easier to get those awards : PPP

[ScarDefault]

Anyone know if there is some way to make this in .php?... I don't understand this language yet 

[juvian]

After an year I stumble upon this topic lol. Nicely done, good to see someone read my long post haha

[Nano]

Anyone know if there is some way to make this in .php?... I don't understand this language yet 

 

 

It's possible, not sure it would be worth it though. Unsure if PHP could match Pythons processing speed for it.

[greatpanda1k]

i happened to stop at the same place. just need to add in a user agent. nothing to do with parsing

 

Is step one mean to stop and hang here:

 

[Nonexistent]

@Neoquest

 

I'm don't know python so the code is very confusing to me, but for this part

return '#{:02X}{:02X}{:02X}'.format(r, g, b)

are you returning the hex representation of the color as a string?

Edited by Nonexistent, 29 May 2016 - 01:45 PM.

[Neoquest]

@Neoquest

 

I'm don't know python so the code is very confusing to me, but for this part

return '#{:02X}{:02X}{:02X}'.format(r, g, b)

are you returning the hex representation of the color as a string?

 

Yep, I'm converting the rgb values to a hex string.

[Nonexistent]

Yep, I'm converting the rgb values to a hex string.

So in the bson document each color would be represented as seven bytes, plus the meta data added in to describe the serializations, and all that comes down to only 1G? Did you filter out all the images that had a great number of color variances, like irl photos, before you proccessed them?

 

Cause my color representations are 4 bytes each, the name of the image is represented by 4 bytes, and a delimiter is represented by 4 bytes, no other metadata of any kind, and my proccessed file still comes down to 2.2G 

Edited by Nonexistent, 29 May 2016 - 04:09 PM.

[Neoquest]

So in the bson document each color would be represented as seven bytes, plus the meta data added in to describe the serializations, and all that comes down to only 1G? Did you filter out all the images that had a great number of color variances, like irl photos, before you proccessed them?

 

Cause my color representations are 4 bytes each, the name of the image is represented by 4 bytes, and a delimiter is represented by 4 bytes, no other metadata of any kind, and my proccessed file still comes down to 2.2G 

 

You've gotta have something wonky going on, because just doing the math:

With 1000 colors per image (way way high, I assume it's going to be like 100 realistically)
And 130,000 images

(1000 * 4 + 4 + 4) * 130,000 = 521040000 bytes or 521 megabytes.

Even if I got something wrong with my interpretation of what you're saying, my overestimate of color count should make your final file size around that size or smaller.