Ladrillos y estabilidad definidos
Esta pregunta utiliza la misma definición de ladrillos y estabilidad que ¿Es estable la estructura de ladrillos?
Deje [__]representar un ladrillo de mampostería y
.
.
.
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
representan una disposición o estructura arbitraria de estos ladrillos, con cada otra fila compensada por medio ladrillo, como es habitual en la construcción de ladrillos. La estructura puede extenderse indefinidamente hacia arriba y hacia la derecha, pero la representación de cadena siempre será un bloque de texto perfectamente rectangular (con espacios finales cuando sea necesario) cuyo ancho es divisible por 4.
Cada uno BRK?en la estructura puede ser un ladrillo ( [__]) o un espacio vacío (4 espacios).
Por ejemplo, una estructura posible (inestable - sigue leyendo) es
[__] [__] [__]
[__] [__]
[__][__] [__]
La estabilidad de una estructura es importante, y una estructura solo es estable si cada uno de sus ladrillos es estable.
Hay tres formas en que un ladrillo individual puede ser estable:
- Cualquier ladrillo en el suelo (la línea más baja de ladrillos) es estable.
Cualquier ladrillo que tenga dos ladrillos directamente debajo es estable:
[__] <- this brick is stable [__][__] <- because these bricks hold it upCualquier ladrillo que tenga un ladrillo encima y debajo del mismo lado es estable:
[__] [__] [__] [__] <- these middle bricks are stable [__] [__] because the upper and lower bricks clamp them in [__] [__] [__] [__] <- these middle bricks are NOT stable [__] [__]
(Sí, sé que estas reglas no son físicamente precisas).
El último desafío fue determinar si una estructura era estable. Este se trata de estabilizar a los que no lo son.
Desafío
Escriba un programa que tome una disposición de ladrillos potencialmente inestable y agregue nuevos ladrillos en espacios de ladrillos vacíos para que todo sea estable e imprima el resultado. Esto debe hacerse sin aumentar las dimensiones generales del bloque de texto de entrada.
El objetivo es crear un algoritmo que estabilice la estructura agregando la menor cantidad posible de ladrillos.
Este JSFiddle ( fuente ) le permite generar arreglos aleatorios de ladrillos para usar mientras prueba su programa. (Ojalá pudiera apilar fragmentos en su lugar). WidthEs la cantidad de ladrillos en la capa base, Heightes la cantidad de capas de ladrillos y Densityes la fracción de espacios de ladrillo rellenos.
Por ejemplo, con Width = 5, Height = 3, Density = 0.6una salida posible es
....[__]....[__]....
..[__]....[__]......
[__]............[__]
Una forma de estabilizar esto con 4 ladrillos nuevos es
....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]
Su programa debe poder estabilizar cualquier estructura de ladrillo que pueda generar JSFiddle.
- Esto incluye la cadena vacía (que se considera estable).
- El ladrillo siempre lo será
[__]. Los períodos (.) solo se usan para mayor claridad. Su programa puede usar puntos o espacios para espacios vacíos. - Es posible que la estructura ya sea estable, en cuyo caso no es necesario hacer nada (además de imprimirla).
- El JSFiddle siempre genera estructuras que pueden estabilizarse (evitando
Width = 1y ladrillos en las esquinas superiores). Puedes confiar en esto. (Llenar todas las esquinas, excepto las superiores, seguramente estabilizará las cosas, pero esto claramente no es óptimo). - Suponga que no hay entrada no válida. Toma la entrada como cadena como quieras. Imprima la estructura estabilizada en stdout o similar.
- Recuerde que las dimensiones del bloque de texto no deberían cambiar de tamaño.
- Los ladrillos preexistentes no se pueden mover ni quitar. La colocación de nuevos ladrillos debe seguir el patrón de cuadrícula offset-every-other-row. Todos los ladrillos deben estar completamente dentro de los límites.
- Se recomienda (pero no es obligatorio) que imprima los ladrillos preexistentes en
[XX]lugar de hacerlo[__], para que las personas puedan ver mejor cómo funciona su solución.
Puntuación
En la parte inferior del JSFiddle hay 8 arreglos de ladrillos inestables predefinidos. (Ellos usan [__]y .y deben permanecer de esa manera a menos que esté utilizando [XX]y / o en su lugar.) Algunos son aleatorios y algunos me crean a mí mismo. Para calcular su puntaje, ejecute su programa en cada uno de ellos y sume el número de ladrillos nuevos agregados a cada uno.
Cuantos menos ladrillos nuevos haya agregado, mejor. La presentación con la puntuación más baja gana. En caso de empate, la respuesta más antigua gana.
Si las cosas se ponen polémicas, puedo agregar algunos casos más predefinidos y juzgar al ganador según ellos.
Notas adicionales
- Su programa debe ejecutarse en el orden de minutos en una computadora moderna para un ancho de cuadrícula de ladrillo y una altura inferior a 100 (máximo 10 minutos en una computadora como esta ).
- No puede codificar su salida para las 8 estructuras predefinidas. Su programa debe tratarlos como trataría cualquier otro arreglo.
- Incluya un resultado de ejemplo o dos, o cualquier estructura interesante que le gustaría compartir. :)
- Este problema está algo relacionado con la búsqueda de un árbol de expansión mínimo .
fuente
Respuestas:
Java - 5.056 ladrillos
El código fuente se puede ver aquí .
El código se ejecuta en unos pocos milisegundos para cualquiera de las 8 entradas de puntuación. Hay algunas salidas notablemente subóptimas, particularmente en la torre entrecruzada y en los casos de 99x99. Tengo varias ideas sobre cómo mejorar la rutina, pero es bastante voluminosa como está y, por lo tanto, lo dejaré solo por ahora.
Las salidas masacran las leyes de la física hasta un punto cómico. :RE
Algunas muestras se muestran a continuación.
20x20, salida 0.03
Salida de casa simple
fuente
Pitón, 18992
Esta es la solución más simplista y la peor puntuación posible. Es solo para referencia; Lo que hay que vencer. Llena cada espacio vacío, excepto las dos esquinas superiores con ladrillos, lo que garantiza la estabilidad.
Para usar, copie la estructura inicial en las comillas triples en la parte superior del programa.
Aquí se ejecuta en la casa, agregando 609 ladrillos:
La cantidad de ladrillos que agrega para cada una de las 8 estructuras predefinidas en orden es
fuente