Pecahkan Masalah Nomor Aristoteles

21

Teka-teki nomor Aristoteles adalah tantangan untuk mengisi masing-masing 19 sel dalam kotak heksagonal dengan bilangan bulat unik antara 1 dan 19 sehingga total sepanjang setiap sumbu adalah 38.

Anda dapat membayangkan papan permainan terlihat seperti ini:

kotak aristotle

Dan teka-teki, pada dasarnya, adalah solusi untuk rangkaian lima belas persamaan berikut:

((a + b + c) == 38 && (d + e + f + g) == 38 && (h + i + j + k + l) == 
   38 && (m + n + o + p) == 38 && (q + r + s) == 38 && (a + d + h) == 
   38 && (b + e + i + m) == 38 && (c + f + j + n + q) == 
   38 && (g + k + o + r) == 38 && (l + p + s) == 38 && (c + g + l) == 
   38 && (b + f + k + p) == 38 && (a + e + j + o + s) == 
   38 && (d + i + n + r) == 38 && (h + m + q) == 38)

Di mana setiap variabel adalah nomor unik di set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Ada beberapa solusi yang mungkin, dan 19!kemungkinan kombinasi bilangan bulat, sehingga gaya kasar naif tidak praktis.

Aturan:

  1. Tidak ada hardcoding jawabannya atau mencari jawabannya di tempat lain; kode Anda perlu menemukannya sendiri
  2. Kecepatan tidak masalah, tetapi Anda harus menunjukkan hasil Anda, jadi kode yang membutuhkan 1000 tahun untuk berjalan tidak akan membantu Anda
  3. Temukan semua jawabannya
  4. Perlakukan jawaban yang identik dengan rotasi sebagai identik
  5. Kurangi 5% dari total byte Anda jika Anda menghasilkan hasilnya di sarang lebah yang menarik
  6. Bytes paling sedikit menang
Michael Stern
sumber
Pertanyaan yang bagus, menantikan untuk bekerja solusi untuk itu.
ProgrammerDan
Apakah Anda menganggap jawaban yang diputar sebagai unik? Misalnya, mari kita asumsikan a, b, c = 1, 18, 19 mengindeks solusi tertentu, jika kita menetapkan c, g, l = 1, 18, 19 dan semua nilai lainnya "diputar" untuk mencocokkan, apakah Anda menganggap ini unik larutan?
ProgrammerDan
@ProgrammerDan Jawaban yang diputar identik. Saya akan mengklarifikasi.
Michael Stern
1
Hexagon memiliki lebih banyak simetri daripada hanya rotasi. Bagaimana dengan jawaban yang identik di bawah kombinasi rotaasi dan refleksi?
Peter Taylor
Tertarik untuk melihat solusi untuk yang ini menggunakan peta yang mengatur sendiri.
Semut

Jawaban:

3

Haskell 295 289

import Data.List
t=38
y a b=[max(19-b)(a+1)..19]
w=y 0 t
x=filter((==w).sort)$[[a,b,c,d,e,f,g,h,i,t-a-e-o-s,k,l,m,t-d-i-r,o,p,q,r,s]|a<-[1..14],c<-y a a,l<-y a c,s<-y a l,q<-y a s,h<-y c q,e<-w,let{f=t-g-e-d;i=t-b-e-m;o=t-r-k-g;k=t-p-f-b;b=t-a-c;g=t-l-c;p=t-l-s;r=t-q-s;m=t-q-h;d=t-a-h}]

Jawaban serupa lainnya, menggunakan aritmatika untuk mendapatkan heks menengah. Tidak seperti solusi lain, saya tidak menguji jumlah tersebut menjadi> 0, menguji bahwa heks yang diurutkan sama dengan kisaran [1..19] sudah cukup. a, c dan h dibatasi sehingga hanya solusi yang diputar / dicerminkan secara unik yang diizinkan. Solusinya muncul setelah beberapa detik, kemudian ada menunggu sekitar satu menit sementara itu memutuskan tidak ada lagi.

Penggunaan dalam ghci:

ghci> x
[[3,19,16,17,7,2,12,18,1,5,4,10,11,6,8,13,9,14,15]]

Diedit untuk mencukur beberapa karakter. 'y 0 t' menghasilkan [1..19].

