Kata learns to code

Quy Hoạch Động (QHD) là 1 phương pháp rất mạnh mẽ trong Tin học. Nếu phân tích kĩ các bạn sẽ thấy những thuật toán nổi tiếng như Ford-Bellman, Dijkstra, hay Floyd đều có bản chất là QHD. Nhưng không phải bài toán nào cũng giải bằng QHD được, nếu quá áp đặt, cố sức giải nó như vậy bạn sẽ dễ dàng mắc phải 1 sai lầm gọi là Phụ thuộc tiền sử.

Để tìm hiểu sai lầm này chúng ta nhắc lại về nguyên lí QHD do Bellman phát minh ra: “Một dãy là tối ưu thì các dãy con của nó cũng là tối ưu”. Nghe có vẻ khó hiểu nhưng đại loại là ta có 1 cái bảng rồi lần lượt điền các số vào bảng đó, các số điền vào đầu tiên thường đơn giản, các số sau
đó dựa vào các số trước mà điền, cho đến khi điền kín bảng. Kết quả bài toán là số mà ta điền cuối cùng. Như vậy nguyên lí “chia để trị” đã được đẩy tới cao độ ở đây.

Khâu quan trọng nhất là làm thế nào điền được số sau dựa trên các số trước, hay nói cách khác là ta đang tìm 1 hệ thức truy hồi.

Gọi f(i) là hàm QHD tại i, ta xây dựng công thức truy hồi tính f(i) dựa vào các f(j) với j = i - 1, i - 2, … Công thức truy hồi này chỉ được phụ thuộc vào các f(j) cùng các đại lượng cố định của các j (cho trong đề bài) tuyệt đối không được phụ thuộc vào tiền sử, cách thức tạo nên f(j). Đây là chính là sai lầm mà tôi muốn nói đến!

Để dễ hiểu chúng ta xét 1 ví dụ rất thú vị sau:

Bài toán: ngày xửa ngày xưa, có 1 chàng Hoàng tử bị 1 mụ Phù thủy hóa phép biến thành 1 con ếch, còn Công chúa thì bị mụ ta nhốt trong 1 tòa lâu đài nằm trên 1 hòn đảo giữa hồ. Bây giờ ếch đang đứng ở bờ hồ, trên đoạn thẳng từ chỗ đó đến tòa lâu đài có các lá sen nổi trên mặt nước ở những vị trí, khoảng cách khác nhau, ếch phải nhảy qua các lá sen để vào tòa lâu đài cứu Công chúa. Bước nhảy kề sau không được dài hơn bước nhảy kề trước A mét cho trước.
Ếch có 1 túi rất nhiều muỗi thần, ăn K con muỗi, ếch có thể nhảy tối đa trong 1 bước là K mét. Mỗi bước nhảy (dù dài hay ngắn) đều tốn 1 giây. Cho trước thời gian giới hạn là T giây, hãy tính số muỗi ít nhất mà ếch cần ăn để có thể nhảy đến tòa lâu đài!

Dữ liệu vào cho trong file ECHOP.INP có cấu trúc:
Dòng đầu là 3 số nguyên N A T
Dòng 2 là N số nguyên dương tăng dần thể hiện tọa độ các lá sen.
Các số trên cùng 1 dòng cách nhau bởi ít nhất 1 dấu cách.
Dữ liệu ra file ECHOP.OUT gồm 1 số duy nhất là số muỗi tối thiểu, nếu không có phương án giải
cứu Công chúa in ra số -1

Rồi, đọc xong là biết phải dùng QHD, đây là cách sai:
Gọi d[t, i] là số muỗi ít nhất cần ăn khi phải nhảy đến lá sen thứ i và thời gian giới hạn là t. Để tính d[t, i] ta chỉ cần xét các d[j, t - 1] với j = i - 1, i - 2, … kiểm tra xem khoảng cách từ lá sen j đến lá sen i là bao nhiêu (là P), xem tiền sử của d[j, t - 1] xem lá sen kề trước j là lá nào (lá thứ z), tính khoảng cách giữa lá sen z và j là Q, kiểm tra Q + A >= P được thỏa mãn rồi đặt x = max(d[t, j], P), trong các x như thế chọn ra cái nhỏ nhất và đó chính là d[t, i]

Cách đúng: gọi d[t, i, j] là số muỗi ít nhất khi trong thời gian t, cần nhảy đến lá sen j nhưng lá kề trước j phải là i. Lúc này hệ thức truy hồi tương tự như trên nhưng không còn phụ thuộc tiền sử nữa.

