Practise programming Python with Python Challenge

Posted in Programming on September 24, 2017 by manhhomienbienthuy Comments
Practise programming Python with Python Challenge

Python là một ngôn ngữ rất linh hoạt và mạnh mẽ. Trong bài viết này, tôi sẽ giới thiệu một nơi giúp chúng ta luyện tập và nâng cao năng lực code Python. Đó chính là Python Challenge.

Có nhiều nguồn để luyện kỹ năng lập trình khác nhau, ngay cả với từng ngôn ngữ riêng biệt. Python cũng không ngoại lệ, Python Challenge chỉ là một trong số hàng trăm trang luyện tập code Python khác. Tuy nhiên, cách làm của Python Challenge có nét tương đồng với notpron. Điều đó khiến chúng ta có cảm giác như đang chơi game vậy, vừa chơi game, vừa suy luận logic vừa nâng cao kỹ năng code. Chính những điều này làm nên sự khác biết và tôi thích sự khác biệt đó.

Python Challenge là chuỗi các câu hỏi với mức độ khó tâng dần, và với mỗi câu, chúng ta chỉ cần một chút code là giải được. Đó cũng là cách luyện tập rất hiệu quả, nhiều tính năng thú vị của ngôn ngữ, nếu chúng ta không biết sẽ phải code rất dài. Nhưng biết rồi thì chỉ cần vài dòng là đủ.

Theo lời tác giả, thì Python Challenge không chỉ dành cho ngôn ngữ Python, bạn có thể sử dụng bất cứ ngôn ngữ nào. Tuy nhiên, một vài câu hỏi yêu cầu thư viện viết riêng cho Python nên bắt buộc phải dùng Python mới giải được.

Trước khi bắt đầu, cũng phải lưu ý với các bạn rằng, vào thời điểm bài viết này, có tất cả 34 câu hỏi khác nhau (kể cả warm up). Tuy nhiên, thứ duy nhất bạn nhận được khi giải được là niềm vui ("it just for fun" trích lời tác giả), không có phần thưởng hay quà tặng nào dành cho bạn.

Cũng vì bạn sẽ nhận được niềm vui khi giải được cái bài toán, bạn nên tự giải một mình. Việc copy lời giải chỉ khiến bạn nhanh chóng chán nản mà thôi.

Một lưu ý nhỏ nữa là đúng như tiêu đề bài viết, nơi này là nơi để luyện tập kỹ năng code Python chứ không phải là nơi học code. Nếu bạn muốn nâng cao kỹ năng code của mình, không chỉ Python mà các ngôn ngữ khác nữa, đây chính là nơi dành cho bạn. Còn nếu bạn muốn đến đây là để học code Python cho người mới bắt đầu, tôi e rằng, bạn đã đến nhầm chỗ.

Giới thiệu thế đủ rồi, giờ thì bắt đầu thôi nào.

Khởi động

URL cho câu hỏi này ở đây. Bạn có thể dễ dàng tìm thấy link này ngay trên trang chủ.

Câu hỏi gợi ý chúng ta thay thế URL và cung cấp một bức ảnh.

warming up

Để ý URL một chút, chúng ta thấy nó là 0.html, vây chắc chắn là cần phải thay số 0 này thành số khác. Quá dễ, ảnh ghi 238 thì điền 238 vào là xong.

http://www.pythonchallenge.com/pc/def/238.html

Nhưng kết quả lại là

No... the 38 is a little bit above the 2...

Vậy là chúng ta đã sai. Nhưng mà sai ở đâu. Có lẽ do trình độ ngoại ngữ của mình có vấn đề nên đọc mãi câu kia mà vẫn không hiểu. Sau một vài tiếng không biết phải làm gì, đang định bỏ của chạy lấy người thì mình để ý thấy bức ảnh có tên là calc.jpg, gợi ý rằng chúng ta phải tính toán.

Cộng với thông báo lúc trước, 38 ở trên một chút so với 2. Nghĩ đi nghĩ lại thì cuối cùng hiểu ra rằng, người ta đang vẽ 2 mũ 38 chứ không phải 238. Vậy là chỉ cần tính 2^38 rồi thay URL là xong. Với Python thì tương đối đơn giản:

>>> 2 ** 38
274877906944

Vậy URL cho level tiếp theo sẽ là 274877906944.html. Truy cập trang này chúng ta sẽ được redirect đến một trang khác, với một bức ảnh khác. Vậy là đã qua bước khởi động.

Tuy nhiên, mở rộng bài toán một chút, thử giải với các ngôn ngữ khác xem sao. Phần lớn ngôn ngữ lập trình cho phép tính toàn số mũ rất đơn giản, thử shell script xem có gì hot:

$ echo "2 ^ 38" | bc
274877906944

Không ngờ lại dễ dàng như vậy, có lẽ là do bài khởi động chỉ đơn giản vậy thôi.

Level 1: Câu hỏi chính thức đầu tiên

URL cho câu hỏi này ở đây. Tiêu đề của đề bài là "What about making trans?" lại cộng với gợi ý ở trong ảnh:

