Peor caso de exclusión de Manhattan

20

Imagine una cuadrícula de cuadrados W por H que se envuelve toroidalmente. Los elementos se colocan en la cuadrícula de la siguiente manera.

El primer elemento se puede colocar en cualquier casilla, pero los elementos posteriores no deben estar dentro de una distancia R de Manhattan de ningún elemento anterior (también conocido como vecindario Von Neumann de rango R ). Elegir cuidadosamente las posiciones permite ajustar una gran cantidad de elementos en la cuadrícula antes de que no haya más posiciones válidas. Sin embargo, considere el objetivo opuesto: ¿Cuál es el menor número de elementos que se pueden colocar y no dejan más posiciones válidas?

Aquí hay una zona de exclusión de radio 5:

Zona de exclusión del radio 5

Aquí hay otra zona de exclusión de radio 5, esta vez cerca de los bordes para que el comportamiento de ajuste sea evidente:

Zona de exclusión del radio de envoltura 5

Entrada

Tres enteros:

  • W : ancho de la cuadrícula (entero positivo)
  • H : altura de la cuadrícula (entero positivo)
  • R : radio de zona de exclusión (entero no negativo)

Salida

Un entero N , que es el número más pequeño de elementos que se pueden colocar, lo que evita cualquier ubicación válida adicional.

Detalles

  • Un radio de cero da una zona de exclusión de 1 cuadrado (en el que se colocó el elemento).
  • Un radio de N excluye la zona que se puede alcanzar en N pasos ortogonales (recuerde que los bordes se envuelven toroidalmente).

Su código debe funcionar para el caso trivial de R = 0, pero no necesita funcionar para W = 0 o H = 0.

El código también debe lidiar con el caso en que R > W o R > H .

Límite de tiempo y casos de prueba

Su código debe poder manejar todos los casos de prueba, y cada caso de prueba debe completarse en 5 minutos. Esto debería ser fácil (la solución de JavaScript de ejemplo tarda unos segundos en cada caso de prueba). El límite de tiempo es principalmente para excluir el enfoque de fuerza bruta extrema. El enfoque de ejemplo sigue siendo la fuerza bruta.

Si su código se completa en 5 minutos en una máquina pero no en otra, estará lo suficientemente cerca.

Casos de prueba en las entradas de formulario: salida comoW H R : N

5 4 4 : 1
5 4 3 : 2
5 4 2 : 2
5 4 1 : 5

7 5 5 : 1
7 5 4 : 2
7 5 3 : 2
7 5 2 : 4

8 8 8 : 1
8 8 7 : 2
8 8 6 : 2
8 8 5 : 2
8 8 4 : 2
8 8 3 : 4

 7  6  4 : 2
 7  6  2 : 4
11  7  4 : 3
11  9  4 : 4
13 13  6 : 3
11 11  5 : 3
15 14  7 : 2
16 16  8 : 2

Fragmento para ayudar a visualizar y jugar con ideas

Mostrar fragmento de código

Solución de ejemplo (sin golf)

Solo un ejemplo para salidas pequeñas (resultantes de un radio no mucho más pequeño que el ancho y la altura). Puede manejar cualquiera de los casos de prueba, pero expirará y se dará por vencido en la mayoría de los casos más grandes.

Mostrar fragmento de código

code-golf geometry grid packing trichoplax
fuente
44
¡Fragmento de código impresionante!
Stretch Maniac
@StretchManiac gracias :) Estoy tratando de aprender JavaScript, así que cualquier comentario es bienvenido
trichoplax
1
Ese es un buen fragmento. También me gusta ese esquema de color. ¿Es de una paleta?
millas
@miles gracias: los colores solo se adivinan y luego se ajustan un poco (pero no mucho; todavía son los códigos de color de 3 caracteres en lugar de 6). Puede ver los colores utilizados en el tercer bloque de líneas en el código de fragmento.
trichoplax

Respuestas:

5

Python 2, 216 182 bytes

def f(W,H,R):L={(i%W,i/W)for i in range(W*H)};M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R};g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1]);return g(M)

Entrada como f(16,16,8). Utiliza prácticamente el mismo algoritmo que la muestra de @ trichoplax , pero con conjuntos. Inicialmente no coloqué el primer elemento (0, 0), pero esto hizo que se ahogara en los últimos casos.

Todos los casos anteriores se completan en 10 segundos, muy por debajo del límite. De hecho, los casos son lo suficientemente pequeños como para tener un poco de espacio para ser menos eficiente, lo que me permite eliminar un cheque que verificó los estados duplicados.

(Gracias a @trichoplax por la ayuda en el golf)

Expandido:

def f(W,H,R):
  # All cells
  L={(i%W,i/W)for i in range(W*H)}                 

  # Mask: Complement of exclusion zone around (0, 0) 
  M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R}

  # Place recursively
  g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1])
  return g(M)
Sp3000
fuente
2

Python 3, 270 262 260 251 246 226

(Gracias a Sp3000 por:

  • -~ en lugar de +1 , lo que me permite perder un espacio después return en la última línea.
  • perdiendo paréntesis superfluos W*H .
  • lambdas ...
  • poniendo todo en una línea.
  • el módulo de Python %da resultados positivos para números negativos, para guardar otros 20 bytes)

Esta es la respuesta de ejemplo de JavaScript de la pregunta portada a Python 3.

Para evitar tener que pasar tantos argumentos de función, he movido las dos funciones de soporte dentro de la función de cálculo para que compartan su alcance. También he condensado cada una de estas funciones en una sola línea para evitar el costo de la sangría.

Explicación

Este enfoque de fuerza bruta coloca el primer elemento en (0, 0) y luego marca todos los cuadrados excluidos. Luego coloca recursivamente un elemento en todos los cuadrados válidos restantes hasta que se excluyan todos los cuadrados, y devuelve el número mínimo de elementos requeridos.

Código de golf:

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

Código sin golf:

def calculate(W, H, R):
    starting_min = W * H + 1
    cells = [0] * (W * H)
    grid_state = grid_with_item_added(cells, 0, 0, W, H, R)
    return min_from_here(grid_state, starting_min, W, H, R) + 1

def min_from_here(grid_state, starting_min, W, H, R):
    no_cells = True
    min = starting_min
    for x in range(W):
        for y in range(H):
            if grid_state[x + W * y] == 0:
                no_cells = False
                new_grid_state = grid_with_item_added(grid_state, x, y, W, H, R)
                m = min_from_here(new_grid_state, starting_min, W, H, R)
                if m < min:
                    min = m

    if no_cells:
        return 0
    else:
        return min + 1

def grid_with_item_added(grid_state, x, y, W, H, R):
    grid = grid_state[:]
    for a in range(W):
        for b in range(H):
            if manhattan_distance(a, b, x, y, W, H) <= R:
                grid[a + W * b] = 1

    return grid

def manhattan_distance(a, b, c, d, W, H):
    horizontal = min(abs(W + c - a) % W, abs(W + a - c) % W)
    vertical = min(abs(H + d - b) % H, abs(H + b - d) % H)
    return horizontal + vertical


if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(calculate(int(arguments[0]), int(arguments[1]), int(arguments[2])))

El código no definido define una función y también incluye código para permitir que se llame desde la línea de comandos. El código de golf solo define la función, que es suficiente para las preguntas de golf de código estándar .

Si desea probar el código de golf desde la línea de comando, aquí está con el manejo de línea de comando incluido (pero no golfizado):

Código de golf comprobable de línea de comando

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(C(int(arguments[0]), int(arguments[1]), int(arguments[2])))
trichoplax
fuente