Old but gold: історія студента, який виграв конкурс Дональда Кнута. Але, звичайно ж, є але

Привіт, спільното! Мене звати Макс, я досліджую та захоплююсь ІТ-індустрією, людьми, які її будують, і створюю про це контент. Конкретно зараз — для школи компʼютерних наук CS Osvita. Маю бажання ділитися більше і тут, на DOU, тож якщо вам буде це цікаво, залиште коментар :)

Колись натрапив на цю історію на Quora, зберіг її собі, а тепер зрозумів, що це той самий old but gold, яким я хотів би розпочати свою активність тут.

***

Оригінал історії можете знайти тут.

В головних ролях — один Дональд Кнут, один конкурс на найкоротшу програму за кількістю інструкцій та один студент, який зараз, згідно з його LinkedIn, є засновником венчурного фонду Berkeley Catalyst Fund. Час та місце: 1970-ті, Стенфорд, Каліфорнія.

Отже, переносимося в кампус Стенфорда, в аудиторію, наповнену PhD-студентами та бакалаврами. Професор — сам Дональд Кнут, автор The Art of Computer Programming, людина, яка навчила покоління інженерів думати про алгоритми не як про набір трюків, а як про систему мислення.

Щотижня професор Кнут пропонував студентам позмагатися в конкурсі. Цього разу завданням було написати програму, яка зчитує опис кросворду з вхідних даних і відтворює його. Не надто драматично. Але був нюанс: переможе та програма, яка матиме найменшу кількість інструкцій. Не найшвидша. Не найелегантніша. Саме найкоротша.

Дрю Ланза, тоді ще бакалавр, працював над цим завданням всю ніч. Десь о другій ночі його осяяло: а що, якщо не будувати алгоритм централізовано, а дозволити кожній клітинці кросворду «поговорити» із сусідніми? Кожна клітинка питає сусіда, той — свого сусіда, і так далі, поки граничні умови самі не проявляться. Рекурсія як діалог між елементами системи.

Код вийшов компактним. Він здав програму Кнуту і мав велику надію, що вона справді буде коротшою за більшість результатів.

Наприкінці заняття Кнут почав оголошувати результати. Третє місце — пʼятдесят інструкцій. Друге — сорок пʼять. Ланза знає, що його код коротший. Чи станеться зараз щось неймовірне і бакалавр обіграє PhD-студентів на курсі Дональда Кнута?

І ось що каже Кнут:

«Я вагаюся присуджувати перше місце. Програма-переможець була вдвічі коротшою за найближчого конкурента.

Коли я вперше запустив програму, здавалося, що вона застрягла в нескінченному циклі. Мейнфрейм зупинив задачу після стандартної однієї секунди процесорного часу. Я запустив її знову, але дав три секунди. Вона не завершилася. Я подивився на код — нічого не міг у ньому розібрати. Але цей студент завжди здавав роботи вчасно. Тож я ризикнув і встановив ліміт процесорного часу на 30 секунд.

Програма виконувалась понад 20 секунд процесорного часу, містере Ланца — це коштувало більше ста доларів. Але вона справді спрацювала, і це була найкоротша програма, тож цього тижня перемагає містер Ланца. Та вдруге так не ризикуйте, домовились?»

Після заняття Ланза підійшов до професора, готуючись до розносу. Замість цього Кнут спокійно пояснив: завдання передбачало лінійний час виконання, а твій алгоритм — експоненційний. Ланза чесно відповів, що просто буквально виконав умову: мінімум інструкцій. Про runtime думати не довелось.

— Як працював твій алгоритм? — запитав Кнут.

— Минулого семестру я проходив курс Lisp в професора Маккарті (це той, що винахідник мови LISP та лауреат премії Тюрінга — прим.) Якщо чесно, з рекурсією не склалося. Але я вирішив розглядати цю задачу як домашнє завдання з того курсу.

Все починається з першої клітинки кросворду — вона «запитує» сусідні клітинки, чи знають вони, що робити. Далі кожна сусідня клітинка рекурсивно робить те саме. Зрештою, граничні клітинки усвідомлюють, що перебувають на межі, і передають цю інформацію назад.

— Але ж це означає, що на кожному кроці рекурсії ти зчитував увесь масив даних, який описує кросворд, щоб перевірити граничні умови. Не дивно, що це тривало так довго.

— Професоре, мені здалося, що найкоротший шлях до мінімальної кількості інструкцій — це просто дозволити всім клітинкам кросворду «спілкуватися» між собою й дати їм самим усе з’ясувати. Саме в цьому й полягала задача з Lisp, яку ми розв’язували.

— До речі, який бал тобі поставив Джон на курсі з Lisp?

— Три з мінусом. Я так і не зрозумів рекурсію.

— О, я б так не сказав, — Кнут посміявся.

***

Ця історія не про рекурсію і не про те, як круто було в Стенфорді в 70-ті. Студент зробив рівно те, що попросили. Кнут сформулював завдання так, як сформулював. Просто умова конкурсу мовчки передбачала контекст, який ніхто не озвучив.

Як-то кажуть, так це ж було вже. Постійно. Команда оптимізує час деплою, а користувачі страждають. ML-інженер женеться за accuracy на валідаційній вибірці, а модель у продакшені деградує на реальних даних. Продакт-менеджер покращує конверсію на онбордингу, а на третій тиждень падає ретеншн.

Саме тому на курсах CS Osvita викладачі так вперто тримають поруч і фундаментальні речі, і продакшен. Бо історії на кшталт цієї за межами аудиторій рідко закінчуються лише сотнею доларів CPU-часу.