La bandera de los Estados Unidos de América contiene, en su cantón, 50 estrellas, que representan los 50 estados.
En el pasado, cuando había menos estados, por supuesto, había menos estrellas, y se organizaban de manera diferente. Por ejemplo, de 1912 a 1959 (después de la admisión de Nuevo México y Arizona pero antes de Alaska), había 48 estrellas en un arreglo rectangular de 6 × 8.
La bandera de 37 estrellas utilizada desde 1867-1877 (después de la admisión de Nebraska pero antes de Colorado) tenía un patrón de estrellas asimétrico.
En caso de que se agregue un estado número 51 en el futuro, el Instituto de Heráldica del Ejército ya ha desarrollado un diseño preliminar para una nueva bandera.
Pero no hay un algoritmo general para organizar las estrellas, ¡así que hagamos uno!
El reto
Escriba un programa que, para un número determinado de estrellas para colocar en el cantón (parte azul) de una bandera de los Estados Unidos, produzca coordenadas óptimas en las que colocar esas estrellas. El sistema de coordenadas se define con el cantón [ no la bandera como un todo] con 0≤x≤W y 0≤y≤H.
Para el propósito de este desafío, una disposición "óptima" se define como aquella que minimiza la distancia media (euclidiana) entre un punto en el cantón y el centro de la estrella más cercana.
Un algoritmo sencillo (si tal vez subóptimo) para aproximar este valor es:
def mean_distance_to_nearest_star(stars, width, height, point_density=100):
"""
Approximate the mean distance between a point in the rectangle
0 < x < width and 0 < y < height, and the nearest point in stars.
stars -- list of (x, y) points
width, height -- dimensions of the canton
"""
total = 0.0
nx = round(width * point_density)
ny = round(height * point_density)
for ix in range(nx):
x = (ix + 0.5) * width / nx
for iy in range(ny):
y = (iy + 0.5) * width / ny
min_dist = float('inf')
for sx, sy in stars:
min_dist = min(min_dist, math.hypot(x - sx, y - sy))
total += min_dist
return total / (nx * ny)
Su programa tomará tres argumentos de línea de comandos (sin contar el nombre del programa en sí):
- El número de estrellas para poner en el cantón.
- El ancho del cantón. (Debe aceptar valores de punto flotante).
- La altura del cantón. (Debe aceptar valores de punto flotante).
(Si su lenguaje de programación preferido no admite argumentos de línea de comandos, haga algo razonablemente equivalente y documente en su respuesta).
La salida debe consistir en valores X e Y separados por comas, uno a una línea. (El orden de los puntos no importa).
Por ejemplo:
~$ flagstar 5 1.4 1.0
0.20,0.20
0.20,0.80
0.70,0.50
1.20,0.20
1.20,0.80
Reglas y notas adicionales
- Tengo derecho a cerrar las lagunas en las reglas en cualquier momento.
La fecha límite para recibir respuestas es el viernes 4 de julio a las 24:00 CDT (UTC-05: 00).Debido a la falta de respuestas, el plazo se ha extendido. TBA- Incluye en tu respuesta:
- El código de su programa
- Una explicación de cómo funciona.
- Su salida con los argumentos de la línea de comandos
50 1.4 1.0
- Su programa debe ejecutarse dentro de un período de tiempo razonable: como máximo 5 minutos en una PC típica. No seré muy estricto con esto, pero descalificaré su programa si lleva horas .
- Su programa debe ser determinista, es decir, siempre debe dar exactamente la misma salida para los mismos argumentos. Por lo tanto, no dependa de
time()
orand()
. Los métodos de Monte Carlo están bien siempre y cuando haga su propio PRNG. - Solo importan los puntos centrales de las estrellas. No te preocupes por tratar de evitar la superposición o algo así.
Tanteo
- Minimice la distancia media desde un punto en el cantón hasta la estrella más cercana. (Véase más arriba.)
- Puede obtener un puntaje basado en cualquier bandera histórica de los EE. UU., Entre 13 y 50 estrellas. El algoritmo exacto para ponderar los puntajes en una sola clasificación se publicará más adelante.
- En caso de empate, el ganador será elegido por el número de votos a favor netos.
- Probablemente publicaré un programa propio, pero me excluiré de ser elegible para la marca de verificación.
fuente
Respuestas:
Javascript: mueve las estrellas hacia el punto más aislado
(con una animación del proceso)
El enfoque es muy simple:
Este proceso se repite una gran cantidad de veces, disminuyendo gradualmente la cantidad de movimiento de las estrellas. Esto reduce la distancia máxima desde un punto hasta la estrella más cercana, reduciendo indirectamente la distancia media desde un punto hasta la estrella más cercana.
Como lo requiere la pregunta, esto no usa la función aleatoria incorporada, sino que usa xorshift .
Gran parte del código cubre la configuración y la animación: la parte que aplica el algoritmo es la función
adjustStars
.Código
Puede ver el proceso en curso en el Fragmento de pila a continuación.
Salida para 50 estrellas
(ancho = 1.4, altura = 1.0)
Distancia media estimada en 0.0655106697162357.
Coordenadas
fuente
Aquí hay un ejemplo simple. Siempre organiza las estrellas en una cuadrícula rectangular y la optimiza eligiendo la factorización en la que las celdas de la cuadrícula están lo más cerca posible del cuadrado. Funciona muy bien cuando el número de estrellas tiene un divisor cerca de su raíz cuadrada, y pesimalmente cuando el número de estrellas es primo.
Salida para 50 estrellas
(ancho = 1.4, altura = 1.0)
Un rectángulo de 10 × 5.
fuente
Javascript: mueve una estrella al azar si se reduce la distancia media
(con una animación del proceso)
Esto no da una animación tan ocupada como mi primera respuesta, ya que tiene largos períodos sin movimiento ya que las posibles reorganizaciones se prueban y rechazan. Sin embargo, el resultado final tiene una distancia media menor, por lo que este método es una mejora.
El enfoque sigue siendo muy simple:
Este proceso se repite una gran cantidad de veces, disminuyendo gradualmente la cantidad de movimiento de las estrellas. La elección aleatoria de la distancia para moverse está sesgada hacia distancias más pequeñas, por lo que el progreso está en pequeñas alteraciones intercaladas con el salto ocasional más grande. Cada paso lleva más tiempo que en mi primera respuesta, ya que medir la distancia media es un proceso lento que requiere muestrear todo el cantón.
Como lo requiere la pregunta, esto no usa la función aleatoria incorporada, sino que usa xorshift .
Gran parte del código cubre la configuración y la animación: la parte que aplica el algoritmo es la función
adjustStars
.Código
Puede ver el proceso en curso en el Fragmento de pila a continuación.
Salida para 50 estrellas
(ancho = 1.4, altura = 1.0)
Distancia media estimada en 0.06402754713808706.
Coordenadas
fuente