Brute Force - Sức mạnh của máy tính

Khởi đầu từ vài bài toán dân gian

Ngày bé khi đi học tiểu học, chúng ta có thể đã từng gặp một bài toán bằng thơ như sau:

Vừa gà vừa chó
Bó lại cho tròn
Ba mươi sáu con
Một trăm chân chẵn
Hỏi có bao nhiêu con gà và bao nhiêu con chó?

Bài toán này đối với học sinh lớp lớn sẽ có cách giải rất đơn giản bằng cách lập hệ phương trình hai ẩn số và nhanh chóng giải ra ngay nghiệm là số chó là 14 con và số gà là 22 con. Tuy nhiên, đối với bài toán dưới đây thì câu chuyện không đơn giản như vậy:

Trăm trâu, trăm cỏ
Trâu đứng ăn năm
Trăm nằm ăn ba
Lụ khụ trâu già
Ba con một bó
Hỏi có bao nhiêu trâu mỗi loại?

Rõ ràng, với bài toán trên, nếu bằng cách lập phương trình, các bạn sẽ chỉ có 2 phương trình mà có đến 3 ẩn:

$$\begin{cases} x+y+z = 100 \\ 5x+3y+\frac z 3 = 100 \end{cases}$$

Đây là dạng phương trình Diophantine (phương trình nghiệm nguyên), một dạng phương trình với cách giải rất bất định và phức tạp. Tuy nhiên, với sức mạnh của máy tính, chúng ta có thể bắt chúng “mò” một cách thủ công chỉ với vài vòng lặp for như sau:

for (let trâu_đứng=0; trâu_đứng <= (100/5); trâu_đứng++){
    for (let trâu_nằm=0; trâu_nằm <= (100/3); trâu_nằm++){
        let trâu_già = 100 - (trâu_đứng + trâu_nằm);
        let số_bó_cỏ = trâu_đứng*5 + trâu_nằm*3 + trâu_già*(1/3);
        if (số_bó_cỏ === 100) {
            console.log(trâu_đứng, trâu_nằm, trâu_già);
        }
    }
}

Mình thường phỏng vấn junior dev bằng các bài toán thú vị thế này để chọn lựa ra ứng viên ưng ý cho mình :)

Ma phương

Hình trên là một ma phương 3×3. Tính chất của một ma phương là tổng các số trên các hàng, các cột, các đường chéo đều bằng nhau.

Mình còn nhớ, vào khoảng năm 1990 hay 1991 gì đó, trên báo Khăn Quàng Đỏ hay báo Nhi Đồng gì đó, mình tìm thấy câu đố về bài toán này: “Tìm cách sắp xếp các số từ 1-9 vào trong một hình vuông 3×3 sao cho tổng các hàng, cột, và đường chéo đều bằng nhau“. Mình và bố mình lúc ấy đã cùng nhau mày mò suốt cả buổi trời để giải bài toán ấy. Thật là một kỷ niệm đẹp!

Sau này, khi lớn lên, mới biết rằng đấy gọi là một ma phương 3×3, thậm chí người ta còn đưa ra được phương pháp tổng quát để giải ma phương bậc n mà lúc ấy mình không hay biết. Thật kỳ diệu! Vì dù chỉ có 9 số (từ 1-9), và 9 ô vuông nhưng có đến \(9! = 362,880\) cách sắp xếp khác nhau. Tuy nhiên, con số 362,880 có thể là một con số lớn đối với con người, nhưng đối với máy tính thì chỉ là … chuyện nhỏ ! Giải thuật đơn giả:

• Sinh ra một hoán vị các số 1-9 rồi đưa vào các ô vuông của ma phương

• Kiểm tra xem ma phương ấy có hợp lệ hay không

const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const permutations = permute(nums);
const result = [];

permutations.forEach(p => {
    const row1 = p[0] + p[1] + p[2];
    const row2 = p[3] + p[4] + p[5];
    const row3 = p[6] + p[7] + p[8];
    const col1 = p[0] + p[3] + p[6];
    const col2 = p[1] + p[4] + p[7];
    const col3 = p[2] + p[5] + p[8];
    const diag1 = p[0] + p[4] + p[8];
    const diag2 = p[2] + p[4] + p[6];
    if (row1 == row2 && row2 == row3 && row3 == col1 && col1 == col2 && col2 == col3 && col3 == diag1 && diag1 == diag2) {
        result.push(p);
    }
});

// print out all results 
result.forEach(r => {
    console.log(`${r[0]} ${r[1]} ${r[2]}\n${r[3]} ${r[4]} ${r[5]}\n${r[6]} ${r[7]} ${r[8]}\n`);
    console.log('---------------------');
});

Giải thuật để sinh hoán vị các bạn có thể tham khảo nhiều nơi trên mạng. Mình xin đưa source code để các bạn tham khảo thêm. Dưới đây là giải thuật sinh hoán vị của \(k\) phần tử trong tập hợp \(n\) phần tử. Ví dụ hoán vị 2 phần tử của các số \(1,2,3\) gồm có: \((1,2),(1,3),(2,1),(2,3),(3,1),(3,2)\)

// generate all permutations with length n of the numbers nums
function permute(nums, len) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    const current = new Array(len);
    function dfs(pos) {
        if (pos == len) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            current[pos] = nums[i];
            dfs(pos + 1);
            used[i] = false;
        }
    }
    dfs(0);
    return result;
}

Câu chuyện ổ khóa của Gargamel và Xì Trum

Gargamel là một phù thủy khét tiếng độc ác. Lão có một chiếc rương đầy kho báu mà lão đã cướp được từ các chú Xì Trum. Một ngày nọ, các chú Xì Trum lẻn vào dinh thự của Gargamel và đánh cắp chiếc rương. Tuy nhiên, chiếc rương này được khóa bằng ổ khóa ba chữ số và Xì Trum không thể phá được chiếc rương. May thay, họ tìm thấy một công thức được khắc trên rương để làm manh mối cho mật khẩu:

• 1,4,7 - một chữ số đúng nhưng sai vị trí

• 1,8,9 - một chữ số đúng và đúng vị trí

• 9,6,4 - hai chữ số đúng nhưng cả hai đều sai vị trí

• 5,2,3 - tất cả đều sai

• 2,8,6 - một chữ số đúng nhưng sai vị trí

Bạn có thể giúp các chú Xì Trum không?

Thoạt nhìn thì bài toán này trông chẳng có vẻ gì là có thể giải bằng lập trình được. Nhưng nếu phát biểu phát biểu lại bằng một cách khác, có lẽ sẽ dễ hình dung hơn:

Cho một tập hợp có thứ tự chứa ba phần tử a,b,c phân biệt (từ 1-9), hãy kiểm tra các các điều kiện sau:

• “x,y,z - một chữ số đúng nhưng sai vị trí” =>
  a=4 hoặc a=7 hoặc b=1 hoặc b=7 hoặc c=1 hoặc c=4

• “1,8,9 - một chữ số đúng và đúng vị trí” =>
  a=1 hoặc b=8 hoặc c=9

• “9,6,4 - hai chữ số đúng nhưng cả hai đều sai vị trí“ => (a=6 và b=4) hoặc (a=4 và c=9) hoặc ….

• … các bạn tự suy ra các luật còn lại nhé!

Việc tiếp theo là sinh ra tất cả các hoán vị 3 phần tử giá trị từ 1-9 và kiểm tra từng hoán vị với tất cả các điều kiện trên (vẫn dùng function permute với length 3). Nếu hoán vị nào vượt qua tất cả các điều kiện thì nó sẽ là đáp án. Source code có thể mô tả như sau:

function rule1Check(permutation) {
    const [a,b,c] = permutation;
    if (a==4 || a==7 || b==1 || b==7 || c==1 || c==4) return true;
    return false;
}
function rule2Check(permutation);
function rule3Check(permutation);
function rule4Check(permutation);
function rule5Check(permutation);

const nums = [1,2,3,4,5,6,7,8,9];
const allPermutations = permute(nums, 3);
allPermutations.forEach(p => {
    if (rule1Check(p) && rule2Check(p) && rule3Check(p) && rule4Check(p) && rule5Check(p)){
        console.log(p);
    }
});

Thoát khỏi Kim Tự Tháp

