Thử thách lập trình hàng tuần 367: Tối ưu hóa số nhị phân và phát hiện xung đột thời gian

Giới thiệu chung

Mỗi tuần, Mohammad S. Anwar gửi đến cộng đồng The Weekly Challenge – một cơ hội tuyệt vời để mọi người cùng nhau tìm ra giải pháp cho hai nhiệm vụ lập trình. Giải pháp của tác giả được viết bằng Python trước, sau đó chuyển sang ngôn ngữ Perl. Đây là cách tuyệt vời để chúng ta cùng thực hành kỹ năng lập trình.

Nhiệm vụ 1: Số nhị phân lẻ lớn nhất (Max Odd Binary)

Nhiệm vụ: Bạn được cung cấp một chuỗi nhị phân có chứa ít nhất một bit "1". Hãy viết một kịch bản để sắp xếp lại các bit sao cho kết quả là một số nhị phân lẻ lớn nhất có thể, trả về chuỗi nhị phân kết quả. Chuỗi kết quả có thể chứa các số 0 ở đầu.

Giải pháp: Bài toán này đòi hỏi một chút lý thuyết số. Để tạo ra một số nhị phân lẻ, bit cuối cùng (ít ý nghĩa nhất) cần phải là 1. Để tạo ra số lớn nhất có thể, các bit "1" còn lại cần được đặt ở vị trí quan trọng nhất (bên trái / nhiều ý nghĩa nhất), trong khi các bit "0" được đặt ở giữa.

Tác giả sử biểu thức chính quy (regex) để kiểm tra đầu vào và đếm số lượng số 0 và số 1. Sau đó, họ trả về một chuỗi bao gồm (số lượng bit 1 trừ đi 1), (số lượng bit 0), và một bit 1 cuối cùng để đảm bảo tính chẵn lẻ.

Nhiệm vụ 2: Xung đột sự kiện (Conflict Events)

Nhiệm vụ: Bạn được cung cấp thời gian bắt đầu và kết thúc của hai sự kiện. Hãy viết một kịch bản để tìm xem có xung đột nào giữa hai sự kiện này hay không. Một xung đột xảy ra khi hai sự kiện có giao điểm không rỗng.

Giải pháp: Một trong những thách thức khi hoàn thành các nhiệm vụ này là đạt được giải pháp tối ưu nhất. Đặc biệt, việc xử lý các thời gian vượt qua nửa đêm (qua đêm) làm cho bài toán phức tạp hơn.

Tác giả tạo ra một hàm hm2m để chuyển đổi thời gian từ định dạng "HH:MM" sang số phút kể từ nửa đêm, đồng thời sử dụng regex để xác thực định dạng đầu vào. Sau đó, họ tạo các đối tượng range từ thời gian bắt đầu đến thời gian kết thúc. Nếu thời gian bắt đầu lớn hơn thời gian kết thúc (qua đêm), chúng sẽ được chia làm hai khoảng: một trước nửa đêm và một sau nửa đêm. Cuối cùng, bằng cách duyệt qua từng phút của các khoảng thời gian này, họ kiểm tra xem có trùng lặp nào không.

Kết luận

Sự chuyển đổi giữa Python và Perl cho thấy sự linh hoạt trong lập trình. Cả hai giải pháp đều tập trung vào việc xử lý dữ liệu đầu vào và logic kiểm tra điều kiện một cách hiệu quả, giúp lập trình viên nắm vững các kỹ thuật xử lý chuỗi và thời gian.