龍窩 2021 魚人節挖幣 (?) 活動

2021_AprilFool_dragoncoin.txt

為了讓 gist 的標題有點意義所以加的檔案

README.md

執行方式

相依套件: libssl-dev

1. clone 這個 gist
2. make
3. ./dragoncoin 執行

在我的 Win10 20H2 的 WSL2 上的執行時間是約 12~13 分鐘。 (之所以在 DC 上貼的圖上的時間是 18 分鐘是因為， 我為了追蹤進度所以印了稍微太多東西出來當進度條了。 印太多東西造成的結果就是有不少時間其實是花在系統 I/O 等待和切換； 那張圖計時的 18 分鐘裡系統有將近 5 分鐘就是這麼回事。)

思考過程

根據 hoi 放出來的提示，原始手牌的字串有以下性質：

1. 每張牌是分開的
2. 有理牌
3. 有聽牌

其中有理牌這件事很重要，除了減少可能性之外， 因為 MD5 的計算是按照字串順序計算的， 所有含 1m 的手牌開頭兩個字的計算是完全一樣的， 因此如果能夠留下中途計算的結果，就能很大程度上節省計算時間。 這可以利用 MD5 計算過程可以分成很多步，中間結果會使用一個狀態結構儲存的界面設計， 將這個狀態變數複製下來就能達成共用中途計算結果。

這裡就給個其他人算過的數字：13 張牌手牌的組合數是 98,521,596,000 種。 這將近一千億種的組合如果全部的 MD5 都要從頭算一次當然會算很久； 就算一次 MD5 能用 1 微秒算出來，一千億種仍然要花上 1 天多才能算完。

(順帶一提，如果是不管一種牌四張直接 34 種牌搭 13 層迴圈高塔的寫法的話， 組合數會是 13 個相同物品放入 34 個不同箱子的重複組合， 是為 C(13+34-1,13) = 101,766,230,790 種，只比限制一種牌四張的組合數多了約三十億種而已。)

但是單單有理牌也仍然是不夠的：到頭來我們仍然是要找過這全部一千億種才行。 這時就是另一個條件派上用場的時候了：有聽牌。 如果只看聽牌的種類數的話，同一個網頁也有算過一般形有 54,747,045 種， 若含七對國士則有 92,371,838 種組合。一千億種組合減少到了剩下一億種， 這就比較能全部試過一次了。

列舉聽牌

下一個問題：要怎麼列舉所有的聽牌型。

和上面一樣的理由，你不能列出所有牌組合後再去看有沒有聽，因為這樣你終究仍要試過那一千億種組合。 這裡就要用上和那個網頁裡一樣的做法了：列出某一色的所有組合，並計算搭子數量， 然後四色各選一種組合湊起來，再去判定是否聽牌。

不過我這裡的做法又更懶惰：我是有列出可能的搭子組合，但並沒有判斷合起來有沒有聽牌； 我只不過只選出可能出現在聽牌形裡的狀況而已。

所謂「可能出現在聽牌形裡的狀況」細說的話是這樣的條件：

1. 對 3n 張牌，全部都是刻子或順子；
2. 對 3n+1 張牌，刻子順子之外可能是一個孤張或兩個搭子；
3. 對 3n+2 張牌，刻子順子之外是一個搭子。

這裡的搭子包含對子、兩面搭和嵌張搭，反正我們只要看張數就通通混一起了。

注意到這只有考慮一色組合，也就是如果四色都考慮進來就會有一些其實沒有聽牌的組合也進行嘗試了。 我在這裡甚至還沒有排除 3n+1 狀況裡兩個搭子都是順搭的狀況 (因為要聽牌的話其中一個必須是對子)， 但可以肯定的是，所有的聽牌形這樣一定會找得出來試，不會有漏掉的。這個才是重點。

有了這個之後，四色只要各選一個出來，湊成 13 張牌，就可以丟去給 MD5 試了。

程式架構