Ali là một nhà thám hiểm nổi tiếng, anh ta đã lẻn được vào một kim tự tháp của một vị Pharaoh và kiếm được một vô số tiền vàng trên đỉnh của kim tự tháp này. Tiếc là đến lúc chuẩn bị đi xuống, anh ta đã vô tình kích hoạt hệ thống báo động và làm các lính canh thức giấc. Kim tự tháp có nhiều tầng, mỗi tầng chia làm nhiều phòng và mỗi phòng có số lượng lính canh khác nhau. Mỗi phòng có hai hành lang bên trái và bên phải dẫn xuống hai phòng ở tầng dưới. Ali cần phải tính toán đường đi xuống đến tầng dưới cùng sao cho gặp ít lính canh nhất.

Đây là một bài toán kinh điển trong phương pháp Quy Hoạch Động (Dynamic Programming). Mình không có ý định đi quá sâu vào chi tiết của phương pháp này. Trong bài viết này, mình chỉ định giới thiệu một giải pháp để áp dụng brute force. Phương pháp đơn giản là đưa mô hình trên thành dạng cây nhị phân như hình vẽ sau:

Hình trên là biểu diễn của tất cả các cách đi từ đỉnh đến tầng thứ 4 từ trên xuống. Nhận xét thấy đường đi từ đỉnh đến mỗi nút lá đều ứng với một con đường mà ta có thể mã hóa thành một giá trị nhị phân lần lượt như sau: \(5(000),9(001),\dots, 10(111)\) và có thể dễ dàng nhận thấy kim tự tháp có \(n\) tầng sẽ có \(2^{n-1}\) con đường đi từ đỉnh đến chân kim tự tháp. Từ đó, chúng ta có thể đề nghị một thuật toán đơn giản để tìm đường tối ưu đi qua kim tự tháp có \(n\) tầng như sau:

• Đặt \(min = + \infty\)

• Lặp cho \(i: 1 \to 2^{n-1}\):

  • Gọi \(s=r_0\) là tổng số lính ban đầu ở phòng đỉnh tháp

  • Gọi \(b\) là giá trị của \(i\) đổi sang số nhị phân, có độ dài \(n-1\). Lần lượt xét các bit nhị phân \(b_j\) của \(b\), với \(j:1 \to n-1\). Ví dụ: \(i=5, n=5 \Rightarrow b=0101, b_1 = 0, b_2=1, b_3=0, b_4=1\)

  • Nếu \(b_j = 0\): đi sang phòng bên trái, cập nhật \(s\)

  • Ngược lại, nếu \(b_j=1\) đi sang phòng bên phải, cập nhật \(s\)

  • Nếu \(s < min\), cập nhật \(min = s\)

Cấu trúc dữ liệu của bài toán dùng một mảng 2 chiều để biểu diễn. Các bạn có thể tham khảo code của mình dưới đây:

const pyramid = [
    [6],
    [3, 5],
    [11, 7, 7],
    [5, 9, 8, 10],
    [6, 4, 6, 12, 5],
    [8, 12, 11, 14, 17, 9]
];

const nLevels = pyramid.length;
const nPaths = 2**(pyramid.length - 1);

let minValue = Infinity;
let path = [];
for (let i=0; i < nPaths; i++){
    // this is to calculate the binary representation of the path
    let pathValue = i;
    // for each path, calculate the sum of the values
    let s = pyramid[0][0];
    // this is to store the path
    let currentPath = [pyramid[0][0]]; 
    // start from the top of the pyramid
    let currentRoomIndex = 0;
    for (let j = 0; j < nLevels - 1; j++){
        // if value is even, go left, else go right
        if (pathValue % 2 == 0){
            s += pyramid[j + 1][currentRoomIndex];
            currentPath.push(pyramid[j + 1][currentRoomIndex]);
        } else {
            currentRoomIndex++;
            s += pyramid[j + 1][currentRoomIndex];
            currentPath.push(pyramid[j + 1][currentRoomIndex]);
        }
        // this is to shift the path value to the right, equivalent to dividing by 2
        pathValue = pathValue >> 1; // (value = value / 2)
    }

    // check if the sum is less than the minimum value
    if (s < minValue){
        minValue = s;
        path = [...currentPath];
    }
}

console.log(minValue, path);