Temukan sandpile identitas

18

Pertanyaan ini adalah tentang tumpukan pasir abelian . Baca tantangan sebelumnya dan tonton video numberphile ini untuk mempelajari lebih lanjut.


Tumpukan abelian ukuran n oleh n adalah kotak yang berisi angka 0, 1, 2 dan 3 (mewakili jumlah butiran pasir). Menambahkan dua tumpukan pasir bekerja dengan pertama-tama menambahkan elemen demi elemen, dan kemudian menggulingkan elemen apa pun yang berada di atas 3. Urutan di mana Anda menjatuhkan tidak masalah, hasil akhirnya sama. Ketika sel menjatuhkan jumlahnya berkurang 4, dan masing-masing tetangga langsungnya bertambah 1. Ini dapat menyebabkan reaksi berantai. Jika sebuah sel berada di tepi kisi, setiap butir yang jatuh dari kisi saat terguling menghilang.

Misalnya, saya menambahkan dua tumpukan pasir 3 oleh 3 (memberikan reaksi berantai yang agak ekstrem):

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

Dalam tantangan ini kami tertarik pada subset dari semua kemungkinan n oleh n tumpukan pasir. Subset ini berisi tumpukan pasir apa pun yang bisa Anda peroleh dengan menambahkan tumpukan pasir sewenang-wenang ke all-3s n oleh n sandpile. Sebagai contoh, tepat di atas kita melihat yang 212 | 101 | 212ada di subset, karena kita mendapatkannya dengan menambahkan sesuatu ke-3 sandpile.

Sekarang bagian ini memiliki elemen yang menarik: elemen identitas . Jika Anda mengambil elemen ini dan menambahkannya ke elemen lain di subset , jumlahnya tidak berubah. Dengan kata lain, tumpukan pasir ini bertindak seperti nol dari subset ini. Kebetulan itu 212 | 101 | 212adalah elemen nol untuk subset dari 3 oleh 3. Misalnya:

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

Sekarang ini tantangan Anda: diberikan n , menemukan unsur identitas subset dari n oleh n jaringan . Keluarkan dengan menetapkan warna unik dengan kontras yang cukup dari pilihan Anda untuk masing-masing 0, 1, 2, 3dan menghasilkan gambar n oleh n. Kode Anda harus dapat menghasilkan case 50 by 50 dalam waktu kurang dari satu menit pada PC modern yang wajar.


Misalnya, elemen 500 hingga 500 identitas:

500 oleh 500 elemen identitas

Ini biru = 3, hijau = 2, merah = 1, putih = 0. Tetapi Anda tidak harus menggunakan skema warna ini dalam jawaban Anda.

orlp
sumber
2
Satu kata peringatan bagi para pesaing: Saya menjelaskan apa solusinya, bukan bagaimana cara menghitungnya. Kode Anda harus dapat menghasilkan case 50 by 50 dalam waktu kurang dari satu menit, jadi memaksa kasar tidak mungkin. Ada algoritma untuk menyelesaikan ini, dan saya tidak memberi Anda mereka. Itu disengaja. Saya merasa bahwa terlalu banyak tantangan memberi Anda makanan pra-kunyah. Saya akan memberikan hadiah +100 untuk jawaban pertama yang tidak meremehkan masalah dengan builtin (melihat Anda, Mathematica), atas kebijakan saya.
orlp
2
Saya pikir gambar identitas 500x500 akan mendapat manfaat dengan mengatakan apa nomor masing-masing warna sesuai.
xnor
Apa yang dimaksud dengan "kontras yang cukup"?
Conor O'Brien
@ ConorO'Brien Set warna apa pun yang cukup dapat dibedakan. Saya bisa menjadikannya 100% objektif dengan beberapa ukuran warna, tapi saya rasa itu berlebihan. Saya tidak peduli jika Anda menggunakan merah, kuning, hijau, skala abu-abu, atau apa pun, hanya saja jangan gunakan 4 warna abu-abu yang berada dalam 1% satu sama lain (seperti # 000000, # 000001, # 000001, # 000002, # 000003).
orlp
ahem Saya yakin pertanyaan ini sekarang memenuhi syarat untuk mendapatkan hadiah. Bisakah saya mendapatkan bonus +100? :)
JungHwan Min

Jawaban:

2

Oktaf, 120 113 byte

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

Terima kasih kepada JungHwan Min karena menyediakan tautan ke makalah referensi dalam jawaban Mathematica-nya.
Terima kasih kepada Stewie Griffin yang menyelamatkan saya 7 byte[any(any(x)) -> nnz(x)]

Berikut dua fungsi yang digunakan:

1 f.: untuk stabilisasi matriks
2. Fungsi anonim yang mengambil ninput dan menunjukkan matriks identitas.

Cobalah Di rextester! untuk pembuatan matriks 50 * 50

