Python cho người Việt

Python cho người Việt

Phỏng vấn: Cài đặt "ngăn xếp" với thao tác "min/max"

written by Nguyễn Thành Nam, on Mar 11, 2015 10:07:20 AM.

Câu hỏi

Cài đặt cấu trúc dữ liệu ngăn xếp với thao tác trả về phần tử nhỏ (hay lớn) nhất hiện tại của ngăn xếp.

Phân tích

Ngăn xếp (stack) là cấu trúc dữ liệu vào sau ra trước (Last In, First Out). Nói đến ngăn xếp ta phải nhớ ngay đến hai tác vụ quan trọng nhất là đẩy vào (push) và lấy ra (pop). Khi push dữ liệu vào, dữ liệu sẽ nằm trên cùng của ngăn xếp (top of stack). Khi pop, dữ liệu trên cùng của ngăn xếp sẽ được lấy ra khỏi ngăn xếp.

Ngoài hai tác vụ trên, ta còn có thể kể thêm một số tác vụ truy vấn cấu trúc dữ liệu này ví dụ như số lượng dữ liệu có trong ngăn xếp, liệu ngăn xếp có dữ liệu hay không, hay xem dữ liệu trên cùng của ngăn xếp (mà không lấy nó ra khỏi ngăn xếp).

Câu hỏi này yêu cầu ta cài đặt hai tác vụ push, pop, và thêm tác vụ min (hoặc max) để cho biết dữ liệu nhỏ nhất (hay lớn nhất) hiện tại trong ngăn xếp mà không lấy nó ra.

Cách giải dễ nhất

Điều đầu tiên ta nghĩ đến sẽ là tạo một biến để chứa giá trị cực tiểu (hay cực đại). Khi push vào, ta sẽ cập nhật lại biến này nếu cần. Khi hỏi min thì ta chỉ cần trả về giá trị này.

Vấn đề phức tạp là khi pop ra, làm sao để ta cập nhật lại biến cực tiểu đó? Một cách rất đơn giản là ta sẽ duyệt lại toàn bộ các dữ liệu đang có trong ngăn xếp để đưa ra giá trị cực tiểu mới.

Cách giải này dẫn đến độ phức tạp O(1) cho push, O(1) cho minO(n) cho pop.

class Stack(object):

    def __init__(self):
        self.store = []
        self.min = None

    def push(self, value):
        self.store.append(value)
        if self.min is None or self.min < value:
            self.min = value

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        if not self.store:
            self.min = None
        else:
            self.min = min(self.store)
        return r

    def min(self):
        return self.min

Cách giải O(1) cho pop

Ta nhận thấy rằng tác vụ pop có độ phức tạp O(n) là bởi vì ta phải duyệt lại toàn bộ các phần tử hiện tại của ngăn xếp để xác định phần tử cực tiểu.

Một phương pháp thường được sử dụng để tăng tốc tác vụ là sử dụng bộ nhớ tạm (cache). Ta sẽ tráo đổi giữa thời gian chạy, và không gian nhớ. Nếu như ở mỗi lần push, ta lưu giá trị cực tiểu của các phần tử trong ngăn xếp này vào trong một ngăn xếp thứ hai, thì khi trả lời min, ta chỉ việc nhìn vào (peek) ngăn xếp thứ hai là sẽ có ngay kết quả. Và khi pop thì ta chỉ việc pop ở cả hai ngăn xếp. Các tác vụ này đều có độ phức tạp O(1), nhưng ta sẽ tốn thêm O(n) bộ nhớ cho ngăn xếp thứ hai.

class StackBase(object):

    def __init__(self):
        self.store = []

    def push(self, value):
        self.store.append(value)

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        return r

    def peek(self):
        return self.store[-1]

    def __bool__(self):
        return bool(self.store)


class StackWithMin(object):

    def __init__(self):
        self.store = StackBase()
        self.mins = StackBase()

    def push(self, value):
        self.store.push(value)
        if not self.mins or self.mins.peek() < value:
            self.mins.push(value)
        else:
            self.mins.push(self.min.peek())

    def pop(self):
        self.mins.pop()
        return self.store.pop()

    def min(self):
        return self.mins.peek()

Cách giải O(1) cho pop cải tiến

Cách giải trên tráo đổi O(1) bộ nhớ và O(n) thời gian cho O(n) bộ nhớ và O(1) thời gian.

Vấn đề dẫn đến O(n) bộ nhớ là do ở mỗi lần push ta cũng lưu lại giá trị cực tiểu của các phần tử hiện tại. Nếu như ta chỉ lưu vị trí của phần tử cực tiểu, thì ta sẽ tiết kiệm được bộ nhớ một chút. Ta chỉ cần lưu lại vị trí của phần tử cực tiểu mới, nếu vị trí này khác với vị trí hiện tại. Khi pop ra, nếu số lượng phần tử hiện tại ít hơn vị trí của phần tử cực tiểu thì ta cũng pop luôn vị trí này ra khỏi ngăn xếp thứ hai. Điều này đảm bảo điều kiện bất biến vị trí của phần tử cực tiểu luôn luôn nhỏ hơn số lượng phần tử trong ngăn xếp.

Cài đặt này xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi tốt nhất để bạn đọc trao đổi thêm.

Phỏng vấn: Tìm tích của mọi phần tử trừ phần tử hiện tại

written by Nguyễn Thành Nam, on Mar 8, 2015 2:05:00 PM.

Câu hỏi

Cho một danh sách các số thực A, trả về một danh sách trong đó phần tử tại vị trí i có giá trị là tích của các phần tử không phải ở vị trí i trong danh sách A.

Phân tích

Trường hợp ngoại lệ

Nếu A chỉ có một phần tử thì giá trị trả về sẽ là gì? Người đi phỏng vấn phải hỏi ngược lại được người phỏng vấn trường hợp này.

Cách giải đơn giản