K -> M
O -> Q
E -> G

Cùng một đống ký tự ở phía dưới

g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp.
bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmle.
sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj.

Với kinh nghiệm chơi CTF vài lần, câu này thuộc loại dễ, đoạn ký tự kia sử dụng mã cổ điển, họ lại gợi ý luôn cách dịch thế kia thì lại càng đơn giản, mỗi ký tự chỉ cần thay bằng ký tự cách nó 1 ký tự về phía sau là xong. Thử xem sao

>>> cipher = "g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc \
... dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm \
... jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj."
>>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
>>> plain = ''
>>> for c in cipher:
...     if c in alphabet:
...         plain += alphabet[(alphabet.index(c) + 2) % 26]
...     else:
...         plain += c
...
>>> plain
"i hope you didnt translate it by hand. thats what computers are for.
doing it in by hand is inefficient and that's why this text is so long.
using string.maketrans() is recommended. now apply on the url."

Vậy là với một chút code đơn giản, chúng ta đã tìm ra được lời giải cho câu hỏi này. Tuy nhiên, câu hỏi recommend chúng ta sử dụng string.maketrans nhưng code trên lại sử dụng cách làm trông rất thủ công. Thử lại với maketrans xem sao:

>>> cipher = "g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc \
... dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm \
... jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj."
>>> intab = 'abcdefghijklmnopqrstuvwxyz'
>>> outtab = intab[2:] + intab[:2]
>>> cipher.translate(str.maketrans(intab, outtab))
"i hope you didnt translate it by hand. thats what computers are for.
doing it in by hand is inefficient and that's why this text is so long.
using string.maketrans() is recommended. now apply on the url."

Trông code đã đẹp hơn rất nhiều rồi đó. Vậy là từ một câu hỏi đơn giản, chúng ta đã biết được một công cụ rất hữu ích của ngôn ngữ Python đó là maketranstranslate

Bây giờ là áp dụng vào URL. URL rất dài nhưng theo kinh nghiệm từ warm up thì chỉ cần để ý vào phần cuối của đường dẫn là đủ:

>>> url = 'map'
>>> url.translate(str.maketrans(intab, outtab))
'ocr'

Vậy câu hỏi tiếp theo sẽ là ocr.html. Mở ra thì chúng ta có được một bức ảnh với gợi ý, đúng là câu hỏi này rồi.

Ngoài lề một chút, chúng ta có thể thử sức giải bài toán này với nhiều ngôn ngữ khác nhau. Ví dụ ngôn ngữ Ruby có hàm tr_s rất giống hàm translate trong trường hợp này. Thậm chí, tr_s của Ruby còn mạnh mẽ hơn nữa cơ.

2.3.1 :001 > cipher = "g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmle. sqgle qrpgl lmu ynnjw ml rfc spj."
 => "g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmle. sqgle qrpgl lmu ynnjw ml rfc spj."
2.3.1 :002 > intab = 'abcdefghijklmnopqrstuvwxyz'
 => "abcdefghijklmnopqrstuvwxyz"
2.3.1 :003 > outtab = intab[2..-1] + intab[0..1]
 => "cdefghijklmnopqrstuvwxyzab"
2.3.1 :004 > cipher.tr_s(intab, outtab)
 => "i hope you didnt translate it by hand. thats what computers are for.
 doing it in by hand is ineficient and that's why this text is so long.
 using strin now aply on the url."
2.3.1 :005 > 'map'.tr_s(intab, outtab)
 => "ocr"
2.3.1 :006 >

Level 2: OCR

URL của câu hỏi này ở đây. OCR có lẽ là Optical character recognition, tức là nhận diện ký tự. Nhưng nhận diện ký tự trong bức ảnh này đến con người còn bó tay chứ nói gì đến máy.

ocr

Nhưng may sao, ngay phía dưới lại có gợi ý

recognize the characters. maybe they are in the book,
but MAYBE they are in the page source.

Kiểm tra mã nguồn của trang xem sao:

Nội dung trang rất dài nhưng đã bị comment gần hết. Có một gợi ý khác cùng với một đống (rất lớn) các ký tự đặc biệt.

find rare characters in the mess below

Như vậy là nhận diện ký tự không phải ở trong bức ảnh, mà chỉ đơn giản là nhận diện ký tự trong đống ký tự đặc biệt đó thôi. Nếu chỉ tìm ký tự bình thường thì đơn giản, giờ lại thêm tìm các ký tự hiếm. Không biết thế nào thì gọi là hiếm đây. Thôi thì cứ đếm xem số lượng các ký tự trong đó thế nào trước đã

