Aquí hay una tabla (20x20) con un número entero de 0 a 99 en cada una de las celdas.
La tarea consiste en encontrar 4 números adyacentes sin romper la cadena, uno tras otro, teniendo el producto más grande. Las diferentes variantes de 4 números adyacentes se resaltan en color (dos números se consideran adyacentes si están ubicados a no más de 1 celda entre sí).
Hoy implementaremos el algoritmo de búsqueda en C #.
Primero, creemos una matriz bidimensional de 20x20 y escribamos en un archivo:
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(" ");
}
}
Ahora podemos escribir los números del archivo en una matriz bidimensional.
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]);
}
}
Creemos una clase Element para representar las coordenadas y el valor de un número:
public class Element
{
public int Line { get; set; }
public int Column { get; set; }
public int Value { get; set; }
}
De acuerdo con las condiciones del problema, debe encontrar una combinación de trabajos. Implementemos la clase Multiplicación para representar una combinación que contiene una matriz de números y el valor del producto de los números en la combinación.
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;
}
}
}
Lo primero que debe hacer es encontrar los vecinos más cercanos del número. Por ejemplo, para el número 40 en nuestro caso, los siguientes vecinos:
Y el número 48 en la esquina inferior derecha tiene solo 3 vecinos. No es difícil entender que los vecinos de cualquier número son:
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]
Después de asegurarnos de que el índice no esté fuera de los límites, obtenemos el método FindNeighbors que devuelve una colección de todos los vecinos más cercanos de un número en particular.
Según el enunciado del problema, necesitamos encontrar una combinación de 4 números adyacentes. Para hacer esto, necesitamos un método para encontrar todas las combinaciones posibles de 4 números:
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;
}
El método obtiene las coordenadas de un número en la tabla y verifica el valor de este número por 0 (al multiplicar cualquier número por 0, siempre resulta ser 0). Luego, el método busca todos los vecinos del número dado. Iteramos sobre los vecinos del primer nivel, si el número no es 0, buscamos todos los vecinos del segundo nivel ...
Anulamos el método Equals para comparar números:
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;
}
}
Continuamos la búsqueda a los vecinos del cuarto nivel, si los números no están duplicados, lo agregamos a nuestra colección.
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);
}
}
El método GetFactorCombinations se puede visualizar de la siguiente manera:
Ahora, recorriendo nuestra matriz bidimensional, buscamos la mayor combinación de números.
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);
Si la siguiente combinación es mayor que maxMultiplication, vuelva a escribirla.
Sí lo hicimos. Hemos encontrado la combinación de 4 números con el producto más grande.
De hecho, hemos resuelto el problema, pero el código está codificado para condiciones específicas, un método puramente procedimental. ¿Y si necesitamos buscar en una matriz no 20 por 20, sino por ejemplo 30 por 30 y una combinación de no 4, sino 5 números? cada vez agregue otro ciclo anidado (para iterar sobre todos con todos) ...
Reservamos 2 constantes para el tamaño de la tabla y para el tamaño de la combinación deseada:
const int TABLE_SIZE = 20;
public const int COMBINATION_SIZE = 4;
Reescribamos el método GetFactorCombinations en un método recursivo:
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;
}
El método funciona de acuerdo con el mismo principio que antes, pero en lugar de bucles anidados, continuamos buscando vecinos de forma recursiva hasta que el número de elementos encontrados sea resultElements.Count ()! = COMBINATION_SIZE
Después de encontrar la combinación, puede mostrarla maravillosamente en la consola:
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();
}
Conclusión
En este artículo, nos familiarizamos con una de las opciones para encontrar combinaciones adyacentes en la tabla NxN.
Qué más puedes hacer:
- Puede considerar deshacerse de múltiples iteraciones de todas las combinaciones con todas y otras formas de optimizar el código.
- Basándose en el algoritmo existente, implemente una búsqueda de combinaciones de números vecinos en una matriz tridimensional. Pero este ya es otro momento ...
