Löse Aristoteles 'Zahlenproblem

21

Aristoteles 'Zahlenrätsel besteht darin, jede der 19 Zellen in einem hexagonalen Raster mit einer eindeutigen Ganzzahl zwischen 1 und 19 zu füllen, sodass die Summe entlang jeder Achse 38 beträgt.

Sie können sich das Spielbrett so vorstellen:

Aristoteles-Gitter

Das Rätsel ist im Wesentlichen die Lösung für die folgenden fünfzehn Gleichungen:

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

Wobei jede Variable eine eindeutige Nummer in der Menge ist {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.

Es gibt mehrere mögliche Lösungen und 19!mögliche Kombinationen von ganzen Zahlen, so dass naive rohe Gewalt unpraktisch ist.

Regeln:

  1. Keine Hardcodierung der Antwort oder Nachschlagen der Antwort an anderer Stelle; Ihr Code muss es selbst finden
  2. Geschwindigkeit spielt keine Rolle, aber Sie müssen Ihre Ergebnisse anzeigen, sodass die Ausführung von Code, dessen Ausführung 1000 Jahre dauert, keine Hilfe darstellt
  3. Hier finden Sie alle Antworten
  4. Behandeln Sie Antworten, die bei Rotation identisch sind, als identisch
  5. Ziehen Sie 5% Ihrer Gesamtbytezahl ab, wenn Sie die Ergebnisse in einer attraktiven Wabe ausgeben
  6. Wenigste Bytes gewinnt
Michael Stern
quelle
Gute Frage, freue mich darauf, eine Lösung dafür zu finden.
ProgrammerDan
Betrachten Sie gedrehte Antworten als einzigartig? Nehmen wir beispielsweise an, dass a, b, c = 1, 18, 19 eine bestimmte Lösung indiziert. Wenn wir c, g, l = 1, 18, 19 setzen und alle anderen Werte entsprechend "gedreht" werden, betrachten Sie dies als eindeutig Lösung?
ProgrammerDan
@ProgrammerDan Gedrehte Antworten sind identisch. Ich werde klären.
Michael Stern
1
Ein Sechseck hat mehr Symmetrien als nur Rotationen. Was ist mit Antworten, die bei einer Kombination aus Rotation und Reflektion identisch sind?
Peter Taylor
Interessiert, eine Lösung für dieses Problem mit selbstorganisierenden Karten zu finden.
Ant P

Antworten:

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

Eine weitere ähnliche Antwort, bei der Arithmetik verwendet wird, um die Zwischenhexe zu erhalten. Im Gegensatz zu den anderen Lösungen prüfe ich nicht, ob diese Summen> 0 sind, sondern ob die sortierten Hexes dem Bereich [1..19] entsprechen. a, c und h sind eingeschränkt, so dass nur eindeutig gedrehte / gespiegelte Lösungen zulässig sind. Die Lösung wird nach ein paar Sekunden angezeigt. Dann dauert es ungefähr eine Minute, bis entschieden wird, dass keine Lösung mehr vorhanden ist.

Verwendung in ghci:

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

Bearbeitet, um ein paar Zeichen zu rasieren. 'y 0 t' ergibt [1..19].

bazzargh
quelle
1
Eigentlich mache ich das gleiche in meiner C-Antwort :) verdammt, wie konnte ich nicht sehen, dass Haskell das perfekte Werkzeug für den Job ist: P +1
Niklas B.
Ich kann Ihren x>0Scheck verpassen , weil ich die Liste mit Negativen sortiere, anstatt ein Array zu erhöhen? Andererseits muss ich die Bereiche (my y a b) einschränken , damit Haskell funktioniert, was mich ein paar Zeichen kostet. Aber es wird mit Sicherheit eine andere Sprache geben, die es mir erlaubt, auf die gleiche Weise zu arbeiten (dich anzusehen, Mathematica).
bazzargh
Ja, das Sortieren in C ist leider nicht so einfach wie in Haskell. Das Problem mit Mathematica ist, dass es nicht kompiliert und daher so verdammt langsam ist :(
Niklas B.
Ich mache diese immer in Haskell zum Üben, auch wenn eine andere Sprache besser wäre.
bazzargh
Eigentlich programmiere ich Haskell als Nebenjob, deshalb bin ich ratlos, dass es mir nicht einmal in den Sinn gekommen ist, es hier zu verwenden: D Es ist eine wirklich großartige Sprache, selbst in der realen / unreinen Welt
Niklas B.
10

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

Das hat Spaß gemacht.

Druckt alle einzigartigen Lösungen für Spiegelung und Drehung in einer angenehmen Wabe (daher 5% Reduzierung)

Laufzeit: ~ 0.122s (122 Millisekunden) auf meinem 4 Jahre alten Laptop.

Golfed Code ( edit erkannte ich dummerweise wurde meinen printfs wiederholen, reduzierte sie auf einen einzigen printf für maximalen Golf) ( neu bearbeiten Reduzieren Anrufe Set - Funktionen in clevere kleinere Funktionen, einige andere Mikro-Optimierungen):

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 ist Passe, aber die geschickte Verwendung der Tatsache, dass nur eine sehr kleine Menge von Lösungen existiert, führte mich zu einer iterationsbasierten Antwort, bei der ich in jeder Schleife der Iteration nur ganze Zahlen berücksichtige, die noch nicht "zugewiesen" wurden. Ich benutze Javas HashSet, um O (1) Lookups für Zahlen zu erhalten, die zuvor verwendet wurden. Schließlich gibt es genau 12 Lösungen. Wenn Sie jedoch Rotation und Spiegelung ausschließen, wird dies auf eine einzige Lösung reduziert. Wenn also die erste Lösung gefunden wird, drucke ich sie aus und beende sie. Schauen Sie sich meinen weniger Golf-Code bei Github an, um ein wenig klarer zu sehen, wie ich mit dieser Lösung umgehe .

Genießen!

ProgrammerDan
quelle
Nun, du liegst in deinem Spoiler, es gibt mehr verschiedene Lösungen, also ist deine Antwort ungültig.
ST3
Starker Anspruch, können Sie dies mit einer eigenen Antwort belegen, um dies zu beweisen? Ich bin mir gewiss keiner absichtlichen Lüge in meinem Spoiler bewusst.
ProgrammerDan
Wenn also die erste Lösung gefunden wird, drucke ich sie aus und beende Regel Nr. 3 sagt sagt, alle Antworten zu finden. Es gibt 19 wie OP sagte, nicht sicher, ob es wirklich 19 ist, aber ich habe ähnliche Aufgaben schon einmal ausgeführt, also wissen Sie, dass es mehr als eine gibt.
ST3
Du musst meinen gesamten Spoiler lesen . Ich habe 12 Lösungen gefunden. Dann müssen Sie die gesamten Kommentare lesen, die der Frage beigefügt sind. Das OP sagt, dass Antworten, die der Rotation gleich sind, äquivalent sind und übersprungen werden sollten. Eine andere Person fragte, ob Antworten, die der Spiegelung entsprechen, übersprungen werden sollten. Obwohl das OP bisher nicht auf diese Frage geantwortet hat, gehen sowohl meine als auch alle anderen bisherigen Lösungen davon aus, dass die Antwort "Ja" lautet. Daher ist meine Lösung vollständig und genau, und hier gibt es keine "Lügen". Wenn Sie jedoch alle 12 Lösungen anzeigen möchten, entfernen Sie die return;Anweisung.
ProgrammerDan
Schließlich ist dies Codegolf. Wenn ich erwäge, eine willkürliche return;Anweisung hinzuzufügen , vergrößert sich meine Codelänge um 7, und es wäre verrückt, sie hinzuzufügen, wenn die wahre Antwort alle 12 Lösungen enthielte, bei denen es sich einfach um gedrehte / gespiegelte Versionen voneinander handelt. Obwohl Wahnsinn nicht ausgeschlossen werden kann, war in diesem Fall das Hinzufügen von return;beabsichtigt, und wie ich beschrieben habe, basierend auf dem vollständigen Frage- und Kommentardialog , den Sie sorgfältig prüfen sollten, bevor Sie Anschuldigungen werfen. Vielen Dank!
ProgrammerDan
8

C, 366 Bytes ( 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);}}

