Автор: Джоэп Шууркс (Joep Schuurkes)
Оригинал статьи
Перевод: Ольга Алифанова

Джеймс Линдси создал ряд потрясающих загадок черного ящика. Это крошечные приложения, которые подталкивают вас разобраться, что же они делают (поддержать Джеймса в создании этих загадок можно на его Patreon-страничке). У двух из этих загадок –29 and 31 – теперь есть не только интерфейс, но и API.

Это навело меня на мысль. Если исследовать загадки через графический интерфейс, то начинаешь с ввода – пробуешь различные виды ввода в надежде выявить логику вывода. Затем эта логика поощряет дальнейшее исследование.

Однако при наличии API, и из-за природы загадки 31, очень легко получить результаты для всех возможных комбинаций исходных данных. Это означает, что исследование можно начинать с результатов, а не с ввода.

Три важных замечания, прежде чем я расскажу вам, как и что я делал.

Во-первых, эта статья- спойлер решения для загадки 31, поэтому отличной идеей будет пойти и решить ее самостоятельно. Как минимум поиграйте с ней хоть чуть-чуть, чтобы понимать, что там на входе и что на выходе.

Во-вторых, несколько месяцев назад я уже решил эту загадку через графический интерфейс. Поэтому это скорее ответ на вопрос, "Могу ли я найти решение и таким способом?", а не "Могу ли я найти решение?".

И, наконец, код и таблицы, которые я создал (перелинкованные в тексте, а также доступные на GitHub), не очень-то чисты. Я думал о том, чтобы их почистить, но не сделал этого по двум причинам – во-первых, я ленив, а во-вторых, так они дают более честную картину того, что я делал.

Получение всех комбинаций для загадки 31

API загадки 31 описан здесь. Вы можете пользоваться им через браузер, добавляя параметры запроса для всех кнопок:

http://blackboxpuzzles.workroomprds.com:8002/puzzle31?buttonA1=up&buttonA2=up&buttonA3=up&buttonB1=up&buttonB2=up&buttonB3=up&buttonC1=up&buttonC2=up&buttonC3=up

Такой запрос вернет ответ {"lamp1":"on","lamp2":"off","lamp3":"off","lamp4":"off"}.

С этим разобрались. Следующий вопрос – как проверить все возможные варианты ввода через АПИ-запросы. Оказывается, в библиотеке Python – itertools – есть функция product, которая делает именно это:

product(('up', 'down'), repeat=9).

Я раньше уже посылал АПИ-запросы через Python (да здравствует библиотека запросов!). Записью данных в csv я тоже занимался. Поэтому я написал вот такой скрипт на Python, и получил вот такой csv-файл.

Ретроспективно – я бы кое-что изменил в этом скрипте. Значения “down”/”up” и “on”/”off” усложняют анализ данных. Позднее я создал другой csv-файл, заменив down/up и on/off на 0/1.

Анализ данных при помощи таблицы

Прежде чем приступить к анализу с Python (см. следующий раздел), я воспользовался для этого таблицей. Я раньше анализировал данные и манипулировал ими при помощи таблиц, и поэтому решил, что при помощи фильтров, формул, условного форматирования и, возможно, сводной таблицы, мне удастся решить загадку.

Таблицу можно найти здесь. В норме я пользуюсь Excel, но мне было любопытно, смогу ли я сделать то же самое при помощи LibreOffice Calc. Оказалось, что смогу.

Решение для лампы 1

Я начал с того, что проверил, какое количество комбинаций включит или выключит каждую лампу. Для лампы 1 таких комбинаций всего 2 – для прочих 510 комбинаций она будет выключена. Лампа 2 включается при 337 комбинациях и выключена при 175. У 3 и 4 ламп соотношение одинаковое – 169 для включения и 343 для выключения.

Эти результаты предполагают, что несмотря на четыре лампы, мы наблюдаем всего три типа поведения (ну или просто три поведения). Поэтому я проверил, а не делают ли лампы 3 и 4 одно и то же, но оказалось, что это не так. В 91 случае обе они включены, для 2*78 случаев одна включена и одна выключена, а для 265 выключены обе.

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

(скриншот сделан после того, как я добавил условное форматирование для решений ламп 3 и 4).

Эврика: лампа 1 включается, когда все кнопки или наверху, или внизу. Первая лампа решена.

Решение для ламп 3 и 4

У ламп 2, 3 и 4 множество комбинаций, включающих и выключающих их. Я добавил колонку в таблице, которая подсчитывала количество кнопок в положении "нажаты" для каждой комбинации. Она показала мне, что включение лампы 2 требует как минимум двух "включенных" кнопок ". Включение 3 или 4 лампы требовало как минимум трех "нажатых" кнопок (лампы 3 и 4 все же сильно похожи).

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

Я решил сначала разобраться с лампами 3 и 4. Изучение комбинаций ввода с минимальным количеством нажатых кнопок (три), включающих лампы, показывает явную закономерность:

Третья лампа: кнопки с одинаковым номером.

Четвертая лампа: кнопки с одинаковой буквой.

