Java - Programm zum Auslesen von Bit-Reihenfolgen

[Mundy]

Liebes Forum,

ich nehme gerade an der 2. Runde des Bundesjugendwettbewerbs Informatik teil. Die erste Runde habe ich gut geschafft, in der 2. Runde habe ich die 1. Aufgabe gut gelöst, an der 2. beiße ich mir allerdings die Zähne aus.

Eines vorweg: Es ist nicht erlaubt, sich Lösungen o.ä. über Dritte zu besorgen. Worum es mir hier geht ist ein Denkansatz, der mich evtl. weiterbringt.

Die Aufgabe lautet, 11 Lochkarten mit je 128 Bit-Positionen aus insgesamt 111 Karten herauszufinden. Die weiteren 100 Lochkarten wurden zufällig erstellt und mit den ursprünglichen 11 vermischt.

Die ursprünglichen 11 haben eine Besonderheit. Die 11. Karte war quasi eine Zusammenfassung der ersten 10 und enthielt als Bitmuster das exklusive Oder der anderen 10 Karten. Sollte also eine der 10 Karten verloren gehen, kann diese mit Hilfe der Sicherungskarte rekonstruiert werden.

Nun werden eben weitere 100, wahllos erstellte Lochkarten, unter die 11 anderen gemischt und man soll ein Programm schreiben, dass die 111 Karten einliest und die 11 richtigen ausgibt, unter Berücksichtigung einer vernünftigen Laufzeit.

Wie diese 11. Sicherungskarte mit dem exklusiven Oder erstellt wird ist mir vollkommen klar. Unter Berücksichtigung der 3 Gesetze (Kommutativ, Distributiv u. Assoziativ) kann ich das nachvollziehen und programmiertechnisch auch verarbeiten. Ich habe auch verschiedene Ansätze die 11 Karten zu identifizieren, allerdings unter vollkommen inakzeptablen Laufzeiten.

Wenn hier jemand eine grundsätzliche Idee bzgl. der Problematik des Laufzeitverhaltens hätte, wäre ich dankbar.

Freundliche Grüße,
Mundy

 

[DaysShadow]

eine grundsätzliche Idee bzgl. der Problematik des Laufzeitverhaltens

Ist nicht auch das Teil deiner Leistung bei einem solchen Wettbewerb?

Hast du denn schon ein Programm oder eine theoretische Lösung was die Problemstellung überhaupt erledigt? Wie schnell oder langsam das passiert ist dabei ja erst einmal egal. Danach kannst du dir immer noch Gedanken machen wie du es beschleunigst.

 

[Mundy]

Ist nicht auch das Teil deiner Leistung bei einem solchen Wettbewerb?

Grundsätzlich ja, wenn auch untergeordnet.

Ja, ich habe schon zwei Programme geschrieben, das Problem ist, dass ich immer in die exponentielle Laufzeit laufe, da ich, recht einfach formuliert, alle möglichen Varianten durchprobiere. Und das ist eigentlich eher mein Thema, nämlich grundsätzlich einen Denkanstoß bzgl. der Vermeidung bzw. Optimierung v. exponentiellem Laufzeitverhalten zu bekommen (also nicht so sehr auf den eigentlichen Wettbewerb bezogen).

 

[BeBur]

Und das ist eigentlich eher mein Thema, nämlich grundsätzlich einen Denkanstoß bzgl. der Vermeidung bzw. Optimierung v. exponentiellem Laufzeitverhalten zu bekommen

Das dürfte das wesentlich an der Aufgabe sein und nicht 'untergeordnet', wenn dir da jemand einen Ansatz nennt, dann hast du direkt gegen die Regeln verstoßen. Naiv alle Kombinationen durchrechnen ist recht simpel und wie du ja gemerkt hast nicht sinnvoll.

 

[BxB]

Problem ist, dass nur korrekter Treffer gilt, also die "beste Lösung", nicht nur eine Annäherung.
Klingt nach einer Idee, wie eine große Matrix aufbauen (SpeicherLimit bei größeren Dimensionen) und viel ausprobieren mit ner eigenen Instanz der zu testenden Elemente.
Hier daraus auslesen und die ganzen Kombinationen auflisten, doppelte Vermeiden, Kombinationen austesten und direkt früh abbrechen, wenn die gewählten 11 nicht zusammen passt.
Die Frage ist, ob es nur 1 gültige Lösung gibt oder mehrere geben kann. Sonst halt bei erstem Treffer Ende.

 

[entropie88]