上面這些「聽牌形中的狀況」甚至可以事先算好列出來，這樣要試 MD5 時就只要直接從列表裡抓抓抓貼起來丟去試就行了。 patterngen.cpp 在做的就是這件事：把萬筒索字四種牌的這種組合全部印出來， 然後把它內建到實際搜尋的程式當中。

主要搜尋的dragoncoin.cpp則就很簡單，把內建進來的組合一個一個選，選一組就丟一次 MD5。 這裡也用上了最開始提的前綴字串部份結果，讓重複的開頭字串的計算不會重覆。

應該有人已經注意到了：這一組程式只有計算一般形而已。 原本是有考慮一般形沒有再去把七對和國士形加進來的，但這樣就已經找到了所以就懶了。(炸)

話說回來，由於答案剛好在我的程式搜尋順序的尾巴的關係，這執行時間其實差不多快把所有的組合都跑過了， 也就是說就算多了一些不可能是聽牌的形式，總共時間還算在合理範圍內的； 程式裡有一個計數器計算嘗試個數，回報的數值是約 3.73 億， 表示說單單這樣一個簡單且粗糙的篩選就能夠把一千億種組合減少到剩下近四億，離真正的組合數只有七倍左右的差距而已。

那麼就是這樣了，有興趣的可以自行研究程式碼，我就不一行一行解說了。

dragoncoin.cpp

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <openssl/md5.h>
using namespace std;

#include "pattern.inc"

const unsigned char target[16] = {
// Challenge vector
	0xe5, 0x05, 0x4c, 0xeb, 0xdf, 0xc9, 0xb0, 0xe6,
	0x7b, 0xe3, 0xc9, 0x51, 0x5e, 0x65, 0xe0, 0x33
// Test vector 1: 1s1s1s1s2s2s2s2s3s3s3s3s4s
//	0x00, 0x29, 0x2f, 0x85, 0x7a, 0x06, 0x14, 0x13,
//	0xcc, 0xdc, 0xdf, 0x49, 0x26, 0x2e, 0xf6, 0x11
};
unsigned char md5result[16];

char currHand[30] = {};
int count = 0;

void check(MD5_CTX *pContext)
{
	MD5_Final(md5result, pContext);
	++count;
	if(memcmp(md5result, target, 16) == 0)
	{
		cout << "\rFound! original = " << currHand << endl;
		cout << "count = " << count << endl;
		exit(0);
	}
}

void search(int suit, int len, MD5_CTX *pContext)
{
	if(suit == 3)
	{
		// only check total len = 13
		int mylen = 13-len;
		int count = patternSize[3][mylen];
		for(int id = 0; id < count; id++)
		{
			MD5_CTX nextContext = *pContext;
			strcpy(currHand + len*2, patternTable[3][mylen][id]);
			MD5_Update(&nextContext, patternTable[3][mylen][id], mylen * 2);
			check(pContext);
		}
	}
	else
	{
		for(int mylen = 0; mylen <= 13-len; mylen++)
		{
			int count = patternSize[suit][mylen];
			for(int id = 0; id < count; id++)
			{
				MD5_CTX nextContext = *pContext;
				strcpy(currHand + len*2, patternTable[suit][mylen][id]);
				//if(suit == 0) cout << "\rSearching " << currHand << "...                          " << flush;
				MD5_Update(&nextContext, patternTable[suit][mylen][id], mylen * 2);
				search(suit + 1, len + mylen, &nextContext);
			}
		}
	}
}

int main()
{
	MD5_CTX context;
	MD5_Init(&context);

	search(0, 0, &context);
	cout << "Not found." << endl;
	return 0;
}

Makefile

CXXFLAGS = -O3
LIBS = -lcrypto

all: dragoncoin

dragoncoin: dragoncoin.cpp pattern.inc
	$(CXX) $(CXXFLAGS) $< $(LIBS) -o $@

patterngen: patterngen.cpp
	$(CXX) $(CXXFLAGS) $^ -o $@

