В чем может быть ошибка при решении задания?

Question

[Dyikot]

Ссылка на само задание.
Пару месецев назад, вроде даже на Habr QA нашел вопрос и там было скинуто много ссылок на задания. Примеры заданий на собеседования. Ну вот решил ради интереса посмотреть пару и показалось интересным одно задание. Решил его сохранить и вот теперь спустя пару месяцев на каникулах решил решить. Где-то на полове решений все казалось должно работать, но возможно я что-то не понимаю?
Мой путь решений:
Уже сейчас думаю лучше было бы использовать классы для облегчения понимаю кода, но об этом позно подумал и сделал на массивах.
План решения:
1) Найти все возможные "зеленые" квадраты, ну или комбинация 4 квадратов подходящий под "зеленое" условие.
2) Объеденить 5 подходящих зеленых квадратов чтобы получилась данныя фигура. (я тут)
3) Отсечь фигуры не подходящие под "желтые условия".
Поиск все возможных зеленых квадратов нашел обойдя в цикле все возможные размещения квадратов. Получается k = 4 и n = 12 и по итогу количество циклов составило 11880 из которых под условие из файла squares0.txt подходят 777 зеленых квадратов. Тут все правильно?
Ну а дальше просто в тупую назначаю первый элемент массива как центральных и проверяю последующие подходят они к этому сверху, снизу, слева и справа. Если нет назначаю второй как центральный и т.д до конца массива. И вот тут пробмела что такой комбинации нету и максимум что он находил это все кроме левого зеленого квадрата. По идеи если как в задании сказано найти чтобы выполнялись все уловия то должен же быть такой зеленый квадрат в центре к которому со всех сторон подойдут другие. В чем моя ошибка?

