Найти комбинацию соседних чисел, имеющих самое большое произведение


Перед вами таблица (20x20) с целым числом от 0 до 99 в каждой из клеток.

Задача — найти 4 соседних числа без разрыва цепочки, одно за другим, имеющих самое большое произведение. Цветом выделены различные варианты 4 соседних чисел (соседними считаются два числа, расположенных не более чем на 1 клетку друг от друга).

Сегодня мы с вами реализуем алгоритм поиска на языке C#.

Для начало создадим двумерный массив 20х20 и запишем его в файл:

static void CreateArrayFile()
{
    Random random = new Random();
    string file = "";
    for (int i = 0; i < 20; i++)
    {
        string line = "";
        for (int j = 0; j < 20; j++)
        {
            line += random.Next(0, 99) + ",";
        }
        line = line + Environment.NewLine;
        file += line;
    }
    using (FileStream fstream = new FileStream($"array.txt", FileMode.OpenOrCreate))
    {
        byte[] array = System.Text.Encoding.Default.GetBytes(file);
        fstream.Write(array, 0, array.Length);
        Console.WriteLine("Массив записан в файл");
    }
}


Теперь мы можем, записать числа из файла в двумерный массив.

string[] lines = arrayFile.Split(Environment.NewLine);
for (int i = 0; i < 20; i++)
{
    string[] items = lines[i].Split(',');
    for (int j = 0; j < 20; j++)
    {
        table[i, j] = Convert.ToInt32(items[j]);
    }
}

Для представления координат и значения числа создадим класс Element:

public class Element
{
    public int Line { get; set; }
    public int Column { get; set; }
    public int Value { get; set; }
}

По условиям задачи, требуется найти комбинацию произведений. Реализуем класс Multiplication для представления комбинации содержащий массив чисел и значение произведения чисел в комбинации.

public class Multiplication
{
    public Multiplication()
    {
        Elements = new Element[4];
    }
    public Element[] Elements { get; set; }
    public int Value
    {
        get
        {
            Multiply();
            return value;
        }
    }
    int value;
    void Multiply()
    {
        if(Elements[0] != null && Elements[1] != null && Elements[2] != null && Elements[3] != null)
        {
            value = Elements[0].Value * Elements[1].Value * Elements[2].Value * Elements[3].Value;
        }
    }
}

Первое что нужно сделать найти ближайших соседей числа. Например, для числа 40 в нашем случае следующие соседи:


А у числа 48 в правом нижнем углу есть всего 3 соседа. Не трудно понять, что соседи любого числа это:

table[i-1][j-1]
table[i-1][j]
table[i-1][j+1]

table[i][j-1]
table[i][j+1]

table[i+1][j-1]
table[i+1][j]
table[i+1][j+1]

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

По условию задачи, нам нужно найти комбинацию из 4 соседних чисел. Для этого нам нужен метод для поиска всех возможных комбинаций из 4 чисел:

