Dada una lista de círculos, genera el área del rectángulo que contiene el más pequeño

28

Se le dará una lista de radios, debe generar el área del rectángulo más pequeño en el que encajarán todos.

Por ejemplo, dada la lista [5,3,1.5]que generaría 157.460.

Esta es la imagen:

El ancho es 15.7460 y la altura es 10, por lo que el área es 157.460

Reglas:

  • Obtiene la lista a través de stdin o argumento de función, emite la respuesta a través de stdout o retorno de función.

  • Los radios tendrán como máximo 2 decimales.

  • La lista tendrá una longitud entre 2 y 6.

  • La salida debe tener una precisión de 3 decimales o más.

  • Si lo necesita, π = 3.1416.

Casos de prueba:

  • [5,3,1.5] = 157.460

  • [9,4,8,2] = 733.431- trabajando aquí .

  • [18,3,1] = 1296.000

El código más corto en bytes gana.

code-golf math optimization Tim
fuente
Relacionado
DJMcMayhem
1
no veo un criterio ganador objetivo
Maltysen
esa es una de nuestras reglas más centrales
Maltysen
2
@Tim La mayoría son códigos de golf, con el objetivo de codificarlos en la menor cantidad de bytes. Creo que esto sería un buen desafío de código de golf, ya que tiene una especificación exacta.
xnor
Recomiendo deshacerse de la condición "redondeada, no truncada" porque es periférica a la tarea, y algunos idiomas pueden hacerlo, mientras que otros necesitan una codificación adicional para que esto suceda. No estoy seguro de si desea que salga más de 3 decimales, pero sugeriría que también lo permita.
xnor

Respuestas:

16

Python 2 + PySCIPOpt , 267 bytes

from pyscipopt import*
R=input()
m=Model()
V,C=m.addVar,m.addCons
a,b,c=V(),V(),V()
m.setObjective(c)
C(a*b<=c)
P=[]
for r in R:
 x,y=V(),V();C(r<=x);C(x<=a-r);C(r<=y);C(y<=b-r)
 for u,v,s in P:C((x-u)**2+(y-v)**2>=(r+s)**2)
 P+=(x,y,r),
m.optimize()
m.printBestSol()

Cómo funciona

Escribimos el problema de la siguiente manera: minimice c sobre las variables a , b , c , x 1 , y 1 , ..., x n , y n , donde

  • ab ≤ c ;
  • r i ≤ x i ≤ a - r i y r i ≤ y i ≤ b - y i , para 1 ≤ i ≤ n ;
  • ( x i - x j ) 2 + ( y i - y j ) 2 ≥ ( r i + r j ) 2 , para 1 ≤ j < i ≤ n .

Obviamente, estamos utilizando una biblioteca de optimización externa para estas restricciones, pero no puede simplemente alimentarlas a cualquier optimizador antiguo, incluso Mathematica se NMinimizequeda atascado en los mínimos locales para estos pequeños casos de prueba. Si observa atentamente las restricciones, verá que constituyen un programa cuadrático con restricciones cuadráticas , y encontrar el óptimo global para un QCQP no convexo es NP-hard. Así que necesitamos un poco de magia increíblemente poderosa. Elegí el solucionador industrial SCIP , que es el único solucionador global QCQP que pude encontrar con una licencia gratuita para uso académico. Afortunadamente, tiene algunos enlaces Python muy bonitos.

Entrada y salida

Pase la lista de radios en stdin, como [5,3,1.5]. La salida muestra objective value:el área de rectángulo, x1, x2dimensiones rectángulo, x3área rectangular de nuevo, x4, x5primeras coordenadas del centro del círculo, x6, x7segundas coordenadas del centro del círculo, etc.

Casos de prueba

[5,3,1.5] ↦ 157.459666673757

5,3,1.5

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.04
Solving Nodes      : 187
Primal Bound       : +1.57459666673757e+02 (9 solutions)
Dual Bound         : +1.57459666673757e+02
Gap                : 0.00 %
objective value:                     157.459666673757
x1                                                 10   (obj:0)
x2                                   15.7459666673757   (obj:0)
x3                                   157.459666673757   (obj:1)
x4                                                  5   (obj:0)
x5                                                  5   (obj:0)
x6                                                  7   (obj:0)
x7                                   12.7459666673757   (obj:0)
x8                                                1.5   (obj:0)
x9                                   10.4972522849871   (obj:0)

[9,4,8,2] ↦ 709.061485909243

Esto es mejor que la solución del OP. Las dimensiones exactas son 18 por 29 + 6√3.

9,4,8,2

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 1.07
Solving Nodes      : 4650
Primal Bound       : +7.09061485909243e+02 (6 solutions)
Dual Bound         : +7.09061485909243e+02
Gap                : 0.00 %
objective value:                     709.061485909243
x1                                                 18   (obj:0)
x2                                   39.3923047727357   (obj:0)
x3                                   709.061485909243   (obj:1)
x4                                                  9   (obj:0)
x5                                   30.3923047727357   (obj:0)
x6                                                 14   (obj:0)
x7                                   18.3923048064677   (obj:0)
x8                                                  8   (obj:0)
x9                                                  8   (obj:0)
x10                                                 2   (obj:0)
x11                                  19.6154311552252   (obj:0)

