Проверка действительности пирамиды домино

Question

Я наткнулся на этот вопрос в интервью по кодированию и не смог найти хорошее решение.

Вам дано 6 домино. Домино имеет 2 половинки каждая с количеством пятен. Вы строите 3-х уровневую пирамиду из домино. На нижнем уровне есть 3 домино, на среднем уровне - 2, а на верхнем - 1.

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

         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

Пирамида должна быть установлена ​​таким образом, чтобы количество пятен на каждой половине домино было таким же, как число на половине под ней. Это не относится к соседним домино на одном уровне.

Можно ли построить пирамиду из 6 домино в порядке, описанном выше? Домино можно свободно расставлять и вращать.

Напишите функцию, которая принимает массив из 12 дюймов (например, arr [0], arr [1] - первое домино, arr [2], arr [3] - второе домино и т. Д.) И возвращает " ДА "или" НЕТ ", если возможно или нет создать пирамиду с данными 6 домино.

Спасибо.

Answer 1

Мы можем сформулировать рекурсивное решение:

valid_row:
  if row_index < N - 1:
    copy of row must exist two rows below
  if row_index > 2:
    matching left and right must exist
    on the row above, around a center
    of size N - 3, together forming
    a valid_row
  if row_index == N - 1:
    additional matching below must
    exist for the last number on each side

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

Answer 2

Прежде чем я начну ... В этом вопросе есть двусмысленность, которая может заключаться в том, что интервьюер был более заинтересован, чем ответ. Это может показаться вопросом вопроса о способе проверки одного конкретного расположения значений, за исключением бита, который говорит «Возможно ли построить пирамиду из 6 домино в описанном порядке выше? Домино можно свободно размещать и вращать. ", что означает, что они могут попросить вас также перемещать домино, чтобы найти решение. Я собираюсь игнорировать это и придерживаться простой проверки того, является ли это действительным соглашением. (Если требуется , я бы разбил массив на пары, а затем перебил все возможные варианты для этого кода, чтобы найти первый действительный код.)

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

В основном проверьте, что каждая строка дублируется в строке ниже (смещение на единицу), и остановитесь, когда вы достигнете последней строки.

Алгоритм отключается, как только обнаруживает ошибку. Этот алгоритм расширяем для больших пирамид; но не проверяет размер входного массива: он будет работать, если массив разумный.

using System;

public static void Main()
{
    int[] values = new int[] { 3, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6 };
    bool result = IsDominoPyramidValid(values);
    Console.WriteLine(result ? "YES" : "NO");
}

private const int DominoLength = 2;

public static bool IsDominoPyramidValid(int[] values)
{
    int arrayLength = values.Length;

    int offset = 0;
    int currentRow = 1; // Note: I'm using a 1-based value here as it helps the maths
    bool result = true;
    while (result)
    {
        int currentRowLength = currentRow * DominoLength;

        // Avoid checking final row: there is no row below it
        if (offset + currentRowLength >= arrayLength)
        {
            break;
        }

        result = CheckValuesOnRowAgainstRowBelow(values, offset, currentRowLength);
        offset += currentRowLength;
        currentRow++;
    }

    return result;
}

private static bool CheckValuesOnRowAgainstRowBelow(int[] values, int startOfCurrentRow, int currentRowLength)
{
    int startOfNextRow = startOfCurrentRow + currentRowLength;
    int comparablePointOnNextRow = startOfNextRow + 1;
    for (int i = 0; i < currentRowLength; i++)
    {
        if (values[startOfCurrentRow + i] != values[comparablePointOnNextRow + i])
        {
            return false;
        }
    }

    return true;
}

Answer 3

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

Подсчитайте количество вхождений каждого числа.Должно быть как минимум 3 для как минимум двух чисел и так далее.Если эти условия не выполняются, решения не существует.На следующих шагах вам нужно учесть расположение чисел на плитках.

Answer 4

Просто повторяйте каждую перестановку и проверяйте каждую. Если вы найдете решение, тогда вы можете остановиться и вернуть «ДА». Если вы прошли через все перестановки, верните «НЕТ». Есть 6 позиций, и у каждого домино есть 2 вращения, таким образом, всего 12 * 10 * 8 * 6 * 4 * 2 = 46080 перестановок. Половина из них является зеркалами друг друга, поэтому мы удваиваем нашу необходимую рабочую нагрузку, но я не думаю, что это будет беспокоить пользователя. Я бы зафиксировал ориентацию домино, затем итерацию всех перестановок позиций, затем итерации перестановок ориентации и повторение.

Итак, я бы представил алгоритм как:

For each permutation of domino orientations
    For each permutation of domino positions
        if arr[0] == arr[3] && arr[1] == arr[4] && arr[2] == arr[7] && arr[3] == arr[8] && arr[4] == arr[9] && && arr[5] == arr[10] then return "YES"
return "NO"

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