Третья лампа включается, если нажаты три кнопки с одинаковым номером. Четвертая лампа включается, если нажаты три кнопки с одинаковой буквой.

Конечно, остается вопрос, а все ли мы знаем про лампы 3 и 4. Я провел быструю визуальную проверку для лампы 4 и комбинаций, в которых нажато больше трех кнопок. Это была формальность, так как я уже решал эту загадку через интерфейс и знал, что мое решение верно.

Однако мне стоило добавить в таблицу формулу, высчитывающую состояние ламп 1, 3 и 4 на основании входных данных. А затем – другую формулу, сравнивающую эти состояния с реальными и проверяющую, правильна ли моя логика. Поэтому я добавил эти формулы для лампы 4 в таблицу на лист “puzzle31_binary”.

Решение для лампы 2

Применяя подход, схожий с лампами 3 и 4, я рассмотрел все комбинации ввода с двумя нажатыми кнопками, включающими лампу 2. Тут намечалась закономерность, связанная со средними кнопками внешних рядов и колонок. Однако эта закономерность перестала соблюдаться, когда я также рассмотрел комбинации с тремя нажатыми кнопками. Мне нужно было больше информации.

Я решил применить сводные таблицы. Это, однако, ничего мне не дало. Я крайне редко пользовался сводными таблицами что в Excel, что в LibreOffice Calc. Мне не удалось сделать сводную таблицу, делающую что-то полезное, и я вернулся к использованию фильтров, чтобы разделаться со второй лампой.

Дабы упростить задачу, я скопировал все комбинации, включающие лампу 2, на новый лист. Отфильтровав комбинации с 2 или 3 нажатыми кнопками и подсчитывая, как часто каждая из них была нажата, я увидел закономерность. Это число равнялось или 5, или 6, или 15, и только случаи с 15 играли роль в комбинациях с двумя нажатыми кнопками. Поэтому я продолжил фильтровать, оставив только комбинации с числом 15. Их две: A1-B2-C3 and A3-B2-C1.

Тут меня озарило догадкой, и я вернулся к первому результату фильтрации, удалив из него две, которые только что нашел (так появилась колонка "ручной фильтр" – "man filter"). Подсчеты оставили меня с двумя группами комбинаций – с цифрой 4 и цифрой 15. Догадка оказалась удачной.

Проделав то же самое для В1, я увидел ту же закономерность, но для А2 и С2. Это означает, что два вида комбинаций включают лампу 2: во-первых, комбинации из зависимости A2-B1|B3, а во-вторых, комбинации из зависимости A1-B2-C3.
Затем я рассмотрел все комбинации, где нажата кнопка А2. Если нажато всего две кнопки – то это или В1, или В3. А когда нажато три, то или В1, или В3 тоже непременно нажаты.

Вот и решение для лампы 2: лампы 3 и 4 – про прямые линии, а лампа 2 – про диагонали.

Анализ данных с pandas и seaborn

Для анализа данных на Python я создал Jupyter -блокнот – давно хотел с ним разобраться – который можно найти здесь (отличный рендер от GitHub, кстати говоря). Для анализа я использовал библиотеку pandas, а для визуализации - seaborn.

Визуализация комбинации при единичном вводе

Используя датафреймы pandas для репликации некоторых шагов в таблице, я решил "злоупотребить" тепловой картой seaborn с целью визуализации двух комбинаций, при которых загорается лампа 1. Это позволило мне разобраться, как создать тепловую карту, и как она будет отображаться в блокноте.

Все кнопки в положении "нажаты".

Все кнопки в положении "не нажаты".

Тепловая карта состояний ламп: первая попытка

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

Комбинации ввода, в результате которых загорается лампа 3.

Это, очевидно, ничем мне не помогло. Честно говоря, я не мог поверить своим глазам, поэтому перепроверил результат при помощи таблицы. Он подтвердился. Раздумывая об этом, я осознал, что комбинации ввода можно разделить на три группы, которые можно описать как "три кнопки с одинаковым номером нажаты и сочетаются со всеми возможными комбинациями для других кнопок". Сигнал утонул во всяком шуме.

Тепловая карта состояний ламп: вторая попытка

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

Только лампа 1: все нажаты или все не нажаты.

Только лампа 2: диагонали.

Только лампа 3: вертикали.

Только лампа 4: горизонтали.

Можно сказать, что тепловая карта лампы 2 предполагает диагональную закономерность, 3 – вертикальную, а 4 – горизонтальную. Однако это не так уж очевидно. Если бы я не знал решение заранее, то не уверен, какой вывод сделал бы из этих карт.

Тепловая карта состояний ламп: отступление

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

Погуглив, я обнаружил, что я могу использовать функцию pandas size() для результата DataFrame.groupby(), чтобы глубже понять корреляции. Как можно видеть ниже, если сгруппировать по А1-А2-А3, можно увидеть, как часто каждая уникальная комбинация А1-А2-А3 встречается в наборе данных.

Я взял набор данных, включающих только лампу 4, и сгруппировал по A1-A2-A3, A1-B1-C1 и A1-B2-C3. Первые два варианта можно увидеть ниже. Третий есть в блокноте – он очень похож на второй.