Kompilieren mit gcc -std=c99 -O3.

Druckt alle einzigartigen Lösungen Modulo-Rotation und Spiegelung im Format a b c d ...einer pro Zeile.

Laufzeit: 0,8 Sekunden auf meinem Computer.

Wir listen die Zellen in der Reihenfolge h -> c -> s -> a -> l -> q -> e auf, um maximale Beschneidbarkeit zu erzielen. Tatsächlich versucht die obige Version nur alle 20 ^ 7 Zuweisungen für diese Variablen. Dann können wir alle anderen Zellen berechnen. Es gibt nur eine einzige Lösung für Modulo-Rotation / Spiegelung. Eine ältere, weniger golfed und ~ 20 - mal schneller (durch Beschneiden) C ++ Version gefunden werden kann auf Github

Niklas B.
quelle
Ich mag den weitgehend arithmetischen Ansatz hier. Bravo! +1
ProgrammerDan
1

Matlab: 333 320 Zeichen

Dies ist ein ziemlich dummer Ansatz, bei dem keine Rekursion angewendet wird. Es baut Teillösungen auf z, die am Ende ausgedruckt werden. Jede Spalte ist eine Lösung; Die Elemente werden von oben nach unten aufgelistet. Die Laufzeit beträgt 1-2 Stunden.

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

Laufen aus Matlab heraus:

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

ans =

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