bazzargh
sumber
1
Sebenarnya saya melakukan hal yang sama dalam jawaban C saya :) sial kenapa saya tidak bisa melihat bahwa Haskell adalah alat yang sempurna untuk pekerjaan itu: P +1
Niklas B.
Saya bisa melewatkan x>0cek Anda , karena saya mengurutkan daftar termasuk negatif daripada menambah array? Di sisi lain, saya harus membatasi rentang (saya y a b) untuk membuat Haskell tampil, yang membuat saya harus mengeluarkan beberapa biaya. Tetapi pasti ada bahasa lain yang memiliki semacam bawaan yang akan mengalahkan saya bekerja dengan cara yang sama (melihat Anda, Mathematica).
bazzargh
Ya, menyortir dalam C sayangnya tidak sesederhana di Haskell. Masalah dengan Mathematica adalah bahwa itu tidak dikompilasi dan dengan demikian sangat lambat :(
Niklas B.
Saya selalu melakukan ini di Haskell untuk latihan, bahkan jika bahasa lain akan lebih baik.
bazzargh
Saya sebenarnya memprogram Haskell sebagai pekerjaan sampingan, jadi saya bingung bahwa tidak terpikir oleh saya untuk menggunakannya di sini: D Bahasa ini benar-benar hebat, bahkan di dunia nyata / tidak murni
Niklas B.
10

Java (1517 - 75.85) = 1441.15 (1429 - 71.45) = 1357.55 (1325 - 66.25) = 1258.75

Ini sangat menyenangkan.

Mencetak semua solusi unik mirroring dan rotasi, dalam sarang madu yang menyenangkan (karenanya pengurangan 5%)

Runtime: ~ 0,122s (122 milidetik) pada laptop saya yang berumur 4 tahun.

Kode golf ( sunting menyadari saya bodoh mengulangi printf saya, menguranginya menjadi printf tunggal untuk golf maksimum) ( suntingan baru Mengurangi panggilan untuk Mengatur fungsi menjadi fungsi yang lebih kecil pintar, beberapa optimasi mikro lainnya):

import java.util.*;class A{boolean c(Set<Integer>u,int z){return!u.contains(z);}Set<Integer>b(Set<Integer>c,int...v){Set<Integer>q=new HashSet<Integer>(c);for(int x:v)q.add(x);return q;}void w(){Set<Integer>U,t,u,v,w,y,z;int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,X,Z;X=20;Z=38;for(a=1;a<X;a++)for(b=1;b<X;b++)if(b!=a)for(c=1;c<X;c++)if(c!=a&&c!=b&&a+b+c==Z){U=b(new HashSet<Integer>(),a,b,c);for(d=1;d<X;d++)if(c(U,d))for(h=1;h<X;h++)if(h!=d&&c(U,h)&&a+d+h==Z){t=b(U,a,b,c,d,h);for(m=1;m<X;m++)if(c(t,m))for(q=1;q<X;q++)if(q!=m&&c(t,q)&&h+m+q==Z){u=b(t,m,q);for(r=1;r<X;r++)if(c(u,r))for(s=1;s<X;s++)if(s!=r&&c(u,s)&&q+r+s==Z){v=b(u,r,s);for(p=1;p<X;p++)if(c(v,p))for(l=1;l<X;l++)if(l!=p&&c(v,l)&&s+p+l==Z){w=b(v,p,l);for(g=1;g<X;g++)if(c(w,g)&&l+g+c==Z)for(e=1;e<X;e++)if(e!=g&&c(w,e))for(f=1;f<X;f++)if(f!=e&&f!=g&&c(w,f)&&d+e+f+g==Z){y=b(w,g,e,f);for(i=1;i<X;i++)if(c(y,i))for(n=1;n<X;n++)if(n!=i&&c(y,n)&&d+i+n+r==Z&&b+e+i+m==Z){z=b(y,i,n);for(o=1;o<X;o++)if(c(z,o))for(k=1;k<X;k++)if(k!=o&&c(z,k)&&m+n+o+p==Z&&r+o+k+g==Z&&b+f+k+p==Z)for(j=1;j<X;j++)if(c(z,j)&&j!=o&&j!=k&&a+e+j+o+s==Z&&c+f+j+n+q==Z&&h+i+j+k+l==Z){System.out.printf("%6d%4d%4d\n\n%4d%4d%4d%4d\n\n%2d%4d%4d%4d%4d\n\n%4d%4d%4d%4d\n\n%6d%4d%4d\n\n",a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s);return;}}}}}}}}}public static void main(String[]a){(new A()).w();}}

Brute force sudah ketinggalan jaman, tetapi penggunaan fakta yang cerdas bahwa hanya sejumlah kecil solusi yang ada membawa saya ke jawaban berbasis iterasi, di mana dalam setiap loop iterasi saya hanya mempertimbangkan bilangan bulat yang belum "ditugaskan". Saya menggunakan Java HashSet untuk mendapatkan O (1) pencarian untuk nomor yang telah digunakan sebelumnya. Akhirnya, ada tepat 12 solusi, tetapi ketika Anda mendiskon rotasi dan mirroring ini berkurang menjadi hanya satu solusi unik, jadi ketika solusi pertama ditemukan, saya mencetaknya dan mengakhiri. Lihat kode kurang golf saya di github untuk sedikit pandangan yang lebih jelas tentang bagaimana saya mendekati solusi ini.

Nikmati!

ProgrammerDan
sumber
Nah, Anda berbohong di spoiler Anda, ada solusi yang lebih berbeda, jadi jawaban Anda tidak valid.
ST3
Klaim yang kuat, dapatkah Anda mendukungnya dengan jawaban Anda sendiri untuk membuktikannya? Saya tentu saja tidak mengetahui adanya kebohongan yang disengaja pada spoiler saya.
ProgrammerDan
jadi ketika solusi pertama ditemukan, saya mencetaknya dan mengakhiri aturan no. 3 memberitahu memberitahu untuk menemukan semua jawaban. Ada 19 seperti kata OP, tidak yakin apakah itu benar-benar 19, tapi saya pernah mengalami tugas yang sama sebelumnya, jadi ketahuilah bahwa ada lebih dari satu.
ST3
Anda perlu membaca seluruh spoiler saya . Saya menemukan 12 solusi. Maka Anda perlu membaca seluruh komentar yang terlampir pada pertanyaan. OP mengatakan bahwa jawaban yang sama dengan rotasi WRT adalah sama, dan harus dilewati. Orang lain bertanya apakah jawaban mirroring yang sama harus dilewati. Meskipun OP sampai saat ini belum menjawab pertanyaan ini, saya dan semua solusi lainnya sampai saat ini menganggap jawabannya adalah "ya". Karenanya, solusi saya sepenuhnya lengkap, sepenuhnya akurat, dan tidak ada "kebohongan" di sini. Namun, jika Anda ingin melihat semua 12 solusi, hapus return;pernyataan itu.
ProgrammerDan
Akhirnya, ini adalah kode golf. Mempertimbangkan menambahkan return;pernyataan arbitrer meningkatkan panjang kode saya sampai 7, akan menjadi gila bagi saya untuk menambahkannya jika jawaban yang benar mencakup semua 12 solusi yang hanya diputar / dicerminkan versi satu sama lain. Meskipun kegilaan tidak dapat dikesampingkan, dalam hal ini, penambahan return;disengaja, dan seperti yang saya jelaskan, berdasarkan dialog pertanyaan dan komentar lengkap , yang harus Anda perhatikan dengan saksama sebelum melemparkan tuduhan. Terima kasih!
ProgrammerDan
8

C, 366 byte ( C ++ 541 450 )

#define R(i)for(int i=19;i;--i)
#define X(x)if(x>0&&!V[x]++)
#define K(X)X(a)X(b)X(c)X(d)X(e)X(f)X(g)X(h)X(i)X(j)X(k)X(l)X(m)X(n)X(o)X(p)X(q)X(r)X(s)
Q(x){printf("%d ",x);}
T=38,V[99];main(){R(h)R(c)R(s)R(a)R(l)R(q)R(e){int d=T-a-h,b=T-a-c,g=T-c-l,p=T-l-s,r=T-q-s,m=T-h-q,f=T-g-e-d,i=T-b-e-m,n=T-d-i-r,o=T-p-n-m,k=T-g-o-r,j=T-h-i-k-l;R(C)V[C]=0;K(X)K(+Q),exit(0);}}

Kompilasi dengan gcc -std=c99 -O3.

Mencetak semua solusi unik, rotasi modulo dan mirroring, dalam format a b c d ..., satu per baris.

Runtime: 0,8 detik di komputer saya.

Kami menghitung sel dalam urutan h -> c -> s -> a -> l -> q -> e untuk prunability maksimum. Sebenarnya versi di atas hanya mencoba setiap 20 ^ 7 tugas untuk variabel-variabel tersebut. Lalu kita bisa menghitung semua sel lainnya. Hanya ada satu solusi unik rotasi / mirroring modulo. Versi C ++ yang lebih lama, kurang golf, dan ~ 20 kali lebih cepat (karena pemangkasan) dapat ditemukan di Github

Niklas B.
sumber
Saya suka pendekatan aritmatika di sini. Bravo! +1
ProgrammerDan
1

Matlab: 333 320 karakter

Ini adalah pendekatan near-brute-force yang cukup bodoh yang tidak menggunakan rekursi. Itu membangun solusi parsial dalam z, yang dicetak pada akhirnya. Setiap kolom adalah solusi; elemen terdaftar az dari atas ke bawah. Runtime adalah 1-2 jam.

z=[];
a='abc adh hmq qrs spl lgc defg beim mnop dinr rokg pkfb hijkl aejos cfjnq';while a[k,a]=strtok(a);n=length(k);x=nchoosek(1:19,n)';s=[];for t=x(:,sum(x)==38)s=[s,perms(t)'];end
m=0.*s;m(19,:)=0;m(k(1:n)-96,:)=s(1:n,:);y=[];for p=m for w=z m=[];l=w.*p~=0;if p(l)==w(l) y(:,end+1)=w+p.*(~l);end
end
end
z=[m,y];end
z

Berlari dari dalam Matlab:

>> aristotle;
>> z(:,1)

ans =

    9
   11
   18
   14
    6
    1
   17
   15
    8
    5
    7
    3
   13
    4
    2
   19
   10
   12
   16
intx13
sumber