О коровах и быках
О, «Медуза» вспомнила одну из любимых игрушек моего детства — «Коровы и быки» (или «Быки и коровы»). Она была стандартным «поездным» развлечением по пути на какой-нибудь юг: благо, ничего, кроме ручки и бумаги для игры не требуются, да и правила простые. Каждый загадывает по четырёхзначному числу без повторяющихся цифр, потом по очереди пытается угадать число соперника. В ответ на догадку соперник сообщает число «быков» — угаданных цифр, которые стоят на своём месте, и «коров» — угаданных цифр, стоящих не на своём месте. Например, если загадано 1234, а догадкой было 1345, то 1 — это бык, 3 и 4 — коровы, и в ответ услышишь «один бык две коровы». Опираясь на эту информацию, нужно сделать новый ход (предложить новую догадку) и так далее, пока не получишь наконец «четырёх быков» (полностью угаданное число). Задача парной игры: угадать число соперника быстрее, чем он угадает твоё. (Понятно, что на самом деле «парность» здесь условная: это просто две параллельные игры, в которых вы и соперник меняетесь ролями — ну, скорее похоже на бег, чем на теннис: от твоих действий никак не зависит, когда соперник придёт к финишу — можно только пытаться его обогнать.)
Компьютерная реализация этой игры пришла вместе с моим первым компьютером — Апогеем БК-01: он загружал программы с аудиомагнитофона, так что вместо имён файлов там были звуковые метки, и мои уши до сих пор помнят, как звучит эта фраза «Коровы и быки» в исполнении неизвестного женского (кажется, несколько пожилого) голоса, после которого на кассете — приятное жужжание, которое компьютер превращал в код. Это была готовая программа и она не умела играть сама, умела только загадывать число и отвечать пользовователю, который пытался его угадать (ну вот примерно как медузовский скрипт делает).
Мне, конечно, хотелось написать такую программу, которая бы умела сама угадывать числа, но поначалу эта задача казалась сложной — когда ты играешь, то применяешь какую-то нетривиальную логику типа «а вот если цифра один тут бык, то двойка тогда точно корова, но тогда она стоит не на втором и не на третьем месте, а первое уже занято — ну, значит, единица не бык, а значит…» и так далее. В общем, до боли знакомые рассуждения для всех любителей логических задач. Но как же их запрограммировать? Это прямо искусственный интеллект надо писать!
Возможно, придись моё детство на сегодняшнее время, я бы сказал
да ерунда, сейчас забабахаем глубокую рекуррентную нейросеть на миллион нейронов на Tensorflow, запустим на тысяче GPU, заставим её сыграть миллиард партий против самой себя и получится чемпион по «Коровам и быкам» — не хуже Alpha Go!
но тогда, к сожалению (или к счастью) таких возможностей не было.
И вот однажды — я, кажется, даже не думал об этом особенно — мне в голову пришёл алгоритм игры, который показался мне оптимальным. Он очень простой. На каждом шаге у нас есть некоторая история игры — информация о предыдущих (своих) ходах и их результатах. Изначально эта история пустая. Рассмотрим теперь какое-нибудь из допустимых чисел — то есть таких, которые в принципе могут участвовать в игре (в данном случае: четырёхзначные, без повторяющихся цифр). Глядя на текущую историю, зададим такой вопрос: может ли это число быть тем самым, которое загадано? Даст ли оно те же реакции на наши предыдущие ходы, которые мы действительно получили? Если да, то такое число мы назовём совместимым с историей, иначе — несовместимым. В начальный момент, когда история пустая, любое число является совместимым (проверять нечего). По ходу игры история растёт, а множество совместимых чисел уменьшается. Идея состояла в том, чтобы просто каждый раз называть какое-нибудь число, совместимое со всей предыдущей историей — то есть то, которое по крайней мере теоретически может быть верным ответом.
Идея очень простая, и её реализация оказалась тоже несложной. Действительно: компьютеры плохо умеют думать (по правде говоря, вообще никак), но зато хорошо считают и перебирают. Не нужно реализовывать никакую сложную логику на тему «а если бы эта цифра стояла здесь…» — достаточно просто перебирать все возможные допустимые числа и для каждого из них отвечать на вопрос «какая реакция была бы дана на такую-то догадку, если бы это число было загаданным?»
На удивление этот алгоритм даёт довольно неплохой результат. Я уже не помню, на каком языке написал его впервые, но сейчас мы используем Python — на нём он выглядит особенно изящно. Итак.
Давайте это запрограммируем!¶
Первое, что нам понадобится — это множество допустимых чисел. По правде говоря, в «коровых и быках» числа не имеют собственно числовой природы, а являются просто цепочками знаков, поэтому мы будем использовать строки вместо настоящих чисел. Чтобы создать нужный набор строк, проще всего использовать функцию itertools.product, находящую декартово произведение списков или других похожих на них объектов.
from itertools import product
everything = ["".join(x) for x in product('0123456789', repeat=4)
if len(set(x)) == len(x)]
Здесь сразу несколько хитростей, заслуживающих отдельного рассказа: строка '0123456789' в данном случае рассматривается как последовательность символов (в этом контексте она эквивалентна ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']), функция product создаёт список (ну хорошо, не список, а итератор), состоящий из всевозможных кортежей типа ('0', '1', '2', '7'), чтобы склеить их в строки мы применяем "".join() (можно было бы этого не делать и работать с кортежами, но так они приятнее выглядят). Условие о том, чтобы в числе не было повторяющихся цифр, записано в виде len(set(x)) == len(x) — то есть элементов во множестве, созданном из элементов x (то есть цифр очередного нашего числа) должно быть столько же, сколько элементов в самом x (в множествах не бывает повторяющихся элементов, поэтому это самый простой способ проверить то, что нам нужно).
Теперь напишем функцию, которая будет возвращать число быков и коров.
def bulls_n_cows(a, b):
assert a in everything and b in everything
bulls = sum(1 for x, y in zip(a, b) if x == y)
cows = len(set(a) & set(b)) - bulls
return bulls, cows
Функция симметричная (если мы поменяем аргументы местами, ответ не изменится), поэтому я не стал называть аргументы guess и answer — здесь эти детали ни к чему. В начале стоит assert, проверяющий, что функция получила на вход только допустимые числа. В принципе, эту строчку можно будет потом убрать — она нужна, чтобы убедиться, что мы нигде не ошиблись и не пытаемся скормить этой функции что-нибудь не то. (Лучше сразу получить ошибку, чем ломать голову над странным результатом.)
Хочется обратить внимание на строку, находящую число коров — она использует множества и выглядит очень изящно, правда? Фактически, тут просто написано: коровы — эти те цифры, которые встречаются в обоих числах и не являются быками.
Теперь нам нужно договориться, как мы будем хранить историю. Предлагаю хранить её в списке, состоящем из трёхэлементных кортежей: (догадка, быки, коровы). Например, [(1234, 0, 1), (2567, 2, 0)]. Теперь мы можем написать функцию, проверяющую, является ли новая догадка совместимой с историей.
def is_compatible(guess, history):
return all(bulls_n_cows(guess, previous_guess) == (bulls, cows)
for previous_guess, bulls, cows in history)
Здесь используется функция all, проверяющая, что все условия из некоторого списка (ну хорошо, не списка, а итератора) выполняются. Ещё раз хочу восхититься тем фактом, что единственная строчка этой функции является просто описанием нашей цели: «проверить все условия о равенстве расчётных коров и быков реально полученным для всех записей из истории». За это мы любим Python: зачастую он позволяет писать программы в стиле «что мы хотим получить», а не «какие шаги нужно сделать, чтобы получить то, что мы хотим получить».
Всё готово к игре!¶
Для простоты заставим компьютер играть сам с собой.
from random import choice
# эта функция нам понадобится, чтобы выбирать случайные элементы
from random import seed
seed(43)
# для воспроизводимости
from itertools import count
# это бесконечный счётчик
def naive_player(answer, verbose=True):
if verbose:
print("My real answer is {}, but let's "
"pretend I don't know it.".format(
answer))
guess_space = set(everything)
# это множество, из которого мы будем выбирать догадки
# и вычёркивать уже выбранные или не подходящие
history = []
# в начальный момент история пуста
for attempt in count(1):
while True:
guess = choice(list(guess_space))
guess_space.remove(guess)
# больше мы уже никогда выбирать это число не будем
if is_compatible(guess, history):
# если совместимо с историей, выбрать его
break
bulls, cows = bulls_n_cows(guess, answer)
history.append((guess, bulls, cows))
if verbose:
print("Attempt {}. My guess is {}. I have {} bull(s) "
"and {} cow(s)".format(
attempt, guess, bulls, cows))
if bulls == len(guess):
if verbose:
print("I won! (Surprise!)")
break
return history
naive_player(choice(everything));
Выглядит неплохо! (Хотя, наверное, компьютеру просто повезло…)
Но так ли уж хорош наш алгоритм?¶
По правде говоря, не факт. Он не делает совсем глупых шагов — не пытается использовать в качестве догадки то, что заведомо не может быть ответом. Но является ли это оптимальной стратегией? Приводит ли она к самой быстрой победе?
Например, когда я играю в «коровы и быки» сам, мои первые два хода обычно — это 1234 и 5678. Я не уверен, что они оптимальны, но мне кажется, что так я получаю сразу много информации о всех цифрах — такой «широкий» выстрел. При этом если в 1234 есть хотя бы один бык или хотя бы одна корова, 5678 не может быть правильным ответом: в моём случае это не попыта угадать ответ, а попытка получить больше информации о нём.
О! А ведь это идея! Может быть, правильная стратегия — выбирать такие числа, которые каждый раз приносят максимум информации об ответе? Только вот что это значит? Как измерить количество информации?
В данном случае очень просто: чем больше у нас информации, тем меньше пространство поиска правильного ответа, то есть множество совместимых чисел. Разные попытки приносят разное количество информации, то есть по-разному сужают это множество. Например, если я просто продублирую одну из попыток, на которую уже получил реакцию раньше, это не даст никакой новой информации. Для тех чисел, которые не фигурировали в игре раньше, разные реакции дают разное количество информации: например, «0 коров 0 быков» позволяет сразу вычеркнуть четыре цифры, а какие-нибудь «1 бык 1 корова» может заставить повозиться.
Как же можно понять, сколько информации принесёт тот или иной ход, если мы не знаем, какая на него последует реакция? Мы не можем найти этого точно, но можем оценить, пользуясь соображениями терии вероятностей.
Допустим, мы сыграли несколько ходов и теперь имеем какую-то историю. Единственное, что мы знаем в этот момент наверняка: правильный ответ является каким-то из чисел, совместимых с этой историей. Если у нас нет каких-то априорных сведений о том, как загадывалось число (если бы мы играли против хорошого знакомого человека, то могли бы использовать какие-то знания о нём — например, набор любимых цифр или комбинаций — но сейчас мы считаем, что таких данных у нас нет), с нашей точки зрения, все совместимые числа имеют равные шансы оказаться ответом.
Пусть теперь нас интересует, сколько информации нам принесёт ход $x$. Мы сейчас не требуем, чтобы $x$ обязательно был совместим с историей. Зафиксируем теперь какой-нибудь предполагаемый ответ $y$ — вот его нужно выбрать только среди допустимых чисел. Найдём, сколько коров и быков мы бы получили в резульатате хода $x$ при условии, что правильным ответом был бы $y$. Добавим дополнительную запись в историю, соответствующую этому (воображаемому) результату, после чего найдём новое (воображаемое) множество совместимых чисел. Чем оно меньше, тем лучше.
Конечно, здесь есть одно но. Какой всё-таки $y$ брать? Поскольку мы не знаем, какой, и все элементы совместимного множества равновероятны в качестве кандидата на правильный ответ, нам нужно повторить эту процедуру для всех таких чисел (в качестве $y$'ов), для каждого посчитать размер нового множества совместимых чисел, а потом найти среднее из этих размеров. Так мы получим величину, которую я предлагаю назвать «ожидаемым размером нового совместимого множества». Она покажет нам, насколько «в среднем» хорош наш ход: нам останется только выбрать такой $x$, чтобы эта величина была минимальной. В этом состоит наш новый алгоритм игры.
Займёмся реализацией!¶
Для начала напишем функцию, которая находит всё множество совместимых чисел (до сих пор нам требовались только отдельные числа из него, а теперь нужно оно целиком).
def compatible_area(history, old_compatible_area=None):
if old_compatible_area is None:
old_compatible_area = everything
return [guess for guess in old_compatible_area
if is_compatible(guess, history)]
Мы будем применять эту функцию несколько раз, по мере совершения новых шагов (настоящих или воображаемых), и хотим её немного оптимизировать: если на прошлом шаге у нас была какая-то история и мы уже вычилили для неё совместимое множество, то на следующем шаге можно проверять не все элементы, а только те, которые были в совместимом множестве в прошлый раз. Отсюда аргумент old_compatible_area.
Теперь напишем функцию для вычисления ожидаемого размера нового совместимого множества. Она будет чуть сложнее, но её код полностью следует описанию выше.
def expected_new_compatible_area(guess, history):
current_compatible_area = compatible_area(history)
new_compatible_area_lengths = []
# будем сохранять сюда размеры совместимых множеств,
# которые будут получаться по ходу, для
# последующего усреднения
new_history = history + [None]
# добавим пустой элемент в историю
for answer in current_compatible_area:
# перебираем все элементы из старого совместимого множества
new_history[-1] = (guess, *bulls_n_cows(guess, answer))
# добавили новый элемент в историю
new_compatible_area_lengths.append(
len(compatible_area(new_history,
current_compatible_area)))
# посчитали новый размер совместимой области
return (sum(new_compatible_area_lengths) /
len(new_compatible_area_lengths))
Посмотрим, как это работает на какой-нибудь вымышленной истории.
expected_new_compatible_area('1567', [('1234', 1, 1)])
М-у-у-у¶
Мне пришлось подождать примерно полминуты пока выполнялась эта ячейка! К сожалению, нам нужно делать многократный полный перебор по всем элементам текущей совместимой области, а на начальных шагах она очень большая. Пожалуй, нет никаких шансов использовать его для выбора наилучшего хода: нам пришлось бы запускать эту функцию столько раз, сколько всего есть допустимых чисел (не обязательно даже совместимых с историей!), то есть очень-очень много раз.
Однако, мы можем упростить игру, чтобы сократить перебор и на этой упрощённой версии изучить, насколько новый алгоритм лучше старого. Будем теперь играть трёхзначными числами, в которых нет цифр 8, 9 и 0. Нам придётся переопределить переменную everything.
everything = ["".join(x) for x in product('1234567', repeat=3)
if len(set(x)) == len(x)]
Я хочу ответить на два вопроса:
- Правда ли, что совместимые с историей числа всегда дают больше информации, чем несовместимые?
- Правда ли, что на самом деле всё равно, какое совместимое число брать — все они дают одинаковое количество информации?
Если ответы на оба вопроса положительны, то наш исходный алгоритм не хуже нового. Если нет — надо дальше смотреть.
import pandas as pd
# я хочу таблички и графики, поэтому использую
# пакет pandas
import numpy as np
Пусть мы сделали один ход и пытаемся найти следующий. Посмотрим, как зависит количество информации от выбранного хода.
def enca_stats_first_turn(answer, first_guess):
df = pd.DataFrame(index=everything)
df['in_compatible_area'] = np.nan
# в этом столбце будет храниться информация
# о том, находится ли данное число в
# совместимом множестве
df['expected_new_compatible_area'] = np.nan
# а сюда запишем ожидаемый
# размер нового совместимого множества
history = [(first_guess, *bulls_n_cows(first_guess, answer))]
current_compatible_area = compatible_area(history)
for guess in everything:
df.loc[guess, 'in_compatible_area'] = str(
guess in current_compatible_area)
# для правильной работы
# библиотеки построения графиков
# приходится конвертировать
# булевские значения в строковые
df.loc[guess, 'expected_new_compatible_area'] = \
expected_new_compatible_area(guess, history)
return df
df = enca_stats_first_turn('126', '213')
%matplotlib inline
df.boxplot(by='in_compatible_area')
Здесь нарисованы ящики с усами. Из картинки видно, что разброс размера нового совместимого множества по попыткам, совместимым со старой историей, гораздо меньше, чем среди не совместимых, но всё же есть. То есть не все совместимые попытки одинаково полезны, и ответ на второй вопрос «нет».
Что насчёт первого вопроса? Из картинки не видно, где меньше минимум, поэтому мы его просто найдём.
df.groupby('in_compatible_area').min()
Похоже, что в этом случае минимум достигается всё-таки в совместимой зоне. Но будет ли так всегда? Попробуем другие стартовые данные.
df = enca_stats_first_turn('126', '123')
df.groupby('in_compatible_area').min()
Хо-хо! Представьте себе: вы играете 123, получаете «двух быков» — что нужно делать дальше? Наверняка попробуете заменить одну из цифр, а две другие оставить на месте. А вот и неправильно: оптимальный алгоритм (с точки зрения сокращения пространства поисков на текущем шаге) советует поступать совсем иначе:
df.expected_new_compatible_area.argmin()
Ход 134 (и не только он) сделает так, что в среднем после него вам предстоит угадывать из двух с половиной чисел, а любой ход из совместимого множества оставит вас разбираться с 4.16 чисел (в среднем — поэтому числа дробные).
df[df.in_compatible_area=="True"]
Можно проверить, почему так происходит.
def simulate_history(answer, guesses):
return [(guess, *bulls_n_cows(guess, answer))
for guess in guesses]
for probable_answer in df[df.in_compatible_area=="True"].index:
print(probable_answer,
compatible_area(
simulate_history(probable_answer, ['123', '124'])))
for probable_answer in df[df.in_compatible_area=="True"].index:
print(probable_answer,
compatible_area(
simulate_history(probable_answer, ['123', '134'])))
Действительно, для разных допустимых ответов ход 134 позволяет сократить множество поисков в среднем более эффективно. Удивительно, но факт!
Итак, ответ на первый вопрос выше: тоже нет, существуют числа, не совместимые с историей, которые приносят больше информации, чем совместимые.
Кто победит?¶
Пожалуй, уже нет никаких шансов на то, что мой первый наивный алгоритм, придуманный в старшей школе, является оптимальным. Тем не менее, было бы интересно сравнить его с более продвинутым алгоритмом, основанном на поиске наиболее информативного хода.
Чтобы понять, какой из алгоритмов лучше, нам придётся заставить их много-много раз сыграть, и посмотреть, какой в среднем быстрее приходит к победе.
def bulls_n_cows(a, b):
# assert a in everything and b in everything
# закомментировали assert, чтобы быстрее было
bulls = sum(1 for x, y in zip(a, b) if x == y)
cows = len(set(a) & set(b)) - bulls
return bulls, cows
def optimal_information_player(answer, max_iterations=100):
guess = choice(everything)
history = simulate_history(answer, [guess])
if history[-1][1] == len(guess):
return history
for attempt in range(2, max_iterations + 2):
current_compatible_area = compatible_area(history)
if len(current_compatible_area) == 1:
# если остаётся только одно совместимое число, то
# его и надо выбирать
# иначе мы рискуем играть очень долго:
# любые другие ходы столь же хороши
# с точки зрения нашего критерия
# потому что уменьшать совместимое
# множество уже некуда
guess = current_compatible_area[0]
else:
guess = min((expected_new_compatible_area(g, history),
g)
for g in everything)[1]
history.append((guess, *bulls_n_cows(answer, guess)))
if history[-1][1] == len(guess):
break
return history
optimal_information_player('543')
Сыграем 200 игр. Будем выбирать случайный ответ и посмотрим, за сколько шагов optimal_information_player приходит к победе.
from random import sample
results = [len(optimal_information_player(x))
for x in sample(everything, 200)]
Найдём среднее число шагов.
np.mean(results)
Сделаем то же самое с алгоритмом naive_player. Он работает гораздо быстрее, поэтому мы можем сыграть больше игр и получить более точный результат.
results_naive = [len(naive_player(x, verbose=False))
for x in everything*100]
np.mean(results_naive)
Ого! Наивный игрок играет лучше! Но может быть это просто случайность? Проверим t-тестом.
from scipy.stats import ttest_ind
ttest_ind(results, results_naive, equal_var=False)
Нет, не похоже на случайность. Видимо, действительно, стратегия «выбирай случайный совместимый ход» оказывается лучше, чем «минимизируй новое совместимое множество».
Почему такое может быть? Возможно, дело в том, что если оптимальный с точки зрения новой стратегии ход оказывается вне совместимого множества, выбирая его, мы лишаешь себя шанса угадать правильный ответ «прямо сейчас». Вероятно, в начале игры, когда шансы малы, это не так важно, но ближе к концу может оказать решающее влияние. Собственно, в первой версии optimal_information_player, которую я написал, был забавный баг на эту тему: программа «сходила с ума», если в какой-то момент в совместимом множестве оставался лишь один элемент. То есть когда мы могли однозначно указать загаданное число, глядя на историю, хотя оно ещё не было названо. В этом случае любой дополнительный ход никак не мог изменить совместимое множество (уменьшить его уже было нельзя) и с точки зрения нашего информационного критерия все ходы были одинаково хорошими. Вместо того, чтобы просто назвать то число, которое однозначно восстанавливалось по истории, программа называла любое другое число. В текущей версии алгоритма этот случай обработан явно, но он показывает, что бывают ситуации, когда информационный критерий работает плохо.
Можно «скрестить ужа с ежом» и сделать алгоритм, который каждый раз выбирает лучший с точки зрения информационного критерия ход, но только среди элементов совместимого множества. Он совсем немного отличается от optimal_information_player.
def optimal_information_compatible_player(answer,
max_iterations=100):
guess = choice(everything)
history = simulate_history(answer, [guess])
if history[-1][1] == len(guess):
return history
for attempt in range(2, max_iterations + 2):
current_compatible_area = compatible_area(history)
guess = min((expected_new_compatible_area(g, history), g)
for g in current_compatible_area)[1]
history.append((guess, *bulls_n_cows(answer, guess)))
if history[-1][1] == len(guess):
break
return history
Чтобы уловить разницу в результатах (если она есть), нам потребуется сделать много испытаний. Я поставил следующую ячейку считаться и пошёл спать.
results_inf_comp = [len(optimal_information_compatible_player(x))
for x in everything*10]
# это будет долго считаться
Доброе утро. Итак, что мы имеем?
np.mean(results_inf_comp)
Похоже, что новый алгоритм всё-таки получше будет. Но не случайность ли это?
ttest_ind(results_naive, results_inf_comp)
Нет! Новый алгоритм всё-таки самую малость, но лучше «наивного»! Ура!
Мы выяснили, что если проучиться математике 8 лет, защитить диссертацию и стать преподавателем, то можно улучшить алгоритм, написанный в старшей школе — на целых 1.5%! :)
Немножко трёхмерных картинок¶
Мне захотелось посмотреть, как выглядят те самые совместимые множества на разных этапах. Наша упрощённая версия игры для этого неплохо подходит: фактически, она состоит из целочисленных векторов в трёхмерном пространстве (поскольку цифры три) и можно их визуализировать с помощью трёхмерных картинок.
from plotly.offline import init_notebook_mode, iplot
from plotly.graph_objs import Scatter3d
init_notebook_mode()
Вот так выглядит всё пространство возможных ходов в этой игре (можете покрутить).
x, y, z = zip(*((map(int, v)) for v in everything))
iplot([Scatter3d(x=x, y=y, z=z, mode='markers')])
Я хочу раскрасить шарики в разные цвета в зависимости от того, на каком шаге соответствующее число выбывает из списка «подозреваемых» (то есть перестаёт быть совместимым с историей).
history = naive_player('253')
history
def get_color(guess, history):
for i in range(len(history)):
if guess not in compatible_area(history[:i+1]):
break
return i
colors = [get_color(x, history) for x in everything]
Получается вот такая картинка: чем темнее точка, тем дольше она считается «подозреваемой».
iplot([Scatter3d(x=x, y=y, z=z, mode='markers', marker=dict(color=colors))])
Как мы видим, структура этих множеств достаточно сложна и трёхмерная визуализация не очень удобная (к тому же, не обобщается на более сложные случаи). Может быть, кто-нибудь придумает более удачную визуализацию? (Я пробовал разные версии MDS и даже новомодную t-SNE, но как-то без особого успеха.)
Вместо заключения¶
Если верить английской Википедии, ссылающейся на этот сайт и эту китайскую статью, классическая версия «Коров и быков» имеет полное оптимальное решение (последняя ссылка мне кажется сомнительной). Русская Википедия рассказывает, что Дональд Кнут (создатель TeX'а) предложил оптимальный алгоритм для игры в Mastermind (вариация «Коров и быков», в которой цифры могут повторяться, но всего их меньше). Доказательство оптимальности этих алгоритмов, насколько я понимаю, существенно опирается на конкретные правила: они плохо обобщаются на случай чисел произвольной длины и с произвольным алфавитом. Те алгоритмы, которые мы обсудили в этом посте, наоборот, обобщаются хорошо (по крайней мере, теоретически). Хотя, по всей видимости, не являются оптимальными.
По мере подготовки этого поста я много раз сталкивался с неожиданными результатами. Оказывается, этот сюжет далеко не исчерпан. Если в знаете ещё что-нибудь интересное про «Быков и коров» — пишите в комментариях!
Комментарии