Cách giải đơn giản nhất là ta thực hiện hai vòng lặp để tính giá trị của từng phần tử của danh sách B.

def solve(A):
  B = [1] * len(A)
  for i in xrange(len(A)):
    for j in xrange(len(A)):
      if i != j:
        B[i] *= A[j]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải này có độ phức tạp là O(n^2).

Cách giải O(n)

Có hai nhận xét đơn giản sau:

  1. Nếu như trong số phần tử còn lại có giá trị 0, thì tích số cũng sẽ là 0.
  2. Giá trị của B[i] sẽ là tích của toàn bộ các phần tử trong A, chia cho A[i]. Ta có thể tính tích của toàn bộ các phần tử trong A qua một vòng lặp, và dùng một vòng lặp khác để tính từng giá trị của B.
def solve(A):
  nr_zeros = 0
  product = 1
  for i in xrange(len(A)):
    if A[i] == 0:
      nr_zeros += 1
    else:
      product *= A[i]
  if nr_zeros >= 2:
    return [0] * len(A)
  B = [0] * len(A)
  for i in xrange(len(B)):
    if A[i] == 0:
      B[i] = product
    elif nr_zeros != 1:
      B[i] = product / A[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải không dùng phép chia

Ta nhận thấy rằng B[i] là tích của các phần tử từ 0 đến i-1 và từ i+1 đến n của A (với n là số phần tử trong A). Nói một cách khác, giá trị trong Btích của hai phần liên tục từ bên trái, và từ bên phải của A . Do đó, ta sẽ sử dụng hai danh sách tạm left_productright_product để chứa tích các phần tử trong A từ bên trái, và từ bên phải, loại trừ phần tử đang xét.

def solve(A):
  left_product = [1] * len(A)
  right_product = [1] * len(A)
  for i in xrange(1, len(A)):
    left_product[i] = left_product[i - 1] * A[i - 1]
  for i in xrange(len(A) - 2, -1, -1):
    right_product[i] = right_product[i + 1] * A[i + 1]
  B = [1] * len(A)
  for i in xrange(len(A)):
    B[i] = left_product[i] * right_product[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Khi đọc kỹ đoạn mã trên, ta sẽ thấy rằng có lẽ danh sách left_product là thừa. Thay vào đó, trong quá trình tính B, ta có thể giữ một biến tạm cho biết tích từ A[0] đến A[i - 1]. Phần này xin được dành làm một thử thách nhỏ cho bạn đọc. Nếu bạn giải ra, xin hãy cùng trao đổi trong diễn đàn.

Phỏng vấn: Cách mua và bán lời nhất

written by Nguyễn Thành Nam, on Mar 6, 2015 11:47:00 AM.

Câu hỏi

Giả sử như bạn có thông tin về giá của một món hàng trong một khoảng thời gian nào đó. Tìm ngày bạn sẽ mua, và ngày bạn sẽ bán món hàng đó để đạt được lợi nhuận cao nhất.

Đầu vào: một danh sách các giá trị thực là giá của món hàng từng ngày.

Đầu ra: hai chỉ mục trong danh sách là ngày mua, và ngày bán.

Ví dụ: với dữ liệu vào [10, 13, 9, 10, 11], thì kết quả là (0, 1) ý là mua ngày 0 với mức giá 10, bán ra ngày 1 với mức giá 13, lợi nhuận cao nhất là 3 đơn vị.

Phân tích

Gọi danh sách đầu vào là A. Câu hỏi này yêu cầu chúng ta tìm hai chỉ mục xy trong A sao cho A[y] - A[x] lớn nhất, với điều kiện x < y.

Đặt min_x là chỉ mục của giá thấp nhất trong danh sách A. Khi xét đến phần tử i trong danh sách A, ta sẽ gặp một số trường hợp sau:

  1. Giá giảm: A[i] < A[min_x] Đây là cơ hội mua vào nên ta sẽ đặt min_x = i.
  2. Giá tăng: A[i] >= A[min_x] Đây là cơ hội bán ra nên ta sẽ phải xét thêm A[i] - A[min_x] > A[y] - A[x], tức là bán vào lúc này có lời hơn lúc trước không. Nếu có, ta sẽ cập nhật y, x = i, min_x.

Cài đặt

def solve(A):
  x = y = min_x = 0
  for i in xrange(1, len(A)):
    if A[i] < A[min_x]:
      min_x = i
    elif A[i] - A[min_x] >= A[y] - A[x]:
      x, y = min_x, i
  return (x, y)

assert(solve([10, 13, 9, 10, 11]) == (0, 1))

Danh sách nhảy cóc (Skip List)

written by Phan Đắc Anh Huy, on May 1, 2014 10:01:00 PM.

Giới thiệu

Qua các lượt bài trước, chúng ta đã thảo luận về thuận toán tìm kiếm nhị phân và ngăn (partition). Cả hai thuận toán này đều dựa trên cấu trúc dữ liệu mảng (array) vốn rất quen thuộc với chúng ta.

Ngoài ra, hai thuật toán trên được xếp vào nhóm thuật toán tất định (determistic algorithm). Các thuật toán thuộc nhóm này thỏa mãn hai điều kiện:

  • Luôn trả về kết quả giống nhau nếu được cung cấp cùng một dữ liệu đầu vào.

  • Các trạng thái (state) trong quá trình tính toán phải giống nhau với cùng một dữ liệu đầu vào.

Trong bài viết này tác giả đề cập đến cấu trúc dữ liệu "Danh Sách Nhảy Cóc" (Skip List), cơ chế hoạt động của cấu trúc dữ liệu này (bao gồm các thao tác Thêm, Xóa, Tìm Kiếm) phụ thuộc vào yếu tố ngẫu nhiên vì vậy nó được xếp vào nhóm thuật toán ngẫu tính (randomized algorithm), trái ngược với nhóm thuật toán tất định.

Mục đích

Một cấu trúc dữ liệu đơn giản nhưng hiệu quả trên các tác vụ cơ bản: Thêm, Xóa và Tìm Kiếm.

Định nghĩa

Danh sách nhảy cóc S là một tập hợp các danh sách S[0], S[1] ... S[N-1]. Để dễ hình dung chúng ta xem mỗi danh sách con tương ứng với một "tầng", trong đó 0 là tầng thấp nhất, cho đến N-1 là tầng cao nhất. Danh sách nhảy cóc luôn thỏa mãn các điều kiện:

  • Mỗi danh sách con chứa các giá trị theo thứ tự tăng dần.

  • Phần từ đầu và cuối mỗi danh sách con đều là NULL.

  • Danh sách ở tầng cao hơn là dãy con của danh sách tầng dưới.

Ví dụ một trạng thái của danh sách nhảy cóc chứa dãy số 12, 23, 34, 46, 64, 78, 89

S[3]    NULL             23                                              NULL
S[2]    NULL             23                      64                      NULL
S[1]    NULL             23      34              64      78              NULL 
S[0]    NULL     12      23      34      46      64      78      80      NULL

Tìm kiếm trong danh sách

Gọi K là giá trị cần tìm kiếm. Ý tưởng chính của thuật toán là cố gắng duyệt càng xa càng tốt trên tầng cao hơn và tiếp tục ở tầng thấp hơn cho đến khi không thể duyệt được nữa.

Thuật toán bắt đầu từ phần tử đầu tiên, tầng trên cùng của danh sách. Duyệt theo quy luật:

  • Nhảy sang phần tử kế tiếp trên cùng tầng nếu phần tử tiếp theo đó khác NULL và bé hơn hoặc bằng K.

  • Nếu không thể di chuyển trên cùng tầng được nữa:

    • Dừng duyệt nếu như đang ở tầng thấp nhất.

    • Ngược lại, nhảy xuống phần tử ngay bên dưới ở tầng tiếp theo.

Sau khi kết thúc duyệt danh sách, nếu phần tử hiện tại bằng K, thuật toán kết luận tìm được K, ngược lại K không tồn tại trong danh sách.

Ví dụ dưới đây minh họa việc tìm kiếm K = 85 trong danh sách S tại trạng thái được mô tả ở phần trước:

S[3]    NULL -------> 23                                        NULL
S[2]    NULL          23  ----------->  64                      NULL
S[1]    NULL          23    34          64 -> 78 -> 83          NULL 
S[0]    NULL    12    23    34    46    64    78    83    90    NULL

Giải thích:

Bước Tầng hiện tại Phần tử hiện tại Phần tử kế tiếp Di chuyển
1 S[3] NULL 23 Nhảy sang phần tử kế tiếp vì 23 <= K
2 S[3] 23 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
3 S[2] 23 64 Nhảy sang phần tử kế tiếp vì 64 <= K
4 S[2] 64 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
5 S[1] 64 78 Nhảy sang phần tử kế tiếp vì 78 <= K
6 S[1] 78 83 Nhảy sang phần tử kế tiếp vì 83 <= K
7 S[1] 83 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
8 S[0] 83 90 Dừng thuật toán vì 90 > K

Dựa vào giá trị của phần tử cuối cùng, chúng ta kết luận không tìm thấy giá trị 85 trong danh sách. Mặt khác, nếu chúng ta tìm K = 83, các bước duyệt trên danh sách sẽ giống hệt như vậy ngoại trừ việc thuật toán sẽ kết thúc ở bước thứ 7 và chúng ta tìm được K.

Để ý các bước duyệt, chúng ta thấy thuật toán đã “nhảy cóc” qua các phần tử 12, 34 và 46.

Thêm phần tử vào danh sách

Gọi H là giá trị của phần tử cần thêm vào danh sách S. Thuật toán được mô tả như sau:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0] tương ứng với tầng N-1, N-2, ... 1, 0.

  • Bước 2: Nếu H đã tồn tại trong danh sách S, kết thúc thuật toán.

  • Bước 3: Thêm phần tử giá trị H vào sau p[0].

  • Bước 4: Tung một đồng xu

    • Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (p[1] nếu là tầng 1, p[2] nếu là tầng 2, …..).

    • Nếu được mặt xấp, dừng thuật toán.

  • Bước 5: Quay lại bước 4.

Lưu ý tại bước 4, thuật toán phải tạo tầng mới nếu đồng xu hiện mặt ngửa và chúng ta đang ở tầng trên cùng.

Xóa phần tử khỏi danh sách

Gọi H là giá trị của phần tử cần phải xóa khỏi danh sách S. Thuật toán khá tương tự với việc thêm phần tử:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0]

  • Bước 2: Nếu không tìm thấy H, thuật toán kết thúc.

  • Bước 3: Ngược lại, xóa tất cả các phần tử tại vị trí p[N-1], p[N-2] … p[1], p[0] khỏi danh sách.

  • Bước 4: Xóa tất cả các tầng trống (tầng chỉ có hai phần tử NULL ở đầu và cuối)

