اختاپوس خسته

یادداشت‌هایی پیرامون کد، زندگی و دوستان

چطور پازل ۳۱ زومیت را حل کردم

اولین روز سال ۱۳۹۳ و اولین پست همین سال :) برای شروع سال چه چیزی بهتر از یه پازل فکری می‌تونه باشه؟ امروز جمعه‌ست و اول سال با آخر هفته شروع شده. آخرهفته‌ها فرصت مناسبی برای پروژه‌های کوچیک و جالب هست. خوب زومیت زحمت کشیده و پازل شمارهٔ ۳۱ام رو روز اول فروردین منتشر کرده. توی این پست می‌خوام توضیح بدم که چطوری این پازل رو حل کردم. در واقع تقلب کردم. چون اولش یک برنامه‌ای نوشتم که پازل رو حل کنه :P بعد رابطه‌ای برای تولید جواب‌ها پیدا کردم که خیلی سخت‌تر از روش اول جواب می‌داد. منتها خوبیش اینه که اجازه میده تعداد جواب‌های موجود رو محاسبه کنیم. تعداد کل جواب‌ها ۳۸ تا خواهد بود منتها با روش ریاضیاتی محاسبهٔ این جواب‌ها تقریباً غیر ممکن‌ه ولی با brute force امیدواری بیشتر میشه!

جایزهٔ این پازل یک عدد هارد دیسک بسیار عالی هست که امیدوارم توی قرعه‌کشی قبول بشم.

یادداشت: شما قبل از پنجشنبه ساعت ۱۲ ظهر (آخرین مهلت ارسال جواب‌ها) نمی‌تونید این پست رو بخونید! ولی دارم اینو اول فروردین می‌نویسم.

صورت‌مسأله

خوب اول از همه باید صورت‌مسأله رو بفهمیم: با استفاده از ۸ تا عدد هشت و عملگرهای ریاضی، عدد ۱۰۰۰ رو تولید کنید. ساده به نظر می‌رسه اما نیست! مسأله پیدا کردن یک چندجمله‌ای با ضرایب ۸ و متغیرهای ۸ هست که مجموع تعداد متغیرها و ضرایب برابر با ۸ باشه. و یا به‌عبارت دیگر، پیدا کردن یک چندجمله‌ای از هشت تا هشت با ضرایب ثابتِ یک. راه حل ساده‌ای برای مسأله وجود نداره بنابراین میریم سراغ راه حل زورِ خری (brute force). پیشنهاد اولیهٔ من اینه که تمام دنباله‌های postfix با استفاده از 8، +، -، / و * درست کنیم، هر کدوم رو ارزیابی کنیم، اگه برابر با ۱۰۰۰ شد، به‌عنوان یک جواب قبولش کنیم. تا همین‌جا کلی مشکل وجود داره! اول از همه ممکنه بپرسید که خوب چرا postfix ؟ چرا همون infix سادهٔ خودمون رو استفاده نمی‌کنیم؟ خوب دلیلش اینه که ارزیابی عبارات postfix ساده‌تره. فقط کافیه بریزیم روی یه پشته و دونه دونه محاسبه کنیم و جایگزین کنیم.

و اما مشکلات!

اولین مشکل اینه که راه حلی برای تولید عبارات معتبر ندارم. (و اصولاً پردازش اعتبارش هم صرف نمی‌کنه) مگر این که کسی بیاد و ادعا کنه که یک عبارت منظم ساده برای اعتبارسنجی عبارات پسوندی درست کرده. تازه اونم شاید (فقط شاید!) پردازش کمتری رو در مجموع انجام بده. اصلاً چرا شاید؟ قطعاً پردازش بیشتری خواهد داشت! خود ارزیابی عبارت (محاسبهٔ مقدارش) خیلی سریع‌تر از چک کردن اعتبار عبارت خواهد بود. پس با این حساب بی‌خیال مشکل اول میشیم و عبارت‌هایی مثل عبارات زیر رو هم ارزیابی می‌کنیم:

1
2
+*/+8*8*+8+8/-8
+++++++---++

توضیح این که اولی غلطه چون اصلا با عملگر شروع شده! دومی هم غلطه چون اصلاً عملوند نداره! خوب من نمیام بررسی کنم ببینم کدوم عبارت درسته کدوم غلطه. بلکه همین عبارت‌های احمقانه رو هم ارزیابی می‌کنم. نهایتاً موقع ارزیابی استک پر نمیشه و میگم حتماً عبارت غلط بوده.

