Trouvez le tas de sable d'identité

18

Cette question concerne les tas de sable abéliens . Lisez ce défi précédent et regardez cette vidéo numérotée pour en savoir plus.


Un tas de sable abélien de taille n par n est une grille contenant le nombre 0, 1, 2 et 3 (représentant le nombre de grains de sable). L'ajout de deux tas de sable fonctionne en ajoutant d'abord élément par élément, puis en renversant tout élément supérieur à 3. L'ordre dans lequel vous basculez n'a pas d'importance, le résultat final est le même. Lorsqu'une cellule bascule, son nombre diminue de 4 et chacun de ses voisins directs augmente de 1. Cela peut provoquer une réaction en chaîne. Si une cellule se trouve au bord de la grille, tous les grains qui tombent de la grille pendant le basculement disparaissent.

Par exemple, j'ajoute deux tas de sable 3 par 3 (donnant une réaction en chaîne plutôt extrême):

3 3 3   1 2 1   4 5 4    4 6 4    6 2 6    6 3 6    2 5 2    4 1 4    4 2 4    0 4 0    2 0 2    2 1 2
3 3 3 + 2 1 2 = 5 4 5 -> 6 0 6 -> 2 4 2 -> 3 0 3 -> 5 0 5 -> 1 4 1 -> 2 0 2 -> 4 0 4 -> 0 4 0 -> 1 0 1
3 3 3   1 2 1   4 5 4    4 6 4    6 2 6    6 3 6    2 5 2    4 1 4    4 2 4    0 4 0    2 0 2    2 1 2

Dans ce défi, nous nous intéressons à un sous-ensemble de tous les tas de sable n par n possibles. Ce sous - ensemble contient des tas de sable que vous pouvez obtenir en ajoutant un tas de sable arbitraire aux tous-3 n par n sandpile. Par exemple, juste au-dessus, nous avons vu que212 | 101 | 212 c'est dans le sous-ensemble, parce que nous l'avons obtenu en ajoutant quelque chose au tas de sable tous-3.

Maintenant, ce sous-ensemble a un élément intéressant: l' élément d' identité . Si vous prenez cet élément et l'ajoutez à tout autre élément du sous - ensemble , la somme reste inchangée. En d'autres termes, ce tas de sable agit comme un zéro de ce sous-ensemble. Il se trouve que 212 | 101 | 212c'est l'élément zéro pour le sous-ensemble de 3 par 3. Par exemple:

2 2 2   2 1 2   4 3 4    0 5 0    2 1 2    2 2 2
2 2 2 + 1 0 1 = 3 2 3 -> 5 2 5 -> 1 6 1 -> 2 2 2
2 2 2   2 1 2   4 3 4    0 5 0    2 1 2    2 2 2

Maintenant, c'est votre défi: étant donné n , trouvez l'élément d'identité du sous-ensemble de la grille n par n . Sortez-le en attribuant une couleur unique avec un contraste suffisant de votre choix à chacun 0, 1, 2, 3et en sortant une image n par n. Votre code doit pouvoir produire le boîtier 50 x 50 en moins d'une minute sur un PC moderne et raisonnable.


Par exemple, l'élément d'identité 500 x 500:

Élément d'identité 500 par 500

Voici bleu = 3, vert = 2, rouge = 1, blanc = 0. Mais vous n'avez pas à utiliser ce schéma de couleurs dans votre réponse.

orlp
la source
2
Un mot d'avertissement aux concurrents: j'ai décrit quelle est la solution, pas comment la calculer. Votre code doit être capable de produire le boîtier 50 x 50 en moins d'une minute, donc le forçage brut n'est pas une possibilité. Il existe des algorithmes pour résoudre ce problème, et je ne vous les donne pas. C'est intentionnel. Je pense que trop de défis vous présentent des aliments pré-mâchés. Je donnerai une prime de +100 à la première réponse qui ne banalise pas le problème avec un intégré (en vous regardant, Mathematica), à ma discrétion.
orlp
2
Je pense que l'image de l'identité 500x500 gagnerait à dire à quel nombre chaque couleur correspond.
xnor
Qu'est-ce qui constitue un "contraste suffisant"?
Conor O'Brien
@ ConorO'Brien Tout ensemble de couleurs suffisamment distinctes. Je pourrais le rendre objectif à 100% avec une certaine mesure de couleur, mais je pense que c'est exagéré. Peu m'importe si vous utilisez du rouge, du jaune, du vert, des niveaux de gris ou autre, n'utilisez simplement pas 4 nuances de gris à moins de 1% l'une de l'autre (comme # 000000, # 000001, # 000002, # 000003).
orlp
ahem je crois que cette question est maintenant éligible pour la prime. Puis-je obtenir le bonus +100? :)
JungHwan Min

Réponses:

2

Octave, 120 113 octets

function a=W(a);while nnz(b=a>3);a+=conv2(b,[t=[0 1 0];!t;t],'same')-b*4;end;end;@(n)imagesc(W((x=ones(n)*6)-W(x)))

Merci à JungHwan Min d' avoir fourni un lien vers le document de référence dans sa réponse Mathematica.
Merci à Stewie Griffin m'a sauvé 7 octets[any(any(x)) -> nnz(x)]

Ici, deux fonctions sont utilisées:

1 f.: pour stabiliser une matrice
2. Une fonction anonyme qui prend nen entrée et montre la matrice d'identité.

Essayez-le sur rextester! pour la génération d'une matrice 50 * 50

Le temps écoulé pour le calcul de la matrice: 0.0844409 seconds.

Explication:

Considérons une fonction f qui stabilise une matrice, la tâche de trouver l'identité est simplement

f(ones(n)*6 - f(ones(n)*6).

cela ones(n)*6signifie une matrice * n de 6.

donc pour n=3:

M = [6 6 6
     6 6 6
     6 6 6];

Le résultat sera f(M-f(M))

Pour la fonction de stabilisation Convolution 2D utilisée pour accélérer la tâche; Dans chaque itération, nous créons une matrice binaire bavec la même taille de la matrice d'entrée et la mettons à 1 si l'élément correspondant de la matrice d'entrée est> 3. Ensuite, nous appliquons une convolution 2D de la matrice binaire avec le masque suivant

0 1 0
1 0 1
0 1 0

représentant quatre voisins directs.
Le résultat de la convolution est ajouté à la matrice et 4 fois la matrice binaire en est soustraite.

La boucle s'est poursuivie jusqu'à ce que tous les éléments de la matrice soient <= 3

Version non golfée :

function a=stabilize(a)
    mask = [t=[0 1 0];!t;t];
    while any(any(b=a>3))
        a+=conv2(b,mask,'same')-b*4;
    end
end
n= 50;
M = ones(n)*6;
result = stabilize(M-stabilize(M));
imagesc(result);
rahnema1
la source
8

Mathematica, 177 157 135 135 133 octets

Colorize[f=BlockMap[⌊{l={0,1,0},1-l,l}#/4⌋~Total~2+#[[2,2]]~Mod~4&,#~ArrayPad~1,{3,3},1]&~FixedPoint~#&;k=Table[6,#,#];f[k-f@k]]&

Prend un certain nombre n . La sortie est le tas de sable d'identité. 0 est noir, 1 est gris clair, 2 est magenta et 3 est bleu-gris.

Malheureusement, Mathematica n'a pas de fonction intégrée pour cela ...

Utilise l'algorithme indiqué dans l'article de Scott Corry et David Perkinson .

Prend 91,7 secondes sur mon ordinateur portable de 5 ans pour calculer le tas de sable d'identité 50x50. Je suis convaincu qu'un ordinateur de bureau moderne et raisonnable est plus de 50% plus rapide. (J'ai aussi un code beaucoup plus rapide à la fin).

Explication

f= ...

Définir une fonction f(l'entrée est une matrice de tas de sable): une fonction qui ...

BlockMap[ ... ]~FixedPoint~#&

... répète l' BlockMapopération jusqu'à ce que la sortie ne change pas. BlockMapopération: ...


#~ArrayPad~1

... remplir le tableau d'entrée avec une couche de 0 ...

{3,3},1

... le partitionner en matrices 3x3, avec décalage 1 ...

⌊{l={0,1,0},1-l,l}#/4⌋~Total~2+#[[2,2]]~Mod~4&

... et pour chaque partition, ajoutez le nombre de grains de sable renversés sur la cellule centrale et la valeur de la cellule centrale mod 4.

c'est-à-dire que la sortie de fest la version stabilisée de l'entrée.


k=Table[6,#,#]

Définissez kcomme un tableau n par n de 6s.

f[k-f@k]]

Calculez f (k - f (k)).

Colorize[ ... ]

Appliquez des couleurs au résultat.

Version plus rapide (142 octets)

Colorize[r=RotateLeft;a=ArrayPad;f=a[b=#~a~1;b+r[g=⌊b/4⌋,s={0,1}]+g~r~-s+r[g,1-s]+r[g,s-1]-4g,-1]&~FixedPoint~#&;k=Table[6,#,#];f[k-f@k]]&

Même code, mais utilise la rotation de liste intégrée au lieu de BlockMap. Calcule n = 50 en 4,0 secondes sur mon ordinateur portable.

JungHwan Min
la source
Étant donné que vous avez respecté l'esprit de la limite de temps (implémenter un algorithme réel plutôt que la force brute), et qu'il est très plausible qu'un ordinateur de bureau puissant soit 50% plus rapide, je le permettrai. Puisqu'il implémente un algorithme réel sans intégré banalisant, cela se qualifie pour le bonus de +100. Vous devrez cependant l'attendre, car je ne peux pas encore commencer de prime.
orlp
Cela étant dit, l'implémentation de cette fonction de manière assez triviale en Python (un langage notoirement lent) ne prend que 2 secondes pour n = 50. Peut-être pouvez-vous accélérer un peu?
orlp
@orlp Terminé, mais il est plus long que le code d'origine. Dois-je faire de la version plus rapide ma réponse principale ou puis-je simplement la mettre à la fin?
JungHwan Min
Comme c'est bien je pense.
orlp
0

Python 3 + Numpy + PIL, 385 370 364 octets

import numpy as q,PIL.Image as w
n=int(input())
z=n,n
def r(p):
 while len(p[p>3]):
  for x,y in q.ndindex(z):
   if p[x,y]>3:
    p[x,y]-=4;p[x-1,y]+=x>0;p[x,y-1]+=y>0
    if~-n>x:p[x+1,y]+=1
    if~-n>y:p[x,y+1]+=1
s=q.full(z,6)
t=s.copy()
r(t)
i=s-t
r(i)
w.fromarray(q.uint8(q.array(q.vectorize(lambda x:[x//1*65]*3,otypes=[object])(i).tolist()))).save('i.png')

Prend entrée sur STDIN. Sort l'image en niveaux de gris vers i.png. Le noir correspond à 0, le gris foncé à 1, le gris clair à 2 et le blanc à 0.

Utilise la formule I = R(S - R(S)), où Iest l'élément d'identité, Sla matrice remplie de six et Rla fonction de réduction.

Je pourrais probablement économiser quelques octets en passant à Python 2 et en le faisant from numpy import*, mais (1) je n'ai pas installé Numpy sur Python 2 et (2) le programme ne se terminait pas avec from numpy import*.

Non golfé:

import numpy as np
from PIL import Image

# Compute the identity element

n = int(input('Size of the sandpile: '))

def reduce_pile(sandpile):
  while any(element >= 4 for element in np.nditer(sandpile)):
    for x, y in np.ndindex((n, n)):
      if sandpile[x, y] >= 4:
        sandpile[x, y] -= 4
        if x > 0: sandpile[x - 1, y] += 1
        if y > 0: sandpile[x, y - 1] += 1
        if x < n - 1: sandpile[x + 1, y] += 1
        if y < n - 1: sandpile[x, y + 1] += 1

s = np.full((n, n), 6, dtype=np.int32)
s_prime = np.copy(s)

reduce_pile(s_prime)

identity = s - s_prime
reduce_pile(identity)

# Output it to identity.png as an image

colours = [[255, 255, 255], [255, 0, 0], [0, 255, 0], [0, 0, 255]]
img_array = np.vectorize(lambda x: colours[x], otypes=[object])(identity)
img_array = np.array(img_array.tolist(), dtype=np.uint8)

img = Image.fromarray(img_array)
img.save('identity.png')
Cuivre
la source
Vous pourrez peut-être enregistrer des octets en utilisant scipyou matplotlibpour afficher les données plutôt que de générer une image explicitement avec PIL.
orlp