Układanka liczb Arystotelesa polega na wypełnieniu każdej z 19 komórek heksagonalną siatką unikalną liczbą całkowitą od 1 do 19, tak że suma wzdłuż każdej osi wynosi 38.

Możesz wyobrazić sobie planszę wyglądającą tak:

Układanka jest w istocie rozwiązaniem następującego zestawu piętnastu równań:

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

Gdzie każda zmienna jest unikalnym numerem w zestawie {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Istnieje wiele możliwych rozwiązań i 19!możliwych kombinacji liczb całkowitych, więc naiwna brutalna siła będzie niepraktyczna.

Zasady:

1. Żadnego wpisywania odpowiedzi na stałe ani szukania odpowiedzi w innym miejscu; Twój kod musi go znaleźć samodzielnie
2. Szybkość nie ma znaczenia, ale musisz pokazać swoje wyniki, więc kod, którego uruchomienie zajmuje 1000 lat, nie pomoże
3. Znajdź wszystkie odpowiedzi
4. Traktuj identyczne odpowiedzi w rotacji jako identyczne
5. Odejmij 5% całkowitej liczby bajtów, jeśli wyprowadzisz wyniki w atrakcyjny plaster miodu
6. Wygrywa najmniej bajtów

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

Inna podobna odpowiedź, wykorzystująca arytmetykę do uzyskania pośrednich heksów. W przeciwieństwie do innych rozwiązań, nie sprawdzam, czy sumy te wynoszą> 0, wystarczy sprawdzić, czy posortowane heksy są równe zakresowi [1..19]. a, c i h są ograniczone, tak że dozwolone są tylko unikatowo obrócone / dublowane rozwiązania. Rozwiązanie pojawia się po kilku sekundach, a następnie trwa około minuty i decyduje, że nie będzie już więcej.

Zastosowanie w ghci:

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

Edytowane, aby ogolić kilka znaków. „y 0 t” daje [1..19].

Java (1517 - 75,85) = 1441,15 (1429 - 71,45) = 1357,55 (1325 - 66,25) = 1258,75

To było fajne.

Drukuje wszystkie unikalne rozwiązania z lustrzanym odbiciem i rotacją, w przyjemnej strukturze plastra miodu (stąd redukcja o 5%)

Runtime: ~ 0,122 s (122 milisekundy) na moim 4-letnim laptopie.

Kod w golfa ( edycja zdała sobie sprawę, że głupio powtarzam moje printfs, zredukowałem je do jednego printf dla maksymalnego golfa) ( nowa edycja Zredukowane wywołania funkcji Set w sprytne mniejsze funkcje, niektóre inne mikrooptymalizacje):

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();}}

Brutalna siła przemija, ale sprytne wykorzystanie faktu, że istnieje tylko bardzo mały zestaw rozwiązań, doprowadziło mnie do odpowiedzi opartej na iteracji, gdzie w każdej pętli iteracji rozważam tylko liczby całkowite, które nie zostały jeszcze „przypisane”. Korzystam z Java HashSet, aby uzyskać O (1) wyszukiwania dla liczb, które były wcześniej używane. Wreszcie istnieje dokładnie 12 rozwiązań, ale po odjęciu zarówno rotacji, jak i odbicia lustrzanego, zmniejsza się to do jednego unikalnego rozwiązania, więc gdy napotkamy pierwsze rozwiązanie, wydrukuję je i zakończę. Sprawdź mój mniej golfowy kod na github, aby uzyskać bardziej przejrzysty widok na to, jak podchodzę do tego rozwiązania.

Cieszyć się!

C, 366 bajtów ( 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);}}

Kompiluj z gcc -std=c99 -O3.

Drukuje wszystkie unikalne rozwiązania modulo rotacji i dublowania, w formacie a b c d ..., jeden na linię.

Runtime: 0,8 sekundy na moim komputerze.

Liczymy komórki w kolejności h -> c -> s -> a -> l -> q -> e dla maksymalnej podatności. W rzeczywistości powyższa wersja po prostu próbuje co 20 ^ 7 przypisań dla tych zmiennych. Następnie możemy obliczyć wszystkie pozostałe komórki. Istnieje tylko jedno unikalne rozwiązanie modulo rotation / mirroring. Starszą, mniej golfową i ~ 20 razy szybszą (z powodu przycinania) wersję C ++ można znaleźć na Github

Matlab: 333 320 znaków

Jest to dość głupie podejście o niemal brutalnej sile, które nie wykorzystuje rekurencji. Tworzy częściowe rozwiązania w z, które są wydrukowane na końcu. Każda kolumna jest rozwiązaniem; elementy są wymienione az od góry do dołu. Czas działania wynosi 1-2 godziny.

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

Uruchamianie z poziomu Matlaba:

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

ans =

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