Pire exclusion de Manhattan

20

Imaginez une grille de carrés W par H qui s'enroule toroïdalement. Les éléments sont placés sur la grille comme suit.

Le premier élément peut être placé sur n'importe quelle case, mais les éléments suivants ne doivent pas être à une distance Manhattan R de tout élément précédent (également connu sous le nom de quartier Von Neumann de la gamme R ). Le choix judicieux des positions permet de placer un grand nombre d'articles sur la grille avant qu'il n'y ait plus de positions valides. Cependant, considérez plutôt l'objectif inverse: quel est le plus petit nombre d'articles pouvant être placés et ne laisser aucune autre position valide?

Voici une zone d'exclusion de rayon 5:

Zone d'exclusion Radius 5

Voici une autre zone d'exclusion de rayon 5, cette fois près des bords, donc le comportement d'enveloppement est apparent:

Rayon d'emballage 5 zone d'exclusion

Contribution

Trois entiers:

  • W : largeur de la grille (entier positif)
  • H : hauteur de la grille (entier positif)
  • R : rayon de la zone d'exclusion (entier non négatif)

Production

Un entier N , qui est le plus petit nombre d'éléments pouvant être placés, empêchant tout autre placement valide.

Détails

  • Un rayon de zéro donne une zone d'exclusion de 1 carré (celle sur laquelle l'objet a été placé).
  • Un rayon de N exclut la zone qui peut être atteinte en N pas orthogonaux (rappelez-vous que les bords s'enroulent toroïdalement).

Votre code doit fonctionner pour le cas trivial de R = 0, mais n'a pas besoin de fonctionner pour W = 0 ou H = 0.

Votre code doit aussi faire face au cas où R > W ou R > H .

Délai et cas de test

Votre code doit être capable de gérer tous les cas de test, et chaque cas de test doit se terminer dans les 5 minutes. Cela devrait être facile (l'exemple de solution JavaScript prend quelques secondes pour chaque cas de test). La limite de temps est principalement d'exclure l'approche extrême de la force brute. L'exemple d'approche est encore assez brutal.

Si votre code se termine dans les 5 minutes sur une machine mais pas sur une autre, ce sera assez proche.

Cas de test sous la forme entrées: sortie en tant queW 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

Extrait pour aider à visualiser et à jouer avec les idées

Afficher l'extrait de code

Exemple de solution (non golfée)

Juste un exemple pour les petites sorties (résultant d'un rayon pas beaucoup plus petit que la largeur et la hauteur). Peut gérer n'importe lequel des cas de test, mais expirera et abandonnera pour la plupart des cas plus grands.

Afficher l'extrait de code

code-golf geometry grid packing trichoplax
la source
4
Extrait de code génial!
Stretch Maniac
@StretchManiac merci :) J'essaie d'apprendre JavaScript, donc tout commentaire est le bienvenu
trichoplax
1
C'est un très bel extrait. J'aime aussi cette palette de couleurs. Est-ce d'une palette?
miles
@miles merci - les couleurs sont juste devinées puis affinées un peu (mais pas beaucoup - ce sont toujours les codes de couleur à 3 caractères plutôt que 6). Vous pouvez voir les couleurs utilisées dans le troisième bloc de lignes du code d'extrait.
trichoplax

Réponses:

5

Python 2, 216 182 octets

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)

Entrez comme f(16,16,8). Utilise à peu près le même algorithme que l'échantillon de @ trichoplax , mais avec des ensembles. Au début, je n'ai pas placé le premier élément sur (0, 0), mais cela l'a étranglé dans les derniers cas.

Tous les cas ci-dessus se terminent en 10 secondes, bien en dessous de la limite. En fait, les boîtiers sont suffisamment petits pour que j'avais un peu de place pour être moins efficace, ce qui me permet de supprimer un chèque qui vérifiait les états en double.

(Merci à @trichoplax pour son aide au golf)

Étendu:

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
la source
2

Python 3, 270 262 260 251 246 226

(Merci à Sp3000 pour:

  • -~ au lieu de +1 , ce qui me permet de perdre un espace après return sur la dernière ligne.
  • perdre des parenthèses superflues autour W*H .
  • lambdas ...
  • mettre tout sur une seule ligne.
  • python modulo %donne un résultat positif pour les nombres négatifs, pour économiser encore 20 octets)

Il s'agit de l'exemple de réponse JavaScript de la question portée dans Python 3.

Pour éviter d'avoir à passer autant d'arguments de fonction, j'ai déplacé les deux fonctions de support à l'intérieur de la fonction de calcul afin qu'elles partagent sa portée. J'ai également condensé chacune de ces fonctions en une seule ligne pour éviter le coût de l'indentation.

Explication

Cette approche assez brutale place le premier élément à (0, 0), puis marque tous les carrés exclus. Il place ensuite récursivement un élément sur tous les carrés valides restants jusqu'à ce que tous les carrés soient exclus et renvoie le nombre minimum d'éléments requis.

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

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

Le code non golfé définit une fonction et inclut également du code pour lui permettre d'être appelé à partir de la ligne de commande. Le code golfé définit simplement la fonction, ce qui est suffisant pour les questions de golf de code standard .

Si vous souhaitez tester le code golfé à partir de la ligne de commande, le voici avec la gestion de la ligne de commande incluse (mais pas golfée):

Code golfable testable en ligne de commande

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
la source