[18,3,1] ↦ 1295.999999999

18,3,1

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 13
Primal Bound       : +1.29599999999900e+03 (4 solutions)
Dual Bound         : +1.29599999999900e+03
Gap                : 0.00 %
objective value:                       1295.999999999
x1                                   35.9999999999722   (obj:0)
x2                                                 36   (obj:0)
x3                                     1295.999999999   (obj:1)
x4                                   17.9999999999722   (obj:0)
x5                                                 18   (obj:0)
x6                                   32.8552571627738   (obj:0)
x7                                                  3   (obj:0)
x8                                                  1   (obj:0)
x9                                                  1   (obj:0)

Casos de bonificación

[1,2,3,4,5] ↦ 230.244214912998

1,2,3,4,5

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 401.31
Solving Nodes      : 1400341
Primal Bound       : +2.30244214912998e+02 (16 solutions)
Dual Bound         : +2.30244214912998e+02
Gap                : 0.00 %
objective value:                     230.244214912998
x1                                   13.9282031800476   (obj:0)
x2                                    16.530790960676   (obj:0)
x3                                   230.244214912998   (obj:1)
x4                                                  1   (obj:0)
x5                                   9.60188492354373   (obj:0)
x6                                    11.757778088743   (obj:0)
x7                                   3.17450418828415   (obj:0)
x8                                                  3   (obj:0)
x9                                    13.530790960676   (obj:0)
x10                                  9.92820318004764   (obj:0)
x11                                   12.530790960676   (obj:0)
x12                                                 5   (obj:0)
x13                                                 5   (obj:0)

[3,4,5,6,7] ↦ 553.918025310597

3,4,5,6,7

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 90.28
Solving Nodes      : 248281
Primal Bound       : +5.53918025310597e+02 (18 solutions)
Dual Bound         : +5.53918025310597e+02
Gap                : 0.00 %
objective value:                     553.918025310597
x1                                   21.9544511351279   (obj:0)
x2                                   25.2303290086403   (obj:0)
x3                                   553.918025310597   (obj:1)
x4                                                  3   (obj:0)
x5                                   14.4852813557912   (obj:0)
x6                                   4.87198593295855   (obj:0)
x7                                   21.2303290086403   (obj:0)
x8                                   16.9544511351279   (obj:0)
x9                                                  5   (obj:0)
x10                                                 6   (obj:0)
x11                                                 6   (obj:0)
x12                                  14.9544511351279   (obj:0)
x13                                  16.8321595389753   (obj:0)

[3,4,5,6,7,8] ↦ 777.87455544487

3,4,5,6,7,8

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 218.29
Solving Nodes      : 551316
Primal Bound       : +7.77874555444870e+02 (29 solutions)
Dual Bound         : +7.77874555444870e+02
Gap                : 0.00 %
objective value:                      777.87455544487
x1                                   29.9626413867546   (obj:0)
x2                                   25.9614813640722   (obj:0)
x3                                    777.87455544487   (obj:1)
x4                                   13.7325948669477   (obj:0)
x5                                   15.3563780595534   (obj:0)
x6                                   16.0504838821134   (obj:0)
x7                                   21.9614813640722   (obj:0)
x8                                   24.9626413867546   (obj:0)
x9                                   20.7071098175984   (obj:0)
x10                                                 6   (obj:0)
x11                                  19.9614813640722   (obj:0)
x12                                                 7   (obj:0)
x13                                                 7   (obj:0)
x14                                  21.9626413867546   (obj:0)
x15                                  8.05799919177801   (obj:0)
Anders Kaseorg
fuente
Es una pena que el último dé un pequeño error de redondeo, ¡pero buen trabajo!
Tim
Me parece que [1, 2, 3, 4, 5] podría mejorarse haciendo que los círculos del radio 3 y del radio 5 se toquen también, luego girando el radio 4 / radio 5 diagonalmente en sentido horario (el círculo del radio 1 debería se puede sacar del camino pero hay mucho espacio muerto para eso. Tanto mi instinto como mis cálculos indican que un rectángulo largo y delgado puede contener los círculos de radio 4 / radio 5 de manera más eficiente que uno más cuadrado.
Level River St
@LevelRiverSt No estoy de acuerdo. Mover 3 hacia arriba para tocar 5 empujaría a 4 hacia la derecha (en sentido antihorario desde 5), no lo dejaría moverse hacia la izquierda (en sentido horario desde 5). La configuración de mi programa es (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13.9282 × 16.5308 ≈ 230.244, mientras que su configuración sugerida es (30 + 15√3) / 4 × (36 + 3 √5 + 6√15) / 4 ≈ 13.9952 × 16.4865 ≈ 230.732.
Anders Kaseorg