Python cho người Việt

Python cho người Việt

Điều khiển thang máy

written by vithon, on Jun 23, 2016 8:58:00 PM.

Nhân việc PyCon vừa qua, nhóm PCNV hân hạnh tổ chức cuộc thi Điều khiển thang máy!

Tương tự như cuộc thi Bắn suồng, cuộc thi Điều khiển thang máy cũng là một cuộc thi lập trình Python và có một số điều lệ sau:

  1. Trò chơi được giới thiệu tại http://codelift.org. Người tham dự có thể thử mã của mình tại trang mạng đó.
  2. Người tham gia phải nộp mã Python (tập tin .py) tới admin+codelift@vithon.org, và đồng ý với việc nhóm PCNV có toàn quyền sử dụng mã đó cho mọi mục đích.
  3. Người tham gia cũng phải gửi thêm một bài viết (dưới dạng .txt) giới thiệu trò chơi, và cách giải của mình đến cùng địa chỉ thư trên.
  4. Hạn nhận bài là ngày 14 tháng 07 năm 2016.
  5. Bài thi sẽ được đọc qua trước, và sẽ được chạy trên cùng hệ thống codelift.org.
  6. Bài thi với số điểm trung bình cao nhất trong 3 tòa nhà được chọn khi chấm sẽ là bài thắng giải.
  7. Ba phần thưởng dành cho ba bài thi với số điểm trung bình cao nhất là ba cái áo thun và một số miếng dán mà bạn Nam đã gửi cho nhóm từ PyCon. Người hạng nhất sẽ được quyền chọn mẫu áo trước, rồi đến hạng nhì, và hạng ba. Mẫu áo đã được công bố trong thư mục chia sẻ ở bài trước.
  8. Quyết định của ban tổ chức là cuối cùng.

Mọi thắc mắc và thảo luận xin hãy dùng diễn đàn.

Chúc may mắn và nhiều niềm vui!

PyCon 2016 ở thành phố Portland

written by Nguyễn Thành Nam, on Jun 13, 2016 1:07:48 AM.

Hai tuần trước mình có tham dự hội thảo PyCon 2016 ở thành phố Portland, tiểu bang Oregon, vùng Tây Bắc nước Mỹ.

Cũng như mọi năm, PyCon vẫn là hội thảo tuyệt vời nhất từ trước đến nay. Tham dự hội thảo không chỉ có lập trình viên mà còn có nhiều nhà khoa học, giáo viên, sinh viên, và cả học sinh tiểu học nữa! Mình chưa từng thấy hội thảo khoa học kỹ thuật nào mà có thể quy tập được nhiều đối tượng tham gia như vậy.

Một điều tuyệt vời nữa là có rất nhiều các bạn nam, các bạn nữ, và cả các bạn chuyển giới tham gia PyCon. Điều này cho thấy Python không chỉ là một ngôn ngữ "có sẵn pin", mà có còn là một cộng đồng rất "bao gồm". Ai cũng được hoan nghênh, ai cũng được đối xử một cách tôn trọng, không có sự phân biệt đối xử.

Sau đây là một số hình ảnh mình ghi lại để chia sẻ cùng các bạn. Hy vọng một dịp nào đó sẽ gặp được các bạn ở trong các kỳ hội thảo trong tương lai:

Bảng hiệu PyCon 2016 ở dọc đường đến trung tâm hội nghị Portland.

Em bé đứng nhìn tượng Martin Luther King, Jr. ở trước trung tâm hội nghị.

Hội trường chính, nơi diễn ra các bài tham luận chủ chốt.

Các bạn có thể thấy con lắc biểu tượng của trung tâm hội nghị Portland trong hai hình sau:

Khu đăng ký (hình 1).

Khu đăng ký (hình 2).

Khu vực phòng Oregon (hình 1).

Khu vực phòng Oregon (hình 2).

Khu vực phòng Oregon (hình 3).

Khu vực phòng Oregon (hình 4).