Waktu berlalu untuk perhitungan matriks: 0.0844409 seconds.

Penjelasan:

Pertimbangkan fungsi f yang menstabilkan matriks, tugas menemukan identitas adalah sederhana

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

itu ones(n)*6berarti * n matriks 6.

jadi untuk n=3:

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

Hasilnya akan f(M-f(M))

Untuk fungsi stabilisasi, konvolusi 2D digunakan untuk mempercepat tugas; Dalam setiap iterasi kita membuat matriks biner bdengan ukuran yang sama dari matriks input dan mengaturnya menjadi 1 jika elemen yang sesuai dari matriks input adalah> 3. Kemudian kami menerapkan konvolusi 2D dari matriks biner dengan mask berikut

0 1 0
1 0 1
0 1 0

mewakili empat tetangga langsung.
Hasil konvolusi ditambahkan ke matriks dan 4 kali matriks biner dikurangi darinya.

Lingkaran berlanjut sampai semua elemen dari matriks adalah <= 3

Versi tidak disatukan :

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
sumber
8

Mathematica, 177 157 135 133 byte

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

Membawa nomor n. Outputnya adalah sandpile identitas. 0 berwarna hitam, 1 berwarna abu-abu muda, 2 berwarna magenta, dan 3 berwarna biru-abu-abu.

Sayangnya, Mathematica tidak memiliki builtin untuk ini ...

Menggunakan algoritma yang dinyatakan dalam makalah Scott Corry dan David Perkinson .

Memakan waktu 91,7 detik pada laptop saya yang berusia 5 tahun untuk menghitung sandpile identitas 50x50. Saya yakin bahwa komputer desktop modern yang masuk akal lebih dari 50% lebih cepat. (Saya juga punya kode cara yang lebih cepat di akhir).

Penjelasan

f= ...

Tentukan fungsi f(inputnya adalah matriks pasir): fungsi yang ...

BlockMap[ ... ]~FixedPoint~#&

... mengulangi BlockMapoperasi sampai output tidak berubah. BlockMapoperasi: ...


#~ArrayPad~1

... pad array input dengan satu layer 0 ...

{3,3},1

... mempartisi ke dalam matriks 3x3, dengan offset 1 ...

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

... dan untuk setiap partisi, tambahkan jumlah butiran pasir yang dijatuhkan ke sel tengah dan nilai sel pusat mod 4.

yaitu output dari fversi input yang distabilkan.


k=Table[6,#,#]

Mendefinisikan ksebagai n oleh n array 6s.

f[k-f@k]]

Hitung f (k - f (k)).

Colorize[ ... ]

Terapkan warna ke hasilnya.

Versi lebih cepat (142 byte)

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

Kode yang sama, tetapi menggunakan rotasi daftar bawaan bukan BlockMap. Menghitung n = 50 dalam 4,0 detik di laptop saya.

JungHwan Min
sumber
Menimbang bahwa Anda mengikuti semangat batas waktu (menerapkan algoritma yang sebenarnya daripada kekuatan kasar), dan sangat masuk akal bahwa komputer desktop yang kuat adalah 50% lebih cepat, saya akan mengizinkannya. Karena mengimplementasikan algoritma yang sebenarnya tanpa built-in yang sepele, ini memenuhi syarat untuk bonus +100. Anda harus menunggu untuk itu, karena saya belum dapat memulai hadiah.
orlp
Yang sedang berkata, menerapkan ini cukup sepele di Python (bahasa yang sangat lambat), hanya membutuhkan ~ 2s untuk n = 50. Mungkin Anda bisa mempercepatnya sedikit?
orlp
@ orlp Selesai, tetapi lebih panjang dari kode aslinya. Haruskah saya menjadikan versi yang lebih cepat sebagai jawaban utama saya atau dapatkah saya hanya meletakkannya di akhir?
JungHwan Min
Sepertinya ini baik-baik saja saya pikir.
orlp
0

Python 3 + Numpy + PIL, 385 370 364 byte

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

Mengambil input pada STDIN. Output gambar sebagai skala abu-abu ke i.png. Hitam sesuai dengan 0, abu-abu gelap ke 1, abu-abu terang ke 2, dan putih ke 0.

Menggunakan rumus I = R(S - R(S)), di mana Ielemen identitas, Sadalah matriks yang diisi dengan enam, dan Rmerupakan fungsi reduksi.

Saya mungkin bisa menyimpan beberapa byte dengan beralih ke Python 2 dan melakukan from numpy import*, tetapi (1) saya tidak memiliki Numpy diinstal pada Python 2 dan (2) program tidak berakhir dengan from numpy import*.

Tidak Disatukan:

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')
Tembaga
sumber
Anda mungkin dapat menyimpan byte dengan menggunakan scipyatau matplotlibmenampilkan data daripada menghasilkan gambar secara eksplisit dengan PIL.
orlp