pattern.inc: patterngen
	./patterngen > pattern.inc

clean:
	rm -f dragoncoin

patterngen.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

inline int extractCount(int pattern, int pos)
{
	return (pattern >> (3 * pos)) & 7;
}

char suits[] = {'m', 'p', 's', 'z'};
vector<string> allPattern[4][13];

void output(int pattern, int sid)
{
	stringstream ss;
	int len = 0;
	for(int i = 0; i < 9; i++)
	{
		int count = extractCount(pattern, i);
		len += count;
		for(int j = 0; j < count; j++)
		{
			ss << (i+1) << suits[sid];
		}
	}
	allPattern[sid][len-1].push_back(ss.str());
	if(sid != 3 && (pattern >> (3*4)) & 7 >= 1)
	{
		ss.str(""s);
		for(int i = 0; i < 9; i++)
		{
			int count = extractCount(pattern, i);
			if(i == 4) {ss << '0' << suits[sid]; count--;}
			for(int j = 0; j < count; j++)
			{
				ss << (i+1) << suits[sid];
			}
		}
		allPattern[sid][len-1].push_back(ss.str());
	}
}

set<int> numcache;
void outputSuit(int pattern)
{
	if(numcache.count(pattern) > 0) return;
	numcache.insert(pattern);
	output(pattern, 0);
	output(pattern, 1);
	output(pattern, 2);
}

set<int> honorcache;
void outputHonor(int pattern)
{
	if(honorcache.count(pattern) > 0) return;
	honorcache.insert(pattern);
	output(pattern, 3);
}

bool valid(int pattern)
{
	for(int i = 0; i < 9; i++)
	{
		if(extractCount(pattern, i) > 4) return false;
	}
	return true;
}