Если нужен код (C#)

string filePath = @"Squares.txt";
            List<List<int>> squares = new();
            List<List<string>> squaresString = new();

            // Getting squares.

            File.ReadAllLines(filePath).ToList().ForEach(squareString =>
                squaresString.Add(squareString.Split(' ').ToList()));
            squaresString.ForEach(squareString =>
            {
                List<int> square = new();
                squareString.ForEach(number => square.Add(int.Parse(number)));
                squares.Add(square);
            });

            // Searching for squares matching the green condition.

            List<List<int>> greenSquares = new();
            int first = 0, second = 1, third = 2, fourth = 3;
            const int maxNumber = 11, minNumber = 0;
            bool isNewCheck4, isNewCheck3, isNewCheck2;

            while(first != maxNumber || second != maxNumber - 1 || third != maxNumber - 2 ||
                fourth != maxNumber - 3)
            {
                isNewCheck2 = isNewCheck3 = isNewCheck4 = true;

                if (DoSquaresFitToGreenCondition(squares[first], squares[second], squares[third],
                    squares[fourth]))
                {
                    greenSquares.Add(new List<int> { first, second, third, fourth });
                }
                
                while (isNewCheck4 || fourth == third || fourth == second || fourth == first)
                {
                    isNewCheck4 = false;
                    if (fourth == maxNumber)
                    {
                        fourth = minNumber;
                        while (isNewCheck3 || third == second || third == first)
                        {
                            isNewCheck3 = false;
                            if (third == maxNumber)
                            {
                                third = minNumber;
                                while (isNewCheck2 || second == first)
                                {
                                    isNewCheck2 = false;
                                    if (second == maxNumber)
                                    {
                                        second = minNumber;
                                        first++;
                                    }
                                    else
                                        second++;
                                }
                            }
                            else
                                third++;
                        }
                    }
                    else
                        fourth++;
                }
            }

            if (DoSquaresFitToGreenCondition(squares[first], squares[second], squares[third],
                    squares[fourth]))
            {
                greenSquares.Add(new List<int> { first, second, third, fourth });
            }

            // Grouping into 5 green squares.

            List<List<int>> groupGreenSquares = new();
            List<int>? upGreenSquare = null, downGreenSquare = null, leftGreenSquare = null,
                rightGreenSquare = null, middleGreenSquare = null;
            List<int> usingSquares = new();
            int cycle = 0;

            while ((upGreenSquare == null || downGreenSquare == null || leftGreenSquare == null ||
                rightGreenSquare == null) && cycle < greenSquares.Count)
            {
                middleGreenSquare = greenSquares[cycle++];
                rightGreenSquare = leftGreenSquare = upGreenSquare = downGreenSquare = null;

                for (int i = 0; i < greenSquares.Count && (upGreenSquare == null ||
                    downGreenSquare == null || leftGreenSquare == null ||
                    rightGreenSquare == null); i++)
                {
                    if (upGreenSquare == null &&
                        middleGreenSquare[0] == greenSquares[i][2] &&
                        middleGreenSquare[1] == greenSquares[i][3] &&
                        !usingSquares.Contains(greenSquares[i][0]) &&
                        !usingSquares.Contains(greenSquares[i][1]) &&
                        !middleGreenSquare.Contains(greenSquares[i][0]) &&
                        !middleGreenSquare.Contains(greenSquares[i][1]))
                    {
                        upGreenSquare = greenSquares[i];
                        usingSquares.AddRange(new int[] { upGreenSquare[0], upGreenSquare[1] });
                    }
                    else if (downGreenSquare == null &&
                        middleGreenSquare[2] == greenSquares[i][0] &&
                        middleGreenSquare[3] == greenSquares[i][1] &&
                        !usingSquares.Contains(greenSquares[i][2]) &&
                        !usingSquares.Contains(greenSquares[i][3]) &&
                        !middleGreenSquare.Contains(greenSquares[i][2]) &&
                        !middleGreenSquare.Contains(greenSquares[i][3]))
                    {
                        downGreenSquare = greenSquares[i];
                        usingSquares.AddRange(new int[] { downGreenSquare[2], downGreenSquare[3] });
                    }
                    else if (leftGreenSquare == null &&
                        middleGreenSquare[0] == greenSquares[i][1] &&
                        middleGreenSquare[2] == greenSquares[i][3] &&
                        !usingSquares.Contains(greenSquares[i][0]) &&
                        !usingSquares.Contains(greenSquares[i][2]) &&
                        !middleGreenSquare.Contains(greenSquares[i][0]) &&
                        !middleGreenSquare.Contains(greenSquares[i][2]))
                    {
                        leftGreenSquare = greenSquares[i];
                        usingSquares.AddRange(new int[] { leftGreenSquare[0], leftGreenSquare[2] });
                    }
                    else if (rightGreenSquare == null &&
                        middleGreenSquare[1] == greenSquares[i][0] &&
                        middleGreenSquare[3] == greenSquares[i][2] &&
                        !usingSquares.Contains(greenSquares[i][1]) &&
                        !usingSquares.Contains(greenSquares[i][3]) &&
                        !middleGreenSquare.Contains(greenSquares[i][1]) &&
                        !middleGreenSquare.Contains(greenSquares[i][3]))
                    {
                        rightGreenSquare = greenSquares[i];
                        usingSquares.AddRange(new int[] { rightGreenSquare[1], rightGreenSquare[3] });
                    }
                }
            }

            groupGreenSquares.AddRange(new List<List<int>>{ upGreenSquare, leftGreenSquare,
                middleGreenSquare, rightGreenSquare, downGreenSquare});
        }

        static bool DoSquaresFitToGreenCondition(List<int> fisrt, List<int> second,
            List<int> third, List<int> fourth)
        {
            return (fisrt[3] + second[2] + third[1] + fourth[0]) == 10;
        }

Comments

[Дмитрий]

Как минимум надо упрощать вложенность
https://www.sonarsource.com/docs/CognitiveComplexi...

Answer 1

[Rsa97]

IMHO, тут нужет обычный рекурсивный алгоритм, только функция проверки получается довольно сложная.
Я бы написал функцию, которая по номеру позиции выдаёт ограничения на углы (min и max для каждого угла) при условии, что предыдущие позиции заполнены, а следующие ещё нет. Затем останется выбирать из оставшихся квадратов те, которые подойдут под ограничения на следующее поле, пробовать подставить их и решить ту же задачу с частично заполненным полем и оставшимися квадратами.

