Недавно Мэтт и Стив, довольно известные ютуберы (один из которых популярнее другого), рассказали интересную историю. Это был рассказ о картине. Это был рассказ о математике. Это был захватывающий анализ выдуманной задачи с интересной математикой из нескольких школ мысли. Вы можете увидеть произведение искусства в их видео (каламбур) на YouTube.
Я здесь не для того, чтобы говорить с вами о том, какие крутые Мэтт и Стив (если только они не читают это, в таком случае да, вы самый крутой). Я здесь, чтобы поговорить о том, насколько глупыми кажутся их простые математические наблюдения любому, у кого есть степень в области компьютерных наук и раздутое эго. Это история случайного инженера-программиста, посмотревшего это видео и получившего вполне адекватную реакцию держи мою клавиатуру.
Ладно, хватит болтовни. О чем это все? Что это за картина? Я не люблю смотреть видео, я предпочитаю читать некачественные описания видео, поэтому скажите мне, о чем это все. Ну, я думал, ты никогда не спросишь. Проблема довольно проста. Возьмите картину.
Это… придется сделать. Хорошо, теперь повесь это на стену. Должно быть довольно просто, верно? Возьмите гвоздь, забейте его и прикрутите.
Прохладный. Так что же будет, если удалить ноготь?
ОК, этого следовало ожидать, я думаю. И вот в чем суть проблемы. Мы удалили один гвоздь, и картина упала на землю. Очевидно, это тривиальный вопрос с одним гвоздем. Но давайте посмотрим, что было бы, если бы у нас было два гвоздя. Как бы вы обычно повесили картину на стену с помощью двух гвоздей? Может быть, что-то вроде этого?
Ну да ладно, как видите, это не совсем работает. Нашим критериям не соответствует то, что в тот момент, когда мы удаляем хотя бы один гвоздь, картина падает. Так как еще мы могли бы осуществить это? О, как насчет того, чтобы попробовать это:
Помимо того, что это очень странный способ повесить картину, это, кажется, работает! Мы удалили ноготь и грустим, падая Лиза. Нам нравится грустная Лиза, это то, чего мы хотим. Мы также нашли красную нить, чтобы повесить вещи, это немного легче увидеть в нашем дрянном арт-проекте. Но подождите секунду. Что, если мы удалим второй гвоздь?
Ладно, блин, тогда это не сработало. Мы хотим убедиться, что удаление любого гвоздя приведет к падению картины. Не буду вас больше мучить, вот решение:
Боже, есть на что посмотреть. В основном потому, что программист пытался что-то рисовать. Мы можем видеть, что это работает для 2 ногтей. Теперь давайте поднимемся до 3… Нет, я просто шучу, вы уже поняли суть проблемы. Но самая интересная часть проблемы — это обобщение решения. Так почему же решение, которое мы выбрали, работает? Ну, есть несколько способов взглянуть на проблему. Мэтт и Стив отлично справляются с интуитивным объяснением двух из этих способов, а в их видео есть ссылки еще на несколько. Но мне понравилось объяснение Мэтта (как придурковатого товарища-математика), поэтому я сделаю здесь краткое изложение. Не стесняйтесь пропустить этот раздел, если хотите. До встречи на кодинге.
Итак, давайте посмотрим на последовательность намотки для нашего решения вокруг каждого гвоздя:
Хорошо. Здесь происходит много всего. Но если вы проследите длину веревки, на которую вы повесили картину, вы увидите, что делаете две петли вокруг каждого гвоздя — одну по часовой стрелке и одну против часовой стрелки. Назовем гвозди A и B. Скажем, если мы делаем петлю вокруг гвоздя по часовой стрелке, мы используем имя гвоздя. Если мы зациклим гвоздь против часовой стрелки, мы просто будем использовать букву с маленьким штрихом (‘) в обозначении. Итак, в нашем примере мы выбрали путь A B’ A’ B. И мы, надеюсь, должны довольно легко понять, почему удаление любого гвоздя приводит к падению изображения — скажем, вы удаляете гвоздь A. Затем наша последовательность становится B’B. А как вы думаете, что произойдет, если намотать на гвоздь кусок веревки против часовой стрелки, а затем сразу же по часовой стрелке? Попробуй. Это не держится, вы, по сути, возвращаете свою работу. Таким образом, это каскадное действие устраняет пары витков после полного удаления гвоздя. Если бы мы хотели распространить это на большее количество гвоздей, скажем, мы ввели гвоздь C, нам просто нужно изменить нашу последовательность и добавить новые витки, например: A B' A' BC B' AB A' C'. Попробуйте, если не верите мне. Имейте в виду, что любые X и X’ рядом друг с другом компенсируют друг друга. Попробуйте удалить A, B или C из приведенной выше последовательности и увидите каскадный сбой в действии.
Вот и все о проблеме и ее решении. Теперь добавляем код \o/
Реальная часть кодирования
Итак… почему я говорю об этом? Хороший вопрос. У меня есть свободное время, и я не могу так долго не программировать. Но кроме того, Мэтт и Стив задали действительно интересный вопрос — вы можете легко найти решение для любого количества гвоздей, следуя описанной выше схеме вывода, со всем обратным ходом и добавлением витков (или просто посмотрите, черт возьми, видео уже). Но каково кратчайшее решение для N, где N — количество гвоздей? В настоящее время. Теперь это похоже на задачу по информатике *угрожающе потирает руки*
Начнем с основ. Что означает кратчайший? Ну, кратчайшая длина строки — это, конечно, один из способов интерпретации. Но… это сложно по причинам, достойным отдельной статьи *подмигивает*. Как насчет минимального количества витков? Да, это звучит хорошо. Используя приведенное выше представление, это просто означает кратчайшую последовательность X и X’, которая каскадно уйдет в забвение и содержит каждый гвоздь хотя бы один раз. Таким образом, для трех гвоздей CCCB C' C' C' B' недействителен, поскольку он не включает A и не содержит ABC. потому что он не будет каскадироваться в пустую последовательность. Хорошо, последнее изменение, прежде чем мы перейдем к кодированию. Мне не хочется добавлять простые числа и учитывать их в строках. Так как насчет того, чтобы использовать заглавные и строчные буквы? Таким образом, наше решение A B’ A’ B C B’ A B A’ C’ становится A b a B C b A B a c. А, намного лучше. Ладно, давайте тоже избавимся от этого пробела, мы же программисты! "AbaBCbABac" — красиво.
Если вы запутались в этом так же, как Мона Лиза… просто потерпите меня. Я знаю, что это сложно, но все, что мы делаем, это просто описываем, как веревка наматывается на гвозди таким образом, чтобы мы могли сгенерировать и оценить на компьютере. Теперь мы знаем последовательность длины 10, которая подходит для трех гвоздей, верно? Ну, откуда мы знаем, что нет более простого? Как насчет того, чтобы проверить их всех :)
Вот суть нашего кода — мы генерируем все возможные последовательности [a, A, b, B, c, C] длиной до 9. Выберите свой яд. Мне нравится Дарт:
С возвращением в колледж (или на собеседования по программированию)! Как получить список всех комбинаторных возможностей длиной от 6 до 10 символов? Что ж, приведенное выше решение - действительно глупый способ сделать это, но оно работает. Итак, что мы получаем? Давайте попробуем пробный запуск с длиной 5.
О, парень. Это не буэно, не так ли? Мы производим много дерьма. Обматывать строку 5 раз вокруг A — это… не лучший вариант. Ни наматывать, ни разматывать его повторно. Итак, давайте внесем небольшую корректировку и избежим дублирования букв:
Хорошо, это немного лучше, я думаю. Теперь это дает нам такие кандидаты, как «AbaBc» и «caCBC», пропуская все «AaAAa» и «BBbCc”с. Хорошо, что еще мы можем просто выбросить в окно? Чем больше мы можем отфильтровать здесь, тем меньше нам нужно будет проверять позже. Что ж, если у нас нет нового предсказания проблемы, мы знаем, что нам нужен хотя бы один символ каждого типа, чтобы найти правильное решение. То есть, если мы пропустим гвоздь или обмотаем его только в одну сторону, мы можем определенно сказать, что это решение не стоит проверять. Для этого нам нужно стать немного умнее:
Хорошо, теперь мы становимся довольно серьезными. Мы даже сделали небольшую оптимизацию, чтобы избежать копирования между списками с помощью нашего тривиального решения. Очевидно, что мы больше не можем запрашивать последовательности длины 5, потому что у нас есть 6 возможных витков! Итак, давайте посмотрим, как это выглядит для 6:
Хороший! Но у нас есть еще одна маленькая вещь, о которой нужно позаботиться, прежде чем мы сможем отфильтровать столько, сколько сможем механически. Мы не совсем видим это в примере с 6, но это должно быть довольно очевидно в этой последовательности длины 9 (фактически, в каждой последовательности длины 9) — “cbcbABaC”. Вы видите это? Давайте посчитаем — вот что у нас есть: {a: 1, A: 1, b: 2, B: 1, c: 2, C: 1}. Видишь это сейчас? Если мы хотим, чтобы что-то сокращалось, у нас должно быть одинаковое количество X и x. В противном случае одно или несколько вхождений того, что мы добавили, неизбежно останется лишним. Таким образом, последнюю проверку выполнить довольно просто, учитывая, что мы отслеживаем, сколько раз мы включали каждую из них:
Со всем этим, как вы думаете, сколько последовательностей мы нашли в общей сложности длиной до 9 (мы пытаемся победить Мэтта, а не просто сравняться)? Мы можем легко это выяснить, вызвав нашу функцию и подсчитав их, и есть ровно 1968 циклических последовательностей, которые соответствуют нашим строгим критериям работоспособности. Если вы хорошенько подумаете, вы поймете, что многие из них изоморфны друг другу (имеется в виду одна и та же последовательность), но не будем вдаваться в подробности. Это уже намного лучше, чем первоначальный алгоритм «производить все». Если мы позволим этому запуститься для длины до 9, всего будет получено 12093234 последовательностей! Это сокращение числа кандидатов на 99,98 %, что сэкономит нам немало времени на финальном этапе проверки. Кстати говоря, мы можем уже перейти к изюминке? Это становится довольно долго.
Хорошо, хорошо, так как же мы проверим шансы 1968 года, чтобы доказать, что Мэтт ошибался? Мы могли бы сделать это вручную? Это было бы отстойно. Если бы только существовал способ механической проверки многих последовательностей… ПОДОЖДИТЕ МИНУТУ
Хорошо, хорошо, я слышу вас, это немного сложнее. Но в конечном счете, если вы не говорите о кодировании, все, что он делает, — это каскадирование, которое мы описали ранее. Он возьмет каждую последовательность, удалит один из символов, устранит любые соседние комбинации верхнего и нижнего регистра и проверит, не приведет ли это к пустой строке.
Я слышу, как ты там бормочешь о том, как я оттягиваю неизбежное. Хорошо, хорошо. Мы написали кучу кода, давайте запустим его. Давайте посмотрим, что произойдет, когда мы запустим его для последовательности из 9 обмоток. Мэтт, вот и мы, хе-хе. Хорошо, вот она, барабанная дробь, пожалуйста…
ЧТО?! Мы потратили все это время на то, чтобы доказать, что Мэтт ошибается, просто чтобы убедиться, что мы не можем этого сделать? И вы, вы потратили впустую все это время, читая это только для того, чтобы прийти к крайне неутешительному выводу, что A B' A' BC B' AB A' C' действительно является кратчайшей последовательностью обмоток на 3 гвоздя? Ну не так быстро.
Во-первых, откуда мы знаем, что алгоритм действительно работает? Возможно, это не самый эффективный алгоритм, но он намеренно написан в простейшей форме, которая соответствует нашим предположениям. Таким образом, если один из наших шагов фильтрации не был неправильным, алгоритм правильный. Кроме того, мы можем запустить полного зверя в DartPad с размером 10 и получить последовательность Мэтта во всех 240 прекрасных в основном изоморфных перестановках, которые она имеет. Опять же, мы не будем вдаваться в подробности, но на самом деле существует несколько классов изоморфных вариаций. Значит, мы что-то делаем правильно.
Я знаю, что математики редко бывают полностью удовлетворены этим, но здесь мы установили структуру, позволяющую исключить все, кроме очень небольшой доли всех возможных витков, и проверить все, что осталось, по отдельности с помощью алгоритма, чтобы установить, что действительно не существует более короткой последовательности, чем 10 для 3 гвоздей. И мы можем использовать то же самое, чтобы показать, что нет более короткой последовательности, чем 22 для 4 гвоздей. Хотя проверка последнего занимает удручающе много времени даже на выделенной виртуальной машине, поэтому не пытайтесь использовать DartPad. А это — это чего-то стоит. Пока кто-нибудь умнее меня не придет и не скажет: «О, очевидно, никогда не будет ничего, кроме ‹некоторой закрытой формулы для предыдущего*2+2›, потому что ‹некоторые математические факты› », это то, за что мы все можем держаться, когда вешаем наши фотографии. И в этом настоящая ценность этого упражнения. Определенно не доказывая, что Мэтт ошибался, это было похоже на приятный бонус или что-то в этом роде. *ворчит, уходя*