>>> cipher = """
... %%$@_$^__#)^)&!_+]!*@&^}@[@%]()%+$&[(_@%+%$*^@$^!+]!&_#)_*}{}}!}_]$[%}@[{_@#_^{*
... @##&{#&{&)*%(]{{([*}@[@&]+!!*{)!}{%+{))])[!^})+)$]#{*+^((@^@}$[**$&^{$!@#$%)!@(&
... ...
... """.replace('\n', '')
>>> char_count = {}
>>> for c in cipher:
...     char_count[c] = char_count.get(c, 0) + 1
...
>>> char_count
{']': 6152, 'e': 1, 't': 1, '@': 6157, '*': 6034, 'l': 1, '(': 6154, '{': 6046, 'y': 1, '_': 6112, 'q': 1, '^': 6030, '%': 6104, '}': 6105, '#': 6115, '[': 6108, '+': 6066, '!': 6079, 'i': 1, '&': 6043, 'a': 1, 'u': 1, '$': 6046, ')': 6186}

Vậy là bài toán này không khó như chúng ta tưởng. Mỗi ký tự hiếm ở đây chỉ xuất hiện đúng 1 lần, còn lại các ký tự khác xuất hiện toàn trên 6000 lần thôi.

Và một điều nữa, chúng ta thấy rằng là các ký tự alphabet bình thường chỉ xuất hiện 1 lần, còn lại các ký tự đặc biệt mới là những ký tự xuất hiện nhiều. Vậy là bài toán này có nhiều hướng giải. Chúng ta có thể dùng 1 trong hai gợi ý là đủ để giải bài toán này chứ không phải kết hợp cả hai chúng lại mới có kết quả. Gợi ý thứ nhất bải chúng ta đơn giản chỉ là nhận diện những chữ cái xuất hiện trong vô vàn những ký tự đặc biệt khác. Hoặc theo gợi ý thức hai là tìm những ký tự chỉ xuất hiện đúng 1 lần. Về cơ bản thì cách nào cũng ra kết quả cả.

Ví dụ làm theo hướng thứ nhất

>>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
>>> ''.join(c for c in cipher if c in alphabet)
'equality'

Với cách làm này thì chúng ta thậm chí còn chẳng cần đến kết quả số lần xuất hiện các ký tự vừa tìm được. Nhưng dù sao đã tính rồi, chúng ta cứ làm theo hướng thứ hai xem sao

>>> ''.join(c for c in cipher if char_count[c] == 1)
'equality'

Về cơ bản cả hai cách này đều có code rất gọn gàng rồi, và tôi không nghĩ ra được cách nào tối ưu nó hơn nữa.

Và với kết quả trên, cộng với kinh nghiệm từ hai câu hỏi trước (thay URL là đến câu hỏi sau) thì câu hỏi tiếp theo mà chúng ta sẽ đối mặt ở địa chỉ equality.html.

Tương tự như câu hỏi trước, chúng ta có thể thử sức với ngôn ngữ Ruby.

Với cách làm thứ nhất

2.3.1 :007 > cipher = <<~'EOS'.gsub(/^[\s\t]*|[\s\t]*\n/, '')
2.3.1 :008'>   %%$@_$^__#)^)&!_+]!*@&^}@[@%]()%+$&[(_@%+%$*^@$^!+]!&_#)_*}{}}!}_]$[%}@[{_@#_^{*
2.3.1 :009'>   @##&{#&{&)*%(]{{([*}@[@&]+!!*{)!}{%+{))])[!^})+)$]#{*+^((@^@}$[**$&^{$!@#$%)!@(&
2.3.1 :010'>   ...
2.3.1 :011'> EOS
 => "%%$@_$^__#)^)&!_+]!*@&^}@[@%]()%+$&[(_@%+%$*^@$^!+]!&_#)_*}{}}!}_]$[%}@[{_@#_^{*@##&{#&{&)*%(]{{([*}@[@&]+!!*{)!}{%+{))])[!^})+)$]\#{*+^((@^@}$[**$&^{$!@\#$%)!@(&..."
2.3.1 :012 > cipher.chars.map{|c| c.match(/^[[:alpha:]]$/) ? c : ''}.join
 => "equality"
2.3.1 :013 >

Cách làm thứ hai

2.3.1 :014 > char_count = Hash.new 0
 => {}
2.3.1 :015 > cipher.chars.each{|c| char_count[c] += 1}
 => ["%", "%", "$", "@", ...]
2.3.1 :016 > cipher.chars.map{|c| char_count[c] == 1 ? c : ''}.join
 => "equality"
2.3.1 :017 >

Kết luận

Bài viết trình bày cách làm một số bài toán đầu tiên của Python Challenge. Hy vọng không spoiler quá nhiều. Python Challenge thực sự là một nơi rất tốt để luyện kỹ năng code. Nó không chỉ giúp chúng ta luyện khả năng code, mà nhiều khi giúp chúng ta học hỏi được nhiều thứ mới mẻ mà các tài liệu nhiều khi bỏ qua mất.

Hơn nữa, nó có thể giúp chúng ta nâng cao tư duy logic, luyện tiếng Anh và luyện tập code cả những ngôn ngữ khác, không nhất thiết phải là Python. Hy vọng, bài viết đã đem đến cho các bạn một thông tin giá trị.

I apologise for any typos. If you notice a problem, please let me know.

Thank you all for your attention.