Comments

[Dyikot]

Это хорошо что есть иное решение, но мне бы хотелось узнать что я не так сделал тут.

[Rsa97]

Dyikot, У вас код такой, что его проще переписать, чем разобраться.
Сравните по понятности со своим вариантом:

for (int first = 0; first < 12; first++) {
    for (int second = 0; second < 12; second++) {
        if (second == first) {
            continue;
        }
        for (int third = 0; third < 12; third++) {
            if (third == second || third == first) {
                continue;
            }
            for (int fourth = 0; fourth < 12; fourth++) {
                if (fourth == third || fourth == second || fourth == first) {
                    continue;
                }
                if (DoSquaresFitToGreenCondition(squares[first], squares[second], squares[third], squares[fourth])) {
                    greenSquares.Add(new List<int> { first, second, third, fourth });
                }
            }
        }
    }
}

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

static bool DoSquaresFitToGreenCondition(List<int> fisrt, List<int> second, List<int> third, List<int> fourth)
{
    int sumCenter = fisrt[3] + second[2] + third[1] + fourth[0];
    int sumTop = first[1] + second[0];
    int sumBottom = third[3] + fourth[2];
    int sumLeft = first[2] + third[0];
    int sumRight = second[3] + fourth[1];
    return sumCenter == 10 && sumTop <= 10 && sumBottom <= 10 && sumLeft <= 10 && sumRight <= 10;
}

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

[Dyikot]

Rsa97, Ну так я разве дальше не перебираю все возможные варианты для центрального зеленого квадрата?

[Rsa97]

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

[Дмитрий]

Подобная проверка когда то мне нужна была, для проверки пустой клетки в игре пятнашки, там проще сделать 4 проверки отдельными методами, и если одна из них дала ложный результат, переходить на следующую

[Dyikot]

Rsa97, Попробывал иначе:
1) Перебрал все зеленые квадраты в качестве центрального, и записал для каждого 4 массива для Up, Down, Left и Right сторон.
2) Удалил центральные у которых хотя бы отсутсвует один сторонний зеленый квадрат.
3) Перебрал оставшиеся центральные квадраты подбирая сторонние к нему. В итоги вышло всего 4.
4) Потом проверил их через желтые условия трех углов и стало 0.
Я что-то не понимаю или как. Вроде бы все варианты перебрал.

Код

