I've recently developed an application named "Sushida Killer," which automatically plays "Sushida," the most famous typing game here in Japan -- For more details, play sushida here --.
This application consists of three parts:
1. Reading problems
2. Recognizing characters in movie
3. Similate key typing
The first part is reading problems.
On first sight, you will notice that a dish of sushi, which corresponds to one problem, emerges every 5 second. So it's not a bad idea to automatically take a screen shot of flash video with a span of 5 seconds. How to get a screen shot automatically? I used the next procedures:
1. Simulate key typing "Alt + PrintScrenn"
2. Access to the clip board with win32 API.
3. Get the Bitmap infomation from the clip board
4. Save it to a bmp file.
The second part is the key part of Sushida Killer.
To read only the charactor on screen, I first created some mimic cpp library that deals with image processing.
With it, I cut off a rectangle, in which a problem text comes up, then changed RGB 3-demension vector infomation of each pixel into 0/1 data using a threshold.
So far, you can get data something like this:
I had to collect many sample data like above to train the classifier, which was done semi-automatically.
After training with enough amounts of learning data sets, the next step is classifying an unknown data to a string. Fortunately I didn't have to use a learning machine based on statistical theory like an SVM and an Bayes' machine, since the characters were written by Flash app, not by a human, so they were neat and tidy enough to be understood by computer.
The key point is speed. How to classify data in less than 5 second?
There are about 1000 sample data, each has a 10,000-pixel relevant rectangle in it.
It seems tough to finish classifying the image data to the corresponding string in 5 seconds, considering that you also have to get a screen shot of the flash movie, and save it to the local file, then classify it into one of about 1000 groups.
So I mapped each learning data's information to a hash value between 0 and 10^10, inclusive.
I thought a collision would never happen because (the number of data / hash value size) was 10^-7. And I was right!! I succeed to finish the process less than 5 second. Actually, it doesn't take more than 1 second.
I preliminarily calculated each data's hash value, and dispatched them to a file. So when playing Sushida, program can load the data in memory, which doesn't take time at all.
The third part is key simulating.
It's not so difficult to simulate key typing if you know about keybd_event() of win32 API.
But getting the window handle of Sushida was a little challenging. The flash app runs in a browser, so it's impossible to get the application window directly.
I had to implement a program that gives you a window handle of the application on which the mouse cursor is located. Thanks to it, I was able to get the handle of Sushida, which was the children of children of children of children of my web browser!!! So I traversed window handle to reach the flash app.
Most of my effort was put into collecting the data. That were tedious tasks, though I did it semi-automatically.
And also selecting parameters was not so interesting, but it was a very important job.
What the size of rectangle?
How long the program have to sleep to wait for the screen shot and file writing to end?
How long the program have to sleep to wait for the key simulation to end?
Finally, I thank the great developer who created sushida for giving me this good challenge.
(Ah, he/she never gave me that kind of challenge, I just think I was given it..)
And I hereby promise that I will never use this Sushida killer to be ranked in the formal site, i.e., this program is for local use only.
Last but not least, here's a demo of Sushida Killer!
/* * 指定されたピクセルに色を設定 */ void BitMapProcessor::setColor(int row, int col, int r, int g, int b) { if (row < 0 || row >= iHeader.height) printf("getColor(): rowが範囲外です。\n"); if (col < 0 || col >= iHeader.width ) printf("getColor(): colが範囲外です。\n");
int width = 3 * iHeader.width; while (width % 4) // ビットマップの1列は4の倍数ビットからなる ++width;
int bPos = row * width + 3 * col; int gPos = bPos + 1; int rPos = bPos + 2;
/* * テスト用関数（1）モノクロ化 */ void twoTone(BitMapProcessor *bmp) { for (int i = 0; i < bmp->height(); i++) for (int j = 0; j < bmp->width(); j++) { int ave = 0; ave += bmp->getColor(i, j).r; ave += bmp->getColor(i, j).g; ave += bmp->getColor(i, j).b; ave /= 3;
bmp->setColor(i, j, ave, ave, ave); } }
/* * テスト関数（2）指定範囲の切り取り */ void extractArea(BitMapProcessor *bmp, int r0, int r1, int c0, int c1) { for (int i = 0; i < bmp->height(); i++) for (int j = 0; j < bmp->width(); j++) { if (r0 <= i && i <= r1 && c0 <= j && j <= c1) continue; bmp->setColor(i,j, 255, 255, 255); } }
/* * テスト関数（3） 色の反転 */ void invert(BitMapProcessor *bmp) { for (int i = 0; i < bmp->height(); i++) for (int j = 0; j < bmp->width(); j++) { int ave = 0; int r = bmp->getColor(i, j).r; int g = bmp->getColor(i, j).g; int b = bmp->getColor(i, j).b;
bmp->setColor(i, j, 255-r, 255-g, 255-b); } }
/* * テスト関数（4）モザイク化 */ void mosaic(BitMapProcessor *bmp, int level) { if (level <= 0) level = 1;
for (int i = 0; i < bmp->height(); i+=2*level) for (int j = 0; j < bmp->width(); j+=2*level) { int r = 0; int g = 0; int b = 0; int cnt = 0;
for (int x = -level; x <= level; x++) for (int y = -level; y <= level; y++) { int xt = i + x; int yt = j + y;
if (xt < 0 || yt < 0 || xt >= bmp->height() || yt >= bmp->width()) continue; ++cnt; r += bmp->getColor(xt, yt).r; g += bmp->getColor(xt, yt).g; b += bmp->getColor(xt, yt).b; }
r /= cnt; g /= cnt; b /= cnt;
for (int x = -level; x <= level; x++) for (int y = -level; y <= level; y++) { int xt = i + x; int yt = j + y;
template <class K, class V> class hashMap { static const unsigned int DEFAULT_SIZE = 1000000; vector<pair<K, V> > *contents; unsigned int _size; unsigned int (*_hashValue) (K, unsigned int);
public: hashMap(unsigned int (*func) (K, unsigned int) , unsigned int size = DEFAULT_SIZE) { _hashValue = func; _size = size; contents = new vector<pair<K, V> > [_size]; }
~hashMap() { delete [] contents; }
bool hashElement(K s) { unsigned int h = _hashValue(s, _size);
for (int i = 0; i < (int)contents[h].size(); i++) { if (contents[h][i].first == s) return true; }
return false; }
void insert(K x, V n) { if (hashElement(x)) return;
unsigned int h = _hashValue(x, _size); contents[h].push_back(make_pair(x, n)); }
pair<K, V> *getElement(K x) { unsigned int h = _hashValue(x, _size); for (int i = 0; i < (int)contents[h].size(); i++) if (contents[h][i].first == x) return &contents[h][i];
return NULL; }
void printHashBalance() { int cnt = 0; double ret = 0.0; int worst = 0;
for (int i = 0; i < (int)_size; i++) { if (contents[i].size()) { ++cnt; ret += contents[i].size(); worst = max<int>(worst, contents[i].size()); } }
The fifth trial of implementing a classic algorithm with Haskell!
Today I'll try Pascal' Triangle.
pascalTriangle x = x : pascalTriangle y where y = zipWith (+) (0:x) (x++[0])
Nothing special. Thanks to lazy evaluation, you can define an infinite list of Pascal's Triangle.
Here's a similar problem:
Let's consider how many times it lands heads if you toss a coin. More specifically, what the probability of the coin landing heads k times out of n tosses?
It seems it's nothing to do with Pascal's Triangle. But it actually is.
prbTree x = x : prbTree y where y = zipWith (+) (map (*0.5) (0:x)) (map (*0.5) (x++[0]))
The tree structure is just like Pascal's Triangle.
In the above source, I used floating point numbers. So they don't sum up to 1.0 due to the limitation of accuracy of the type.
You can also use rational numbers, which is in Data.Ratio module, instead of floating point numbers. In that case, they sum up to 1.0 when added together.
import Data.Ratio
half = (*) (1%2) prbTree x = x : prbTree y where y = zipWith (+) (map half $ 0:x) (map half $ x++[0])
-- quick sort qsort :: (Ord a) => [a] -> [a] qsort [] = [] qsort (x:xs) = let left = filter (<x) xs right = filter (>=x) xs in qsort left ++ [x] ++ qsort right
Haskellは美しい。次に、merge sort。
msort :: (Ord a) => [a] -> [a] msort [x] = [x] msort [x, y] = [min x y, max x y] msort xs = let len = length xs `div` 2 pre = msort $ take len xs suf = msort $ drop len xs in merge pre suf
merge [] [] = [] merge x [] = x merge [] y = y merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys
もうちょっと綺麗に書けそうだが、こんなもんだろう。
適当に乱数をソートしてみる。
getRandoms :: Int -> [Int] getRandoms n = take n $ randomRs (1, 100000) $ mkStdGen 0
data Check a = YES | NO | Unknown a deriving (Show, Eq)
この型を利用するために以下の関数を定義する。
passTest f x = if f x == True then YES else Unknown x failTest f x = if f x == True then NO else Unknown x determine f x = if f x == True then YES else NO
さらに、この型をモナドインスタンスとして実装する。
instance Monad Check where return x = Unknown x YES >>= _ = YES NO >>= _ = NO Unknown x >>= f = f x