Bạn cũng dễ mắc sai lầm này khi đi tìm cách giải hoàn hảo cho các bài toán “bất trị”, cho đến nay loài người vẫn chưa giải được như bài toán Người du lịch, bài toán Tìm đường đi dài nhất không lặp lại đỉnh trên đồ thị trọng số dương, bài toán Tập thống trị nhỏ nhất…

Những ai đam mê lập trình và thuật toán hẳn có nhiều lúc ngây ngất trước vẻ đẹp của các thuật toán cũng như sự tinh tế trong cách cài đặt chúng! Có nhiều bài toán nghĩ ra thuật toán rất khó nhưng nghĩ ra rồi thì cài đặt lại rất dễ. Lại có những bài ngược lại, thuật toán thì thấy ngay nhưng để biểu diễn cho máy nó hiểu thì khó vô cùng. Lại cũng có những bài “quái chiêu” cả thuật toán lẫn cài đặt đều khó nhăn răng và 1 trong số đó là bài toán kinh điển Hôn Nhân Bền Vững tôi muốn giới thiệu cùng các bạn.

Phát biểu bài toán nghe khá hấp dẫn: có N chàng trai và N cô gái, mỗi chàng trai phát biểu cảm nghĩ về N cô gái kia (rằng là cô này anh ta thích nhất, cô này thích nhì, ba, … cho đến cô thích thứ N) tương tự các cô gái cũng phát biểu như vậy về các chàng trai. Hãy ghép đôi họ với nhau sao cho các cuộc hôn nhân này là bền vững nghĩa là không được tồn tại 2 cặp mà người chồng bên cặp này lại thích người vợ bên cặp kia hơn vợ mình, đồng thời người vợ bên cặp kia lại cũng thích người chồng bên cặp này hơn chồng mình, khi đó 2 người này sẽ tìm đến với nhau và thế là ngoại tình.

Bây giờ chúng ta sẽ nghiên cứu 1 thuật toán xây dựng các cặp bền vững dựa trên ý tưởng giống như đời thực của bài toán. Mỗi chàng trai X sẽ chọn cho mình 1 cô dâu, hiển nhiên là anh ta sẽ chọn cô gái đầu tiên trong danh sách của mình. Nếu cô này đã hứa hôn (đã được chọn trước đó) với chàng trai khác mà cô ta thích hơn thì anh chàng X phải chọn người phụ nữ kế tiếp trong danh sách của anh ta, quá trình này tiếp tục cho đến khi X tìm được một cô Y chưa được hứa hôn hoặc thích anh ta hơn anh chàng đã hứa hôn trước đó. Nếu Y chưa được hứa hôn thì cô ta sẽ được gả cho X và chúng ta tiếp tục cho người đàn ông kế tiếp. Còn nếu Y đã hứa hôn thì sẽ hủy bỏ cuộc đính hôn và gả cô ta cho X (vì cô ta thích X hơn), và chúng ta lại tiếp tục với anh chàng vừa bị từ hôn.

Phương pháp này có lẽ được mô phỏng từ 1 câu chuyện trong các tiểu thuyết của thế kỉ 19. Rất đơn giản phải không? Nhưng còn cài đặt thì sao? Trong các tài liệu thường thấy ở VN thì họ dùng foward bởi phải xây dựng 2 hàm mà trong thân hàm này gọi tới hàm kia, rất rối rắm phức tạp, khó sửa lỗi và code cũng dài dòng. Còn trong cuốn Cẩm Nang Thuật Toán (sách dịch nước ngoài) tập 2, tác giả đã có 1 cách cài đặt vô cùng đỉnh cao, gọn nhẹ và xúc tích, (điều thường thấy trong bộ sách này) chẳng phải pho goắc pho ghiếc gì hết.

Bởi vì tất cả các danh sách sở thích đều co chung độ dài, cài đặt đơn giản nhất là dùng mảng 2 chiều. Ví dụ prefer[m, w] là cô gái thứ w trong danh sách sở thích của chàng trai thứ m. Hơn nữa chúng ta cần theo dõi xem mỗi chàng trai đã xử lí đến đâu trong danh sách anh ta. Điều nay có thể được thực hiện bằng 1 mảng 1 chiều next, mảng này khởi tạo đến 0 và next[m] + 1 là chỉ số của cô gái kế tiếp trong danh sách của chàng trai thứ m, chỉ danh của cô tra sẽ là prefer[m, next[m] + 1]. Với mỗi cô gái ta cần theo dõi vị hôn phu hiện thời là ai (fiancee[w] sẽ là chàng trai đã hứa hôn với cô gái w) và chúng ta cần trả lời câu hỏi ” người đàn ông thứ s có được thích hơn so với người đàn ông fiancee[w] hay không?”. Câu trả lời này có thể được giải đáp bằng cách tìm kiếm tuần tự cho tới khi s hoặc fiancee[w] được tìm thấy, nhưng cách này không hiệu quả nếu 2 người nằm ở cuối danh sách. Thay vì vậy, chúng ta dùng 1 danh sách ngược: rank[w, s] là chỉ số của chàng trai thứ s trong danh sách sở thích của cô w. Sự phù hợp của vị hôn phu s có thể xác định rất nhanh chóng bằng cách kiểm tra xem rank[w, s] có nhỏ hơn rank[w, fiancee[w]] hay không. Các mảng này được xây dựng dễ dàng và trực tiếp từ danh sách các sở thích. Để khởi đầu, chúng ta dùng 1 lính canh là chàng trai 0 để khởi tạo cho vị hôn phu và đặt anh ta ở cuối tất cả các danh sách sở thích của các cô gái.

