Project Euler #144 solución en VB.NET

Resolución de ejercicio #144 de Project Euler en VB.NET.



Este es un interesante ejercicio que simula un sistema de espejos que reflejan un laser.

El ejercicio consiste en averiguar cuántas veces el haz de un laser rebota dentro de una elipse antes de salir por un pequeño orificio de entrada/salida ubicado en la parte superior.

Una forma de resolverlo es con un método (algoritmo, función) que, a partir del punto de colisión (sobre el que incide el laser en la elipse), calcule el próximo punto de colisión del haz siguiendo las leyes de la reflexión.
El proceso continúa hasta que el punto de colisión obtenido pertenezca al orificio de entrada.










Para resolverlo, se utilizaron dos clases simples: RectaR2 y PuntoD.
La primera representa a una recta en el plano y la segunda representa a un punto en el plano:

'Clase para representar a una recta en el plano
Public Class RectaR2
 Public P As PuntoD
 Public m As Double
 'A partir de la pendiente y un punto incluido en la recta
 Sub New(ByVal m As Double, ByVal P As PuntoD)
  Me.m = m
  Me.P = P
 End Sub
 'A partir de dos puntos de la recta
 Sub New(ByVal P1 As PuntoD, ByVal P2 As PuntoD)
  Dim m As Double = (P2.Y - P1.Y) / (P2.X - P1.X)
  Me.m = m
  Me.P = P2
 End Sub
 'Ecuacion Explicita
 Public Overrides Function ToString() As String
  Return String.Format("y = {0}x + {1}", Me.m, Me.P.Y - Me.m * Me.P.X)
 End Function
End Class
'Clase para representar un punto en el plano
Public Class PuntoD
 Public X As Double, Y As Double
 Sub New()
 End Sub
 Sub New(ByVal x As Double, ByVal y As Double)
  Me.X = x
  Me.Y = y
 End Sub
End Class

También se utilizó un método que denominé Paso, que calcula el siguiente punto de colisión del laser a partir del punto de colisión actual.

Este método es el que contiene los cálculos trigonométricos necesarios para obtener la reflexión del laser.

'A partir de un punto de inicio y fin de un rayo laser (ambos en la elipse)
'retorna el proximo punto de contacto del laser (tambien en la elipse)
Function Paso(ByVal Pini As PuntoD, ByVal Pfin As PuntoD) As PuntoD
 Dim SgtePunto As New PuntoD()
 'Calculo la pendiente de la recta tangente a la elipse en el Punto de Fin (m = 4x/y)     (m1)
 Dim m1 As Double = -4 * Pfin.X / Pfin.Y
 'Obtengo la pendiente de la recta reflejada (reflejo sobre la recta tangente)... Y = m2*X + b
 'tmp = (m0-m1)/(1+m0*m1)         m2 = (m1-X)/(1+X*m1)
 Dim m0 As Double = (Pfin.Y - Pini.Y) / (Pfin.X - Pini.X)
 Dim tmp As Double = (m0 - m1) / (1 + m0 * m1)
 Dim m2 As Double = (m1 - tmp) / (1 + tmp * m1)
 'Obtengo los 2 puntos de interesección entre la recta reflejada y la elipse
 Dim b As Double = Pfin.Y - Pfin.X * m2
 Dim CoordsX As PuntoD = Cuadratica(4 + (m2 ^ 2), 2 * m2 * b, (b ^ 2) - 100)
 'Descartar el punto fin (Pfin)
 SgtePunto.X = If(Math.Abs(CoordsX.Y - Pfin.X) < 0.001, CoordsX.X, CoordsX.Y)
 SgtePunto.Y = m2 * SgtePunto.X + b
 Return SgtePunto
End Function

También se utilizó una forma para poder graficar el recorrido del laser en la pantalla:

Public Class Form1
 Private bitmap As Bitmap = New Bitmap(500, 1000)
 Sub New()
  ' This call is required by the Windows Form Designer.
  InitializeComponent()
  'Dibujar la elipse
  Using g As Graphics = Graphics.FromImage(bitmap)
   g.DrawEllipse(Pens.Blue, g.VisibleClipBounds)
  End Using
 End Sub
 'Convertir un punto del plano en un punto de la forma
 Public Function ConvertirPunto(ByVal P0 As PuntoD) As PointF
  Return New PointF(CSng(250 + P0.X * 50), CSng(500 - P0.Y * 50))
 End Function
 'Dibujar un segmento de recta dado
 Public Sub DibujarRecta(ByVal P0 As PuntoD, ByVal P1 As PuntoD)
  Using g = Graphics.FromImage(bitmap)
   g.DrawLine(Pens.Red, ConvertirPunto(P0), ConvertirPunto(P1))
   Me.PictureBox1.Image = bitmap
  End Using
 End Sub
 'Dibujar un número dado en la parte inferior
 Public Sub DibujarNum(ByVal num As Integer)
  Dim pt1 As New PointF(450, 970)
  Using g = Graphics.FromImage(bitmap)
   g.FillRectangle(Brushes.LightGray, pt1.X, pt1.Y, 50, 30)
   g.DrawString(num.ToString, New Font("Verdana", 14.0!), Brushes.Black, pt1)
   Me.PictureBox1.Image = bitmap
  End Using
 End Sub
End Class

Y por último, la entrada principal de la aplicación, donde está el ciclo que efectúa la búsqueda de puntos de incidencia, el conteo y la orden de dibujar en pantalla:

Sub Main()
 Dim PIni As New PuntoD(0, 10.1)
 Dim PFin As New PuntoD(1.4, -9.6)
 Dim frm As New Form1
 Dim temp As PuntoD
 Dim steps As Integer = 0
 frm.Show()
 While PFin.Y < 0 OrElse Math.Abs(PFin.X) > 0.01
  frm.DibujarRecta(PIni, PFin)
  frm.DibujarNum(steps)
  Application.DoEvents()
  temp = PIni
  PIni = PFin
  PFin = Paso(temp, PFin)
  steps += 1
 End While
 MessageBox.Show("Euler144=" & steps)
End Sub

Espero a alguien le sea útil... Y sino, no importa...



-- Puedes bajar este ejemplo aquí --