Cài đặt

Chúng ta định nghĩa một phần tử của danh sách nhảy cóc như sau:

class SkipListNode(object):

    def __init__(self, value):
        self.value = value
        self.next  = None
        self.down  = None

Như các bạn thấy, với mỗi phần tử ngoài giá trị cần lưu, chúng ta chỉ quan tâm đến phần tử kế tiếp (bên phải) và phần tử tương ứng nằm ở tầng dưới.

Kế tiếp, định nghĩa danh sách nhảy cóc với hàm khởi tạo:

class SkipList(object):

    def __init__(self):
        self.head = SkipListNode(None)

Lớp SkipList sử dụng biến head để lưu phần tử đầu tiên của tầng cao nhất, đây luôn là vị trí bắt đầu khi chúng ta duyệt danh sách.

Dễ thấy rằng tác vụ Thêm và Tìm Kiếm đều cần phải duyệt qua danh sách với cùng một cách để tìm một giá trị, vì vậy chúng ta định nghĩa hàm _search để có thể dùng chung cho cả hai như sau:

    def _search(self, value):
        last_nodes   = []
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                current_node = current_node.next
            else:
                last_nodes.append(current_node)
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break
        return last_nodes

Cách hoạt động của hàm này được mô tả ở mục Tìm kiếm trong danh sách, giá trị trả về là danh sách p[N-1], p[N-2], ... p[0] tương ứng với phần tử cuối cùng được duyệt đến tại các tầng N-1, N-1, ... 0

