Находим случайный seed, решающий задачу с LeetCode

У меня есть хобби — решать задачи LeetCode непредназначенным для этого образом, часто при помощи запутанных однострочников. Такие самостоятельно накладываемые ограничения делают задачки интереснее и заставляют искать нестандартные решения.

Одним из ежедневных челленджей LeetCode была такая задача (я немного упростил её для понятности):

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

Например, если у нас есть список "010", "110", "111", то возможным решением будет "001". Задача с LeetCode имеет большой набор тестов — 183 тестовых сценариев с , а точную формулировку задачи можно найти здесь.

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

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        random.seed((69299878 + sum(ord(c)*(i*j+111) for (i, n) in enumerate(nums) for (j, c) in enumerate(n))) % 999999999)
        return ''.join(random.choice('01') for _ in nums)

Можете попробовать это решение самостоятельно (оно должно работать, если LeetCode не обновил свой набор тестов. Если это произошло, сообщите мне об этом).

Ниже я расскажу, как это сделал.

▍ Введение

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

def find_new_string_cantor(bitstrings):
    return ''.join('0' if n[i] == '1' else '1' for (i, n) in enumerate(bitstrings))

Что касается случайной генерации, то первым делом стоит разобраться, как же я понял, что это вообще возможно? Да, шансы случайно получать правильно каждый ответ настолько малы, что мне никогда бы не удалось найти решение, LeetCode забанил бы меня раньше за слишком большое количество повторяющихся отправленных ответов. Подобное решение задачи похоже на бросание 183 монет «с перекосом» и получение в результате 183 орлов. Вероятность этого для обычной монеты равна . К счастью для нас, в этом предложении очень важно слово перекос, благодаря которому шансы в реалистичном наборе тестов гораздо выше.

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

А для каждого существует способов выбора строк битов. При больших это число растёт очень быстро, но для меньших с ним работать чуть удобнее. Например, при существует всего возможных входных значений. Так как вероятность случайной генерации валидного ответа для входного равна , случайный выбор строки битов для каждого из входных значений длиной подойдёт в 1 из 64 случаев.

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

Это понимание вероятности случайного решения больших наборов тестов придало мне уверенности в том, что подходящий seed можно найти за разумное время.

▍ Реализация

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

Первой попыткой создания seed из входных данных стало использование встроенной hash языка Python для отображения входных данных в скаляр, например, sum(hash(b) for b in bitstrings). Однако в Python3 хэширование не является детерминированным и меняется после перезапуска интерпретатора, поэтому мне пришлось придумывать другую хэш-функцию, которая точно будет детерминированной. К счастью, в данном случае качество хэша было не так важно, поэтому я выбрал простую функцию, которая формирует хэш, вычисляя значение из символов каждой строки битов и их позиции в массиве: sum(ord(c)*j*i for (i, b) in enumerate(bitstrings) for (j, c) in enumerate(b)).

Документация по случайному seed в Python была довольно туманной, а поскольку я не знаю точных подробностей seed, но уверен, что он получает как минимум 32-битный seed, я выбрал деление с остатком на , что меньше , но всё равно достаточно велико для нахождения валидного seed.

Моя уверенность в достаточной величине этого делителя для высокой вероятности нахождения валидного seed была вызвана следующей эвристикой: я был достаточно уверен в том, что все возможные случаи и большое количество случаев будет присутствовать в наборе тестов, а затем я понял, что они просто будут случайно заполняться тестовыми сценариями с бОльшими значениями . Так как я знал вероятности случайного прохождения любого заданного тестового сценария, то просто вычислил вероятность случайного прохождения набора тестов из 183 тестов случайного размера, как описано выше. Оказалось, что она имеет , то есть следует ожидать, что в интервале можно найти примерно 30 подходящих seed.

Затем я внёс небольшое изменение в общую хэш-функцию: добавил дополнительный член + 111, чтобы гарантировать, что она никогда не вернёт 0 ни для одной части входных данных. Теоретически, это нужно было для предотвращения коллизий (в противном случае первая строка битов целиком и первый бит других строк битов игнорировались бы), но выяснилось, что на самом деле это не особо помогает. И что есть некоторые простые случаи, которых можно было избежать.

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

В конечном итоге у меня получилось следующее:

def find_new_string(bitstrings, seed_value):
    random.seed((seed_value + sum(ord(c)*(i*j+111) for (i, n) in enumerate(nums) for (j, c) in enumerate(n))) % 999999999)
    return ''.join(random.choice('01') for _ in nums)

Я собрал набор тестовых сценариев и выполнил следующий скрипт:

good_seeds = []
for i in range(100_000_000):
    if all(find_new_string(bitstrings, i) not in bitstrings for bitstrings in test_suite): good_seeds.append(i)

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

Думаю, этот поиск можно было ускорить множеством разных способов. Основной способ заключается в том, что я практически уверен в наличии дубликатов в наборе тестов, только в перестановленном порядке (например, ["00", "11"] и ["11", "00"]). Такие входные данные для seed хэшировались в разные значения, усложняя задачу (особенно если было малым). Сортировка перед применением хэша решила бы эту проблему. Кроме того, я думаю, что можно было использовать хэш-функцию получше. Например, seed Python, похоже, может получать на входе строку, поэтому я бы мог отправлять хэш-функции в качестве seed конкатенацию всех строк битов. Думаю, это могло быть самым серьёзным препятствием к решению этой задачи, ведь в интервале, который я использовал для хэш-функции, мы ожидали примерно тридцать значений; любые коллизии хэшей могли запросто привести к тому, что мы бы не нашли валидных seed, если бы не увеличили делитель.