Pior caso Exclusão de Manhattan

20

Imagine uma grade de quadrados W por H que envolve toroidalmente. Os itens são colocados na grade da seguinte maneira.

O primeiro item pode ser colocado em qualquer quadrado, mas os itens subsequentes não devem estar a uma distância de Manhattan R de nenhum item anterior (também conhecido como bairro de Von Neumann, no intervalo R ). A escolha cuidadosa das posições permite ajustar um grande número de itens na grade antes que não haja mais posições válidas. No entanto, considere o objetivo oposto: qual é o menor número de itens que podem ser colocados e não deixam mais posições válidas?

Aqui está uma zona de exclusão do raio 5:

Zona de exclusão do raio 5

Aqui está outra zona de exclusão do raio 5, desta vez próxima às bordas, para que o comportamento de quebra seja aparente:

Zona de exclusão do raio de embrulho 5

Entrada

Três inteiros:

  • W : largura da grade (número inteiro positivo)
  • H : altura da grade (número inteiro positivo)
  • R : raio da zona de exclusão (número inteiro não negativo)

Saída

Um número inteiro N , que é o menor número de itens que podem ser colocados, impedindo outros canais válidos.

Detalhes

  • Um raio de zero fornece uma zona de exclusão de 1 quadrado (aquele em que o item foi colocado).
  • Um raio de N exclui a zona que pode ser alcançada em N etapas ortogonais (lembre-se de que as arestas estão dispostas toroidalmente).

Seu código deve funcionar para o caso trivial de R = 0, mas não precisa funcionar para W = 0 ou H = 0.

Seu código também deve lidar com o caso em que R > W ou R > H .

Prazo e casos de teste

Seu código deve poder lidar com todos os casos de teste e cada caso de teste deve ser concluído em 5 minutos. Isso deve ser fácil (a solução JavaScript de exemplo leva alguns segundos para cada caso de teste). O prazo é principalmente para excluir a abordagem de força bruta extrema. A abordagem de exemplo ainda é uma força bastante bruta.

Se o seu código for concluído dentro de 5 minutos em uma máquina, mas não em outra, ela estará próxima o suficiente.

Casos de teste nas entradas do formulário: output asW 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

Snippet para ajudar a visualizar e brincar com idéias

Mostrar snippet de código

Solução de exemplo (não destruída)

Apenas um exemplo para pequenas saídas (resultantes de um raio não muito menor que a largura e a altura). É capaz de lidar com qualquer um dos casos de teste, mas o tempo limite é interrompido e a maioria dos casos maiores.

Mostrar snippet de código

code-golf geometry grid packing Trichoplax
fonte
4
Trecho de código incrível!
Stretch Maniac
@StretchManiac obrigado :) Eu estou tentando aprender JavaScript assim qualquer feedback é bem-vinda
Trichoplax
1
Esse é um trecho bem legal. Eu também gosto desse esquema de cores. É de uma paleta?
milhas
@miles obrigado - as cores são apenas adivinhadas e depois ajustadas um pouco (mas não muito - ainda são todos os códigos de cores com três caracteres em vez de 6). Você pode ver as cores usadas no terceiro bloco de linhas no código do snippet.
Trichoplax

Respostas:

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). Usa praticamente o mesmo algoritmo que da amostra do @ trichoplax , mas com conjuntos. Inicialmente, não coloquei o primeiro item (0, 0), mas isso o fez sufocar nos últimos casos.

Todos os casos acima são concluídos em 10 segundos, bem abaixo do limite. De fato, os casos são pequenos o suficiente para que eu tivesse um pouco de espaço para ser menos eficiente, permitindo remover uma verificação que verificava estados duplicados.

(Obrigado a @trichoplax pela ajuda no golfe)

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
fonte
2

Python 3, 270 262 260 251 246 226

(Obrigado ao Sp3000 por:

  • -~ em vez de +1 , o que me permite perder um espaço depois return na última linha.
  • perdendo parênteses supérfluos ao redor W*H .
  • lambdas ...
  • colocando tudo em uma linha.
  • módulo python %fornece resultado positivo para números negativos, para salvar outros 20 bytes)

Este é o exemplo de resposta em JavaScript da pergunta portada no Python 3.

Para evitar ter que passar tantos argumentos de função, movi as duas funções de suporte dentro da função de cálculo para que elas compartilhem seu escopo. Também condensamos cada uma dessas funções em uma única linha para evitar o custo do recuo.

Explicação

Essa abordagem de força bastante bruta coloca o primeiro item em (0, 0) e marca todos os quadrados excluídos. Em seguida, coloca recursivamente um item em todos os quadrados válidos restantes até que todos os quadrados sejam excluídos e retorna o número mínimo de itens necessários.

Código de golfe:

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 não destruído:

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])))

O código não protegido define uma função e também inclui código para permitir que seja chamado a partir da linha de comando. O código golfed apenas define a função, que é suficiente para perguntas padrão do golf do código .

Se você deseja testar o código de golfe na linha de comando, aqui está o tratamento da linha de comando incluído (mas não no golfe):

Código testável da linha 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
fonte