Khu vực phòng Portland (hình 1).

Khu vực phòng Portland (hình 2).

Hình Guido bắt đầu bài tham luận chính. Guido vẫn mặc chiếc áo bé gái như mọi năm. Không biết cái áo này sẽ còn theo Guido đến PyCon năm nào đây. Điều này cũng cho thấy Guido rất quan tâm đến sự đối xử bình đẳng, tôn trọng giới tính ở hội thảo PyCon.

Bảng đăng ký không gian mở (open spaces) ở hội thảo.

Ảnh trưng bày (poster session) (hình 1).

Ảnh trưng bày (poster session) (hình 2).

Hai hình ảnh của tác giả bài viết:

Ảnh đẹp nhất hội thảo (hình 1).

Ảnh đẹp nhất hội thảo (hình 2).

Toàn bộ các hình ảnh có thể được truy cập trong thư mục https://drive.google.com/folderview?id=0B4aYVYJVZM_zT2tzZGdTNTUwQWc&usp=sharing.

Sách "Python rất là cơ bản"

written by vithon, on Nov 19, 2015 12:16:36 AM.

Bạn Võ Duy Tuấn có thực hiện một quyển sách về Python với tựa đề Python rất là cơ bản. Nhóm PCNV xin giới thiệu cùng các bạn.

http://bloghoctap.com/python/download-sach-python-rat-la-co-ban.html

Phỏng vấn: Sắp xếp lắc lư

written by Nguyễn Thành Nam, on May 5, 2015 7:05:39 AM.

Câu hỏi

Cho một mảng A các số nguyên a[i], tìm cách sắp xếp mảng sao cho phần tử thứ nhất nhỏ hơn phần tử thứ hai, phần tử thứ hai lớn hơn phần tử thứ ba, phần tử thứ ba nhỏ hơn phần tử thứ tư v.v... Tức là:

  a[0] <= a[1] >= a[2] <= a[3] >= a[4] ...

Ta gọi một mảng có thứ tự như vậy là một mảng đã được sắp xếp lắc lư (wiggly sorted).

Phân tích

Ta nhận xét rằng yêu cầu thứ tự chỉ áp dụng vào hai phần tử lân cận của phần tử đang xét. Ví dụ, phần tử a[1] chỉ cần lớn hơn hai phần tử a[0]a[2], ngoài ra không còn quan hệ với phần tử nào nữa. Điều đó dẫn đến ý tưởng giải sẽ rất có thể ở dạng tham ăn (greedy algorithm).

Giả sử như ta đã có mảng A' có độ dài 2n (chẵn) thỏa mãn điều kiện. Phần tử kế tiếp (2n + 1) vì ở vị trí lẻ nên sẽ phải nhỏ hơn phần tử cuối cùng trong mảng, đồng thời cũng phải đảm bảo nhỏ hơn phần tử sau đó (2n + 2). Vì ta không biết phần tử (2n + 2) sẽ có giá trị bao nhiêu nên cách an toàn nhất để thỏa mãn hai điều kiện cho phần tử 2n + 1 là chọn phần tử nhỏ nhất trong số các phần tử còn lại của A.

Lập luận tương tự cho thấy rằng phần tử ở vị trí chẵn nên có giá trị lớn nhất trong số các phần tử còn lại.

Tóm lại, cách giải câu hỏi này sẽ bao gồm hai bước chính:

  1. Sắp xếp mảng A theo thứ tự tăng dần.
  2. Lần lượt gán a[0] = min(A), và a[1] = max(A[1 : ]), và a[2] = min(A[2 : ]), v.v...

Dĩ nhiên là ta không cần gọi min hay max mà chỉ cần giữ hai biến chỉ mục từ đầu, và cuối mảng A để tìm ngay giá trị cực tiểu hay cực đại vì A đã được sắp xếp ở bước đầu tiên.

Độ phức tạp thực thi của cách giải này phụ thuộc vào thuộc toán sắp xếp sử dụng ở bước đầu tiên.