Với cấu trúc dữ liệu được khởi tạo bằng phương pháp này, việc cài đặt có thể thực hiện dễ dàng như sau:

Language: Pascal
Author: Katatunix

for m := 1 to N do
begin
    s := m;
    repeat
        next[s] := next[s] + 1;
        w := prefer[s, next[s]];
        if rank[w, s] < rank[w, fiancee[w]] then
        begin
            t := fiancee[w]; fiancee[w] := s; s := t;
        end;
    until s = 0;
end;

1 + 1 = ?
12*(16-(6-40/20)-7) + 5*(23-3*(7-2)) = ?
sqrt[pow[12*(16-(6-40/20)-7) + 5*(23-3*(7-2)),3]] = ?

package calexp;

public class CalculateExpression {

    private static final String MSG = "Invalid Expression";

    private static final String[] FUNCTION_LIST = {
        "abs", "sqrt", "sin", "cos", "tan", "cotan", "log", "exp", "pow"
    };

    private static final int[] PARAMETER_NUMBER = {
            1,      1,     1,     1,     1,       1,     1,     1,     2
    };

    public static double calculate(String exp) throws Exception {
        int sepa = findSeparator(exp);

        if (sepa == -1)
            return calcuSingleExp(exp);

        if (sepa == 0)
            switch (exp.charAt(0)) {
                case '+':
                    return calculate(exp.substring(1));
                case '-':
                    return -calculate(exp.substring(1));
                default:
                    throw new Exception(MSG);
            }

        double part1 = calculate(exp.substring(0, sepa));
        double part2 = calculate(exp.substring(sepa + 1));

        switch (exp.charAt(sepa)) {
            case '+':
                return part1 + part2;
            case '-':
                return part1 - part2;
            case '*':
                return part1 * part2;
            default:
                return part1 / part2;
        }
    }

    private static double calcuSingleExp(String exp) throws Exception {
        exp = exp.trim();
        if (exp.isEmpty()) throw new Exception(MSG);

        int len = exp.length();
        if (exp.charAt(len - 1) == ')') {
            if (len < 3 || findOpen(exp, len - 1) != 0)
                throw new Exception(MSG);
            return calculate(exp.substring(1, len - 1));
        }

        try {
            return Double.valueOf(exp);
        } catch (NumberFormatException e) {
            if (exp.charAt(len - 1) != ']') throw new Exception(MSG);
            int open = findOpen(exp, len - 1);
            String func = exp.substring(0, open).trim();

            exp = exp.substring(open + 1, len - 1);
            String[] sub = splitFay(exp);

            int funcIndex = findFuncIndexOf(func);
            if (funcIndex == -1) throw new Exception(MSG);
            if (sub.length > PARAMETER_NUMBER[funcIndex]) throw new Exception(MSG);

            double res = calculate(sub[0]);

            switch (funcIndex) {
                case 0: return Math.abs(res);
                case 1: return Math.sqrt(res);
                case 2: return Math.sin(res);
                case 3: return Math.cos(res);
                case 4: return Math.tan(res);
                case 5: return 1.0 / Math.tan(res);
                case 6: return Math.log(res);
                case 7: return Math.exp(res);
                default: return Math.pow(res, calculate(sub[1]));
            }
        }
    }

    private static int findFuncIndexOf(String func) {
        for (int i = 0; i < FUNCTION_LIST.length; i++)
            if (FUNCTION_LIST[i].equalsIgnoreCase(func))
                return i;
        return -1;
    }

    private static String[] splitFay(String listExp) throws Exception {
        java.util.ArrayList<String> listSub = new java.util.ArrayList<String>();
        char ch;
        int j = 0;
        for (int i = listExp.length() - 1; i >= 0; i--) {
            ch = listExp.charAt(i);
            if (ch == ')' || ch == ']')
                i = findOpen(listExp, i);
            else if (ch == ',') {
                listSub.add(listExp.substring(j, i));
                j = i + 1;
            }
        }
        listSub.add(listExp.substring(j, listExp.length()));
        String[] s = new String[listSub.size()];
        for (j = 0; j < s.length; j++)
            s[j] = listSub.get(j);
        return s;
    }

