Relacionado con esta pregunta .
Una habitación se define como un polígono no intersecante (no necesariamente convexo), expresado como una lista ordenada de coordenadas bidimensionales. Se coloca una bombilla suficientemente brillante en un punto específico dentro de la habitación y emite luz en todas las direcciones. Su tarea es encontrar el área iluminada total de la habitación. Puede recibir información en cualquier formato razonable. Los puntos en el polígono / habitación, así como las coordenadas de la fuente de luz, son números racionales. Se pueden tomar en sentido horario o antihorario, cualquiera de los formatos está bien. El caso de prueba en el problema se da en sentido antihorario.
La siguiente imagen muestra dos salas de ejemplo, donde el punto púrpura representa la fuente de luz y la región sombreada representa el área iluminada.
Caso de prueba:
(1/2, 18)
(1,3)
(5,1/2)
(7,5)
(12,7)
(16,3)
(15,11)
(8,19)
(3,7)
Light source located at (5,8)
Answer: 815523/6710 ≈ 121.538
Aquí hay una representación gráfica de la solución a ese caso de prueba. Los dos puntos que definen la solución que no están en el polígono original son (55/61, 363/61) y (856/55, 357/55).
Esta fórmula puede ser útil para calcular el área.
Como se trata de código golf , gana el código más corto en bytes.
[tag:code-golf]
Respuestas:
Python 3 , 388
398408409415417493bytesPara hacerlo más preciso, aumente
n
Enfoque básico de Montecarlo. Pasos enumerados a continuación.
s
s
entre los números totales, luego multiplique por el área de rango total.Versión sin golf:
Pruébalo en línea!
Crédito por algoritmo de intersección de línea
Además, agradezca a todos los comentaristas útiles sobre cómo jugar golf aún más.
fuente
from random import*
(salto de línea)u=uniform
para -2 bytesg=lambda i:
n
Tiene que ser una potencia de 10? De lo contrario, puede guardar un byte usando una potencia de 9.i:(min
, el espacio en tambiénx[i]for
se puede eliminar. Además,return float(s/n)*(r*t)
puede serreturn(r*t)*float(s/n)
. Y no estoy del todo seguro, pero no puedo las variablesr
ye
puede quitar y utilizar directamente, ya que sólo se utiliza una vez? De alguna manera, da un resultado ligeramente diferente a pesar deg
que no se modifica, por lo que esa parte me confunde un poco (no estoy muy familiarizado con Python para entender por qué el resultado es ligeramente diferente).Haskell , 559
618632bytesSolución exacta (salvo errores). Haskell tiene una aritmética racional exacta incorporada. Pruébalo en línea!
Tenga en cuenta que esto da
815523/6710
, no814643/6710
, para la sala de ejemplo, y la primera intersección de la pared se calcula como(55/61, 363/61)
. Estoy bastante seguro de que esto es correcto porque la entrada de Monte Carlo (lentamente) converge al mismo resultado.Leyenda:
Bonus: GUI brillante para pruebas. Haga clic al lado de los puntos para moverlos.
fuente
APL + WIN
Esta es una versión no golfista de este interesante desafío que ofrezco para demostrar mi lógica. Mi versión antigua de APL + WIN no se adapta bien a las estructuras de control anidadas de golf. Las APL más modernas podrían hacerlo mejor: ¿desafío?
Si los lectores validan la lógica, intentaré jugar esta solución. Si la lógica es incorrecta, simplemente eliminaré.
fuente
R ,
296255bytesPruébalo en línea!
Esta es una versión más reducida de la respuesta de Python . El método central de Monte Carlo es el mismo, pero reorganicé algunas de las funciones para acortarlas. En mi primera iteración, había sido demasiado agresivo en la reorganización, y luego me di cuenta de que podía optimizar tanto la longitud como la velocidad al volver a una versión del algoritmo de intersección más cercano a la pitón.
Aquí hay una versión sin golf que también traza los resultados:
fuente