Дональд Кнут —  автор «Искусства программирования»  и  великий мастер ордена программистов Земли04.01.2022 12:46

Фото для коллажа взято с сайта The New York Times

Уже совсем скоро — 10 января  гранд-мастеру программирования исполнится 84 года,  , а он считает, что для окончания основного труда его жизни «Искусства программирования» ему необходимо еще 25 лет.  Дай бог ему здоровья, сил и ясный ум, а со всем остальным он точно справится сам. Кстати, рост у него не как у мастера Йоды — 190 см, вот здесь хорошо видно по плечам, хотя он, конечно, сильно сутулится.

https://www.fi.muni.cz/events/2019–10–09-donald-knuth-question-answer-session-boundless-interests-brno.html.en

На Хабре писали про Кнута  предостаточно, потому  ограничусь здесь  моими любимыми цитатами и одной замечательной историей из его жизни, про которую здесь  почему-то еще  не писали.

Именно  ее я поведал  своим ученикам на самых первых уроках программирования лет 20 назад (да, был такой период, когда я преподавал в техническом лицее в маленьком  провинциальном городке у полярного круга).  Зачем же я ее рассказал? Чтобы объяснить, какие именно качества необходимы будущему программисту, хотя в нашей истории нет ни единого слова ни о программировании, ни о компьютерах.

«Дональд Кнут был  младше вас, сидящих здесь в классе, ему едва ли исполнилось 14 лет,  когда он услышал, как по ТВ объявили  о конкурсе местной кондитерской компании:  предлагалось из букв использованных в названии нового  шоколадного батончика  «Гигантские батончики Циглера» («Ziegler’s Giant Bar») составить наибольшее количество слов. Приз  для победителя  держали в тайне, но как обещали, он  точно должен быть весьма ценным.  Игры в слова, настолки  типа скрэббла, до сих популярны в США и являются  традиционным семейным досугом.  Потому многие любители настольных  игр, конечно же, тут же подписались на участие в конкурсе.

Поразмыслив  Дональд тоже решил принять участие.  Что он мог противопоставить  компании (семье) из 5–6 друзей  заядлых игроков- «монстров  скрэббла», которые за считанные минуты  могли составить десятки слов, а за один  только вечер уж точно не менее нескольких сотен слов в сумме?

Если на короткой дистанции в 2–3 дня  у него точно нет ни единого шанса,   то на длинной  —  в две недели он вполне может победить, просто потому что примерно знал, как именно его соперники  будут действовать.  Каждый из игроков  станет составлять список слов самостоятельно в течение определенного времени,  затем они соберутся в одной большой комнате и начнут  по очереди их зачитывать, при этом каждый  игрок будет вычеркивать у себя уже  прозвучавшие слова. В конце  все полученные незачеркнутые слова будут занесены  (переписаны)  в основной список.  На второй и третий день количество таких слов  уменьшится в разы.  При этом все больше времени станет уходить на сверку  новых слов с предыдущим списком.  Очевидно, что скорость роста основного списка будет неуклонно и быстро падать с каждым днем.

Так каким  же образом  Дональд  мог обогнать целую команду таких игроков?

Только если выберет иной путь к достижению цели.  И он делает это:   зачем  составлять  слова из данного  набора букв, когда можно  проверять готовый список слов на наличие в нем этих самых  букв?!

 Если взять  достаточно полный словарь английского языка,   то база для поиска  слов будет просто огромной, а, следовательно,   итоговый  результат должен   быть  заметно лучше  чем у «монстров скрэббла».  Тем более, что такой словарь  у Дональда, а точнее у его отца  — владельца типографии,   был:   New Standard Unabridged Dictionary of the English Language,  Funk & Wagnalls. Замечательный  двухтомник — всего навсего на две тысячи страниц.

Что же такое словарь?    Это, по сути, список всех слов в алфавитном порядке.  Значит, отпадает одна из главных проблем — проверка  найденных слов на уникальность,   поскольку в словаре изначально нет повторов. Скорость поиска слов таким методом хоть изначально не слишком высока, но будет практически постоянной все две недели, не снижаясь к концу срока.

Идея использовать словарь, конечно же, замечательная, но как ее осуществить?   Каким образом перебрать более 50 тысяч слов на наличие  в них определенного набора букв за столь короткий срок?    Кнут  в воспоминаниях не описывает своего  алгоритма,   но, уверен,  мы сами сможем восстановить его, используя его упоминания про закладки и карточки.  