و اما مشکل دوم! مشکل بزرگ‌تر… اندازهٔ مجموعهٔ جستجو خیلی بزرگه و ایده‌ای در مورد اندازهٔ مجموعهٔ جواب هم نداریم! مثلاً ممکنه فقط یک جواب یکتا وجود داشته باشه. بیاین یه حساب سرانگشتی بکنیم. اگر فرض کنیم طول رشتهٔ پسوندی ما کمتر از ۲۰ و بیشتر از ۵ باشه، در این صورت اندازهٔ مجموعه‌ای که باید پردازش کنیم برابر خواهد بود با: $$S=\sum_{i=5}^{20}{5^{i}}=23,841,857,909,375$$ یعنی بیست و سه تریلیارد و هشتصد و چهل و یک میلیارد و هشتصد و پنجاه و هفت میلیون و نهصدونه‌هزار و سی‌صد و پنجاه و هفت :D عدد خیلی بزرگی هست و برای این که بفهمیم چقدر بزرگه باید بگم که پردازش این تعداد دنباله روی کامپیوتر نسبتاً سریع من (پردازندهٔ Corei5) چیزی حدود ۴۰۰ سال طول می‌کشه. اما چی باعث میشه که بشینیم و برای یه همچین مقدار بزرگی کد بنویسیم؟ خیلی ساده: شانس و کمی شهود می‌تونم ادعا کنم که یه دنبالهٔ ۵ تایی به‌هیچ وجه نمی‌تونه عدد ۱۰۰۰ رو تولید کنه و همین‌طور دنبالهٔ ۲۰ تایی خیلی طولانی‌یه. بنابراین سعی می‌کنم دامنهٔ جستجو رو محدود کنم. به‌جای ۵ از ۱۰ شروع می‌کنم. همچنین اول از رشته‌های ۱۵ تایی شروع می‌کنم چون احتمال میدم جواب اون طرف‌ها باشه. بعدش میرم سراغ ۱۴ تایی‌ها و بعد ۱۶ تایی‌ها (از مرکز به طرف بیرون). اندازهٔ اولین مجموعه که باید جواب رو توش پیدا کنم برابر میشه با:

$$S’=5^{15}=30,517,578,125$$ یعنی سی‌میلیارد. برآورد می‌کردم حدود ۱۰۰ ساعت وقت لازم داشته باشم. ولی با پردازش‌های اضافی و کمی ایجاد تغییرات توی کدها، و البته محاسبهٔ تخمینی زمان باقی‌مانده داخل کدهای برنامه، این عدد تبدیل به ۳۰۰ ساعت شد. خوب همین مقدار امید برای شروع کافیه :)

کدنویسی

راستش اولش می‌خواستم با پایتون شروع کنم به نوشتن کدهای برنامه. ولی بعد به خودم گفتم مرد باش! بشین با سی++ بنویس. حدود نیم ساعت بعد یه همچین چیزی درآوردم که زیر می‌بینید. پیاده‌سازی کامل برنامه رو می‌تونید از این آدرس کلون کنید:

1
git@github.com:soroush/8-8-puzzle.git

توی این کد برای اولین بار سعی کردم یک الگوریتم بازگشتی رو به‌شکل موازی پیاده‌سازی کنم. چیزی که اولش نوشتم چندان جالب نبود ولی بعد ایدهٔ بسیار خوبی از سایت استک گرفتم: «هر جا تصمیم به ایجاد ترد جدید گرفتی، ورودی رو کپی کن. در بقیهٔ موارد اشاره‌گر بده به فراخوانی‌های پایین‌تر». خیلی عالی بود! خیلی خوشم اومد. موقع پیاده‌سازی البته رودست خوردم :) توجه نکرده بودم که تردهای C++11 سطح سیستم‌عامل نیستن. شاید هم روشی برای بردن‌شون به سطح کرنل پیدا کردم و کدها رو تبدیل کردم.

قبل از توضیح کدها نتیجهٔ اجرا رو می‌خوام نشون‌تون بدم. بعد از حدود دو ساعت پردازش تک‌هسته‌ای (روی Core2 duo) مقدار ۰٫۱ درصد (یک هزارم!) از مجموعهٔ جستجو رو اسکن کردم و بیست و پنج تا جواب برای مسأله پیدا کردم که خوب تعدادی‌شون هم‌ارز هستند. برای دیدن هم‌ارزی‌شون تعدادی از جمله‌ها رو نوشتم:

1
2
3
4
5
6
7
8
...
8888+*888++8/-*        (8*((8*(8+8))-((8+(8+8))/8)))
8888+*88+8+8/-*        (8*((8*(8+8))-(((8+8)+8)/8)))
8888+*88+8/-*8-        ((8*((8*(8+8))-((8+8)/8)))-8)
8888+*88/-*88+-        ((8*((8*(8+8))-(8/8)))-(8+8))
8888+*88/-*8-8-        (((8*((8*(8+8))-(8/8)))-8)-8)
888+88+8/88*-*-        (8-((8+8)*(((8+8)/8)-(8*8))))
...

جواب‌های کامل رو می‌تونید این‌جا ببینید.

