Estoy en la posición (0, 0) de una ciudad bidimensional infinita, que está perfectamente dividida en bloques centrados en cada punto de la red, algunos de los cuales contienen edificios. Un edificio en un cierto punto (x, y) ocupa todo el cuadrado con esquinas opuestas en (x-.5, y-.5) y (x + .5, y + .5) , incluido su borde. Un edificio es visible si hay algún segmento de línea desde (0, 0) hasta un punto en el edificio que no se cruza con ningún otro edificio.
Por ejemplo, yo (el @
) puedo ver 6 edificios ( *
) en la siguiente ciudad:
*
*
*
*@
x**
* y
No puedo ver el edificio marcado con un x
, en (-1, -1) porque está obstruido por los dos adyacentes; o el marcado con un y
at (3, -2) porque está obstruido por el borde del edificio (1, -1) .
Entrada
Una cadena de varias líneas, o una lista de líneas, opcionalmente rellenadas con espacios en un rectángulo. Contendrá solo:
- una sola
@
(mi posición) - Espacios
*
, que representan edificios.
Siempre habrá al menos un edificio y, por lo tanto, al menos un edificio visible.
Salida
El número de edificios visibles.
Casos de prueba
*@
1
* *******
@ *
7
*****
**@**
*****
4
*
**
@ **
2
* *
* *
@
4
@
*
***
1
Gracias a @Geobits por el título .
Respuestas:
Unidad + C #, 589 bytes
Este es probablemente el peor lenguaje para hacer un código de golf (léase: peor que Java), pero Unity viene con muchas características útiles para este desafío.
EDITAR: perdió un par de espacios, devuelve la longitud de la lista, no el contador
Golfizado:
Sin golf:
Utilicé 3600 raycasts porque falla el quinto caso de prueba con menor. Todavía podría fallar para casos de prueba aún más grandes / más precisos.
Desafortunadamente, las compilaciones de webgl y de escritorio parecen romperse, por lo que todo lo que tengo es el código fuente para probar en github .
fuente
read: worse than Java
¡Esto es 383 bytes más corto que la solución Java!total+=1
contotal++
? Creo que otra forma de guardar algunos personajes es crear el cubo del edificio y establecer su posición en una sola declaración. No parece reutilizar lacube
variable en ningún lado.GameObject b=GameObject.CreatePrimitive(PrimitiveType.Cube);b.transform.position=new Vector3(x,y);
. No sé si es posible en C #, pero en Java se podría escribir en suGameObject.CreatePrimitive(PrimitiveType.Cube).transform.position=new Vector3(x,y);
lugar.Java 8 lambda,
15061002972942 caracteresQuería superar este desafío, ya que es muy interesante. El resultado
(no muy golfista)se puede ver aquí:Por supuesto, esto también existe en la versión sin golf:
Por lo tanto, parece muy difícil, pero es mucho más fácil de lo que uno podría pensar. Mi primera idea fue usar un algoritmo de intersección para verificar si una línea desde mi posición hasta el edificio se puede hacer sin intersecciones. Para hacer esto, decidí usar el algoritmo Cohen-Sutherland y dibujar líneas en las cuatro esquinas del edificio. Esto funcionó bastante bien para las primeras pruebas, pero la última falló. Pronto descubrí que es un caso en el que no se pueden ver las esquinas, sino una parte de un borde. Así que pensé en algún tipo de casting de rayos como @Blue lo hizo. Dejé de lado ese desafío, ya que no obtuve algún progreso. Entonces vi la respuesta de Blue y me vino a la mente la siguiente idea simple: cada edificio bloquea algún ángulo en el que no se puede ver nada más. Solo necesito hacer un seguimiento de lo que se puede ver y lo que ya está oculto por otros edificios. ¡Eso es!
El algoritmo funciona de la siguiente manera: determina el edificio con la menor distancia a la persona. Luego imaginamos cuatro líneas dibujadas desde la persona a las esquinas del edificio. Dos de estos tienen un valor extremo: el ángulo mínimo y máximo en el que se puede ver el edificio. Los tomamos como un rango y los comparamos con otros edificios de los cuales sabemos que se pueden ver (ninguno al principio). Los rangos pueden superponerse, incluirse entre sí o no tocarse en absoluto. Comparo los rangos y obtengo algunos nuevos rangos del edificio que no están ocultos por los edificios visibles. Si queda algo después de compararlo con los edificios a la vista, el edificio también es visible. Agregamos el rango de ángulo restante a la lista de rangos para comparar y comenzar con el próximo edificio con la siguiente distancia más larga.
A veces, los rangos pueden superponerse de una manera que termino con un rango de 0 grados. Estos rangos se filtrarán para no agregar por error un edificio que ni siquiera se puede ver.
Espero que alguien haya entendido esta explicación :)
Sé que este código no se juega mucho, lo haré lo antes posible.Esa fue una tarea realmente desafiante. Pensaste que encontraste una solución que funciona, pero aún estás lejos. Creo que esta solución funciona bastante bien. No es muy rápido, pero al menos funciona;) ¡Gracias por ese rompecabezas!
Actualizar
Encontré el tiempo para jugar golf todo en una sola función, que por lo tanto se puede convertir en una lambda. Todas las funciones solo se llamaron una vez y, por lo tanto, se pueden poner en un solo método. Cambié de listas a conjuntos ya que esto guarda algunos caracteres adicionales. Las declaraciones se han reunido. Las comparaciones se han reunido y los caracteres fueron reemplazados por su valor ascii. La comparación de rango se puede expresar como muchos ternaries. Algunos trucos aquí y allá para evitar expresiones largas como Double.NEGATIVE_INFINITY se hicieron. Siempre que sea posible, se realizan asignaciones en línea. Para ahorrar un poco más, pasé de comparar los ángulos en grados a comparar los radianes. Todo el cambio salvó más de 500 caracteres, aunque espero tenerlo todo por debajo de 1000;)
Eliminé los genéricos cuando fue posible y acorté la comparación de retorno creando una matriz de un elemento y verifiqué su valor. También reemplacé el Double.NEGATIVE_INFINITY con PI2 y -PI2 ya que estos son los límites superior e inferior de los ángulos. ¡Ahora finalmente tiene menos de 1000 caracteres!
Fusioné los bucles para encontrar la ubicación de las personas y el iterador del edificio para guardar algunos personajes. Desafortunadamente, esto nos obliga a mover el retorno fuera del ciclo y aún usar un descanso, pero esta vez sin una etiqueta. Fusioné
max
ydistanceSquared
, ymin
, ynewDistanceSquared
, ya que no se requieren al mismo tiempo. He cambiadoInteger.MAX_VALUE
a2e31-1
. También creé una constantehalf = 0.5
que se usa para calcular las esquinas del edificio. Esto es más corto en la versión de golf. ¡En general, salvamos otros 30 caracteres!fuente