Lúc này hàm search của chúng ta khá đơn giản, chỉ cần kiểm tra giá trị của phần tử cuối cùng được trả về bởi _search:

    def search(self, value):
        last_nodes = self._search(value)

        if last_nodes[-1].value == value:
            return value

        return None

Hàm insert để thêm phần tử vào danh sách:

    def insert(self, new_value):

        last_nodes = self._search(new_value)

        # Stop if the value is already there in the list
        if last_nodes[-1].value == new_value:
            return 

        last_created_node = None
        while True:
            new_node = SkipListNode(new_value)

            if len(last_nodes) > 0:
                last_node       = last_nodes.pop()
                new_node.next   = last_node.next
                last_node.next  = new_node
            else:
                new_head       = SkipListNode(None)
                new_head.down  = self.head
                new_head.next  = new_node
                new_node.next  = None
                self.head      = new_head

            new_node.down      = last_created_node
            last_created_node  = new_node

            # We are flipping the coin now 
            if random.randint(0, 1) != 0:
                break

Và cuối cùng là hàm remove để xóa phần tử khỏi danh sách:

    def remove(self, value):
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                if current_node.next.value < value:
                    current_node = current_node.next
                else: 
                    current_node.next = current_node.next.next

                if current_node.value is None and current_node.next is None\ 
                    and current_node.down is not None:
                    self.head = current_node.down
            else:
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break

Về cơ bản hàm này khá giống hàm _search: chúng ta vẫn duyệt từ head để tìm kiếm giá trị value. Điểm khác biệt là, nếu tìm thấy value ở bất kỳ tầng nào, chúng ta tiến hành xóa phần tử khỏi tầng đó đồng thời xóa luôn tầng này nếu không còn phần tử (khác NULL) nào khác.

Độ phức tạp

  • Trung bình:

    • Bộ nhớ cần thiết: O(n)

    • Thời gian tìm kiếm, thêm, xóa: O(logn)

  • Tệ nhất:

    • Bộ nhớ cần thiết: O(n*logn)

    • Thời gian tìm kiếm, thêm, xóa: O(n)

Bàn luận thêm

  • Các bạn có thể thấy ở thao tác Thêm phần tử, danh sách không thay đổi nếu chúng ta thêm một phần tử vốn đã có sẵn trong danh sách. Điều này đồng nghĩa với việc chúng ta mặc định các phần tử là đôi một khác nhau. Hãy sửa lại các đoạn mã ở trên để danh sách nhảy cóc của chúng ta có thể hỗ trợ các phần tử giống nhau.

  • Để ý rằng độ phức tạp của Danh Sách Nhảy Cóc tương đương với Cây Nhị Phân, ngoại trừ việc Danh Sách Nhảy Cóc sử dụng nhiều bộ nhớ hơn. Bạn đọc có thể chỉ ra điểm nhỉnh hơn của Danh Sách Nhảy Cóc không ? (Gợi ý: chuyện gì xảy ra đối với hai danh sách khi có nhiều tiến trình muốn thêm phần tử vào danh sách cùng một lúc ?)

  • Hãy viết hàm in ra trạng thái của danh sách nhảy cóc.

  • Hãy viết hàm in ra các phần tử của danh sách nhảy cóc.

Chương trình đường hầm HTTP bằng Python

written by Phan Đắc Anh Huy, on Jan 14, 2014 1:43:00 AM.

(Bài gửi đến PCNV từ cộng tác viên Vũ Khuê. Xin cảm ơn bạn.)

Giới thiệu

Có những lúc bạn cần kết nối đến máy chủ ngoài mạng nội bộ ở một cổng không thuộc những giao thức ứng dụng phổ biến như HTTP hay HTTPS (cổng 80 hoặc 443). Nhưnng điều đáng buồn là tường lửa chặn yêu cầu đến những cổng ngoài 80 hoặc 443. Khi đó, điều bạn có thể làm là thiết lập một chương trình trên một máy ngoại mạng. Chưong trình này nhận yêu cầu tử cổng 80 hoặc 443 và chuyển nó đến cổng và máy chủ thực sự. Việc này thường được gọi là thiết lập đường hầm (tunneling).

Trên thực tế, chương trình ssh với tuỳ chọn -L thường được sử dụng cho nhiệm vụ này. Tuy nhiên trong bài này chúng ta sẽ viết chương trinh đường hầm này dựa trên giao thức HTTP. Mục đích chính là miêu tả việc xử lý dữ liệu mạng tầm thấp với Python.

Cấu trúc

Chương trình này gồm 2 thành phần máy khách (client) và máy chủ (server)

  • Tunnel.py: thành phần máy khách. Thành phần này nhận yêu cầu từ một cổng nhất định và bọc dữ liệu này duới dạng một yêu cầu HTTP rồi gửi đến thành phần máy chủ.
  • Tunneld.py: thành phần máy chủ. Thành phần thực chất là một máy chủ HTTP (HTTP server). Khi có yêu cầu gửi đến, nó sẽ đọc yêu cầu này và thực hiện tác vụ tương ứng. Ví dụ như thực hiện kết nối với một máy khác hoặc chuyển dữ liệu từ tải của yêu cầu HTTP đến máy này.

Để thiết lập đường hầm, chạy 2 thành phần như sau:

python tunnel.py -p [client_listen_port] -h [target_host]:[target_port]
python tunneld.py -p [server_listen_port]