اول از همه کلاس اصلی برنامه:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class EightPuzzleSolver
{
public:
    EightPuzzleSolver(WINDOW *_window, const std::string& outFile);
    ~EightPuzzleSolver();
    bool initialize(const size_t &start, const size_t &end);
    void start();
    void setThreadCount(const size_t&);
    std::vector<std::string> getResults();
private:
    bool check(const std::string &inputs);
    void permutation(std::string &input, size_t index);
    double total;
    int current;
    double precentage;
    uint printLine;
    std::pair<size_t,size_t> range;
    WINDOW* window;
    std::stack<int> evaluation;
    std::string symbols;
    std::vector<std::string> results;
    std::ofstream outFile;
    size_t splitDepth;
    std::mutex guard;
    // Timing
    std::chrono::steady_clock::time_point startTime;
};

پیاده‌سازی تابع تولید جایگشت:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void EightPuzzleSolver::permutation(string &input, size_t index)
{
    if(index==input.size()) {
        this->guard.lock();
        steady_clock::time_point now = steady_clock::now();
        auto ticks = now-this->startTime;
        auto s = duration_cast<chrono::seconds>(ticks).count()%60;
        auto m = duration_cast<chrono::minutes>(ticks).count()%60;
        auto h = duration_cast<chrono::hours>(ticks).count();
        auto ms = duration_cast<chrono::milliseconds>(ticks).count();
        wmove(window, 2, 0);
        ++current;
        precentage = 100.0*static_cast<double>(current)/total;
        std::chrono::milliseconds predict(static_cast<int>(100*ms/precentage));
        wprintw(window, "Elapsed Time: %dh:%dm:%ds,"
                   " Remaining Time: %04dh:%02dm:%02ds,"
                   " Progress: %d of %.0lf (%.4f%%) sample: %s",
                h,m,s,
                duration_cast<std::chrono::hours>(predict).count(),
                duration_cast<std::chrono::minutes>(predict).count()%60,
                duration_cast<std::chrono::seconds>(predict).count()%60,
                current,total,precentage,input.c_str());
        wrefresh(window);
        if(check(input)) {
            wmove(window, printLine, 0);
            wprintw(window, "%d: %s",results.size()+1,input.c_str());
            results.push_back(input);
            outFile << input << std::endl;
            wrefresh(window);
            ++printLine;
        }
        this->guard.unlock();
        return;
    }
    else if (index == this->splitDepth) {
        vector<thread> threads;
        for (char symbol : this->symbols) {
            input[index] = symbol;
            threads.emplace_back([=] {
                string cpy(input);
                permutation(cpy, index+1);
            });
        }
        for (thread& t: threads) {
            t.join();
        }
    }
    else {
        for (char symbol : this->symbols) {
            input[index] = symbol;
            permutation(input, index+1);
        }
    }
}

و تابع ارزیابی عبارت پسوندی:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
bool EightPuzzleSolver::check(const string &inputs)
{
    while(!evaluation.empty()) {
        evaluation.pop();
    }
    for(const auto& n: inputs) {
        int n1, n2;
        switch (n) {
        case '+': {
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n1 = evaluation.top();
                    evaluation.pop();
                }
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n2 = evaluation.top();
                    evaluation.pop();
                }
                evaluation.push(n2+n1);
            }
            break;
        case '-': {
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n1 = evaluation.top();
                    evaluation.pop();
                }
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n2 = evaluation.top();
                    evaluation.pop();
                }
                evaluation.push(n2-n1);
            }
            break;
        case '*': {
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n1 = evaluation.top();
                    evaluation.pop();
                }
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n2 = evaluation.top();
                    evaluation.pop();
                }
                evaluation.push(n2*n1);
            }
            break;
        case '/': {
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n1 = evaluation.top();
                    evaluation.pop();
                }
                if(evaluation.empty()) {
                    return false;
                }
                else {
                    n2 = evaluation.top();
                    evaluation.pop();
                }
                if(n1==0) {
                    return false;
                }
                else {
                    evaluation.push(n2/n1);
                }
            }
            break;
        case '8':
            evaluation.push(8);
            break;
        default:
            return false;
            break;
        }
    }
    return (evaluation.size()==1 && evaluation.top()==1000);
}

و در نهایت پیاده‌سازی تابع شروع کننده:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void EightPuzzleSolver::start()
{
    for (size_t length = this->range.second; length> this->range.first; --length) {
        wmove(window, 0, 0);
        total = pow(5.0,length);
        current = 0;
        precentage = 0.0;
        wprintw(window, "Checking strings of length: %d",length);
        wmove(window, 1, 0);
        wprintw(window, "Total: %.0lf",pow(5.0,length));
        string input(length,'8');
        this->startTime = steady_clock::now();
        permutation(input,0);
    }
}

دیدگاه‌ها