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

 

[Nolag]

Sollte also eine der 10 Karten verloren gehen, kann diese mit Hilfe der Sicherungskarte rekonstruiert werden.

Man kann eine Zahl rekonstruieren, aber die Zahl muss nicht nur aus einer Zahl bestehen. Wenn man das verstanden hat, kann man das Problem auf 111 über 5 reduzieren, was dann immerhin bereits in unter einer Stunden erledigt sein sollte.

 

[BeBur]

Man kann eine Zahl rekonstruieren [...]

Am 25. April ist Einsendeschluss bei dem Wettbewerb, ich würde vorschlagen, dass wir Lösungsansätze und Ideen danach erst hier rein schreiben. Ich kann ja verstehen, dass es in den Fingern juckt - geht mir auch so - aber das ist super unfair denen gegenüber, die zuhause vor einem Blatt Papier überlegen wie das gehen könnte und nicht online nach Tipps fragen bzw. suchen.

 

[andy_m4]

Am 25. April ist Einsendeschluss bei dem Wettbewerb, ich würde vorschlagen, dass wir Lösungsansätze und Ideen danach erst hier rein schreiben.

Oder als persönliche Nachricht an mich schicken. Ich verwahre es dann aus die hier einzige vertrauenswürdige Person sicher auf. ;-)

 

[tollertyp]

Und mir dann die Eigenschaften von XOR zunutze machen. Das sollte einen signifikanten Haufen Input verwerfen können.

Wie soll das gehen? Welche Eigenschaften meinst du denn konkret?

Wie willst du denn frühzeitig Karten verwerfen können? Eine Karte ändert alles.

Wenn es um eine Summenbildung von positiven Zahlen ginge, und die Zielsumme sei Betrag X, dann kann man immer wieder die Summenbildung abbrechen, sobald man X überschritten hat. Sind aber auch noch negative Zahlen dabei, ändert sich das dann auch wieder schnell...

Allerdings gibt es, wenn man es auf die Summenbilung übertragen würde, hier keine Einschränkungen bzgl. Vorzeichens und wir suchen X noch.

Ich finde, wenn Leute irgendwelche Schlagwörter oder so in den Raum werfen, sollten sie auch beschreiben, wie die Idee konkret aussieht.

 

[Nolag]

...was dann immerhin bereits in unter einer Stunden erledigt sein sollte.

Damit ich keinen Unfug erzähle, habe ich das mal laufen lassen. Auf einem i9-10900 dauert es zwischen 30 Sekunden und 2 Minuten, wenn 10 Threads verwendet werden.

 

[RalphS]

Ich finde, wenn Leute irgendwelche Schlagwörter oder so in den Raum werfen, sollten sie auch beschreiben, wie die Idee konkret aussieht.

In einem Thread der mit den Worten "für einen Wettbewerb" beginnt? Niemals, und jeder Post hier ist schon einer zuviel vor dem Hintergrund!

Aber es ist ein interessantes Problem. As for XOR, ich sehe hier keine Zahlen, sondern ich sehe 128bit lange Bitmuster und mit den Eigenschaften von XOR meine ich natürlich genau das: unter welchen Umständen welche Bits wie gesetzt sein können(!) wenn meine Eingabe so-und-so aussieht.
Also eben jene Eigenschaften, die man nutzt, um eben jenes XOR für Checksums zu verwenden.

Das Ausgangsproblem scheint, wenn ich es richtig verstanden habe, dasselbe "Problem" zu haben wie RAID4: Die Parität ist konzentriert, nicht verteilt.

Ich sage aber an der Stelle auch, ich habe hier nur sehr wenig "Grips" investiert, siehe auch den OP. Alle weiteren konkreteren Gedanken, wenn ich sie hätte, würde ich sie hier nicht posten oder würde dies zumindest gemäß @BeBur's Vorschlag erst später tun.

 

[tollertyp]

Bin immer noch etwas unschlüssig, welche Gedanken man sich da konkret machen kann.

Und sehe auch nicht, was das konkret mit RAID4 zu tun hat.

 

[BFF]

Am 25. April ist Einsendeschluss bei dem Wettbewerb, ich würde vorschlagen, dass wir Lösungsansätze und Ideen danach erst hier rein schreiben.

Und damit niemand vorher "petzen" kann, ist hier auch zu.

@Mundy
Melde Dich bei Bedarf nach dem 25. April falls dann noch Interesse am Thread besteht bei mir oder einem anderen Moderator.