Hola gente de taringa, voy a retomar con un poco de programación.
Consiste en la solución de un desafío, que puede ser resuelto en forma manual, pero que resulta un tanto engorroso si lo intentamos de esa manera, además en caso de presentarse un desafío similar pero más complejo es posible usar la misma solución.
De todos modos la solución presentada tiene la desventaja de tomar muchos datos iniciales que hay que cargarlos a mano, es decir el posible error humano no queda descartado.
No estoy diciendo que sea “la solución” por computadora, es una entre tantas que debe existir.
Listo, metámonos en el problema. Me entero del desafío por medio de un shout de @Lean_InkiciLove donde retaba a @comandowar a resolverlo, el desafío es el siguiente:
Y la solución manual que presentó @comandowar es la siguiente: (según él la imagen contiene 172 triángulos)
Veamos si se equivocó o no.
Como dije es posible resolverlo manualmente, pero yo me voy a enfocar en la solución por computadora.
De la imagen sale que para formar triángulos nos podemos basar en el cálculo aritmético, teniendo los puntos cargados y tratar de determinar si esos puntos forman una línea recta, pero eso implicaría el tratamiento con valores reales, los cuales son una complicación ya que tendríamos que establecer rangos de precisión.
La anterior solución es ineficiente, complicada y de poca fiabilidad, siempre que es posible hay que tratar de tomar valores discretos, es decir valores enteros.
Para tal planteo se me ocurrió tomar los puntos vértices y numerarlos, pero sin tener el dato de la posición. Con esos puntos formo muchas líneas, y con esas líneas tengo la suficiente información para obtener todos los triángulos.
“Se forma un triángulo cuando tres líneas distintas comparten tres puntos distintos”.
Con ésta definición no necesito saber donde se encuentra el punto, y es suficiente para formar el algoritmo de solución completo, es decir los ‘if’ y ‘for’ que componen el algoritmo salen de esa simple definición.
Primero voy recorriendo línea por línea, y de cada línea obtengo cada uno de los puntos (los primeros dos ‘for’), en ese mismo bucle recorro todas las líneas, menos la línea seleccionada en el primer ‘for’, y obtengo todos los puntos de cada línea (los siguientes dos ‘for’) compara los dos puntos seleccionados de las dos líneas y si son iguales significa que se encontró la primera de tres intersecciones que forman un triángulo.
Con esa intersección encontrada continúo en el bucle, y busco otra línea que no sea ni la primera, ni la segunda y todos sus puntos (los siguientes dos ‘for’) Los siguientes dos ‘for’ se encargan de determinar si la primera o la segunda línea interceptan a la tercera línea, en caso de ser así, significa que se encontró un triángulo, pero eso no es suficiente como para incrementar el contador de triángulos, porque es posible que esté repetido, se comprueba si es distinto con todos los triángulos guardados en la lista, en tal caso se lo carga en esa misma lista.
Con eso ya tenemos el funcionamiento completo. En C# el código fuente es el siguiente:
El programa funcionando se ve de la siguiente manera. Borro el resultado porque lo vamos a ver al final del post.
Como podemos ver eso te dice el resultado, pero nos impide tener una comprobación visual, para ello, en lugar de crear una aplicación de consola, cree una aplicación para Windows.
Arrastré los siguientes controles: NumericUpDown (valor mínimo ‘1’, y con el evento ValueChange ), un Lavel y un TextBox (marcado en solo lectura).
Al Form le agregué el evento Paint y le marqué la propiedad DoubleBuffered en true, ya quedaría listo junto con el siguiente código:
Noten que en el método CargaLineas() se pone casi todo el código de la aplicación de consola. En el método CargaPuntos() le brindamos los datos para que puedan visualizarse los triángulos, es decir tampoco tiene incidencia en la resolución del problema, sino que es una ayuda para que podamos comprobar el resultado.
El resultado definitivo es de 178 triángulos, es decir @comandowar se equivocó, dejo una imagen representativa:
Consiste en la solución de un desafío, que puede ser resuelto en forma manual, pero que resulta un tanto engorroso si lo intentamos de esa manera, además en caso de presentarse un desafío similar pero más complejo es posible usar la misma solución.
De todos modos la solución presentada tiene la desventaja de tomar muchos datos iniciales que hay que cargarlos a mano, es decir el posible error humano no queda descartado.
No estoy diciendo que sea “la solución” por computadora, es una entre tantas que debe existir.
Listo, metámonos en el problema. Me entero del desafío por medio de un shout de @Lean_InkiciLove donde retaba a @comandowar a resolverlo, el desafío es el siguiente:
Y la solución manual que presentó @comandowar es la siguiente: (según él la imagen contiene 172 triángulos)
Veamos si se equivocó o no.
Como dije es posible resolverlo manualmente, pero yo me voy a enfocar en la solución por computadora.
De la imagen sale que para formar triángulos nos podemos basar en el cálculo aritmético, teniendo los puntos cargados y tratar de determinar si esos puntos forman una línea recta, pero eso implicaría el tratamiento con valores reales, los cuales son una complicación ya que tendríamos que establecer rangos de precisión.
La anterior solución es ineficiente, complicada y de poca fiabilidad, siempre que es posible hay que tratar de tomar valores discretos, es decir valores enteros.
Para tal planteo se me ocurrió tomar los puntos vértices y numerarlos, pero sin tener el dato de la posición. Con esos puntos formo muchas líneas, y con esas líneas tengo la suficiente información para obtener todos los triángulos.
“Se forma un triángulo cuando tres líneas distintas comparten tres puntos distintos”.
Con ésta definición no necesito saber donde se encuentra el punto, y es suficiente para formar el algoritmo de solución completo, es decir los ‘if’ y ‘for’ que componen el algoritmo salen de esa simple definición.
Primero voy recorriendo línea por línea, y de cada línea obtengo cada uno de los puntos (los primeros dos ‘for’), en ese mismo bucle recorro todas las líneas, menos la línea seleccionada en el primer ‘for’, y obtengo todos los puntos de cada línea (los siguientes dos ‘for’) compara los dos puntos seleccionados de las dos líneas y si son iguales significa que se encontró la primera de tres intersecciones que forman un triángulo.
Con esa intersección encontrada continúo en el bucle, y busco otra línea que no sea ni la primera, ni la segunda y todos sus puntos (los siguientes dos ‘for’) Los siguientes dos ‘for’ se encargan de determinar si la primera o la segunda línea interceptan a la tercera línea, en caso de ser así, significa que se encontró un triángulo, pero eso no es suficiente como para incrementar el contador de triángulos, porque es posible que esté repetido, se comprueba si es distinto con todos los triángulos guardados en la lista, en tal caso se lo carga en esa misma lista.
Con eso ya tenemos el funcionamiento completo. En C# el código fuente es el siguiente:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
//Contine 36 puntos numerados del 1 al 36 y una serie de líneas
List<List<int>> lLineas = new List<List<int>>();
List<int[]> lTriangulos = new List<int[]>();
List<int> lLineaAux;
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 2, 5, 10, 17, 26 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 4, 9, 16, 25, 36 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 3, 4 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 6, 7, 8, 9 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 11, 12, 13, 14, 15, 16 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 18, 19, 20, 21, 22, 23, 24, 25 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 27 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 18, 28 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 11, 19, 29 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 6, 12, 20, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 3, 7, 13, 21, 31 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 4, 8, 14, 22, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 9, 15, 23, 33 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 16, 24, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 25, 35 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 28 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 19, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 12, 21, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 7, 14, 23, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 25, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 16, 23, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 9, 14, 21, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 4, 7, 12, 19, 28 });
lLineas.Add(lLineaAux);
//Busca triángulos distintos
for (int i = 0; i < lLineas.Count; i++)
{
for (int j = 0; j < lLineas[i].Count; j++)
{
for (int k = 0; k < lLineas.Count; k++)
{
if (k == i) { continue; }
for (int l = 0; l < lLineas[k].Count; l++)
{
if (lLineas[i][j] == lLineas[k][l])
{
//Encuentra primera intersección
for (int m = 0; m < lLineas.Count; m++)
{
if (m == i) { continue; }
if (m == k) { continue; }
int contInterseccion = 0;
int p2 = 0;
int p3 = 0;
for (int n = 0; n < lLineas[m].Count; n++)
{
//Busca un punto de la primera línea que coincida
for (int o = 0; o < lLineas[i].Count; o++)
{
if (o == j) { continue; }//no puede ser el primer punto
if (lLineas[i][o] == lLineas[m][n])
{
//Encuentra segunda intersección
contInterseccion++;
p2 = lLineas[i][o];
break;
}
}
//Busca un punto de la segunda línea que coincida
for (int o = 0; o < lLineas[k].Count; o++)
{
if (o == l) { continue; }//no puede ser el primer punto
if (lLineas[k][o] == lLineas[m][n])
{
//Encuentra tercer intersección
contInterseccion++;
p3 = lLineas[k][o];
break;
}
}
}
if (contInterseccion >= 2)
{
if ((p2 > 0) && (p3 > 0) && (p2 != p3))
{
//Encuentra un triángulo
int p1 = lLineas[i][j];
//Busca que no exista
bool qExiste = false;
for (int i1 = 0; i1 < lTriangulos.Count; i1++)
{
int contPuntos = 0;
for (int i2 = 0; i2 < lTriangulos[i1].Length; i2++)
{
if (lTriangulos[i1][i2] == p1) { contPuntos++; }
if (lTriangulos[i1][i2] == p2) { contPuntos++; }
if (lTriangulos[i1][i2] == p3) { contPuntos++; }
}
if (contPuntos >= 3)
{
qExiste = true;
break;
}
}
if (!qExiste)
{
lTriangulos.Add(new int[] { p1, p2, p3 });
}
}
}
}
}
}
}
}
}
Console.WriteLine("Contiene {0} triángulos", lTriangulos.Count);
Console.ReadLine();
}
}
}
El programa funcionando se ve de la siguiente manera. Borro el resultado porque lo vamos a ver al final del post.
Como podemos ver eso te dice el resultado, pero nos impide tener una comprobación visual, para ello, en lugar de crear una aplicación de consola, cree una aplicación para Windows.
Arrastré los siguientes controles: NumericUpDown (valor mínimo ‘1’, y con el evento ValueChange ), un Lavel y un TextBox (marcado en solo lectura).
Al Form le agregué el evento Paint y le marqué la propiedad DoubleBuffered en true, ya quedaría listo junto con el siguiente código:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace WindowsApplication1
{
public partial class Form1 : Form
{
private List<Point> lPuntos = null;
private List<List<int>> lLineas = null;
private List<int[]> lTriangulos = null;
public Form1()
{
InitializeComponent();
lLineas = new List<List<int>>();
lTriangulos = new List<int[]>();
lPuntos = new List<Point>();
CargaPuntos();
CargaLineas();
numericUpDown1.Maximum = lTriangulos.Count;
textBox1.Text = lTriangulos.Count.ToString();
this.Invalidate();
}
private void CargaLineas()
{
List<int> lLineaAux;
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 2, 5, 10, 17, 26 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 4, 9, 16, 25, 36 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 3, 4 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 6, 7, 8, 9 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 11, 12, 13, 14, 15, 16 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 18, 19, 20, 21, 22, 23, 24, 25 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 27 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 18, 28 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 11, 19, 29 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 6, 12, 20, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 1, 3, 7, 13, 21, 31 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 4, 8, 14, 22, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 9, 15, 23, 33 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 16, 24, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 25, 35 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 17, 28 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 10, 19, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 5, 12, 21, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 2, 7, 14, 23, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 25, 34 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 16, 23, 32 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 9, 14, 21, 30 });
lLineas.Add(lLineaAux);
lLineaAux = new List<int>();
lLineaAux.AddRange(new int[] { 4, 7, 12, 19, 28 });
lLineas.Add(lLineaAux);
//Busca triángulos distintos
for (int i = 0; i < lLineas.Count; i++)
{
for (int j = 0; j < lLineas[i].Count; j++)
{
for (int k = 0; k < lLineas.Count; k++)
{
if (k == i) { continue; }
for (int l = 0; l < lLineas[k].Count; l++)
{
if (lLineas[i][j] == lLineas[k][l])
{
//Encuentra primera intersección
for (int m = 0; m < lLineas.Count; m++)
{
if (m == i) { continue; }
if (m == k) { continue; }
int contInterseccion = 0;
int p2 = 0;
int p3 = 0;
for (int n = 0; n < lLineas[m].Count; n++)
{
//Busca un punto de la primera línea que coincida
for (int o = 0; o < lLineas[i].Count; o++)
{
if (o == j) { continue; }//no puede ser el primer punto
if (lLineas[i][o] == lLineas[m][n])
{
//Encuentra segunda intersección
contInterseccion++;
p2 = lLineas[i][o];
break;
}
}
//Busca un punto de la segunda línea que coincida
for (int o = 0; o < lLineas[k].Count; o++)
{
if (o == l) { continue; }//no puede ser el primer punto
if (lLineas[k][o] == lLineas[m][n])
{
//Encuentra tercer intersección
contInterseccion++;
p3 = lLineas[k][o];
break;
}
}
}
if (contInterseccion >= 2)
{
if ((p2 > 0) && (p3 > 0) && (p2 != p3))
{
//Encuentra un triángulo
int p1 = lLineas[i][j];
//Busca que no exista
bool qExiste = false;
for (int i1 = 0; i1 < lTriangulos.Count; i1++)
{
int contPuntos = 0;
for (int i2 = 0; i2 < lTriangulos[i1].Length; i2++)
{
if (lTriangulos[i1][i2] == p1) { contPuntos++; }
if (lTriangulos[i1][i2] == p2) { contPuntos++; }
if (lTriangulos[i1][i2] == p3) { contPuntos++; }
}
if (contPuntos >= 3)
{
qExiste = true;
break;
}
}
if (!qExiste)
{
lTriangulos.Add(new int[] { p1, p2, p3 });
}
}
}
}
}
}
}
}
}
}
private void CargaPuntos()
{
int lX = 30, lY = 60;
int x = 70, y = 50;
lPuntos.AddRange(new Point[] {
new Point(0, 0),
new Point(x + lX * 5, y + lY * 0),
new Point(x + lX * 4, y + lY * 1),
new Point(x + lX * 5, y + lY * 1),
new Point(x + lX * 6, y + lY * 1),
new Point(x + lX * 3, y + lY * 2),
new Point(x + lX * 4, y + lY * 2),
new Point(x + lX * 5, y + lY * 2),
new Point(x + lX * 6, y + lY * 2),
new Point(x + lX * 7, y + lY * 2),
new Point(x + lX * 2, y + lY * 3),
new Point(x + lX * 3, y + lY * 3),
new Point(x + lX * 4, y + lY * 3),
new Point(x + lX * 5, y + lY * 3),
new Point(x + lX * 6, y + lY * 3),
new Point(x + lX * 7, y + lY * 3),
new Point(x + lX * 8, y + lY * 3),
new Point(x + lX * 1, y + lY * 4),
new Point(x + lX * 2, y + lY * 4),
new Point(x + lX * 3, y + lY * 4),
new Point(x + lX * 4, y + lY * 4),
new Point(x + lX * 5, y + lY * 4),
new Point(x + lX * 6, y + lY * 4),
new Point(x + lX * 7, y + lY * 4),
new Point(x + lX * 8, y + lY * 4),
new Point(x + lX * 9, y + lY * 4),
new Point(x + lX * 0, y + lY * 5),
new Point(x + lX * 1, y + lY * 5),
new Point(x + lX * 2, y + lY * 5),
new Point(x + lX * 3, y + lY * 5),
new Point(x + lX * 4, y + lY * 5),
new Point(x + lX * 5, y + lY * 5),
new Point(x + lX * 6, y + lY * 5),
new Point(x + lX * 7, y + lY * 5),
new Point(x + lX * 8, y + lY * 5),
new Point(x + lX * 9, y + lY * 5),
new Point(x + lX * 10, y + lY * 5)
});
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
Graphics g = e.Graphics;
if (lPuntos != null)
{
g.FillPolygon(new SolidBrush(Color.Red), new Point[] {
lPuntos[lTriangulos[(int)numericUpDown1.Value - 1][0]],
lPuntos[lTriangulos[(int)numericUpDown1.Value - 1][1]],
lPuntos[lTriangulos[(int)numericUpDown1.Value - 1][2]]});
}
if (lLineas != null)
{
for (int i = 0; i < lLineas.Count; i++)
{
g.DrawLine(new Pen(new SolidBrush(Color.Gray)), lPuntos[lLineas[i][0]], lPuntos[lLineas[i][lLineas[i].Count - 1]]);
}
}
}
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
this.Invalidate();
}
}
}
Noten que en el método CargaLineas() se pone casi todo el código de la aplicación de consola. En el método CargaPuntos() le brindamos los datos para que puedan visualizarse los triángulos, es decir tampoco tiene incidencia en la resolución del problema, sino que es una ayuda para que podamos comprobar el resultado.
El resultado definitivo es de 178 triángulos, es decir @comandowar se equivocó, dejo una imagen representativa: