Вопрос для интервью: детерминированное случайное окрашивание сетки с менее чем тремя последовательными цветами - PullRequest
0 голосов
/ 04 ноября 2019

Недавно получил этот вопрос из интервью FAANG.

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

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

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

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

Редактировать:

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

1 Ответ

0 голосов
/ 06 ноября 2019

Я получил следующий ответ в Математическом стеке :

Это кажется очень простым.

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

Всегда можно выбрать цвет для каждого узла, так какСуществует не более двух возможных триплетов, которые может завершить посещаемый в данный момент узел (с двумя узлами слева или двумя узлами над ним - остальные направления еще не окрашены), поэтому не более двух цветов с k> 2 запрещены.

...