Для начала Дональд аккуратно   выписывает буквы из фразы «Ziegler’s Giant Bar»,   удаляя  повторы и размещая их в алфавитном порядке (11 букв).  На втором листе  он выписывает все буквы  невходящие  в эту фразу так же в алфавитном порядке (15 букв).  Затем вносит закладки в словарь по начальным буквам, которых нет в ключевой фразе.  На этом этапе таким образом он исключает  для будущего анализа, не менее 30  тысяч слов.  Потом   приступает к делу, составляя карточки с сочетаниями первых и вторых букв, пропуская ровно так же слова, у которых вторые буквы не входят  в ключевую фразу. Уже на этом этапе  у него остается всего около 10 тысяч слов.   Поскольку словарь, напоминаю,   упорядочен по алфавиту,   натыкаясь, например, на третью букву невходящую в список,   он листает словарь, пока эта или предыдущие по порядку буквы в словах не сменятся.

Тем не менее, такой  кропотливый труд требует много времени,   и с началом второй недели до окончания конкурса,   понимая, что он катастрофически не успевает закончить перебор всех слов,  Дональд  отпрашивается с уроков на неделю, сославшись на сильные боли в животе, и запирается дома в подвале на восемь часов в день и больше, анализируя и выписывая полученные слова.

Итог его работы за две недели — четыре с половиной тысяч слов!

Ни один других  участников не составил  более двух тысяч слов,   у самих судей на руках изначально — список всего из двух с половиной тысяч.   Такого результата от долговязого 13-летнего школьника не ожидал никто. Его пригласили на телепередачу,   где торжественно вручили  главный приз  — телевизор   и большую  коробку шоколадных батончиков.  Телевизор достался школе, а батончики  он раздал в своим одноклассникам».  

Так какие же качества будущего программиста продемонстрировал  Дональд Кнут в данной истории?

Первое:  умение выполнить  постановку  задачи.  То, чему в школе, да зачастую и в университетах не учат в принципе.  Вспомните формулировки задач в учебниках: вот вам необходимые и достаточные данные  для решения, , а теперь решайте задачу и получите  ответ. В жизни так не бывает.  Ты получаешь задание,  , а вот постановку задачи  ты должен сделать сам, как, впрочем, определить  и найти  нужные данные  для ее решения.  В нашем случае  задание: «Составить как можно больше слов из данного набора букв»,   он свел к очень конкретно  поставленной задаче:   «Найти  все слова в данном словаре,   полностью состоящих из данного набора букв».

Второе:   вместо того, чтобы действовать и сразу же приступить к поиску этих слов в словаре,  он сначала разработал алгоритм отсеивания  слов,  неподходящих  к требованиям задачи. К сожалению, у многих программистов умение остановиться  и подумать, прежде чем начать стучать по клавиатуре, напрочь отстутствует, они предпочитают, как я это называю,   «думать руками» — кодят сразу: «Хрен ли здесь думать — прыгать надо!» И это, уж извините, очень плохо.

Третье: хотя  постановка задачи и разработка алгоритма решения задачи весьма интересны и очень важны, но занимают они в самом лучшем случае лишь 5%  от затраченного времени и сил  в процессе решения той или иной задачи.  Остальное — рутина:   реализация алгоритма  с учетом особенностей языка программирования,   доводка программы до рабочего состояния,  затем  тестирование, бесконечное вылавливание блох (исправление багов)  в программе. Без огромного упорства и концентрации на предмете в программировании абсолютно точно нечего делать. Именно эти свойства  и продемонстрировал нам тринадцатилетней подросток, работая без выходных две недели в подвале своего дома, просто потому что решил довести дело, за которое взялся, до конца. Увы, если у вас «шило в заднице» — программирование не для вас, каким бы острым и быстрым  умом вы не обладаете.

После знакомства с основными  понятиями и операторами  языка программирования, давал ученикам эту задачу, как одну из начальных после освоения азов, причем  исходный словарь они должны были найти сами. При желании може раскрыть спойлер и посмотреть.

Ziegler’s Giant Bar

with open("c:\wordbook.txt", "r") as file1:
    mn_zgbar=set("zieglersgiantbar")
    i=0
    # итерация по строкам словаря
    for line in file1:
        if line[len(line)-1]=='\n':
          line=line[:len(line)-1]
        #line = line.replace('\n','')
        mn_line=set(line)
        if mn_zgbar >= mn_line:  # проверка вхождения букв слова в ключевую фразу
            i+=1
            print(i,' ', line)

with open("c:\wordbook.txt", "r") as file1:
    zgbar="abegilnrstz"
    i=0
    # итерация по строкам словаря
    for line in file1:
        if line[len(line)-1]=='\n':
           line=line[:len(line)-1]
        k=0
        flag=False
        while k