Vấn đề cài đặt cách giải xin được để lại cho bạn đọc. Diễn đàn là nơi tốt nhất để trao đổi về các yếu tố liên quan đến cài đặt.

Tổng kết

Qua loạt bài Phỏng vấn, tác giả hy vọng rằng bạn đọc nhận ra được sự quan trọng của bộ kiến thức nền tảng, đặc biệt là các cấu trúc dữ liệu phổ biến. Từ các kiến thức nền tảng này, chúng ta có thể giải quyết được rất nhiều những vấn đề khác.

Python cùng với phương châm kèm cả pin đem đến cho chúng ta một loạt các cấu trúc dữ liệu qua các kiểu, hoặc mô-đun có sẵn. Python thật sự là một công cụ mạnh mẽ và hữu ích.

Phỏng vấn: Tìm 1 triệu số nhỏ nhất trong 1 tỷ số

written by Nguyễn Thành Nam, on Apr 30, 2015 11:56:00 AM.

Câu hỏi

Cho 1 tỷ số thực, tìm 1 triệu số nhỏ nhất trong 1 tỷ số đấy.

Phân tích

Cách giải đơn giản nhất là sắp xếp từ bé đến lớn 1 tỷ số đầu vào, sau đó chọn ra 1 triệu số đầu tiên. Độ phức tạp của cách giải này phụ thuộc vào độ phức tạp của thuật toán sắp xếp. Cách này có hai nhược điểm lớn: 1. là tốn bộ nhớ để chứa 1 tỷ số đầu vào để sắp xếp, 2. là nếu số lượng đầu vào không có giới hạn thì cách giải này không dùng được.

Giả sử ta chỉ có 1 triệu số đầu vào, thì rõ ràng kết quả sẽ chính là 1 triệu số đó. Khi có thêm 1 số mới, số mới này sẽ nằm trong kết quả nếu như nó nhỏ hơn số lớn nhất trong 1 triệu số kết quả hiện tại.

Với nhận xét đó, ta có cách giải thứ hai, tối ưu hơn cách đầu tiên. Ta sẽ tạo một max heap với 1 triệu phần tử. Với mỗi phần tử đầu vào, ta sẽ:

  1. Đưa vào heap nếu heap chưa có đủ 1 triệu số
  2. Nếu heap đã có đủ một triệu số thì lấy từ đỉnh heap ra (tức lấy phần tử lớn nhất trong heap) so sánh với phần tử đầu vào, và đưa lại vào heap phần tử nhỏ hơn trong phép so sánh đó.

Độ phức tạp thực thi của cách giải này là O(nlogn) nhưng chỉ tốn bộ nhớ tỷ lệ với số phần tử đầu ra.

Cài đặt

Ta có thể dùng mô-đun heapq có sẵn để trả lời câu hỏi này. Mô-đun này giúp ta quản lý một min heap. Tuy nhiên, vì ta cần max heap nên các giá trị đầu vào sẽ được đổi thành số bù 0 - x.

# encoding: utf-8
import heapq

def solve(inp, n=1000000):
    heap = []
    for i in inp:
        i = -i
        if len(heap) < n:
            heapq.heappush(heap, i)
        else:
            m = heap[0]
            if m < i:
                heapq.heapreplace(heap, i)
    return [-x for x in heap]

assert(set(solve([1, 2, 3, 4, 5], 3)) == set([1, 2, 3]))
assert(set(solve([5, 4, 3, 2, 1], 3)) == set([1, 2, 3]))

Mô-đun heapq cũng có sẵn hàm nsmallest để giải quyết câu hỏi này ;).

Phỏng vấn: Số nhân viên cấp dưới

written by Nguyễn Thành Nam, on Apr 10, 2015 11:56:00 AM.

Câu hỏi