static List<Multiplication> GetFactorCombinations(int line, int column)
{
    List<Multiplication> combinations = new List<Multiplication>();
    if (table[line, column] != 0)
    {
        List<Element> firstLevelNeighbors = FindNeighbors(line, column);
        foreach (var firstLevelNeighbor in firstLevelNeighbors)
        {
            Element[] elements = new Element[4];
            elements[0] = new Element
            {
                Line = line,
                Column = column,
                Value = table[line, column]
            };
            elements[1] = firstLevelNeighbor;
            List<Element> secondLevelNeighbors = FindNeighbors(firstLevelNeighbor.Line, firstLevelNeighbor.Column);
            foreach (var secondLevelNeighbor in secondLevelNeighbors)
            {
                if (!elements[0].Equals(secondLevelNeighbor) && !elements[1].Equals(secondLevelNeighbor))
                {
                    elements[2] = secondLevelNeighbor;
                }
                if (elements[2] != null)
                {
                    List<Element> thirdLevelNeighbors = FindNeighbors(secondLevelNeighbor.Line, secondLevelNeighbor.Column);
                    foreach (var thirdLevelNeighbor in thirdLevelNeighbors)
                    {
                        if (!elements[0].Equals(thirdLevelNeighbor) && !elements[1].Equals(thirdLevelNeighbor) && !elements[2].Equals(thirdLevelNeighbor))
                        {
                            elements[3] = thirdLevelNeighbor;
                            Multiplication multiplication = new Multiplication 
                            { 
                                Elements = elements
                            };
                            if (combinations.Where(p=>p.Elements[0].Value==elements[0].Value&& p.Elements[1].Value == elements[1].Value && p.Elements[2].Value == elements[2].Value && p.Elements[3].Value == elements[3].Value).FirstOrDefault()==null)
                            {
                                var nnnn =new Multiplication
                                {
                                    Elements = new Element[] { elements[0], elements[1], elements[2], elements[3]}
                                };
                                combinations.Add(nnnn);
                            }
                        }
                    }
                }
            }
        }
    }
    return combinations;
}

Метод получает координаты числа в таблице и проверяет значение этого числа на 0 (При умножении любого числа на 0 всегда получается 0). Потом метод ищет всех соседей данного числа. Перебираем соседей первого уровня, в случае если число не 0 ищем всех соседей второго уровня…

Переопределяем метод Equals для сравнивания чисел:

public override bool Equals(Object obj)
{
    if (this==null || (obj == null) || !this.GetType().Equals(obj.GetType()))
    {
        return false;
    }
    else if(Line == ((Element)obj).Line && Column == ((Element)obj).Column)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Продолжаем поиск до соседей четвертого уровня если числа не дублируются, то добавляем его в нашу коллекцию.

if (!elements[0].Equals(thirdLevelNeighbor) && !elements[1].Equals(thirdLevelNeighbor) && !elements[2].Equals(thirdLevelNeighbor))
{
    elements[3] = thirdLevelNeighbor;
    Multiplication multiplication = new Multiplication 
    { 
        Elements = elements
    };
    if (combinations.Where(p=>p.Elements[0].Value==elements[0].Value&& p.Elements[1].Value == elements[1].Value && p.Elements[2].Value == elements[2].Value && p.Elements[3].Value == elements[3].Value).FirstOrDefault()==null)
    {
        var combination=new Multiplication
        {
            Elements = new Element[] { elements[0], elements[1], elements[2], elements[3]}
        };
        combinations.Add(combination);
    }
}

Работу метода GetFactorCombinations можно визуализировать так:


Теперь перебрав наш двумерный массив ищем самую большую комбинацию чисел.

for (int i = 0; i < 20; i++)
{
    for (int j = 0; j < 20; j++)
    {
        List<Multiplication> combinations = GetFactorCombinations(i, j);
        foreach (var combination in combinations)
        {
            if (combination.Value > maxMultiplication.Value)
            {
                Console.WriteLine("Найдена новая самая большая комбинация " + combination.Elements[0].Value + " * " + combination.Elements[1].Value + " * " + combination.Elements[2].Value + " * " + combination.Elements[3].Value + " = " + combination.Value);
                maxMultiplication = combination;
            }
        }
    }
}
Console.WriteLine("Самое большое произведение четырех чисел = " + maxMultiplication.Elements[0].Value + " * " + maxMultiplication.Elements[1].Value + " * " + maxMultiplication.Elements[2].Value + " * " + maxMultiplication.Elements[3].Value + " = " + maxMultiplication.Value);

Если следующая комбинация больше чем maxMultiplication, переписываем его.


Да, мы сделали это. Мы нашли комбинацию из 4 чисел с самым большим произведением.

Фактически, мы решили задачу, но код захардкожен под конкретные условия, чисто процедурный метод. А если нам нужно будет искать из матрицы не 20 на 20, а к примеру 30 на 30 и комбинацию не из 4, а 5 чисел? каждый раз добавлять еще один вложенный цикл (для перебора всех со всеми) …

Зарезервируем 2 константы для размера таблицы, и для размера искомой комбинации:

const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;

Перепишем метод GetFactorCombinations на рекурсивный метод:

static List<Multiplication> GetMultiplicationForStep(int line, int column, List<Element> otherElements = null)
{
    List<Multiplication> resultMultiplications = new List<Multiplication>();
    List<Element> resultElements = new List<Element>(); 
    Element element = new Element
    {
        Column = column,
        Line = line,
        Value = table[line, column]
    };
    if (otherElements == null)
    {
        otherElements = new List<Element>();
    }
    if(otherElements!=null)
    {
        resultElements.AddRange(otherElements);
    }
    if (table[line, column] != 0)
    {                
        if (otherElements.Where(p => p.Equals(element)).FirstOrDefault() == null)
        {
            resultElements.Add(element);
        }
    }
    if (resultElements.Count() == COMBINATION_SIZE)
    {
        Multiplication multiplication = new Multiplication
        {
            Elements = resultElements.ToArray()
        };
        resultMultiplications.Add(multiplication);
    }
    else
    {
        List<Element> elementNeighbors = FindNeighbors(line, column);
        elementNeighbors = elementNeighbors.Where(p => !p.Equals(element)&& otherElements.Where(p=>p.Equals(element)).FirstOrDefault()==null).ToList();
        List<Multiplication> newMultiplications = new List<Multiplication>();
        foreach(Element neighbor in elementNeighbors)
        {
            // Если количество комбинаций меньше COMBINATION_SIZE рекурсивно продолжаю искать соседей...
            newMultiplications.AddRange(GetMultiplicationForStep(neighbor.Line, neighbor.Column, resultElements).Where(p=>p!=null));
        }
        foreach(Multiplication multiplication in newMultiplications)
        {
            if(resultMultiplications.Where(p=>p.Value==multiplication.Value).FirstOrDefault()==null)
            {
                resultMultiplications.Add(multiplication);
            }
        }
    }
    return resultMultiplications;
}

Метод работает по тому же принципу как и раньше только вместо вложенных циклов, рекурсивно продолжаем поиск соседей пока количество найденных элементов resultElements.Count() != COMBINATION_SIZE

После нахождения комбинации можно его красиво отобразить в консоли:

for (int i = 0; i < TABLE_SIZE; i++)
{
    for (int j = 0; j < TABLE_SIZE; j++)
    {
        if (maxMultiplication.Elements.Where(p => p.Line == i && p.Column == j).FirstOrDefault() != null)
        {
            Console.BackgroundColor = ConsoleColor.White;
            Console.ForegroundColor = ConsoleColor.Black; // Тут я вывожу таблицу заново, и отображаю самую большую найденную комбинацию
            Console.Write(table[i, j] + " ");
            Console.ResetColor();
        }
        else
        {
            Console.Write(table[i, j] + " ");
        }
    }
    Console.WriteLine();
}



Заключение


В этой статье мы познакомились с одним из вариантов нахождения соседних комбинаций в таблице NxN.

Что можно сделать еще:

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

Средняя зарплата в IT

113 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 5 503 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 24

    +2
    А кроме прямого перебора никакие оптимизированные методы не искали?
      0
      Первое что приходит в головы, найти самое большое число, и начать поиск соседей с него, но этот вариант отсеивается тем, что его соседи могут быть не большими. Сейчас рассматриваю
      совет сохранять хэши перебранных ранее вариантов…
        0
        Ну можно еще посмотреть в сторону наибольших сумм с соседями, либо какого-нибудь анализа сумм строк/столбцов/даигоналей для поиска групп наибольших чисел.
        0
        +1. Тоже ждал какого-нибудь интересного алгоритма из динамического программирования.

        Вызывает удивление как этот факт, так и выбранные структуры данных. Два new List и new Element на каждый чих (т.е. примерно 20*20*8^4 раз) вводят меня в ступор, честно говоря (надеюсь, компилятор их соптимизирует)
        0

        Искал оптимизацию полного перебора, хотя бы тупое отсечение по нехватке миллиона на умножение текущего элемента для превышения текущего максимума. Так как все числа меньше 100, если текущий максимум превышает 50 00 00 00, или 50 миллионов, пропускать элементы со значением 50 или ниже.
        Ещё — ваш метод GetFactorCombinations не позволяет цепочки в форме ромба, т.е. перебор ещё и неполон. Цепочка в форме ромба — от стартового элемента вниз-вправо, вниз-влево, вверх-влево.

          0
          Так как все числа меньше 100, если текущий максимум превышает 50 00 00 00, или 50 миллионов, пропускать элементы со значением 50 или ниже.

          И это действительно дельный совет. То есть, максимально возможный результат произведения это 100*100*100*100 = 100 000 000. Если комбинация со значением произведения уже равна 80 000 000 можно игнорировать все числа меньше 80. Возьму на вооружение
          На счет цепочки в форме ромба. Только что проверил, их он тоже учитывает.

          гляньте на число 78 нулевая строка, первый столбец.
            0

            Хмм, рекурсивный, кажется, полный, а вот итеративный — нет. Разве что у меня глазной дебаггер заглючил :)

              +1
              Максимальное произведение — 96059601. У вас же максимальное число в ячейке 99, а не 100.
              А когда ищете четвёртого соседа, то можно не всех найденных добавлять, а максимального из соседей, чтобы не делать лишние умножения потом, по всем найденным комбинациям.
                0
                когда ищете четвёртого соседа, то можно не всех найденных добавлять, а максимального из соседей

                Согласен. Рациональная идея.
            +2
            Если бы речь шла про сумму, можно было бы все распараллелить и оптимизировать через операцию свертки (Conv2D в данном случае) с несколькими ядрами. С другой стороны, так как числа по определению > 0, то логарифм произведения есть сумма логарифмов. Так что можно посчитать поэлементно логарифм, а потом применить операцию свертки.
            PS — идея абсолютно не протестирована ).
              0

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

                0
                Да, верно. Я думал про ядра W как 3D тензор размерности (4, 4, N) состоящий из нулей и единиц, где N — количество валидных цепочек в матрице 4x4. Тогда операция Conv2D(X, W) даст 3D тензор, в котором пространственные индексы максимального элемента укажут на под-матрицу (4,4) исходной матрицы, а третий индекс укажет на конкретное ядро, т.е. укажет какие 4 элемента надо выбрать.
                  0

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

                  +1
                  Нули можно специально не обрабатывать, так как логарифм нуля будет -Infinity, и суммы с ним будут корректно обрабатываться
                0
                Можно сразу отбрасывать ячейки с маленькими числами и не строить на их базе матрицы, поскольку маленькие числа значительно сильнее портят результат чем большие числа улучшают результат. Правда каким должен быть порог отсечения — это нужно думать.
                  0

                  Имхо медиана значений матрицы будет неплохим кандидатом.

                  0

                  Если оптимизировать для длины 4, то можно было бы вычислить в отдельный массив результат умножения пары чисел (4 варианта для каждой ячейки — вправо, вниз, вниз-влево, вниз-вправо), и затем перебирать уже пары для этого нового массива. Причем перебирать не все пары "пар", а только те, которые дают цепочку, подходящую под задание (скажем, "вниз" от текущей ячейки умножить на "вправо" от ячейки вниз-вправо), и без дублирования "фигур". Есть необоснованное подозрение, что в таком случае получим оптимальное число операций умножения. Кроме того, необязательно вычислять весь массив пар сразу — достаточно вычислить 3 строки массива для 4 строк исходных данных, поискать фигуры в них, и потом для каждой строки данных отбрасывать верхнюю строку массива и вычислять одну новую.

                    +1
                    Вам бы кэш уже умноженных значений внедрить, сильно быстрее станет сразу. А чтобы память всю не сожрал, несложно придумать, как этот кэш сливать, когда алгоритм заведомо «уходит» за ту границу, где кэш может быть полезен.

                    UPD: я подумал еще раз и понял, что сильно быстрее не станет, извиняюсь.
                      0
                      Комментария для автора: А можно более реальные алгоритмы разбирать? Например выборку-формулы для trend \ hot допустим видео, как делают такое на разных сайтах.
                        +1
                        Спасибо, интересная задача!
                        Я применил некоторые оптимизации, результат ускоряется очень сильно. Понятно, что 20x20 будет работать быстро и без опnимизаций, поэтому я мерил производительность на двух случаях: 1) матрица 10,000x10,000, заполненная случайными значениями, и 2) матрица 1,000x1,000, заполненная «наихудшими» значениями так, чтобы максимальное произведение четырех соседних элементов было в самом конце.
                        Без оптимизаций первый вариант я не дождался, когда закончит вычисления, а второй вариант — 30 секунд.
                        Оптимизация, которую нашел vesper-bot, — пропускать числа, умножение которых на 99*99*99 будет меньше уже найденного результата, улучшает сильнее всего — «случайный» вариант ускоряется до 8 секунд, наихудший — никак не ускоряется (так как я специально подбирал для него значения!)
                        Кроме этого, если текущее значение = 99*99*99*99, то можно дальше не искать, так как это максимально возможный результат. Это ускоряет случайный вариант до 6 секунд.
                        Далее, так как перебирать всех соседей всех клеток на каждом шаге дорого, то до начала работы можно вычислить уникальные пути из четырех клеток. Их оказалось всего 102. Это ускоряет случайный вариант до 3 секунд, а наихудший — с 30 до 2 секунд.
                        При этом в случайном варианте заполнение матрицы случайными значениями занимает больше времени, чем решение задачи. Поэтому последня оптимизация — не создавать всю матрицу с нуля, а создать первые 4 строчки, а потом сдвигать их вверх, вычисляя четвертую строчку на каждом шаге. Также, на данном этапе проверка выхода за границу матрицы уже дает ощутимый вклад, поэтому еще одна оптимизация — расширить матрицу на три клетки во все стороны, заполненные нулями. Это ускоряет случайный вариант до 0.2 секунд, а наихудший — до 1 секунды, больше я ускорить не смог. Еще я проверил идею заменить произведение суммой логарифмов, но особо результат не ускорился (но и не замедлился).

                        Интересно, что хотя сложность задачи совершенно явно O(n*n), но для случайной матрицы, если она достаточно большая, рано или поздно найдется максимальное произведение (99*99*99*99), и дальше можно будет не искать. Учитывая, что оптимизированная версия создает матрицу построчно, скорость работы в среднем случае для случайной матрицы, похоже, будет O(n). Именно поэтому «случайный» вариант работает в 10 раз быстрее на большей матрице.
                          0
                          А если число в ячейке не ограничивать диапазоном 0-99?
                          А если разрешить отрицательные значения?
                            0
                            В случае если разрешить отрицательные значения, придется игнорировать комбинации с нечетным количеством отрицательных чисел
                              0
                              В общем случае не придется, ведь у нас может быть задан нечетный размер комбинации, а таблица при этом может сгенериться полностью из отрицательных чисел.
                          +1
                          я бы построил граф с весами и нашел Гамильтонову цепь глубиной 4 (в Вашем случае). Поскольку у Вас достаточно жесткая структура(матрица), то так же можно легко построить список деревьев (те самые «уникальные пути») и пройтись по ним, найдя дерево с самым большим весом. НЕ используйте массивы для таких задач

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

                          Самое читаемое