int main()
{
	int threePattern[16];
	for(int i = 0; i < 9; i++) threePattern[i] = 3 << (3 * i);
	for(int i = 0; i < 7; i++) threePattern[i+9] = 0111 << (3 * i);

	int twoPattern[24];
	for(int i = 0; i < 9; i++) twoPattern[i] = 2 << (3 * i);
	for(int i = 0; i < 8; i++) twoPattern[i+9] = 011 << (3 * i);
	for(int i = 0; i < 7; i++) twoPattern[i+17] = 0101 << (3 * i);

	int onePattern[9];
	for(int i = 0; i < 9; i++) onePattern[i] = 1 << (3 * i);

#define ONE(p) for(int p : onePattern)
#define TWO(p) for(int p : twoPattern)
#define THREE(p) for(int p : threePattern)
#define CHECK(p) if(valid(p))
#define OUT(p) outputSuit(p)
#define CHECKOUT(p) CHECK(p) OUT(p)

	ONE(p1) OUT(p1); // 1
	TWO(p1) 
	{
		OUT(p1); // 2
		TWO(p2) CHECKOUT(p1+p2); // 2+2
	}
	THREE(p1)
	{
		OUT(p1); // 3
		ONE(p2) CHECKOUT(p1+p2); // 3+1
		TWO(p2) CHECK(p1+p2)
		{
			OUT(p1+p2); // 3+2
			TWO(p3) CHECKOUT(p1+p2+p3); // 3+2+2
		}
		THREE(p2) CHECK(p1+p2)
		{
			OUT(p1+p2); // 3+3
			ONE(p3) CHECKOUT(p1+p2+p3); // 3+3+1
			TWO(p3) CHECK(p1+p2+p3)
			{
				OUT(p1+p2+p3); // 3+3+2
				TWO(p4) CHECKOUT(p1+p2+p3+p4); // 3+3+2+2
			}
			THREE(p3) CHECK(p1+p2+p3)
			{
				OUT(p1+p2+p3); // 3+3+3
				ONE(p4) CHECKOUT(p1+p2+p3+p4); // 3+3+3+1
				TWO(p4) CHECK(p1+p2+p3+p4)
				{
					OUT(p1+p2+p3+p4); // 3+3+3+2
					TWO(p5) CHECKOUT(p1+p2+p3+p4+p5); // 3+3+3+2+2
				}
				THREE(p4) CHECK(p1+p2+p3+p4)
				{
					OUT(p1+p2+p3+p4); // 3+3+3+3
					ONE(p5) CHECKOUT(p1+p2+p3+p4+p5); // 3+3+3+3+1
				}
			}
		}
	}

	int triplePattern[7];
	int doublePattern[7];
	int singlePattern[7];
	for(int i = 0; i < 7; i++)
	{
		triplePattern[i] = 3 << (3 * i);
		doublePattern[i] = 2 << (3 * i);
		singlePattern[i] = 1 << (3 * i);
	}

#undef ONE
#undef TWO
#undef THREE
#undef OUT
#undef CHECKOUT
#define ONE(p) for(int p : singlePattern)
#define TWO(p) for(int p : doublePattern)
#define THREE(p) for(int p : triplePattern)
#define OUT(p) outputHonor(p)
#define CHECKOUT(p) CHECK(p) OUT(p)

	ONE(p1) OUT(p1); // 1
	TWO(p1) 
	{
		OUT(p1); // 2
		TWO(p2) CHECKOUT(p1+p2); // 2+2
	}
	THREE(p1)
	{
		OUT(p1); // 3
		ONE(p2) CHECKOUT(p1+p2); // 3+1
		TWO(p2) CHECK(p1+p2)
		{
			OUT(p1+p2); // 3+2
			TWO(p3) CHECKOUT(p1+p2+p3); // 3+2+2
		}
		THREE(p2) CHECK(p1+p2)
		{
			OUT(p1+p2); // 3+3
			ONE(p3) CHECKOUT(p1+p2+p3); // 3+3+1
			TWO(p3) CHECK(p1+p2+p3)
			{
				OUT(p1+p2+p3); // 3+3+2
				TWO(p4) CHECKOUT(p1+p2+p3+p4); // 3+3+2+2
			}
			THREE(p3) CHECK(p1+p2+p3)
			{
				OUT(p1+p2+p3); // 3+3+3
				ONE(p4) CHECKOUT(p1+p2+p3+p4); // 3+3+3+1
				TWO(p4) CHECK(p1+p2+p3+p4)
				{
					OUT(p1+p2+p3+p4); // 3+3+3+2
					TWO(p5) CHECKOUT(p1+p2+p3+p4+p5); // 3+3+3+2+2
				}
				THREE(p4) CHECK(p1+p2+p3+p4)
				{
					OUT(p1+p2+p3+p4); // 3+3+3+3
					ONE(p5) CHECKOUT(p1+p2+p3+p4+p5); // 3+3+3+3+1
				}
			}
		}
	}

	for(int sid = 0; sid < 4; sid++)
	{
		cout << "const char* pattern_" << suits[sid] << "_0" << "[] = {\"\"};" << endl;
		for(int i = 0; i < 13; i++)
		{
			cout << "const char* pattern_" << suits[sid] << "_" << (i+1) << "[] = {" << endl;
			sort(begin(allPattern[sid][i]), end(allPattern[sid][i]));
			for(string& s : allPattern[sid][i])
			{
				cout << "\t\"" << s << "\"," << endl;
			}
			cout << "};" << endl;
		}
	}
	cout << "const char** patternTable[4][14] = {";
	for(int sid = 0; sid < 4; sid++)
	{
		cout << "{";
		for(int i = 0; i < 14; i++)
		{
			cout << "pattern_" << suits[sid] << "_" << i << ", ";
		}
		cout << "}, ";
	}
	cout << "};" << endl;
	cout << "const int patternSize[4][14] = {";
	for(int sid = 0; sid < 4; sid++)
	{
		cout << "{1, ";
		for(int i = 0; i < 13; i++)
		{
			cout << allPattern[sid][i].size() << ", ";
		}
		cout << "}, ";
	}
	cout << "};" << endl;

	return 0;
}