Rozwiąż problem z liczbą Arystotelesa

21

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:

aristotle grid

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
Michael Stern
źródło
Świetne pytanie, nie mogę się doczekać wypracowania rozwiązania tego problemu.
Programator
Czy uważasz, że obrócone odpowiedzi są unikalne? Np. Załóżmy, że a, b, c = 1, 18, 19 indeksuje konkretne rozwiązanie, jeśli ustawimy c, g, l = 1, 18, 19 i wszystkie inne wartości zostaną „obrócone”, aby dopasować, czy uważasz to za wyjątkowe rozwiązanie?
Programator
@ProgrammerDan Obrócone odpowiedzi są identyczne. Wyjaśnię.
Michael Stern
1
Sześciokąt ma więcej symetrii niż tylko obroty. Co z odpowiedziami, które są identyczne w połączeniu rotacji i refleksji?
Peter Taylor
Chciałbym zobaczyć rozwiązanie tego problemu, korzystając z samoorganizujących się map.
Ant P

Odpowiedzi:

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

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

bazzargh
źródło
1
Właściwie robię to samo w odpowiedzi na C :) cholera, jak mogłem nie zauważyć, że Haskell jest idealnym narzędziem do pracy: P +1
Niklas B.
Mogę przegapić twój x>0czek, ponieważ sortuję listę zawierającą negatywy zamiast zwiększania tablicy? Z drugiej strony muszę ograniczyć zakresy (moje y a b), aby Haskell mógł wykonać, co kosztuje mnie kilka znaków. Ale musi istnieć inny język z wbudowanym rodzajem, który pobije mnie, pracując w ten sam sposób (patrząc na ciebie, Mathematica).
bazzargh
Tak, sortowanie w C niestety nie jest tak proste jak w Haskell. Problem z Mathematica jest to, że nie jest skompilowany, a więc tak cholernie wolno :(
Niklas B.
Zawsze robię to w Haskell, aby ćwiczyć, nawet jeśli inny język byłby lepszy.
bazzargh
Właściwie programuję Haskella jako pracę poboczną, więc jestem zaskoczony, że nawet nie przyszło mi do głowy, aby go tutaj użyć: D To naprawdę świetny język, nawet w prawdziwym / nieczystym świecie
Niklas B.
10

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ę!

ProgrammerDan
źródło
Cóż, leżysz w swoim spojlerze, istnieje więcej różnych rozwiązań, więc twoja odpowiedź jest nieprawidłowa.
ST3
Mocne twierdzenie, czy możesz poprzeć własną odpowiedź, aby to udowodnić? Na pewno nie wiem o umyślnych kłamstwach w moim spoilerze.
Programator
więc gdy napotkamy pierwsze rozwiązanie, drukuję je i kończę regułę nr. 3 mówi każe znaleźć wszystkie odpowiedzi. Jest 19, jak powiedział OP, nie jestem pewien, czy to naprawdę 19, ale wcześniej spotkałem się z podobnym zadaniem, więc wiedz, że jest więcej niż jedno.
ST3
Musisz przeczytać cały mój spoiler. Znalazłem 12 rozwiązań. Następnie musisz przeczytać cały komentarz dołączony do pytania. OP twierdzi, że odpowiedzi, które są równe rotacja wrt są równoważne i powinny zostać pominięte. Inna osoba zapytała, czy należy pomijać odpowiedzi równe dla kopii lustrzanej. Chociaż OP jak dotąd nie odpowiedział na to pytanie, zarówno moje, jak i wszystkie inne dotychczasowe rozwiązania zakładają, że odpowiedź brzmi „tak”. Dlatego moje rozwiązanie jest w pełni kompletne, w pełni dokładne i nie ma tutaj „kłamstw”. Jeśli jednak chcesz zobaczyć wszystkie 12 rozwiązań, usuń return;instrukcję.
Programator
Wreszcie jest to golf golfowy. Biorąc pod uwagę, że dodanie dowolnego return;zdania zwiększa długość mojego kodu o 7, dodanie go byłoby szaleństwem, gdyby prawdziwa odpowiedź obejmowała wszystkie 12 rozwiązań, które są po prostu obróconymi / dublowanymi wersjami siebie. Chociaż nie można wykluczyć szaleństwa, w tym przypadku dodanie return;było zamierzone i, jak to opisałem, w oparciu o pełne okno dialogowe pytań i komentarzy , które powinieneś przejrzeć przed podrzuceniem oskarżeń. Dzięki!
Programator
8

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

Niklas B.
źródło
Uwielbiam tutaj podejście w dużej mierze arytmetyczne. Brawo! +1
programista
1

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
intx13
źródło