    private static int findSeparator(String exp) throws Exception {
        int len = exp.length();
        if (isOperator(exp.charAt(len - 1)))
            throw new Exception(MSG);

        int i, j = -1;
        char ch;
        for (i = len - 1; i >= 0; i--) {
            ch = exp.charAt(i);
            if (ch == ')' || ch == ']') {
                i = findOpen(exp, i);
                if (i == -1)
                    throw new Exception(MSG);
            } else if (ch == '+' || ch == '-') {
                return i;
            } else if (ch == '*' || ch == '/') {
                j = i;
            }
        }
        return j;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    private static int findOpen(String exp, int off) throws Exception {
        int count = 0;
        char close = exp.charAt(off);
        char open = close == ')' ? '(' : '[';
        while (off >= 0) {
            if (exp.charAt(off) == close) {
                count++;
            } else if (exp.charAt(off) == open) {
                count--;
                if (count == 0) return off;
            }
            off--;
        }
        throw new Exception(MSG);
    }

    public static void main(String[] args) {
        try {
            String s = "12*(16-(6-40/20)-7)  +  5*(23-3*(7-2))";
            System.out.println(calculate(s));

            s = "sqrt[pow[12*(16-(6-40/20)-7)  +  5*(23-3*(7-2)),3]]";
            System.out.println(calculate(s));

            s = "abs[cotan[sin[(5*(13-7)- (5*6-9)*2)+pow[2,3]*(sqrt[9*pow[9.13,2.2]]-8+12*cos[23])]-log[4]]]";
            System.out.println(calculate(s));

            s = "(1 * (4 + 50)) / 69";
            System.out.println(calculate(s));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

Trò chơi Trúc Xanh (Kawai Chen Program Study) khá phổ biến, đặc biệt đối với chị em phụ nữ. Luật chơi là tìm ra 2 quân giống nhau và có đường đi giữa chúng không rẽ quá 2 lần. Đường đi là 1 dãy liên tiếp các ô trống kề cạnh nhau. Dưới góc độ lập trình, tôi tự hỏi khi người chơi click vào 2 quân giống nhau làm thế nào để kiểm tra xem giữa chúng có tồn tại đường đi thỏa mãn hay không? Bảng Pokemon được biểu diễn bởi ma trận a[0..17, 0..10], ở đây để cho khớp với hệ tọa độ khi lập trình GUI tôi cho chỉ số cột của a đứng trước chỉ số hàng, điều này cũng không có gì quan trọng lắm. Bảng thực sự chỉ có các cột 1..16 và các hàng 1..9 các ô đường viền dùng làm lính canh (trong luật chơi cho phép đi ra ngoài bảng) các ô này đương nhiên đều là ô trống. Ma trận a quy ước như sau:

• a[i, j] = 0 nếu ô (i, j) trống
• a[i, j] = k > 0 nếu ô (i, j) chứa quân thứ k

Giả sử có 2 ô có quân Pokemon giống nhau cho trước (i1, j1) và (i2, j2) làm thế nào để kiểm tra đường đi thỏa mãn giữa chúng? Vì số lần rẽ chỉ giới hạn là 2 nên bạn có thể liệt kê, xét hết tất cả các trường hợp cùng với 1 đống if else lồng nhau loạn xạ, cách này không hay cho lắm. Ta hãy xét 1 cách khác hay hơn, chuyển bài toán về dạng đồ thị như sau:

• 2 ô (i1, j1) và (i2, j2) cho trở thành ô trống
• tập đỉnh của đồ thị là tập các ô trống
• 2 đỉnh có cạnh nối với nhau nếu 2 ô tương ứng với chúng là (u1, v1) và (u2, v2) cùng nằm trên 1 cột hay 1 hàng và nằm giữa 2 ô này toàn là ô trống
• trọng số tất cả các cạnh đều = 1

Bài toán chuyển về tìm đường đi ngắn nhất từ đỉnh ứng với ô (i1, j1) đến đỉnh ứng với ô (i2, j2). Nên dùng Tìm kiếm theo chiều rộng vì trọng số các cạnh chỉ là 1. Nếu đường đi này có độ dài không vượt quá 3 thì kết luận có đường đi thỏa mãn, ngược lại thì không có.

Các bạn thấy sao? Có ai có thuật toán nào nhanh hơn thì vào bàn bạc nhé!