Cho một từ điển từ chuỗi sang chuỗi, khoá là tên nhân viên, và giá trị là tên của người quản lý. Nhân viên cấp cao nhất báo cáo cho chính họ. Tìm số nhân viên cấp dưới của một nhân viên nào đó.

Ví dụ: Trong từ điển sau, A và B cùng báo cáo cho C, C và E báo cáo cho F, D báo cáo cho E, và F là nhân viên cấp cao nhất.

{
    "A": "C",
    "B": "C",
    "C": "F",
    "D": "E",
    "E": "F",
    "F": "F",
}

Số lượng nhân viên cấp dưới của A là 0, B là 0, C là 2, D là 0, E là 1, và F là 5.

Phân tích

Giả sử A là nhân viên cấp dưới của B, và B là nhân viên cấp dưới của C.

Cách nhìn trực tiếp từ trên xuống theo câu hỏi này là C có 2 nhân viên cấp dưới, và B có một nhân viên cấp dưới. Nếu nhìn ngược lại, ta sẽ nói rằng A "đội" B lên 1, đội tiếp C lên 1, và B đội C lên thêm 1. Tức là mỗi nhân viên sẽ đội tất cả các nhân viên cấp trên của họ lên 1 (A đội B và C, B đội C).

Do đó, cách giải câu hỏi này là duyệt hết các phần tử trong danh sách, với mỗi phần tử, lần lượt đội (cộng 1) vào kết quả của các nhân viên cấp trên của phần tử đấy.

Độ phức tạp thực thi là O(n^2) và tốn O(n) bộ nhớ.

Nếu bạn có cách giải tốt hơn xin hãy cùng chia sẻ tại diễn đàn.

Cài đặt

def solve(employees):
    subordinate_count = {}
    for emp, boss in employees.iteritems():
        if emp not in subordinate_count:
            subordinate_count[emp] = 0
        while emp != boss:
            try:
                subordinate_count[boss] += 1
            except KeyError:
                subordinate_count[boss] = 1
            emp, boss = boss, employees[boss]
    return subordinate_count

inp = {"A": "C", "B": "C", "C": "F", "D": "E", "E": "F", "F": "F"}
exp = {"A": 0, "B": 0, "C": 2, "D": 0, "E": 1, "F": 5}
assert(solve(inp) == exp)

Phỏng vấn: Cộng chuỗi ít tốn nhất

written by Nguyễn Thành Nam, on Mar 23, 2015 2:08:53 AM.

Câu hỏi

Cho n chuỗi, tìm cách cộng các chuỗi này lại theo một thứ tự nào đó sao cho ít tốn bộ nhớ nhất.

Ví dụ: Cho chuỗi A="abc", B=wxyz, C=g, và xét hai cách cộng chuỗi sau:

  1. Cộng AB trước, sau đó cộng với C. A + B sẽ tốn 3 + 4 = 7. Sau đó cộng thêm C sẽ tốn 7 + 1 = 8. Tổng cộng tốn 7 + 8 = 15.
  2. Cộng AC trước, sau đó cộng với B. A + C tốn 3 + 1 = 4. Sau đó cộng thêm B sẽ tốn 4 + 4 = 8. Tổng cộng tốn 4 + 8 = 12.

Cách cộng chuỗi thứ 2 đỡ tốn bộ nhớ hơn cách thứ 1, và cũng là cách tốn ít bộ nhớ nhất.

Phân tích

Việc cộng n chuỗi với nhau luôn luôn tốn n-1 phép cộng chuỗi, và tạo ra chuỗi cuối cùng với độ lớn không đổi. Do đó, lý do tốn bộ nhớ không phải là vì kết quả cuối cùng, mà là do các mảng nhớ tạm ta phải sử dụng để chứa kết quả của các phép cộng chuỗi này.