https://en.wikipedia.org/wiki/Backtracking wäre zb der einfachste Ansatz.

 

[Tornhoof]

Das ist primär erstmal doch kein Programmierproblem, sondern ein Matheproblem im GF(2) Galois Feld.
Das ist zwar schon Jahre her dass ich mich mit sowas in der Uni auseinandergesetzt habe, aber deine CRC Operationen (XOR) ist im GF2 Feld abbildbar, das ist wenn ich mich richtig erinnere die Addition im GF(2).
Der Rest ist dann dir nen entsprechenden Solver zu besorgen/schreiben der die Rechnung K(1)+K(2)+...+K(10 =K(11) löst bei einem Alphabet von 111. (K für Karte)

(Unter der Haube stinkt die ganze Fragestellung btw nach Kryptgraphie )

 

[Phrasendreher]

Hast Du für die Aufgabe zufällig einen Quantencomputer im Zugriff?

SCNR

 

[Mundy]

Das dürfte das wesentlich an der Aufgabe sein

In den bisherigen Aufgaben, die ich eingereicht habe, war das eher nachrangig. Es wurde zwar, in erster Linie durch die Teilnehmer selbst, das Thema aufgegriffen, z.B. ist den Foren. In den Aufgabenstellungen wird aber nichts zur Laufzeit geschrieben und auch in der Bewertung der Aufgaben war das bisher kein Thema - zumindest nicht bei mir.

Ergänzung (5. April 2022)

Problem ist, dass nur korrekter Treffer gilt, also die "beste Lösung", nicht nur eine Annäherung.

https://en.wikipedia.org/wiki/Backtracking wäre zb der einfachste Ansatz.

Das ist primär erstmal doch kein Programmierproblem, sondern ein Matheproblem im GF(2) Galois Feld

Wow, ich bin beeindruckt! Erstmal vielen Dank. Ich werde das jetzt mal durchgehen und recherchieren und melde mich wieder.

 

[tollertyp]

Grundsätzlich eine interessante Aufgabe, deren Aufgabenstellung ich dennoch etwas kritisieren muss: Laut Beschreibung ist nicht sichergestellt, dass es genau eine "Lösung" gibt. Natürlich ist es extrem unwahrscheinlich. Und damit meine ich nicht, dass eine der zufälligen 100 mit einer der 11 übereinstimmen muss (dann wäre es ja mehr oder weniger egal, weil die Information ja dieselbe ist), sondern eben dass z.B. 2 Karten aus den 100 via XOR dasselbe Ergebnis haben können wie 2 Karten aus den 11. Welche 2 sind dann die richtigen?

Soll nicht dein Problem bei der Lösung sein.

Zum Backtracking:
Weiß nicht, wie zielführend das ist, denn an und für sich weißt du erst nach letzten Mal XOR ob du einen Treffer hast, und kannst nicht vorher schon wissen, ob du mit dem Strang (der Teillösung) abbrechen kannst... oder übersehe ich da was?

 

[Raijin]

Mal ungeachtet des mathematischen Aspekts - das Galois Feld ist mir zB nicht galoifig ():

Ja, ich habe schon zwei Programme geschrieben, das Problem ist, dass ich immer in die exponentielle Laufzeit laufe, da ich, recht einfach formuliert, alle möglichen Varianten durchprobiere.

Da es bei einer Menge aus 111 Karten und einer Stichprobengröße von 11 Karten wirklich sehr sehr viele Kombinationen gibt, ist es nachvollziehbar, dass das banale Durchprobieren nacheinander ewig dauert. Zum Vergleich: 6 aus 49 ergibt schon knapp 14 Millionen Kombinationen und 11 aus 111 ist nochmal um mehrere Größenordnungen größer...

Multithreading kann bei solchen Problemen helfen, in dem man die Bearbeitung sinnvoll auf mehrere Threads aufteilt. Was/wie/wo bleibt natürlich dir überlassen.

 

[BeBur]

n den bisherigen Aufgaben, die ich eingereicht habe, war das eher nachrangig.

Informatik ist halt ein weites Feld. Aufgaben, bei welchen der naive Ansatz zu aufwendig ist und man sich was schlaues überlegen muss, das ist recht klassisch für solche Aufgaben. Kenne ich persönlich zur genüge aus einschlägigen Codewars challenges und natürlich von Uni-Aufgaben.

Reich einfach deine Lösung ein, wenn du glaubst alles andere sei nachrangig. Ich denke aber du vermutest bereits ein wenig, dass du dich hier grad selber belügst.

 

[Guyinkognito]

Wenns erlaubt ist: lädste mal die Daten hoch oder schickst per PN? Ich will dir jetzt nicht groß helfen aber klingt nach ner netten Beschäftigung fürn Sonntag Nachmittag mit 5 Bier, da können wir hier auch nen schönen Contest draus machen solange wir die Lösungen nicht posten

Davon ab: Hier fiel ja schon Backtracking - wahrscheinlich schlechte Idee. Wenn ich mir den Binominalkoeffizienten von 10 über 111 angucke gibts da wahrscheinlich Speicherprobleme wenn man es falsch angeht, Rekursion kann in solchen Fällen echt ne Bitch sein (abhängig von der Sprache, in manchen Sprachen ist das nicht so das Thema). Save währe da eher ne Lösung mit Stack oder sowas, außerdem kann man die Vergleiche aufs Xor vllt optimieren...

 

[Raijin]

Wenn ich mir den Binominalkoeffizienten von 10 über 111 angucke gibts da wahrscheinlich Speicherprobleme

Die Stichprobe ist sogar 11 groß. Es ist also 111 über 11 und somit gibt es 473 x 10¹² bzw 473 Billionen Kombinationen. Nicht dass 111 über 10 mit 51 Billionen nicht schon groß genug wäre.......

 

[Phrasendreher]

Rekursion kann in solchen Fällen echt ne Bitch sein (abhängig von der Sprache, in manchen Sprachen ist das nicht so das Thema)

+1, ausser man ginge das Problem in Prolog an. Dann wär das ein Klacks.

 

[Guyinkognito]

Die Stichprobe ist sogar 11 groß. Es ist also 111 über 11 und somit gibt es 473 x 10¹² bzw 473 Billionen Kombinationen. Nicht dass 111 über 10 mit 51 Billionen nicht schon groß genug wäre.......

Nein ist sie nicht, du wählst 10 Karten aus, hast dann noch 101 und guckst in denen ob das XOR passt. Man kann das auch mit 11 Karten machen aber da rechnet man unnötig doppelt.

 

[Raijin]

Nein ist sie nicht, du wählst 10 Karten aus, hast dann noch 101 und guckst in denen ob das XOR passt

Ähm... Also wählst du 10 + 1 = 11 Karten aka eine Stichprobe mit k = 11 aus n = 111 und somit n über k = 111 über 11.

Es gilt, ein Set von 11 Karten aus 111 Karten zu wählen und da gibt es mathematisch 111 über 11 verschiedene Kombinationen, egal wie du sie am Ende testen möchtest.

 

[Guyinkognito]

Ähm... Also wählst du 10 + 1 = 11 Karten aka eine Stichprobe mit k = 11 aus n = 111 und somit n über k = 111 über 11.

Es gilt, ein Set von 11 Karten aus 111 Karten zu wählen und da gibt es mathematisch 111 über 11 verschiedene Kombinationen, egal wie du sie am Ende testen möchtest.

Per Pn...

 

[Raijin]

Brauchst du nicht, so wichtig ist es mir nicht, Recht zu haben oder widerlegt zu werden. Ob 111 über 10 oder über 11 ist beides "viel" und dauert beim banalen Durchprobieren "lange". Sofern es da keine mathematische Methode gibt, das irgendwie in einer Matrix zu berechnen (keinen blassen Schimmer...), kann man meiner Meinung nach nur mit geschickter Aufteilung und Parallelisierung und natürlich der Optimierung der eigentlichen Prüfung nennenswerte Performancevorteile erarbeiten. Ob das dann am Ende 50 oder 450 Billionen Kombos snd, spielt keine Rolle, weil ja nur der Performancevergleich zur sequentiellen Lösung zählt.

 

[RalphS]

Hmm.... ohne jetzt besonders viel Hirnschmalz da reinzustecken, würde ich glaub ich zunächst mal alle 111 Karten als "Checksum-Karte" definieren und entsprechend jeweils einen Thread dafür aufmachen (also 111).

Und mir dann die Eigenschaften von XOR zunutze machen. Das sollte einen signifikanten Haufen Input verwerfen können. Es geht ja nicht um "irgendwelche 11 Karten aus dem Haufen". Die Dinger stehen über XOR in Bezug zueinander, bzw sollen das, und diesen Teil gilt es zu validieren. Und das möglichst "schnell".

Ja, da sind wir ganz fix bei Kryptographie, Challenge Response Systemen und der Überlegung, daß ich ein Ergebnis nicht kennen muß, um zu prüfen, ob es überhaupt ein solches sein KANN.