Một ứng dụng muốn gửi yêu cầu đến máy nào đó (target_host), nó cần gửi yêu cầu đó thông qua cổng mà tunnel.py được khởi tạo với (client_listen_port).

Triển khai

Bạn có thể tìm thấy mã chương trình tại đây: https://github.com/khuevu/http-tunnel.

Tunnel.py

Thành phần này nghe ở một cổng nhất định. Nó có 2 tiểu trình (thread) riêng biệt để nhận và trả lời yêu cầu:

	...
	BUFFER = 1024 * 50

	#set global timeout
	socket.setdefaulttimeout(30)

	class SendThread(threading.Thread):

	    """
	    Thread to send data to remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	        	# receive data and send to through tunnel
	            data = self.socket.recv(BUFFER)
	            self.conn.send(data)
	    ...

	class ReceiveThread(threading.Thread):

	    """
	    Thread to receive data from remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	            data = self.conn.receive()
	            self.socket.sendall(data)

	    ...

Hằng số BUFFER là lượng dữ liệu theo byte mà chường trình sẽ nhận từ ứng dụng trước khi gửi qua đường hầm. Có thể có nhiều ứng dụng kết nối với chương trình tunnel.py. Vì thế, ta cần tạo kết nối riêng cho mỗi ứng dụng. Dưới đây là đoạn mã của lớp Connection:

class Connection():
    
    def __init__(self, connection_id, remote_addr):
        self.id = connection_id
        self.http_conn = httplib.HTTPConnection(remote_addr['host'], remote_addr['port'])
    ...

    def create(self, target_addr):
        params = urllib.urlencode({"host": target_addr['host'], "port": target_addr['port']})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}

        self.http_conn.request("POST", self._url("/" + self.id), params, headers)

        response = self.http_conn.getresponse()
        response.read()
        if response.status == 200:
            print 'Successfully create connection'
            return True 
        else:
            print 'Fail to establish connection: status %s because %s' % (
                response.status, response.reason)
            return False 

    def send(self, data):
        params = urllib.urlencode({"data": data})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}
        try: 
            self.http_conn.request("PUT", self._url("/" + self.id), params, headers)
            response = self.http_conn.getresponse()
            response.read()
            print response.status 
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Sending Data: %s" % ex

    def receive(self):
        try: 
            self.http_conn.request("GET", "/" + self.id)
            response = self.http_conn.getresponse()
            data = response.read()
            if response.status == 200:
                return data
            else: 
                print "GET HTTP Status: %d" % response.status
                return ""
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Receiving Data: %s" % ex
            return "" 

    ...

Như bạn thấy ở đây, Connection có những hàm để thiết lập đường hầm, gửi và nhận dữ liệu. Sự tưong tác này được xây dựng trên giao thức HTTP. Cụ thể là:

  • POST request: yêu cầu thiết lập kết nối.
  • PUT request: gửi dữ liệu qua kết nối.
  • GET request: nhận kết nối.
  • DELETE request: kết thúc kết nối.

Sẽ rõ ràng hơn khi ta nhìn vào mã của tunneld.py, thành phần nhận những yêu cầu HTTP này:

class ProxyRequestHandler(BaseHTTPRequestHandler):
    ...

    BUFFER = 1024 * 50 

    def _get_connection_id(self):
        return self.path.split('/')[-1]
    ...

    def do_GET(self):
        """GET: Read data from TargetAddress and return to client through http response"""
        s = self._get_socket()
        if s:
            try:
                data = s.recv(self.BUFFER)
                print data
                self.send_response(200)
                self.end_headers()
                if data:
                    self.wfile.write(data)
        ...

    def do_POST(self):
        """POST: Create TCP Connection to the TargetAddress"""
        id = self._get_connection_id() 

        length = int(self.headers.getheader('content-length'))
        req_data = self.rfile.read(length)
        params = cgi.parse_qs(req_data, keep_blank_values=1) 
        target_host = params['host'][0]
        target_port = int(params['port'][0])

        print 'Connecting to target address: %s % s' % (target_host, target_port)
        #open socket connection to remote server
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect((target_host, target_port))
        s.settimeout(7)
        print 'Successfully connected'
        #save socket reference
        self.sockets[id] = s
        try: 
            self.send_response(200)
            self.end_headers()
        except socket.error, e:
            print e

    def do_PUT(self):
        """Read data from HTTP Request and send to TargetAddress"""
        id = self._get_connection_id()
        s = self.sockets[id]
        length = int(self.headers.getheader('content-length'))
        data = cgi.parse_qs(self.rfile.read(length), keep_blank_values=1)['data'][0] 
        try: 
            s.sendall(data)
            self.send_response(200)
        ...

    def do_DELETE(self): 
        self._close_socket()
        self.send_response(200)
        self.end_headers()

Ở đây, ProxyRequestHandler chính là một máy chủ HTTP, nhận và xử lý những yêu cầu cơ bản của HTTP.

  • do_POST: hàm này xử lý những yêu cầu POST. Nó sẽ lấy thông tin về máy đối tượng (tên miền, cổng) và tạo kết nối TCP đến máy đó. Nó trả về trạng thái 200 nếu kết nối này thành công.
  • do_GET: hàm này lấy dữ liệu từ kết nối đã được thiết lập với máy đối tương trong do_POST. Sau đó nó trả dữ liệu này trong trả lời HTTP của yêu cầu GET.
  • do_PUT: hàm này lấy nhận yêu cầu PUT, đọc dữ liệu từ tải của yêu cầu đó và gửi qua kết nối nói trên.
  • do_DELETE: hàm này đóng kết nối với máy đối tượng.

Thử nghiệm chương trình

Chúng ta sẽ thử chương trình này bằng việc kết nối với một IRC server thông qua chương trình. Trước hết, thiết lập đường hầm cần thiết. Tại một máy ngoại mạng, không bị chặn bởi tường lửa, chạy:

python tunneld.py -p 80

Tại máy nội mạng chạy:

python tunnel.py -p 8889 -h mayngoaimang:80 irc.freenode.net:6667

Như vậy ta đã thiết lập một đương hầm ở cổng 8889 qua máy ngoại mạng đến IRC server ở cổng 6667. Yêu cầu đến cổng 6667 thường bị chặn bởi tường lửa. Để thử nghiệm, ta kết nối đến cổng 8889 và gửi yêu cầu theo giao thức IRC:

nc localhost 8889
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz

(nc - netcat - là một công cụ giúp bạn gửi giữ liệu trên TCP: http://www.irongeek.com/i.php?page=backtrack-3-man/netcat).

Ta nhận được trả lời thông báo kết nối thành công:

:calvino.freenode.net NOTICE * :*** Looking up your hostname...
:calvino.freenode.net NOTICE * :*** Checking Ident
:calvino.freenode.net NOTICE * :*** Found your hostname
:calvino.freenode.net NOTICE * :*** No Ident response
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz
:calvino.freenode.net 001 abcxyz :Welcome to the freenode Internet Relay Chat Network abcxyz
:calvino.freenode.net 002 abcxyz :Your host is calvino.freenode.net[ ... /6667], running version ircd-seven-1.1.3
:calvino.freenode.net 003 abcxyz :This server was created Sun Dec 4 2011 at 14:42:47 CET
:calvino.freenode.net 004 abcxyz calvino.freenode.net ircd-seven-1.1.3 DOQRSZaghilopswzCFILMPQbcefgijklmnopqrstvz bkloveqjfI
:calvino.freenode.net 005 abcxyz CHANTYPES=# EXCEPTS INVEX CHANMODES=eIbq,k,flj,CFLMPQcgimnprstz CHANLIMIT=#:120 PREFIX=(ov)@+ MAXLIST=bqeI:100 MODES=4 NETWORK=freenode KNOCK STATUSMSG=@+ CALLERID=g :are supported by this server
:calvino.freenode.net 005 abcxyz CASEMAPPING=rfc1459 CHARSET=ascii NICKLEN=16 CHANNELLEN=50 TOPICLEN=390 ETRACE CPRIVMSG CNOTICE DEAF=D MONITOR=100 FNC TARGMAX=NAMES:1,LIST:1,KICK:1,WHOIS:1,PRIVMSG:4,NOTICE:4,ACCEPT:,MONITOR: :are supported by this server
:calvino.freenode.net 005 abcxyz EXTBAN=$,arx WHOX CLIENTVER=3.0 SAFELIST ELIST=CTU :are supported by this server
:calvino.freenode.net 251 abcxyz :There are 232 users and 70582 invisible on 31 servers
:calvino.freenode.net 252 abcxyz 45 :IRC Operators online
:calvino.freenode.net 253 abcxyz 10 :unknown connection(s)
:calvino.freenode.net 254 abcxyz 34513 :channels formed
:calvino.freenode.net 255 abcxyz :I have 6757 clients and 1 servers
:calvino.freenode.net 265 abcxyz 6757 10768 :Current local users 6757, max 10768
:calvino.freenode.net 266 abcxyz 70814 83501 :Current global users 70814, max 83501
:calvino.freenode.net 250 abcxyz :Highest connection count: 10769 (10768 clients) (2194912 connections received)
...

Kết

Như vậy chúng ta đã đi qua một chương trình xử lý dữ liệu mạng với Python. Chương trình chủ yếu làm việc với dữ liệu thông qua socket API. Một điều quan trọng khác mà bài viết này đề cập đến là sự tách biệt giữa giao thức ứng dụng và dữ liệu gửi trên giao thức đó. Chúng ta có thể vận chuyển dữ liệu mà thông thường đuợc gửi bằng giao thức này qua một giao thức khác.

Chú ý: Chương trình chỉ có mục đích thí nghiệm và không phù hợp với chạy thực dụng.

Thuật toán đẹp: Tìm chuỗi Boyer-Moore-Horspool

written by Nguyễn Thành Nam, on Jan 9, 2014 2:35:00 PM.

Mục đích

Tìm chính xác (exact match) chuỗi con (substring) trong một chuỗi dài hơn.

Ý tưởng chính

Gọi chuỗi cần tìm là P (pattern), và chuỗi dài là T (text).

So sánh ngược P trong T, nghĩa là ta sẽ so sánh ký tự cuối của P trước, sau đó so sánh ký tự kế cuối, và lần lượt như vậy đến ký tự đầu tiên trong P. Gọi vị trí trong T để bắt đầu so sánh hai chuỗi là i. Việc so sánh sẽ so sánh lần lượt T[i] với ký tự cuối của P, rồi T[i-1] với ký tự kế cuối của P, v.v...

Nếu việc so sánh ngược vượt qua được ký tự đầu tiên trong P, ta đã tìm được P trong T.

Nếu việc so sánh ngược bị thất bại, ta sẽ căn P cho khớp với T[i] và thử lại việc so sánh ngược. Điều này tương đương với việc dịch chuyển i đến vị trí xa hơn trong T. Đây là ý tưởng chủ chốt của thuật toán BMH.

  • Nếu T[i] không có trong P, thì ta có thể dịch chuyển i đến vị trí i + len(P).
  • Nếu vị trí cuối cùng của T[i] trong P là x thì ta dịch chuyển i đến vị trí i + len(P) - x - 1.
Trạng thái bắt đầu

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
           = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh sai

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
         ! = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

Căn P theo T[i]...

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             |
          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

------------------------------------------

... cũng có nghĩa là dịch chuyển i

                   i
                   |
                   v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

Để cài đặt hai bước trên, người ta thường dùng một mảng chứa vị trí cuối cùng của các ký tự trong P trừ ký tự cuối cùng (P[ : -1]).

Ví dụ

Giả sử chúng ta muốn tìm chuỗi needle trong chuỗi find the needle in the haystack.

Trước khi bắt đầu, ta sẽ lập bảng vị trí cuối của các ký tự trong P[ : -1].

Ký tựVị tríDiễn giải
n0
e2Ta chọn vị trí của ký tự thứ hai.
d3
l4

Và sự thay đổi ở các bước của thuật toán. Vì độ dài của P là 6, nên i sẽ bắt đầu từ vị trí 5. Trong bảng dưới, chữ đậm là ký tự trùng nhau của T và P, chữ gạch dưới là các ký tự đang xét.

iTT[i]Diễn giải
5find the needle in the haystacktt không có trong bảng. Dịch i lên 11 (5 + 6).
11find the needle in the haystackee có trong bảng. Dịch i lên 14 (11 + 6 - 2 - 1).
14find the needle in the haystackeTìm thấy. e có trong bảng. Dịch i lên 17 (14 + 6 - 2 - 1).
17find the needle in the haystacknn có trong bảng. Dịch i lên 22 (17 + 6 - 0 - 1).
22find the needle in the haystackkhoảng trắngkhoảng trắng không có trong bảng. Dịch i lên 28 (22 + 6).
28find the needle in the haystackaa không có trong bảng. Dịch i lên 34 (28 + 6). Dừng việc tìm kiếm vì đã xét hết chuỗi.

Độ phức tạp

Thời gian chạy: Tệ nhất là O(n*m), với n là độ dài của T và m là độ dài của P. Trung bình là O(n). Và tốt nhất là dưới tuyến tính (sublinear) vì thuật toán có thể nhảy qua nhiều ký tự. Trong ví dụ trên, ta chỉ cần 12 phép so sánh để tìm chuỗi needle (6 ký tự) trong chuỗi find the needle in the haystack (31 ký tự).

Bộ nhớ cần thiết: O(n) với n là số ký tự trong bảng chữ cái (ví dụ như 256 giá trị của một byte, hoặc nếu bảng chữ cái là Unicode thì có thể sẽ nhiều hơn 60000 giá trị) vì chúng ta cần tạo bảng vị trí các ký tự trong P.

Thuật toán BMH là thuật toán tìm chuỗi chính xác tổng quát nhất, nhanh nhất, và đơn giản nhất.

Thuật toán đẹp: Partition (ngăn)

written by Nguyễn Thành Nam, on Jan 1, 2014 12:34:00 AM.

Mục đích

Chia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại.

Cài đặt

Sử dụng mảng phụ

def partition(a, pred):
    head = [x for x in a if pred(x)]
    tail = [x for x in a if not pred(x)]
    return head + tail, len(head)

Không dùng mảng phụ

Ý tưởng chính là sử dụng một biến phụ chứa vị trí trong mảng A mà nếu phần tử đang xét thỏa điều kiện sẽ được chuyển vào.

def partition(a, pred):
    okay_idx = 0
    for i, x in enumerate(a):
        if pred(x):
            a[okay_idx], a[i] = a[i], a[okay_idx] # swap
            okay_idx += 1
    return a, okay_idx

Độ phức tạp

Thời gian chạy: O(n)

Bộ nhớ cần thiết: O(n) nếu sử dụng mảng phụ, hoặc O(1) nếu không

Ứng dụng

Ứng dụng nổi tiếng nhất là thuật toán QuickSort do Tony Hoare sáng tạo ra. Thuật toán QuickSort sắp xếp một mảng với độ phức tạp trung bình là O(n*logn) với n là số lượng phần tử trong mảng. Độ phức tạp trong trường hợp xấu nhất có thể là O(n*n).

Sau đây là một cài đặt dễ hiểu của QuickSort. Cài đặt này chỉ dùng để thể hiện ý tưởng chứ không nên dùng trong các ứng dụng.

Ý tưởng chủ đạo là lấy ra một phần tử nào đó trong A (tức là A' chỉ còn N-1 phần tử) gọi là pivot, ngăn A' thành hai cụm (một cụm nhỏ hơn pivot, một cụm còn lại). Tiếp tục gọi đệ quy để sắp xếp hai cụm đó và nối chúng lại với nhau thông qua pivot.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[-1]
    a, pivot_idx = partition(a[ : -1], lambda x: x <= pivot)
    return quicksort(a[ : pivot_idx]) + [pivot] + quicksort(a[pivot_idx : ])

import itertools
for l in range(8):
    a = range(l)
    for p in itertools.permutations(a):
        p = list(p)
        assert quicksort(p) == a

Bài toán mở rộng

  1. Cho một mảng số nguyên A. Tìm K phần tử nhỏ nhất trong A.
  2. Cho một mảng số nguyên A và một số nguyên X. Đếm số tập hợp 2-phần-tử trong mảng A có tổng nhỏ hơn hoặc bằng X.

Các bạn có thể trao đổi về cách giải bài các bài toán mở rộng này với độ phức tạp trung bình O(n) trong diễn đàn.

Thuật toán đẹp: Tìm nhị phân

written by Nguyễn Thành Nam, on Dec 27, 2013 1:13:00 PM.

Mục đích

Tìm phần tử X trong một mảng đã được sắp xếp.

Ý tưởng chính

Chia mảng ra thành 3 cụm: cụm bên trái, phần tử ở giữa, và cụm bên phải. So sánh X với phần tử ở giữa. Nếu X bằng với phần tử ở giữa thì ta đã tìm được X trong mảng. Nếu X lớn hơn thì tìm X trong cụm bên phải. Nếu X nhỏ hơn thì tìm X trong cụm bên trái.

Hiệu quả

Thời gian thực hiện: O(logn)

Bộ nhớ cần thiết: O(1)

Cài đặt

Cài đặt đệ quy

def bin_search(x, a, left_idx, right_idx):
    if left_idx > right_idx:
        return -1
    mid_idx = left_idx + (right_idx - left_idx) // 2
    mid = a[mid_idx]
    if x == mid:
        return mid_idx
    elif x < mid:
        return bin_search(x, a, left_idx, mid_idx - 1)
    else:
        return bin_search(x, a, mid_idx + 1, right_idx)

assert bin_search(0, [0], 0, 0) == 0
assert bin_search(0, [1], 0, 0) == -1
assert bin_search(0, [0, 1], 0, 1) == 0
assert bin_search(1, [0, 1], 0, 1) == 1
assert bin_search(2, [0, 1], 0, 1) == -1

Cài đặt vòng lặp

def bin_search(x, a, left_idx, right_idx):
    while left_idx <= right_idx:
        mid_idx = left_idx + (right_idx - left_idx) // 2
        mid = a[mid_idx]
        if mid == x:
            return mid_idx
        elif x < mid:
            right_idx = mid_idx - 1
        else:
            left_idx = mid_idx + 1
    return -1

Tham khảo thêm

Mô-đun bisect trong thư viện chuẩn của Python.

Một số bài toán mở rộng

  1. Mảng đã được sắp xếp nhưng đã bị xoay vòng (ví dụ [4, 5, 6, 7, 1, 2, 3]).
  2. Mảng 2 chiều đã được sắp xếp theo dòng, và cột (a[i][j] < a[i + 1][j] và a[i][j] < a[i][j + 1]).

Các bạn có thể trao đổi ý tưởng giải quyết các bài toán mở rộng này trong diễn đàn.

Kết quả cuộc thi giải toán lần II

written by vithon, on Apr 18, 2013 11:29:51 PM.

Cảm ơn sự hưởng ứng nhiệt tình của các bạn với cuộc thi giải toán lần II của PCNV.

Lần này nhóm nhận được sự sự tham gia của năm bạn Phạm Ngọc Quang Nam, Nguyễn Văn Nam, Vũ Khuê, Hoàng Quốc Thịnh, và Đậu Duy Khánh.

Bài của bạn Thịnh:

09:03:48 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt
09:04:22 ~/tmp/pell2$ python checker.py < thinhhq.txt
Max 448985
09:04:30 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt2
09:05:04 ~/tmp/pell2$ python checker.py < thinhhq.txt2
Max 449905
09:05:08 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt3
09:05:39 ~/tmp/pell2$ python checker.py < thinhhq.txt3
Max 449421

Bài của bạn Văn Nam:

09:05:46 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt
09:07:12 ~/tmp/pell2$ python checker.py < namnv.txt
Max 1394855
09:07:28 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt2
09:07:47 ~/tmp/pell2$ python checker.py < namnv.txt2
Max 1394855
09:08:00 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt3
09:08:19 ~/tmp/pell2$ python checker.py < namnv.txt3
Max 1394855

Bài của bạn Khanh:

09:12:49 ~/tmp/pell2$ python3.3 khanhdd.py | python timer.py > khanhdd.txt
Traceback (most recent call last):
  File "khanhdd.py", line 13, in <module>
    print (a1,' ',b1)
BrokenPipeError: [Errno 32] Broken pipe
09:13:27 ~/tmp/pell2$ python checker.py < khanhdd.txt
ERROR:root:Format
Traceback (most recent call last):
  File "checker.py", line 16, in <module>
    n, k = map(long, line.split())
ValueError: too many values to unpack

Bài của bạn Khuê

09:14:37 ~/tmp/pell2$ python3.3 khuev.py | python timer.py > khuev.txt
  File "khuev.py", line 35
    print "n: %d - k: %d" % (-b / 2, k)
                        ^
SyntaxError: invalid syntax

Bài của bạn Quang Nam:

09:15:19 ~/tmp/pell2$ python3.3 nampnq.py | python timer.py > nampnq.txt
  File "nampnq.py", line 5
    print "n=%d, k=%d" % (n,k)
                     ^
SyntaxError: invalid syntax

Mã nguồn và bản lưu kết quả của cuộc thi có thể được tải về từ https://docs.google.com/file/d/0B5X03CmpgiFeMkNubXlGNFlCMjQ/edit?usp=sharing.

Như vậy, bạn Văn Nam đã thắng giải kỳ này. Xin chúc mừng bạn Văn Nam.

Bạn Văn Nam gửi thư cho admin@ cho biết mẫu áo bạn chọn, và thông tin bưu điện để nhóm PCNV có thể gửi áo về cho bạn.

Cuộc thi giải toán bằng Python

written by vithon, on Mar 31, 2013 9:18:00 AM.

Trong lần thi trước (http://www.vithon.org/2010/05/24/phat-d%E1%BB%99ng-cu%E1%BB%99c-thi-gi%E1%BA%A3i-toan-b%E1%BA%B1ng-python), chúng ta đánh giá chương trình dựa trên số lượng cặp N, K tìm được.

Tiêu chí của lần thi này là in ra cặp số N, K lớn nhất có thể tìm được trong 30 giây. Cặp số cuối cùng được in ra trong 30 giây sẽ được xem là cặp số lớn nhất và dùng để đánh giá các chương trình với nhau.

Giải thưởng của kỳ thi lần này sẽ là một áo thun do bạn Nguyễn Thành Nam đã tặng nhóm PCNV trong lần đi PyCon vừa qua. Các bạn có thể xem qua các áo giải thưởng (trừ EdX cỡ L, các áo khác cỡ M, chỉ được chọn 1) ở URL sau:

https://drive.google.com/folderview?id=0B5X03CmpgiFeNzNJN09qZnd2Sk0&usp=sharing

Các bài tham dự gửi bằng thư điện tử về cho admin@ hạn chót trong ngày 14 tháng 04 năm 2013. Nhằm khuyến khích việc sử dụng Python 3, các bài tham gia kỳ thi này sẽ được chấm trên Python 3.3. Mòng các bạn chú ý yêu cầu này.

Quyết định của người chấm là cuối cùng. Xin miễn nhận khiếu nại.