Xét ba chuỗi bất kỳ với độ lớn x <= y <= z. Ta cần thực hiện 2 phép cộng chuỗi, và độ lớn của chuỗi cuối cùng sẽ là tổng của x + y + z không đổi. Độ lớn của chuỗi tạm sẽ là tổng này trừ đi độ lớn của chuỗi gốc trong phép cộng chuỗi thứ 2. Dễ thấy rằng nếu ta để dành chuỗi có độ lớn z để cộng cuối cùng, thì độ lớn của chuỗi tạm sẽ là nhỏ nhất, x + y.

Do đó, ta sẽ để dành chuỗi có chiều dài lớn nhất cho các phép cộng sau cùng, chuỗi có độ dài lớn thứ hai cho phép cộng kế cuối... Vì vậy, cách giải bài toán này chỉ đơn giản là sắp xếp các chuỗi đã cho theo thứ tự tăng dần về độ lớn chuỗi.

Phần cài đặt xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi phù hợp để trao đổi thêm về những vấn đề tương tự.

Phỏng vấn: In ra phần tử nhỏ thứ n trong cây nhị phân

written by Nguyễn Thành Nam, on Mar 19, 2015 11:19:23 AM.

Câu hỏi

Cho một cây nhị phân tìm kiếm (binary search tree), in ra phần tử nhỏ thứ n trong cây này.

Ví dụ: Với cây nhị phân như sau:

                7
           5         9
        3     6         10

Phần tử nhỏ nhất (n=1) là 3, phần tử nhỏ thứ 2 là 6, phần tử nhỏ thứ 3 là 5.

Phân tích

Vì đây là cây nhị phân tìm kiếm nên ta luôn có điều kiện bất biến là các đỉnh bên trái luôn luôn nhỏ hơn hoặc bằng, và các đỉnh bên phải luôn luôn lớn hơn hoặc bằng giá trị của đỉnh đang xét.

Do đó, phần tử nhỏ nhất thứ n cũng là phần tử thứ n trong quá trình duyệt cây theo thứ tự trái, giữa, phải, tức là theo cách tìm kiếm ưu tiên chiều sâu (depth first search).

# encoding: utf-8
def solve(root, n):

    def traverse(node, nr_seen):
        '''Trả về (số đỉnh đã qua, và kết quả).'''
        if node is None:
            return nr_seen, None

        # Tìm trong nhánh trái
        nr_seen, answer = traverse(node.left, nr_seen)
        if answer is not None:
            # Tìm thấy kết quả bên nhánh trái.
            return nr_seen, answer

        nr_seen += 1
        if nr_seen == n:
            # Đỉnh hiện tại chính là đỉnh cần tìm.
            return nr_seen, node.value

        # Tìm trong nhánh phải
        nr_seen, answer = traverse(node.right, nr_seen)
        return nr_seen, answer

    nr_seen, answer = traverse(root, 0)
    return answer


class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


root = Node(7, Node(5, Node(3), Node(6)), Node(9, None, Node(10)))
assert(solve(root, 1) == 3)
assert(solve(root, 2) == 5)
assert(solve(root, 3) == 6)
assert(solve(root, 4) == 7)
assert(solve(root, 5) == 9)
assert(solve(root, 6) == 10)

Phỏng vấn: Tìm các từ cùng bộ ký tự

written by Nguyễn Thành Nam, on Mar 16, 2015 9:05:00 AM.

Câu hỏi

Cho một quyển từ điển D, và một từ W trong từ điển, yêu cầu xuất ra tất cả các từ có trong từ điển với cùng bộ ký tự như từ W.

Ví dụ từ mary có bộ ký tự là một chữ m, một chữ a, một chữ r và một chữ y, từ army cũng có cùng bộ ký tự như vậy.

Phân tích

Mối quan hệ giữa từ, và bộ ký tự là 1-n, tức là một từ sẽ có một bộ ký tự, nhưng một bộ ký tự có thể có nhiều từ. Do đó, cách giải bài này là thể hiện mối quan hệ giữa từ và bộ ký tự của nó.