Я заметил две вещи – во-первых, результат для A1-A2-A3 следует какой-то логике, а A1-B1-C1 выглядит более случайным. Во-вторых, группа A1-A2-A3 содержит комбинации, при которых все три кнопки нажаты или не нажаты. Другие группы таких вариантов не содержат.

Тепловая карта состояний ламп: корреляция.

Чувствуя, что я на верном пути, я начал изучать документацию pandas и нашел решение: метод DataFrame.corr(). Он делает именно то, что мне нужно. Вы скармливаете ему все комбинации ввода, в результате которых включается, скажем, лампа 4, а он высчитывает корреляцию.

Результат – это таблица, где положительное число говорит о позитивной линейной корреляции (максимум 1), ноль – об отсутствии корреляции, а отрицательное число – о негативной линейной корреляции (минимум -1).

Так как мы ищем позитивную корреляцию (совместное нажатие/не нажатие на кнопки вызывает включение лампы 4), эта таблица позволяет найти решение для четвертой лампы. Все с положительным числом – часть закономерности для лампы 4.

Эта закономерность еще выпуклее на тепловой карте:

Тепловая карта корреляции ввода для лампы 4.

Так как мне было любопытно, я проделал то же самое для набора комбинаций, при которых включалась только лампа 4 и никакие другие. Интересно отметить, что закономерность все еще видна, но выглядит менее явной. Нам нужен полный набор, включающий то, что я ранее назвал "шумом", для правильного подсчета корреляции.

Тепловая карта для корреляции комбинаций, при которых включается только лампа 4.

Теперь давайте посмотрим на три другие тепловые карты. Карта для лампы 3 показывает явную закономерность, похожую на лампу 4.

Тепловая карта корреляции комбинаций для лампы 3.

Тепловая карта корреляции для лампы 1 показывает явную закономерность, хоть и выглядит странновато из-за логики поведения: все кнопки или включены, или выключены.

Тепловая карта корреляции комбинаций для лампы 1.

И, наконец, тепловая карта лампы 2 показывает довольно явную закономерность, однако она не такая четкая, как в случаях с лампами 3 и 4.

Тепловая карта корреляции комбинаций для лампы 2.

Мне приходят в голову две причины того, что здесь закономерность не настолько очевидна:

Во-первых, в данных две закономерности: диагонали двух нажатых кнопок и трех нажатых кнопок. Добавьте к этому различные состояния остальных кнопок, и получите большое количество шума.

Во-вторых, некоторые корреляции в закономерности двух нажатых кнопок взаимоисключающи. Это можно увидеть на тепловой карте, показывающей корреляцию между комбинациями с максимум двумя нажатыми кнопками, включающими лампу 2:

Тепловая карта корреляции комбинаций для лампы 2 – две нажатых кнопки (рендер matplotlib).

Не думаю, что эта тепловая карта – валидный способ использования коэффициентов корреляции (из-за ограниченного набора данных), однако она все же что-то говорит нам о поведении лампы 2.

Итак, вот и все: загадка 31 решена при помощи анализа данных через Python.

Заключение

Так как не все инструменты, которыми я пользовался, были мне знакомы, то такое решение загадки заняло много времени – буквально часы. В следующий раз я сделаю это быстрее, но поиск решения через интерфейс занимает 5-10 минут.

Мне было очень весело разбираться в том, как заставить инструменты делать то, что мне нужно. Спасибо всем тем прекрасным людям, которые их сделали!

Мне еще многому нужно научиться, чтобы хорошо проводить анализ данных. К примеру, видя положительные числа в корреляционных таблицах, я вскричал "Загадка решена!" Только когда я приступил к этой статье, я глубже вник в то, что эти числа на самом деле значат.

Не недооценивайте мощь таблиц. Как сказала Фелиенн Херманс в докладе “How to teach programming and other things?” (отличный доклад, посмотрите его, когда закончите читать статью) в 5:25:

"Excel – изумительный язык программирования, который позволяет "нормальным людям" программировать в различных областях финансов. И это стало девизом моей диссертации – "Таблицы – это код". Таблицы – валидное средство программирования".

В этом ключе было интересно отметить, что блокнот Jupyter – это в основном таблица на стероидах.

Решать загадку через Python оказалось не так забавно, как я ожидал. У меня не было чувства "эврика!", когда я видел, как тепловые карты корреляции дают мне решение. Да, это был конец тяжелого дня, и я знал решение заранее, но все же.

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

Если бы я не знал интерфейс и решение, то, думаю, мы увидели бы более четкую разницу между моим подходом через анализ данных, и решением через интерфейс. Вместо ментального представления 9 кнопок в таблице 3х3 и 4 ламп, у меня были бы только данные. 512 комбинаций 9 бинарных переменных и 4 бинарных результата. Я бы нашел закономерности в данных, а затем… А затем не уверен. Посмотрел бы в интерфейс, чтобы увидеть, к чему относятся данные?

Думаю, есть только один способ проверить это – когда Джеймс Линдси выпустит новую загадку черного ящика с АПИ, я начну с АПИ.

Обсудить в форуме