Diese Herausforderung ist teils eine Herausforderung für Algorithmen, teils eine Herausforderung für die Optimierung und teils einfach eine Herausforderung für den schnellsten Code.
Die AT-Matrix wird vollständig durch ihre erste Zeile r
und erste Spalte spezifiziert c
. Jedes verbleibende Element der Matrix ist nur eine Kopie des Elements, das diagonal nach oben und links zeigt. Das ist M[i,j] = M[i-1,j-1]
. Wir werden T-Matrizen zulassen, die nicht quadratisch sind. Wir gehen jedoch immer davon aus, dass die Anzahl der Zeilen nicht größer als die Anzahl der Spalten ist. Betrachten Sie beispielsweise die folgende 3 x 5 T-Matrix.
10111
11011
11101
Wir sagen, eine Matrix hat die Eigenschaft X, wenn sie zwei nicht leere Sätze von Spalten mit nicht identischen Indizes enthält, die dieselbe (Vektor-) Summe haben. Die Vektorsumme einer oder mehrerer Spalten ist einfach eine elementweise Summierung ihrer Spalten. Das ist die Summe von zwei oder mehr Spalten, die x
Elemente enthalten. Jede ist eine andere Spalte, die x
Elemente enthält. Die Summe einer Spalte ist trivial die Spalte selbst.
Die obige Matrix hat trivialerweise die Eigenschaft X, da die erste und die letzte Spalte gleich sind. Die Identitätsmatrix hat niemals die Eigenschaft X.
Wenn wir nur die letzte Spalte der obigen Matrix entfernen, erhalten wir ein Beispiel, das keine Eigenschaft X hat und eine Punktzahl von 4/3 ergibt.
1011
1101
1110
Die Aufgabe
Die Aufgabe besteht darin, Code zu schreiben, um die T-Matrix mit der höchsten Punktzahl mit binären Einträgen zu finden, die keine Eigenschaft X hat. Aus Gründen der Klarheit hat eine Matrix mit binären Einträgen die Eigenschaft, dass jeder ihrer Einträge entweder 0 oder 1 ist.
Ergebnis
Ihre Punktzahl besteht aus den Zahlenspalten geteilt durch die Anzahl der Zeilen in Ihrer besten Bewertungsmatrix.
Tie Breaker
Wenn zwei Antworten die gleiche Punktzahl haben, gewinnt die zuerst eingereichte.
In dem (sehr) unwahrscheinlichen Fall, dass jemand eine Methode findet, um unbegrenzte Punktzahlen zu erhalten, wird der erste gültige Beweis für eine solche Lösung akzeptiert. Für den noch unwahrscheinlicheren Fall, dass Sie einen Beweis für die Optimalität einer endlichen Matrix finden, werde ich natürlich auch den Gewinn vergeben.
Hinweis
Alle Antworten unter Matrix mit der höchsten Punktzahl finden ohne Eigenschaft X sind hier gültig, aber nicht optimal. Es gibt T-Matrizen ohne Eigenschaft X, die nicht zyklisch sind.
Zum Beispiel gibt es eine 7 × 12 T-Matrix ohne Eigenschaft X, aber keine solche zyklische Matrix.
21/11 würde alle aktuellen Antworten aus dieser und der vorherigen Herausforderung übertreffen.
Sprachen und Bibliotheken
Sie können jede Sprache verwenden, die einen frei verfügbaren Compiler / Interpreter / etc. für Linux und alle Bibliotheken, die auch für Linux frei verfügbar sind.
Bonus Die erste Antwort mit einer Punktzahl von mehr als 2 erhält sofort eine Prämie von 200 Punkten . Ton Hospel hat dies jetzt erreicht!
Aktuelle Rangliste
- C ++ . Partitur 31/15 von Ton Hospel
- Java . Ergebnis 36/19 von Peter Taylor
- Haskell . Ergebnis 14/8 von alexander-brett
quelle
Antworten:
C ++, Partitur
23/1225/1327/1428/1431/15Endlich ein Ergebnis mit Verhältnis> 2:
Ich habe 1 bis 14 Zeilen vollständig erkundet. 15 würde zu lange dauern, um vollständig zu erkunden. Die Ergebnisse sind:
Der unten angegebene Code ist eine ältere Version des Programms. Die neueste Version finden Sie unter https://github.com/thospel/personal-propertyX .
quelle
Haskell 14/8 = 1,75
Zuvor 9/6 = 1,5
Ich schrieb dies, sah mir dann die Antworten auf die andere Frage an und war ... entmutigt.
quelle
main
ist die Zahl (in diesem Fall8
) die Höhe der Matrix, und das Programm durchläuft die Breiten[1..]
. Für jede Kombination aus Höhe und Breite wird ein Array von Spalten einer gültigen Matrix gedruckt.C.
Hier ist eine Antwort, die funktioniert und wesentlich speichereffizienter ist als der Haskell. Leider ist mein Computer immer noch zu langsam, um in angemessener Zeit eine bessere Leistung als 14/8 zu erzielen.
Versuchen Sie,
gcc -std=c99 -O2 -fopenmp -o matrices.exe matrices.c
mitmatrices.exe width height
oder ähnlich zu kompilieren und auszuführen . Die Ausgabe ist eine Ganzzahl, deren Bits die Basis für die betreffende Matrix bilden, zum Beispiel:Dann ist da
1650223 = 0b110010010111000101111
die fragliche Matrix:Wenn jemand mit 8 Kernen und Zeit auf seinen Händen dies für eine Weile ausführen möchte, denke ich, dass einige gute Dinge resultieren könnten :)
quelle
valid i: 7481
. In Python bin (7481) ist 0b1110100111001, was nicht lang genug ist. Irgendeine Idee, was los ist?