Với mỗi từ X trong từ điển, ta sẽ tìm ra bộ ký tự K tương ứng của từ đó, và lưu X vào danh sách các từ có bộ ký tự K. Để trả lời câu hỏi, ta chỉ việc in ra danh sách các từ có bộ ký tự tương ứng với W.

Độ phức tạp thực thi của cách giải này là O(1) với O(n) bước xử lý trước (preprocessing), và tốn O(n) bộ nhớ.

from collections import defaultdict

def get_alphabet(word):
    count = defaultdict(int)
    for c in word:
        count[c] += 1
    # vì kiểu dict là khả biến, nên ta phải
    # chuyển "count" thành kiểu string để
    # có thể dùng làm khóa trong một dict khác
    r = []
    for k in sorted(count.keys()):
        r.append('%c%d' % (k, count[k]))
    return ''.join(r)

assert(get_alphabet('aaabb') == 'a3b2')

def solve(D, W):
    alpha_to_words = defaultdict(list)
    for word in D:
        alpha = get_alphabet(word)
        alpha_to_words[alpha].append(word)
    return alpha_to_words[get_alphabet(W)]

assert(solve(['mary', 'army', 'vithon'], 'mary') == ['mary', 'army'])

Cách giải trên sẽ áp dụng tốt nếu ta cần trả lời cho một loạt các từ W bởi vì ta chỉ tốn thời gian xử lý trước một lần, và sau đó có thể truy vấn alpha_to_words cho mỗi từ W sau đó. Tuy nhiên, nếu ta chỉ cần trả lời câu hỏi cho duy nhất một từ W thì việc tốn thêm O(n) bộ nhớ cho alpha_to_words là không cần thiết. Trong trường hợp đó, ta chỉ việc xét từng từ trong D, nếu nó có cùng bộ ký tự như W thì ta xuất nó ra ngay.

Phỏng vấn: Số lượng số chính phương ít nhất để có tổng là n

written by Nguyễn Thành Nam, on Mar 14, 2015 10:53:00 PM.

Câu hỏi

Cho một số nguyên dương n, tìm số lượng số chính phương ít nhất có tổng là n.

Ví dụ: Với n là 9, thì đáp án là 1 (vì 9 là số chính phương), với n là 10 thì đáp án là 2 (9 + 1), với n là 11, đáp án là 3 (9 + 1 + 1), với n là 12 thì đáp án là 3 (4 + 4 + 4).

Phân tích

Giả sử như ta đã có đáp án cho tất cả các giá trị từ 1 đến n-1, đáp án cho n sẽ là min(1 + đáp án của (n-x)) với x là một số chính phương. Nói một cách khác, với mỗi số chính phương x nhỏ hơn hoặc bằng n, số lượng số chính phương cần để có tổng là n sẽ là số lượng số chính phương cần để tạo ra tổng là n-x thêm 1 (chính là x). Do đó, đáp án cho n sẽ chính là min của các cách tạo ra tổng n từ các số chính phương nhỏ hơn hoặc bằng n.

Như vậy, ta có thể giải bài toán này bằng cách điền vào bảng trả lời (đặt tên là ans) cho các giá trị từ 0 đến n. Kết quả cuối cùng sẽ là giá trị của ans[n].

Cách giải các bài toán mà đáp án cho giá trị cuối cùng có thể được tính từ đáp án của các giá trị trước, và ta có thể tính các giá trị này bằng cách từ từ điền vào bảng, được gọi là quy hoạch động (dynamic programming).

def solve(n):
    ans = [n] * (n + 1)
    ans[0] = 0
    ans[1] = 1
    for i in xrange(2, n + 1):
        x = 0
        while True:
            x += 1
            x2 = x * x
            if x2 > i:
                break
            ans[i] = min(ans[i], 1 + ans[i - x2])
    return ans[n]

assert(solve(9) == 1)
assert(solve(10) == 2)
assert(solve(11) == 3)
assert(solve(12) == 3)

Độ phức tạp thực thi của cách giải này là O(n * sqrt(n)), và tốn O(n) bộ nhớ.