// Searching for all green square position.

            List<List<List<List<int>>>> matchingSquares = new();
            List<int> middleGreenSquare = new();

            for (int cycle = 0; cycle < greenSquares.Count; cycle++)
            {
                middleGreenSquare = greenSquares[cycle];
                matchingSquares.Add(new List<List<List<int>>>
                {
                    new List<List<int>>(),
                    new List<List<int>>(),
                    new List<List<int>>(),
                    new List<List<int>>()
                });

                for (int i = 0; i < greenSquares.Count; i++)
                {
                    if (middleGreenSquare[0] == greenSquares[i][2] &&
                        middleGreenSquare[1] == greenSquares[i][3]) // Up side
                    {
                        matchingSquares[cycle][0].Add(greenSquares[i]);
                    }
                    else if (middleGreenSquare[2] == greenSquares[i][0] &&
                        middleGreenSquare[3] == greenSquares[i][1]) // Down side
                    {
                        matchingSquares[cycle][1].Add(greenSquares[i]);
                    }
                    else if (middleGreenSquare[0] == greenSquares[i][1] &&
                        middleGreenSquare[2] == greenSquares[i][3]) // Left Side
                    {
                        matchingSquares[cycle][2].Add(greenSquares[i]);
                    }
                    else if (middleGreenSquare[1] == greenSquares[i][0] &&
                        middleGreenSquare[3] == greenSquares[i][2]) // Right Side
                    {
                        matchingSquares[cycle][3].Add(greenSquares[i]);
                    }
                }
            }

            // Remove bad combination ( there may not be at least one pair for the middle square).

           matchingSquares.RemoveAll(middleSquare => middleSquare.Exists(sideSquare=>
                sideSquare.Count == 0));

            // Finding groups of green squares where the sum of the square numbers is 66.
            // Removing groups that have repeated square numbers.
            // This leaves groups with unique numbers and satisfying the green condition.

            List<List<List<int>>> groupsGreenSquares = new();
            List<List<int>>? upSquares, downSquares, leftSquares, rightSquares;
            List<int> usingSquares = new();
            const int sumOfRightSqaureCombination = 66; // 1 + 2 + ... + 11
            int squaresSum, uniqueSquaresCount;
            
            foreach (var middleSquare in matchingSquares)
            {
                upSquares = middleSquare[0];
                downSquares = middleSquare[1];
                leftSquares = middleSquare[2];
                rightSquares = middleSquare[3];

                foreach(var upSquare in upSquares)
                {
                    foreach(var downSquare in downSquares)
                    {
                        foreach(var leftSquare in leftSquares)
                        {
                            foreach(var rightSquare in rightSquares)
                            {
                                squaresSum = upSquare.Sum() + downSquare.Sum() + leftSquare[0] +
                                    leftSquare[2] + rightSquare[1] + rightSquare[3];

                                if (squaresSum == sumOfRightSqaureCombination)
                                {
                                    usingSquares.Clear();
                                    usingSquares.AddRange(new List<int>
                                    {
                                        upSquare[0], upSquare[1], upSquare[2], upSquare[3],
                                        downSquare[0], downSquare[1], downSquare[2], downSquare[3],
                                        leftSquare[0], leftSquare[2],
                                        rightSquare[1], rightSquare[3]
                                    });
                                    uniqueSquaresCount = usingSquares.Distinct().ToList().Count;

                                    if (uniqueSquaresCount == usingSquares.Count)
                                    {
                                        groupsGreenSquares.Add(new List<List<int>>
                                        {
                                            upSquare,
                                            leftSquare,
                                            rightSquare,
                                            downSquare
                                        });
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // Checking the yellow condition for three corners.

            groupsGreenSquares.RemoveAll(groupGreenSquares =>
                !DoCornersFitToYellowCondition(new List<List<int>>
                {
                    squares[groupGreenSquares[0][0]],
                    squares[groupGreenSquares[0][1]],
                    squares[groupGreenSquares[1][0]],
                    squares[groupGreenSquares[1][1]],
                    squares[groupGreenSquares[2][0]],
                    squares[groupGreenSquares[2][1]],
                    squares[groupGreenSquares[1][2]],
                    squares[groupGreenSquares[1][3]],
                    squares[groupGreenSquares[2][2]],
                    squares[groupGreenSquares[2][3]],
                    squares[groupGreenSquares[3][2]],
                    squares[groupGreenSquares[3][3]]
                }));

static bool DoCornersFitToYellowCondition(List<List<int>> squares)
        {
            int leftUpCorner = squares[0][2] + squares[2][1] + squares[3][0];
            int rightUpCorner = squares[1][3] + squares[4][1] + squares[5][0];
            int leftDownCorner = squares[6][3] + squares[7][2] + squares[10][0];
            int rightDonwCorer = squares[8][3] + squares[9][2] + squares[11][1];

            return leftUpCorner < 10 && rightUpCorner < 10 && leftDownCorner < 10 &&
                rightDonwCorer < 10;
        }

[Rsa97]

Dyikot, Какая-то жуть непонятная. Всё делается намного проще.

const tiles = [
  [1, 0, 7, 5],
  [3, 4, 1, 3],
  [5, 1, 1, 4],
  [7, 6, 1, 8],
  [5, 7, 4, 4],
  [8, 3, 3, 4],
  [7, 1, 5, 4],
  [4, 1, 1, 0],
  [3, 1, 1, 4],
  [2, 4, 3, 8],
  [5, 1, 1, 7],
  [4, 2, 4, 2],
];

function calculateLimits(field, tileNumber) {
  switch (tileNumber) {
    case 0:
      return [
        [0, 9],
        [0, 9],
        [0, 9],
      ];
    case 1:
      return [
        [0, 10 - field[0][1]],
        [0, 9],
        [0, 9],
      ];
    case 2:
      return [
        [0, 9],
        [0, 10 - field[0][2]],
        [0, 9],
      ];
    case 3:
      return [
        [0, 10 - field[0][2] - field[2][1]],
        [0, 10 - field[0][3] - field[1][2]],
        [0, 10 - field[2][3]],
      ];
    case 4:
      return [
        [
          10 - field[0][3] - field[1][2] - field[3][1],
          10 - field[0][3] - field[1][2] - field[3][1],
        ], 
        [0, 10 - field[1][3]],
        [0, 10 - field[3][3]],
      ];
    case 5:
      return [
        [0, 10 - field[1][3] - field[4][1]],
        [0, 9],
        [0, 10 - field[4][3]],
      ];
    case 6:
      return [
        [0, 10 - field[2][2]],
        [0, 10 - field[2][3] - field[3][2]],
        [0, 9],
      ];
    case 7:
      return [
        [
          10 - field[2][3] - field[3][2] - field[6][1],
          10 - field[2][3] - field[3][2] - field[6][1],
        ],
        [0, 10 - field[3][3] - field[4][2]],
        [0, 10 - field[6][3]],
      ];
    case 8:
      return [
        [
          10 - field[3][3] - field[4][2] - field[7][1],
          10 - field[3][3] - field[4][2] - field[7][1],
        ],
        [0, 10 - field[4][3] - field[5][2]],
        [0, 10 - field[7][3]],
      ];
    case 9:
      return [
        [
          10 - field[4][3] - field[5][2] - field[8][1],
          10 - field[4][3] - field[5][2] - field[8][1],
        ],
        [0, 10 - field[5][3]],
        [0, 10 - field[8][3]],
      ];
    case 10:
      return [
        [0, 10 - field[6][3] - field[7][2]],
        [0, 10 - field[7][3] - field[8][2]],
        [0, 9],
      ];
    case 11:
      return [
        [
          10 - field[7][3] - field[8][2] - field[10][1],
          10 - field[7][3] - field[8][2] - field[10][1],
        ],
        [0, 10 - field[8][3] - field[9][2]],
        [0, 10 - field[10][3]],
      ];
  }
}

function nextTile(field, restTiles, tileNumber) {
  if (tileNumber === 12) {
    return [field];
  }
  const limits = calculateLimits(field, tileNumber);
  let results = [];
  for (let i = 0; i < restTiles.length; i += 1) {
    if (
      restTiles[i][0] >= limits[0][0] && restTiles[i][0] <= limits[0][1] &&
      restTiles[i][1] >= limits[1][0] && restTiles[i][1] <= limits[1][1] &&
      restTiles[i][2] >= limits[2][0] && restTiles[i][2] <= limits[2][1]
    ) {
      const newTiles = restTiles.concat([]);
      newTiles.splice(i, 1);
      results = results.concat(
        nextTile(field.concat([restTiles[i]]), newTiles, tileNumber + 1),
      );
    }
  }
  return results;
}

const result = nextTile([], tiles, 0);

for (let i = 0; i < result.length; i += 1) {
  for (let j = 0; j < 12; j += 1) {
    console.log(result[i][j].join(' '));
  }
  console.log('');
}

/* 
5 7 4 4
3 4 1 3
8 3 3 4
3 1 1 4
4 2 4 2
5 1 1 4
7 1 5 4
4 1 1 0
1 0 7 5
7 6 1 8
5 1 1 7
2 4 3 8
*/

[Dyikot]

Rsa97, Главное мне надо понять, сама логика т.е не код, правильно или нет, может там где-то ошибка ( в коде). Просто может не все варианты разобраны.

[Dyikot]

Rsa97, Решил проверить ваш ответ и желтые условия же должны быть < 10, у вас 10. Исправте пожалуйста и тогда я смогу понять где исключается правильный вариант.

[Rsa97]

Dyikot, Условие "не более 10", так что может быть 10.

[Dyikot]

Rsa97, ясно где ошибка.

[Dyikot]

Rsa97, просто я сам не писал проверку желтых условий я взял вашу где еще и зеленые проверяются а там <10.

[Dyikot]

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

[Rsa97]

Dyikot, Да, там действительно ошибка. Поправил.