Lập trình động không phải ma thuật hắc ám

 (qsantos.fr)
2 điểm bởi GN⁺ 2024-01-15 | 1 bình luận | Chia sẻ qua WhatsApp
  • Ngay cả những bài toán có nhiều trường hợp đặc biệt như Advent of Code 2023 Day 12, nếu tìm được cấu trúc lặp lại cùng các bài toán con thì vẫn có thể xử lý bằng lập trình động
  • Cốt lõi là tách bài toán bằng đệ quy, giảm tính toán trùng lặp bằng memoization, rồi chuyển sang tính lặp bằng cách điền các giá trị cần thiết theo thứ tự phụ thuộc
  • Ví dụ Fibonacci cho thấy đệ quy ngây thơ đánh giá lặp lại f(1), nhưng nếu dùng cache thì chỉ cần đánh giá n + 1 giá trị từ f(0) đến f(n)
  • Khoảng cách Levenshtein và Advent of Code Day 12 minh họa quá trình dùng chỉ số trạng thái như độ dài chuỗi và chỉ số quy tắc làm khóa cache, rồi biến lời gọi đệ quy thành việc điền mảng
  • Khi nắm được lập trình động, bạn không chỉ cải thiện hiệu năng mà còn nhìn thấy trạng thái trung gian và quan hệ phụ thuộc của thuật toán, từ đó dễ tìm cơ hội tối ưu bộ nhớ hơn

Tên gọi dễ gây nhầm lẫn, nhưng ý tưởng thì đơn giản

  • Tên “dynamic programming” không liên quan trực tiếp đến các nghĩa hiện đại như “phong cách lập trình” hay “kiểu động”
  • Cốt lõi là một cách thiết kế thuật toán: chia bài toán thành các bài toán tương tự nhỏ hơn và tái sử dụng kết quả của chúng
  • Bài viết có thêm ghi chú biên tập rằng nếu nhìn theo nghĩa lịch sử của “programming” thì cách gọi này là hợp lý
  • Điểm xuất phát thường là một dạng phân rã bài toán thành các bài toán nhỏ hơn, giống như hàm đệ quy
  • Khi cùng một bài toán con xuất hiện nhiều lần, nhu cầu lưu kết quả tính toán để dùng lại bằng caching sẽ nảy sinh tự nhiên

Caching và chuyển sang vòng lặp qua ví dụ Fibonacci

  • Hàm Fibonacci được định nghĩa là f(n) = f(n - 1) + f(n - 2), và cách cài đặt đệ quy ngây thơ sẽ tính đi tính lại cùng các giá trị
  • f(1) là giá trị thực sự được cộng vào kết quả cuối cùng, nên khi f(n) lớn lên, số lần đánh giá của đệ quy ngây thơ cũng tăng rất nhanh
  • Nếu cache kết quả hoặc dùng memoization, ta không cần tính lại các giá trị f(4), f(3), f(2) đã tính rồi
  • Với cách này, chỉ cần đánh giá tổng cộng 7 giá trị từ f(0) đến f(6); nói chung giảm xuống còn n + 1 lần đánh giá
  • Tiến thêm một bước, nếu điền các giá trị cần thiết theo thứ tự từ f(0), f(1), các lời gọi đệ quy sẽ biến mất
    • F[2] = F[1] + F[0]
    • F[3] = F[2] + F[1]
    • Tiếp tục như vậy để tính đến F[6] = 8
  • Với Fibonacci, thậm chí không cần cả mảng; chỉ cần giữ giá trị liền trước và giá trị trước đó nữa
  • Luồng này cho thấy một con đường có hệ thống: bắt đầu từ định nghĩa toán học rồi chuyển sang cài đặt lặp

