You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Optionally take the number of moves, current score, and coordinates of the dots to skip parsing the image. Also optionally take options like whether to use powerups or not.
Parse Image
Turns Remaining and Current Score
This doesn't really need to be there for the hackathon. It adds to much complication for such a time limited competition.
Do OCR on the top gray areas of the image.
tesseract seems to work pretty well but it has to be cropped pretty well to be accurate from my brief messing around with it.
My cropping algorithm:
Similar to the edge detection for finding dots below.
First crop the gray header (easy, iterate until you hit white pixels to find the height of the header).
Do edge detection from the top, and their should be groups of edges. Some of those groups will be significantly taller than the rest (the numbers are taller than their labels).
Crop near those boundaries edges to two smaller images which should be just the number.
tesseract -psm 8 filename.png output
The value is in output.txt
Coordinates of Dots
Use simple edge detection to find the circles.
For each row in the image whose first pixel is white, find the first non-white pixel in that row. If the scan goes all the way through without finding any non-white pixels, no dot was hit. This should give you the left edges of circles. Given one list of coordinates representing an edge, the number of coordinates in that list is the diameter and the minimum x coordinate (denoted (x, y)) in that list is the center of the dot on the y-axis. The center of the dot is (x + radius, y).
We only need to do this for the first two dots to get the left most coordinate and the distance between dots.
Given x0, y0, and d (the distance between dots), the coordinate of the dot at (row, col) is (x0+d*row, y0+d*col).
Colors of the Dots
Needed for the path finding algorithm.
Assuming a 6x6 2d array of coordinates and a PIL image:
First break up grid into simple graphs (connected nodes representing dots) of connected chunks of the same color.
Starting at each of the 36 dots, perform a "flood fill" search for adjacent matching colors, marking nodes as visited.
The flood fill can be a naive recursive solution, and the restricted space will keep it tame.
Time complexity: linear to the number of dots.
For each subgraph from the previous step, link all of nodes (marking each other as neighbors).
itertools.combinations(subgraph, 2) is what I'm thinkin of.
A quick way to check adjacency is using the 1-norm (abs(r_1-r_0)+abs(c_1-c_0)==1).
Time complexity: not sure, but the worst case (36 choose 2) isn't that bad.
For each subgraph, do a depth-first search starting from each node to iterate through all possible paths.
DFS is simple. It's basically a brute force on a node, iterating through all of its neighbors, then each of each neighbor's neighbors, and so on.
The main restriction on paths is that line segments can not be repeated.
This should be efficient except when their are cycles, which happen to have special meaning in Dots! So we can short circuit.
I haven't proved this but I think this is true: If you repeatedly remove nodes with less than 2 edges from the subgraph, the remaining graph must either be empty or it has a cycle in it.
After removing those 1 edged nodes, choose an arbitrary node and follow neighbors until it forms a cycle.
This could miss some cycles which are better than others (for example it might miss a cycle that encircles other dots if a smaller cycle that is available.
Assign weights to each edge so that weight=|v_1|+|v_2| where v_1 and v_2 are the vertices that the edge connects.
For each vertex, add the edge(s) with the maximum weight to a set of edges to be removed. If either of the vertices of one of those paths has a degree of 2, don't remove it.
Remove all of the edges in that set.
DFS until you have the Eularian path.
We still need to think of a decent algorithm to detect dots encircled by a cycle. (Aside: the bounding box of a set/graph is called the "convex hull")
This could benefit from an adjacency matrix for checking adjacency and disconnecting nodes without modifying the actual graph.
Instead of using an actual matrix, it's probably quicker to use a dictionary which maps nodes to a set of their neighbors.
Recursively try all possible moves
Apply a path to the grid.
When removing a dot and making the above dots fall down, go from top to bottom so that we don't mess up the coordinates in our path.
Fill in unknown dots with None, and have our path finding algorithm ignore them (alternatively, use a probabilistic estimation of value based on what color they might be, or something like that.)
For each path apply it to the board, and for each path in that board do the same, until there are no more moves to be made (the board is filled with Nones.) Choose a path from the first level that has the highest estimated number of dots removed.
Cycle Detection
A simple O(1) way to detect cycles in a path is to check if len(dots) != len(set(dots)). In other words, look for repeated dots in a path.
Hashing Collections of Dots
When checking if a segment already exists, we'll want to be able to quickly check if segments are equivalent, i.e.
def__eq__(self, other):
a, b=selfc, d=otherreturn (a, b) == (c, d) or (a, b) == (d, c)
We also want the hash to reflect the equality so we can using hash sets for constant time operations. I suggest using a bitfield. This will use 36 bits (1 for each position) and has the advantage that it can extend to any sized collection of dots in case we want to compare the equivalence of paths or something.
Plug-in Optimizations with Cython
We can probably easily and significantly speed up our code using cython's augmenting pxd file. By providing this extra file with type annotations cython is able to compile the code to a .so file that is importable by regular python, while leaving the original python file unchanged as well! This could be an easy way to get our crazy exponential complexity algorithm to run in decent time if hashing and stuff isn't good enough.
cdef class Dot:
cdef int row, col, color
cpdef print_dot(Dot dot)
setup.py
from distutils.core import setup
from Cython.Build import cythonize
setup(ext_modules=cythonize('foo.py'))
Now running python setup.py build_ext --inplace will generate a .so and we get speedups at little cost! Woohoo! After messing with it a little bit the only caveat I have seen is that there is no support for the yield keyword which I use a lot.... Idk how slow our algorithm will actually run/if it will be worth it or not.
End Result
The program should output coordinate pairs in terms of pixels.
Twilio MMS Service
An addition to the server that people can text screenshots, and it draws a path on their screenshot and texts it back to them.
The twilio callback should simply queue images and the phone number that they came from. Optionally, the body of the incoming MMS's can specify parameters to our algorithm. Then, a worker pool can process the images as follows:
Queue the image and phone number.
Wait for the image to be processed by workers running the above program.
Generate images of dots with paths drawn on them and save them in a publicly accessible directory.
Use twilio to send them the generated image (code sample from here). Note this requires us to get a Canadian phone number ($1/mo) or a short code ($1000/mo). Tough decision.
message=client.messages.create(
body="Hello Monkey!", # Message body, if anyto="+12125551234",
from_="+15105551234",
media_url=[ # List of media URLs, if any"http://example.com/image1.jpg",
"http://example.com/image2.jpg",
],
)
Emulators
Army of emulators, all using the above webserver to decide their moves in an effort to make high scores, and tweeting about their progress (I have preemptively registered @DotBotDotBot in anticipation). Justification: Android images have a minimal linux install, without things like python, curl, find, etc that we take for granted. Result: Move most of the code to the webserver, so that the application running on the emulator is only translating coordinate pairs to touch events and writing them to /dev/input/event0. This will probably be a shell script or written in C.
We can use imagemagick: import -window 5554:DotBot ~/Pictures/screenshot.png, where 5554:DotBot is the title of the gui window we're taking the screenshot of.
We might be able to edit /data/data/com.nerdyoctopus.gamedots/files/.Defaults.plist to give us free powerups.
I have been successful by killing the app, pulling the file, adding some entries, pushing it back, and then restarting the app. Experimentation has shown that the counts use signed 32 bit integers, and that 2**31-1=2147483647 is the maximum value that can be entered without resulting in negative values.
The source code for sendevent reveals it's a simple wrapper around writing directly to the device file, so we could either use sendevent or write it ourselves.
usage: sendevent <device> <type> <code> <value>
In the above emulator setup, all events should be written to /dev/input/event0
type
code
value
what it means
3
0
pixel
x coordinate
3
1
pixel
y coordinate
1
330
1
finger down
1
330
0
finger up
0
0
0
separator
Sample drag event
This should drag in a right triangle shape. This is untested, I just figured it out from getevent output and sendevent.c. The timing between events might need tweaking to make android register them appropriately. Also I don't know how many points (if any) need to be registered in between coordinates to make a proper path but we can experiment with that.
We ought to make a simple webpage to "sell" what we did. I'm thinking a twitter feed of our exploits, plus a video of the emulator playing itself, plus a big bold phone number with "Text Your Screenshots to This Number!". Plus of course a snazzy "Fork me on GitHub" banner. GitHub pages is as good a place as any to do this.
Domain Names
The way my GitHub is configured, the default URL will be http://peterjohnson.io/DotBot/. Alternatively, we can buy a domain name. If we do, we should probably do this at least a few days in advance so we aren't worrying about the registration getting processed in time like last year or about DNS propagation.
Thoughts on Dots
Dots Solving Program
It takes a screenshot and returns a path to take.
Optionally take the number of moves, current score, and coordinates of the dots to skip parsing the image. Also optionally take options like whether to use powerups or not.
Parse Image
Turns Remaining and Current Score
This doesn't really need to be there for the hackathon. It adds to much complication for such a time limited competition.
Do OCR on the top gray areas of the image.tesseractseems to work pretty well but it has to be cropped pretty well to be accurate from my brief messing around with it.My cropping algorithm:Similar to the edge detection for finding dots below.First crop the gray header (easy, iterate until you hit white pixels to find the height of the header).Do edge detection from the top, and their should be groups of edges. Some of those groups will be significantly taller than the rest (the numbers are taller than their labels).Crop near those boundaries edges to two smaller images which should be just the number.tesseract -psm 8 filename.png outputThe value is inoutput.txtCoordinates of Dots
Use simple edge detection to find the circles.
For each row in the image whose first pixel is white, find the first non-white pixel in that row. If the scan goes all the way through without finding any non-white pixels, no dot was hit. This should give you the left edges of circles. Given one list of coordinates representing an edge, the number of coordinates in that list is the diameter and the minimum x coordinate (denoted
(x, y)) in that list is the center of the dot on the y-axis. The center of the dot is(x + radius, y).We only need to do this for the first two dots to get the left most coordinate and the distance between dots.
Given
x0,y0, andd(the distance between dots), the coordinate of the dot at(row, col)is(x0+d*row, y0+d*col).Colors of the Dots
Needed for the path finding algorithm.
Assuming a 6x6 2d array of coordinates and a PIL image:
Find Optimal Path
Iterate through all paths
itertools.combinations(subgraph, 2)is what I'm thinkin of.abs(r_1-r_0)+abs(c_1-c_0)==1).Recursively try all possible moves
None, and have our path finding algorithm ignore them (alternatively, use a probabilistic estimation of value based on what color they might be, or something like that.)Nones.) Choose a path from the first level that has the highest estimated number of dots removed.Cycle Detection
A simple O(1) way to detect cycles in a path is to check if
len(dots) != len(set(dots)). In other words, look for repeated dots in a path.Hashing Collections of Dots
When checking if a segment already exists, we'll want to be able to quickly check if segments are equivalent, i.e.
We also want the hash to reflect the equality so we can using hash sets for constant time operations. I suggest using a bitfield. This will use 36 bits (1 for each position) and has the advantage that it can extend to any sized collection of dots in case we want to compare the equivalence of paths or something.
Plug-in Optimizations with Cython
We can probably easily and significantly speed up our code using cython's augmenting pxd file. By providing this extra file with type annotations cython is able to compile the code to a .so file that is importable by regular python, while leaving the original python file unchanged as well! This could be an easy way to get our crazy exponential complexity algorithm to run in decent time if hashing and stuff isn't good enough.
Example:
foo.pyfoo.pxdsetup.pyNow running
python setup.py build_ext --inplacewill generate a .so and we get speedups at little cost! Woohoo! After messing with it a little bit the only caveat I have seen is that there is no support for theyieldkeyword which I use a lot.... Idk how slow our algorithm will actually run/if it will be worth it or not.End Result
The program should output coordinate pairs in terms of pixels.
Twilio MMS Service
An addition to the server that people can text screenshots, and it draws a path on their screenshot and texts it back to them.
The twilio callback should simply queue images and the phone number that they came from. Optionally, the body of the incoming MMS's can specify parameters to our algorithm. Then, a worker pool can process the images as follows:
Emulators
Army of emulators, all using the above webserver to decide their moves in an effort to make high scores, and tweeting about their progress (I have preemptively registered @DotBotDotBot in anticipation).
Justification: Android images have a minimal linux install, without things like python, curl, find, etc that we take for granted.
Result: Move most of the code to the webserver, so that the application running on the emulator is only translating coordinate pairs to touch events and writing them to
/dev/input/event0. This will probably be a shell script or written in C.import -window 5554:DotBot ~/Pictures/screenshot.png, where5554:DotBotis the title of the gui window we're taking the screenshot of.Setup up Remove Instance with X and VNC
https://www.digitalocean.com/community/articles/how-to-setup-vnc-for-ubuntu-12
Setup Emulator with Dots
<bundle>/sdk/toolsand<bundle>/sdk/platform-toolsare in your$PATH.android sdk # Install everything for version 4.3android avd # Create an avdemulator @DotBot -no-boot-anim -no-audioadb install com.nerdyoctopus.gamedots.apkPowerups
We might be able to edit
/data/data/com.nerdyoctopus.gamedots/files/.Defaults.plistto give us free powerups.I have been successful by killing the app, pulling the file, adding some entries, pushing it back, and then restarting the app. Experimentation has shown that the counts use signed 32 bit integers, and that
2**31-1=2147483647is the maximum value that can be entered without resulting in negative values.sendevent format
The source code for sendevent reveals it's a simple wrapper around writing directly to the device file, so we could either use sendevent or write it ourselves.
In the above emulator setup, all events should be written to
/dev/input/event0Sample drag event
This should drag in a right triangle shape. This is untested, I just figured it out from getevent output and
sendevent.c. The timing between events might need tweaking to make android register them appropriately. Also I don't know how many points (if any) need to be registered in between coordinates to make a proper path but we can experiment with that.Website
Domain Names
We ought to make a simple webpage to "sell" what we did. I'm thinking a twitter feed of our exploits, plus a video of the emulator playing itself, plus a big bold phone number with "Text Your Screenshots to This Number!". Plus of course a snazzy "Fork me on GitHub" banner. GitHub pages is as good a place as any to do this.
Domain Names
The way my GitHub is configured, the default URL will be http://peterjohnson.io/DotBot/. Alternatively, we can buy a domain name. If we do, we should probably do this at least a few days in advance so we aren't worrying about the registration getting processed in time like last year or about DNS propagation.
http://dotbot.bo/t ($140, dot bot dot bot :D)Dependencies
Python
So that means we can probably write it in Python 3.3 and we won't be restricted to GPL.
Emulator Stuff
The text was updated successfully, but these errors were encountered: