Kipp den Sandhaufen um

12

(Es gibt verwandte Fragen zu unendlichen Sandhaufen und zum Auffinden von Identitätselementen von Sandhaufen .)

Bei einer Matrix nicht negativer Ganzzahlen geben Sie eine Matrix mit den gleichen Dimensionen zurück, die jedoch gestürzt wurde :

  1. Wenn die Matrix keine Werte größer als 4 enthält, geben Sie sie zurück.
  2. Jede "Zelle", die größer als 3 ist, wird um 4 verringert, und alle direkt benachbarten Zellen (oben, unten, links und rechts) werden inkrementiert, falls vorhanden.
  3. GOTO 1.

Beispiele:

0 1 0        0 2 0
2 4 0   ->   3 0 1
0 0 3        0 1 3

1 2 3    2 3 4    2 5 1    4 1 2    0 3 3    0 3 3    0 3 3
4 5 6 -> 2 4 4 -> 4 2 3 -> 0 5 4 -> 3 2 1 -> 3 3 1 -> 3 3 2
7 8 9    5 7 7    2 6 5    4 3 2    0 5 3    1 1 4    1 2 0

(Sie müssen nur das Endergebnis zurückgeben. Der Pfad, auf dem Sie es erreichen, kann sich von dem hier gezeigten unterscheiden: Es spielt keine Rolle, in welcher Reihenfolge Sie die Sturzoperationen ausführen, sie führen alle zum gleichen Ergebnis.)

Für eine tiefere Erklärung und eine gewisse Motivation siehe dieses Numberphile-Video oder den Wikipedia-Artikel über das abelsche Sandpile-Modell .

Regeln:

  • Sie können die Ein- und Ausgabe auf eine der Standardmethoden vornehmen
  • Lücken sind verboten
  • Input und Output können sein:
    • eine verschachtelte Liste: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    • eine einfache Liste: [1, 2, 3, 4, 5, 6, 7, 8, 9]und die Form
    • eine Art nativer Matrixtyp
    • eine Zeichenfolge, z 1 2 3\n4 5 6\n7 8 9
    • oder was sonst noch in deiner Sprache funktioniert.
  • Eingabe und Ausgabe müssen in derselben Form vorliegen
  • Die Eingabe kann größere Zahlen als die hier gezeigten enthalten, die Größe ist jedoch möglicherweise an die Grenzen Ihrer Sprache gebunden (ggf. MAXINT-Äquivalente).
  • Die Matrix kann eine beliebige Form haben (zB 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
  • Sie müssen den Fall nicht behandeln, in dem die Form 0xN oder Nx0 ist.

Testfälle

[[2, 5, 4], [8, 6, 4], [1, 2, 3]] -> [[3, 3, 0], [1, 2, 2], [1, 3, 2]]
[[0, 0, 2], [1, 3, 3], [0, 0, 0]] -> [[0, 0, 2], [1, 3, 3], [0, 0, 0]]
[[9, 9, 9], [9, 9, 9], [9, 9, 9]] -> [[1, 3, 1], [3, 1, 3], [1, 3, 1]]
[[4, 5], [2, 3]] -> [[2, 3], [0, 1]]
[[2, 3, 5], [2, 2, 0]] -> [[3, 0, 2], [2, 3, 1]]
[[7]] -> [[3]]

Dies ist , der kürzeste Code (pro Sprache) gewinnt.

L3viathan
quelle
Ist es in Ordnung, alle Zwischenergebnisse anzuzeigen?
Feersum
@feersum Ich denke schon, solange klar ist, was das Endergebnis ist.
L3viathan

Antworten:

8

MATL , 17 Bytes

tss:"t3>t1Y6Z+w4*-+

Probieren Sie es bei MATL Online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Das Programm iteriert so oft wie die Summe der Eingaben. Dies ist eine lockere Obergrenze für die erforderliche Anzahl von Iterationen.

Bei jeder Iteration werden Einträge in der Sandpile-Matrix, die überschritten 3werden, erkannt, was eine Matrix von 1und 0ergibt, die mit der 4-Nachbarn-Maske gefaltet wird. Die 3in der Sandpile-Matrix übersteigenden Einträge werden um reduziert 4, und das Ergebnis der Faltung wird addiert.

Bei den letzten Iterationen, bei denen die Sandpile-Matrix keine Zahlen übersteigt 3, werden Nullen abgezogen und hinzugefügt, sodass sie nicht betroffen sind.

t       % Implicit input (matrix). Duplicate
ss      % Sum of matrix entries
:"      % Repeat that many times
  t     %   Duplicate
  3>    %   True for matrix entries that exceed 3
  t     %   Duplicate
  1Y6   %   Push predefined literal [0, 1, 0; 1, 0, 1; 0, 1, 0]
  Z+    %   2D convolution, keeping size
  w     %   Swap
  4*    %   Multiply by 4
  -     %   Subtract
  +     %   Add
        % Implicit end. Implicit display
Luis Mendo
quelle
3
Faltung hoch fünf.
Martin Ender
@MartinEnder Ah, das hast du auch genutzt :-) Schön, einen Mitstreiter zu sehen! Ich bin sicher, Flawr wird bald zu uns stoßen
Luis Mendo
2
@ LuisMendo Convolutionista
Suever
4

Mathematica, 65 Bytes

#//.s_:>s+ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]-4x&

Erläuterung

#//.s_:>...&

Transformieren Sie die Eingabe wiederholt, indem Sie alle Stapel größer als 3 stürzen. Dieser Vorgang stoppt automatisch, wenn die Transformation die Matrix nicht ändert (dh wenn keine großen Stapel mehr vorhanden sind). Im folgenden Ausdruck wird die Matrix aufgerufen s.

...x=UnitStep[s-4]...

Erstellen Sie eine Matrix mit einer, 1wenn die aktuelle Matrix eine 4oder mehr und andernfalls eine Null aufweist. Dies ist im Wesentlichen eine Maske, die angibt, welche Stapel gestürzt werden müssen. Nenne die Maske x.

ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]

Zuerst berechnen wir die Anzahl der Sande, die aufgrund umgestürzter benachbarter Pfähle zu jedem Pfahl hinzugefügt werden. Dies geschieht mit einer Faltung der folgenden Matrix über x:

0 1 0
1 0 1
0 1 0

Im Wesentlichen wird für jeden von-Neumann-Nachbarn in der Maske eine Zelle zur aktuellen Zelle hinzugefügt.

s+...-4x

Wir addieren das vorherige Ergebnis sund subtrahieren dann das Vierfache der Maske, um die umgestürzten Stapel zu reduzieren.

Martin Ender
quelle
3

Oktave, 65 Bytes

Das scheint nicht sehr gut zu sein, ich muss ein paar Tricks verpassen ...

m=input(0);do;m+=conv2(m>3,[0 1 0;1 -4 1;0 1 0],"same")
until m<4
Feersum
quelle
Welche Version von Octave benutzt du, die erlaubt input(0)?
Suever
@ Suever>> version ans = 4.0.1
feersum
2

JavaScript (ES6), 101 bis 95 Byte

Nimmt die Breite der Matrix wund ein Array von Werten ain der aktuellen Syntax an (w)(a). Gibt ein Array von Werten zurück.

w=>g=a=>(b=a.map((n,i)=>n%4+(F=d=>~m|i%w&&a[i+d]>>2)(m=w)+F(-w)+F(m=-1)+F(!++i)))+0==a+0?a:g(b)

Formatiert und kommentiert

w =>                      // main function: takes w as input, returns g
  g = a =>                // recursive function g: takes a as input
    (                     //
      b = a.map((n, i) => // for each element n at position i in a:
        n % 4 + (         //   keep only n MOD 4
          F = d =>        //   define F(): function that takes d as input
            ~m |          //     if m is not equal to -1
            i % w &&      //     or i MOD w is not null:
            a[i + d] >> 2 //       return a fourth of the value of the cell at i + d
        )(m = w) +        //   test the cell below the current cell
        F(-w) +           //   test the cell above
        F(m = -1) +       //   test the cell on the left
        F(!++i)           //   test the cell on the right
      )                   // end of map(): assign the result to b
    ) + 0 == a + 0 ?      // if b is equal to a:
      a                   //   stop recursion and return a
    :                     // else:
      g(b)                //   do a recursive call with b

Testfälle

Arnauld
quelle
1

JavaScript (ES6), 118 114 104 Byte

2 Bytes dank @Neil gespeichert

f=a=>a.find(b=>++y&&b.find(c=>++x&&c>3,x=0),y=0)?f(a.map(b=>b.map(c=>c+=--i|y?i*i+y*y==1:-4,i=x,--y))):a
ETHproductions
quelle
Hilft das (i-=x)|y-j?i*i+?
Neil
@Neil Tut es ja, danke!
ETHproductions
... Ich war am Telefon, habe aber auch darüber nachgedacht a.find(...b.find(...c>3&&a.map(...)))&&f(a).
Neil
@Neil Ich glaube nicht, dass das funktionieren würde, da .mapnicht mutiert ...
ETHproductions
Es scheint, dass es etwas weniger kostet, es zu verändern, als die Karte innerhalb des Funds zu verschieben:f=a=>a.find((b,x)=>b.find((c,y)=>c>3&&a.map(b=>b.map((_,j)=>b[j]+=x|(j-=y)?x*x+j*j==1:-4)&x--)))&&f(a)
Neil,
1

C ++, 261 258 250 Bytes

#import<vector>
#define S size()
void f(std::vector<std::vector<int>>&m){s:int i,j,r;for(i=r=0;i<m.S;++i)for(j=0;j<m[i].S;++j){if(m[i][j]>3){r=1;m[i][j]-=4;j>0&&m[i][j-1]++;i>0&&m[i-1][j]++;j<m[i].S-1&&m[i][j+1]++;i<m.S-1&&m[i+1][j]++;}}if(r)goto s;}

Nimmt Eingaben als Referenz auf einen Vektor von Vektoren und ändert sie direkt.

Probieren Sie es online!

Steadybox
quelle