Mở rộng bằng ví dụ khoảng cách chỉnh sửa

  • Khoảng cách chỉnh sửa giữa hai chuỗi là số phép chỉnh sửa tối thiểu cần để biến một chuỗi thành chuỗi kia
  • Bài toán thay đổi tùy theo các loại chỉnh sửa được cho phép
    • Nếu chỉ cho phép thay thế ký tự thì là Hamming distance
    • Nếu cho phép cả chèn và xóa thì là Levenshtein distance
  • Khoảng cách Levenshtein có thể được chia thành các bài toán nhỏ hơn dựa trên ký tự cuối cùng của hai chuỗi A, B
    • Nếu ký tự cuối cùng giống nhau, bỏ qua hai ký tự đó và dùng khoảng cách của phần chuỗi còn lại
    • Nếu ký tự cuối cùng khác nhau, chọn chi phí nhỏ nhất trong thay thế, xóa, chèn
    • Nếu A rỗng, phải chèn mọi ký tự của B, nên chi phí là b
    • Nếu B rỗng, phải xóa mọi ký tự của A, nên chi phí là a
  • Nếu chuyển nguyên định nghĩa này sang đệ quy Python, nó sẽ rất chậm với các chuỗi dài và có nhiều khác biệt
  • Nếu Fibonacci tăng xấp xỉ thành hai nhánh ở mỗi tầng của cây gọi hàm, thì đệ quy này có thể tăng thành ba nhánh tùy trường hợp
  • Gắn functools.cache của Python vào sẽ cho phép tái sử dụng kết quả tính toán của cùng các tổ hợp chuỗi con
  • Cách cài đặt tốt hơn là không liên tục tạo chuỗi mới, mà chỉ truyền chuỗi gốc A, B cùng độ dài chuỗi con a, b
  • Ở bước cuối, ta trực tiếp tạo mảng cache hai chiều và điền theo thứ tự sao cho cache[a][b] = levenstein(A[:a], B[:b])
  • Phiên bản lặp duyệt a và b từ 0 đến độ dài chuỗi, đồng thời tham chiếu các giá trị ở hàng trước và cột trước đã được điền

Áp dụng cho Advent of Code 2023 Day 12

  • Bài toán ngày 12 tháng 12 năm 2023 của Advent of Code là bài toán giải nonogram một chiều
  • Dữ liệu ví dụ có dạng .??..??...?##. 1,1,3, trong đó ? có thể trở thành . hoặc #
  • Cách tiếp cận brute force dùng backtracking, nhưng nếu có n dấu hỏi thì phải đánh giá 2^n ứng viên, nên tăng theo cấp số mũ
  • Xuất hiện cấu trúc trong đó cùng các bài toán con được lặp lại
    • ..#..??...?##. (1),1,3
    • .#...??...?##. (1),1,3
    • Nếu bỏ phần đầu đã xử lý, chúng trở thành những bài toán gần như giống nhau như .??...?##. 1,3, ..??...?##. 1,3
  • Hàm backtracking cơ bản nhận conditions và rules rồi tính số cách sắp xếp khả dĩ
    • Nếu không còn quy tắc nào, kiểm tra xem phần điều kiện còn lại có # hay không
    • Nếu không còn điều kiện nào, kiểm tra xem còn quy tắc nào không
    • Nếu ký tự hiện tại là . hoặc ?, tính tiếp sau khi bỏ qua một ô
    • Nếu ký tự hiện tại là # hoặc ?, kiểm tra kích thước quy tắc tiếp theo và điều kiện dấu phân tách, rồi chuyển sang trạng thái tiếp theo
  • Trong Python, chỉ cần gắn @cache là có thể áp dụng memoization
  • Để chuyển sang lập trình động, không cắt chuỗi và quy tắc để truyền đi nữa, mà dùng offset chuỗi i và offset quy tắc j làm trạng thái
  • Sau đó trực tiếp tạo cache[i][j] và thay đệ quy bằng tính lặp bằng cách điền chỉ số theo thứ tự ngược
  • Ví dụ cài đặt Rust được cung cấp qua liên kết Rust implementation trong bài viết

Những điều thấy được khi tự điền cache

  • Phiên bản lập trình động của Advent of Code Day 12 có thể trông chậm hơn phiên bản memoization
  • Khác biệt này có thể là do cài đặt Python chưa được tối ưu
  • Khi tự xây dựng cache, bạn sẽ thấy rõ hơn những giá trị nào thực sự cần thiết
  • Với bài toán Day 12, phiên bản lập trình động cho thấy chỉ cần cột trước đó
  • Vì vậy, có thể thay mảng hai chiều bằng hai mảng một chiều đại diện cho cột trước và cột hiện tại

Các bài toán đáng luyện tập và kết luận

  • Lập trình động không hề tầm thường, nhưng cũng không phải kỹ thuật ngoài tầm với của hầu hết lập trình viên
  • Nếu hiểu cách chia bài toán thành các bài toán nhỏ hơn, trong nhiều tình huống chỉ riêng memoization cũng đã cải thiện đáng kể so với cài đặt ngây thơ
  • Khi thành thạo hơn, bạn có thể hiểu một họ thuật toán, nắm rõ hơn các đánh đổi và tìm thêm các tối ưu hóa
  • Các bài toán sau được gợi ý để luyện tập
  • Sau khi cài đặt, đừng quên benchmark và profiling

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-01-15
Các ý kiến trên Hacker News

  • Tôi thích việc bài viết chỉ ra rằng thuật toán quy hoạch động chỉ là một cách thông minh để cache đệ quy. Theo kinh nghiệm của tôi, trước tiên tìm ra lời giải đệ quy là điểm khởi đầu tốt nhất để tìm lời giải quy hoạch động; một khi đã có, memoization rất dễ áp dụng và có thể đem lại mức tăng tốc lớn.
    Đôi khi nó còn nhanh hơn quy hoạch động theo kiểu từ dưới lên, vì chỉ tính những lời giải thực sự cần thiết. Điểm cốt lõi là dù cây gọi có nhiều bài toán con cũng không sao, nhưng số lượng bài toán con khác nhau phải tương đối ít. Không có lý do gì để cache một kết quả chỉ cần một lần, và cái khó là chia bài toán ban đầu thành đủ ít bài toán con khác nhau

    • Phần nói rằng số bài toán con khác nhau phải tương đối ít là mấu chốt. Toàn bộ thuật toán là dạng đệ quy hay dạng lặp chỉ là thứ yếu, và quy hoạch động thường bộc lộ rõ trong các thuật toán đệ quy
    • Cách giải thích “quy hoạch động là cách cache đệ quy” là khoảnh khắc khiến tôi hiểu ra. Hồi đại học, có lẽ vì lập trình thủ tục khi đó là chủ đạo, các ví dụ điền bảng từ dưới lên trong giáo trình trông như ma thuật
      Về mặt thực tế thì làm vậy là đúng, vì loại bỏ lời gọi đuôi không phải lúc nào cũng được áp dụng, nhưng tôi ước gì mình đã được học trước theo góc nhìn trực quan hơn: đệ quy từ trên xuống kèm cache
    • Khi mới học, tôi từng nghĩ nếu đây là một tính năng hào nhoáng như vậy thì chẳng phải nên gọi là memoization bằng mảng hoặc memoization ngăn xếp lời gọi sao. Tôi nghĩ cái tên “quy hoạch động” lẽ ra nên được dành cho một thứ gì đó hay hơn
    • Tôi cho rằng xem quy hoạch động đơn giản là đệ quy có memoization là một hiểu lầm phổ biến. Nếu học theo cách đó, sẽ rất khó hiểu các bài toán quy hoạch động thuộc kiểu điền mảng hai chiều
      Ví dụ, nhìn vào loạt bài “Best Time to Buy and Sell Stock” trên LeetCode, những bài như https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... chẳng phải cách điền mảng tự nhiên hơn nhiều sao. Tôi chưa từng giải bằng đệ quy, và cũng không chắc có lời giải đệ quy tự nhiên hay không
      Liên kết trên là bài III, nhưng với người mới làm lần đầu thì bắt đầu từ bài đầu tiên https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... sẽ là cách nhập môn quy hoạch động tốt
    • Nói “quy hoạch động chỉ là caching/memoization” cũng giống như nói “đầu tư chỉ là mua đồ rồi bán lại sau”. Về mặt kỹ thuật có thể đúng ở mức nào đó, nhưng bỏ sót quá nhiều độ phức tạp và sự khó khăn của chủ đề nên có thể trông buồn cười hơn là sâu sắc

  • Nguồn gốc của tên gọi “quy hoạch động” đến từ người phát minh ra nó, Richard Bellman. Năm 1950 tại RAND, ông đang tìm một cái tên cho quá trình ra quyết định nhiều giai đoạn; khi đó Bộ trưởng Quốc phòng Wilson được nói là ghét từ “nghiên cứu” đến mức bệnh lý, và từ “toán học” thì càng phải tránh hơn
    Bellman cần một cái tên để che giấu với Wilson và Không quân rằng thực ra họ đang làm toán bên trong RAND. Vì vậy, nó liên quan đến lập kế hoạch, ra quyết định và tư duy, nhưng “planning” không hay vì nhiều lý do, nên ông chọn “programming”; để chứa khái niệm nhiều giai đoạn và thay đổi theo thời gian, ông thêm “dynamic”, một từ có ý nghĩa chính xác trong vật lý cổ điển
    Ông cũng thích việc “dynamic” là một tính từ khó dùng theo nghĩa tiêu cực, và đó là một cái tên mà nghị sĩ cũng khó phản đối, nên ông đã dùng dynamic programming làm tên gọi bao quát cho hoạt động của mình
    Nguồn: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

  • Tôi thích cách bài viết trước hết bộc lộ bài toán theo kiểu đệ quy, rồi dần dần thêm caching, và cuối cùng giảm kích thước cache xuống chỉ còn mức cần thiết
    Tôi thường cố đi thẳng tới lời giải quy hoạch động rồi bị kẹt, hoặc phải gắng sức quá mức để làm cho nó chạy được. Từ giờ tôi sẽ tự buộc mình đi theo từng bước theo đúng thứ tự

    • Theo kinh nghiệm của tôi, nếu dạy quy hoạch động ngay từ đầu thì nó có cảm giác như một câu đố. Khi đi qua từng bước, giải thích vì sao dùng bảng, rồi liên hệ khái niệm đó với caching, người học sẽ hiểu tốt hơn nhiều

  • Một ứng dụng thú vị của quy hoạch động là căn chỉnh từng cặp trình tự nucleotide/protein
    https://en.wikipedia.org/wiki/Sequence_alignment
    https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
    https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

    • Tôi cho rằng các thuật toán này là một trong những thuật toán quan trọng nhất trong tin sinh học/sinh học. Phạm vi ứng dụng của chúng rất rộng

  • Tôi từng có một giáo sư thuật toán rất giỏi, từng học ở UCLA. Buổi học về quy hoạch động rất xuất sắc: trước hết bắt đầu bằng một bài toán mà cách giải đơn giản có độ phức tạp thời gian hàm mũ, sau đó chia bài toán thành các bài toán nhỏ hơn để hạ độ phức tạp xuống mức đa thức, rồi lại áp dụng memoization để giảm xuống tuyến tính
    Ước gì tôi nhớ được khi đó thầy đã dùng những bài toán nào

    • Các ứng viên có thể là dãy Fibonacci, bài toán đổi tiền xu, bài toán ba lô 0/1, nhân chuỗi ma trận, dãy con chung dài nhất, dãy con tăng dài nhất, các bài toán đường đi ngắn nhất như Floyd-Warshall, và khoảng cách chỉnh sửa (khoảng cách Levenshtein)
      Tất cả đều là những ví dụ tiêu biểu trong đó cách giải ngây thơ kém hiệu quả và được cải thiện rất nhiều bằng quy hoạch động
    • Trong bài viết cũng có ghi vài bài, và đây đều là các bài toán thường thấy trong bài giảng hoặc thực hành. Ví dụ có dãy con chung dài nhất, chuỗi con chung dài nhất, line warp, tổng tập con, phân hoạch, bài toán ba lô
      Có thể xem thêm nhiều ví dụ tại https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
    • Ngoài các bài toán người khác đã nêu, cũng có thể đó là bài toán lập lịch. Chẳng hạn bài toán có N sự kiện chồng lấn về thời gian, hoặc tối ưu thời khóa biểu môn học hay các tiến trình CPU theo tiêu chí như thông lượng
      Theo tôi biết, nếu thêm các ràng buộc đặc biệt như “hai môn này phải học cùng nhau” thì nó trở nên phức tạp và khó xử lý hơn nhiều so với quy hoạch động thông thường
    • Có phải người đó từng học dưới Kang ở UCLA không?

  • Có vẻ trang gốc không chịu nổi lưu lượng truy cập, nên tôi để lại liên kết lưu trữ
    https://web.archive.org/web/20240114111200/https://qsantos.f...

  • Nhờ quy hoạch động, người ta đã tính được số thế cờ vây hợp lệ, và giá trị đó là một số có 171 chữ số
    Cách ngây thơ phải xét mọi thế cờ có thể có trên bàn cờ vây n×n nên mất 3^(n^2) thời gian, còn quy hoạch động về cơ bản loại bỏ một chiều, giảm độ phức tạp thời gian xuống O(n^5 * 5.4^n) và độ phức tạp không gian xuống O(n * 5.4^n)
    https://tromp.github.io/go/legal.html
    https://tromp.github.io/go/gostate.pdf

  • Cái tên “Dynamic Programming” có thể nghe hơi kỳ vì ở đây programming không chỉ lĩnh vực lập trình. Trong trường hợp này, nó mang nghĩa gần với tối ưu hóa, tương tự như quy hoạch tuyến tính
    Có thể xem quy hoạch động là phương pháp giải các bài toán ra quyết định theo thời gian rời rạc, tức là chọn thứ tự tối ưu {a_t} để tối đa hóa \sum_t u_t(a_t) dưới các ràng buộc. Nó định nghĩa hàm giá trị V* là V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) }, qua đó giảm mạnh số chiều của bài toán tối ưu

    • Thật ra nguồn gốc chính thức của cái tên này https://en.wikipedia.org/wiki/Dynamic_programming#History khá buồn cười. Bellman nói ông thích “dynamic” vì đó là một tính từ không thể bị dùng theo nghĩa tiêu cực, và coi đây là cái tên mà ngay cả nghị sĩ cũng không thể phản đối
    • Khi người khác dùng cụm “quy hoạch động”, đôi khi tôi cảm thấy như họ đang phô trương để tỏ ra thông minh. Thực ra chỉ là dùng một cách tiếp cận tự nhiên và trực quan, nhận ra rằng có thể chia bài toán thành các bài toán con ngày càng nhỏ hơn, nhưng lại nói như thể đã “dùng” một kỹ thuật đặc biệt nào đó
    • Thật thú vị là ngày trước, việc tính toán một thứ gì đó, như trong các bài toán tối ưu hóa, từng chi phối mạnh hơn nhiều trong cách người ta nghĩ về việc máy tính sẽ làm gì. Ngày nay phần lớn là lưu trữ·truy vấn dữ liệu và networking; ngay cả khi bên trong có tính toán thì thường cũng có cảm giác là đã được đóng gói kỹ
    • Từ “tối ưu hóa” cũng gây hiểu nhầm tương tự. Có lần tôi từng học một lớp khoa học máy tính tên là “optimization” và đã kỳ vọng một thứ hoàn toàn khác
    • Lùi xa hơn nữa, “programming” thực ra mô tả chính xác khái niệm này. Thứ ngày nay chúng ta gọi là “lập trình” thật ra là viết mã, và có thể chia thành nhiều nhánh lập trình như hàm, khai báo, thủ tục. Dưới chiếc ô đó còn có nhiều thứ hơn rất nhiều

  • Khi nghe “quy hoạch động”, nếu chỉ nghĩ đó là memoization thì có sai không? Phần còn thiếu có thể là việc chia nhỏ bài toán một cách khéo léo để có thể dùng memoization

    • Memoization là một kỹ thuật tổng quát hơn. Thường nó chỉ là cache kết quả đã tính để phòng khi sau này cần dùng lại
      Quy hoạch động gần với memoization có hệ thống hơn. Ta giải các bài toán con ngày càng lớn để đi đến lời giải của toàn bộ bài toán. Cụm “thuật toán quy nạp” cũng hợp ở một mức nào đó, vì các thuật toán quy hoạch động điển hình về cơ bản giống với một chứng minh bằng quy nạp toán học. Tiếc là thuật ngữ đó đã có những nghĩa khác
    • Tôi dạy quy hoạch động đúng theo cách đó. Trước hết giải bằng đệ quy, rồi sau đó thêm memoization. Cách này gọi là từ trên xuống
      Sau đó, khi nhận ra đệ quy và memoization có overhead, ta xây bảng từ dưới lên và loại bỏ các lời gọi đệ quy; như vậy sẽ thành quy hoạch động
    • Theo cách tiếp cận của tôi, memoization là bước 2 trong 3 bước của quy hoạch động. Bước 1 là tìm thuật toán đệ quy, bước 2 là memoization, bước 3 là biến nó thành dạng lặp/từ dưới lên, và nếu có thể thì bước 3b là tối ưu không gian
      Bước 3 là phần đặc trưng nhất của quy hoạch động, nhưng tôi nghĩ dừng ở bước 2 vẫn có thể gọi là quy hoạch động. Chỉ là nó chưa hiệu quả hết mức có thể. Nói cách khác, memoization là caching, còn bước 3 là hỏi liệu có cách nào điền trước cache đó hay không
    • Cũng có các lời giải quy hoạch động không dựa trên memoization. Ví dụ, trong bài toán tìm chuỗi con chung dài nhất của hai chuỗi, ta chỉ cần các ô bên trái và bên trên của bảng một lần, nên memoization không giúp ích nhiều
      Nói chung, nếu các bài toán con chồng lặp nhiều và bài toán con tối ưu phải trở thành một phần của nghiệm tối ưu toàn cục, thì có cơ hội dùng quy hoạch động. Nói chỉ memoization mới là quy hoạch động cũng giống như nói chỉ hash table mới là kiểu dữ liệu trừu tượng
    • Theo tiêu chuẩn của tôi thì nghĩ như vậy là sai. Trước hết, có một phản ví dụ rõ ràng là memoization có thể dùng bên ngoài quy hoạch động. Ngược lại, phần lớn thuật toán quy hoạch động có thể được triển khai bằng cách lưu kết quả vào bảng rồi về sau tìm đáp án tốt nhất từ bảng đó
      Memoization về cơ bản là một chiến lược làm thuật toán chạy nhanh hơn

  • Việc hoàn thành Advent of Code năm nay khá thú vị. Rõ ràng ngày 1, đặc biệt là phần 2, khó hơn hẳn các năm trước, và tôi cũng đã viết về điều đó ở https://blog.singleton.io/posts/2024-01-02-advent-of-code-20..., nhưng chỉ so sánh thống kê hiện tại của năm 2022 với thống kê hiện tại của năm 2023 thì không rõ ràng, vì các câu đố năm 2022 đã có thêm một năm để mọi người giải
    Khi tôi lấy thống kê năm 2022 vào ngày 14/1/2023 https://web.archive.org/web/20230114172513/https://adventofc... thì khác biệt khá lớn. Nếu vẽ thống kê hoàn thành phần 2 https://blog.singleton.io/static/imgs-aoc23/completion.png thì quy mô nhóm bắt đầu ngày 1 tương tự nhau, nhưng năm 2023 rõ ràng có vẻ khó hơn năm 2022 cho đến ngày 15
    Tỷ lệ những người giải được phần 1 nhưng không giải được phần 2 https://blog.singleton.io/static/imgs-aoc23/ratios.png cũng cao hơn nhiều ở nhiều ngày trong năm 2023, đặc biệt cho thấy ngày 5, ngày 10, ngày 12 và ngày 22 phần 2 là khó

    • Advent of Code thời kỳ đầu rất vui, và trước các chặng cuối vẫn có thể trụ được mà không cần kỹ thuật gì quá hoành tráng. Về sau nó trở nên khó hơn và kém vui, nên tôi bỏ cuộc và không đụng đến nữa
    • Advent of Code năm nay tôi không tiến xa được vì thiếu thời gian, nhưng có thể sau này sẽ thử lại
      Tuy nhiên tôi đã rất ngạc nhiên về độ khó của ngày 5 phần 2. Tôi vẫn giải được mà không bỏ cuộc, nhưng cứ nghĩ có lẽ mình đã bỏ sót điều gì đó hiển nhiên nên mới giải quá phức tạp; biết rằng vốn dĩ đó là một bài khá thách thức khiến tôi thấy nhẹ nhõm
    • Đây chỉ là trải nghiệm cá nhân, và cũng có thể bị ảnh hưởng bởi việc tôi thử bằng một ngôn ngữ không phải ngôn ngữ thường dùng, nhưng tôi cho rằng ngày 1 phần 2 không hẳn là khó mà là mô tả bài toán không phù hợp
      Các ví dụ được đưa ra là two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen, nhưng lại thiếu ví dụ cốt lõi như oneight. Nếu không có những ví dụ như vậy, rất khó xác định chính xác phải thay thế giá trị như thế nào
    • Nói thêm về cuộc thảo luận này, tôi có một script để xem tiến độ theo từng ngày. Nhìn vào hai cột cuối sẽ thấy năm 2023 khắc nghiệt hơn năm 2022 đến mức nào, đặc biệt là giai đoạn đầu
      Năm 2022, trong vài ngày đầu hầu hết mọi người tiếp tục tham gia, tỷ lệ duy trì ở nhiều ngày vượt 80%, và gần như tất cả đều giải cả hai phần. Trái lại, vào ngày 1 năm 2023, trong số những người giải được phần 1, chỉ 76% giải tiếp được phần 2, và rất nhiều người bỏ cuộc ở ngày 3 và ngày 5
      Điều thú vị là vài ngày cuối không thấp đến vậy, điều này có thể được giải thích bằng việc Advent of Code 2023 gần đây hơn 2022. Theo cách diễn giải của tôi, nhóm này là những người sẽ vượt qua mọi thử thách đến một mức nào đó bất kể độ khó, còn nhiều người khác sẽ dừng lại nếu cảm thấy nó tốn quá nhiều thời gian