Als die Hamming-Distanz zweier beliebiger Binärwörter mit gleicher Länge bezeichne man die Anzahl der Stellen, an welchen sich die beiden gegebenen Wörter unterscheiden. Die Hamming-Distanz einer Menge an Binärwörter mit gleicher Länge ist die kleinste Hamming-Distanz von paarweise verschiedenen Wörtern in dieser Menge (sind hingegen zwei gleiche Elemente in einer Menge, ist die Hamming-Distanz \(0\)).

Zur Repräsentation eines Binärworts mit digits Ziffern werden longs verwenden, wobei ausschließĺich die niederwertigsten digits Ziffern verwendet werden.
Beispiel: Das Binärwort \(101010\) entspricht in der internen Darstellung eines longs \(\underbrace{0 … 0}_{58 \text{ Nullen}}101010\).

Die Methode hdWord soll die Hamming-Distanz zwischen zwei Wörtern bestimmen.


Hinweis: Sie dürfen in der ersten Teilaufgabe natürlich nicht hdList aus der nachfolgenden Teilaufgabe verwenden. :)

Die Methode hdList soll die Hamming-Distanz der durch l repräsentierten Menge an Codewörter bestimmen. Nutzen Sie hierfür hdWord aus der vorherigen Teilaufgabe.

Mithilfe von Backtracking soll nun eine größtmögliche Menge an Binärwörtern mit digits Zeichen bestimmt werden, die eine Hamming-Distanz von mindestens hd hat. Implementieren Sie hierfür die Methode helper, welche von bestList aufgerufen wird. Die Liste \(l\) ist dabei eine Arbeitsliste, die den aktuellen Zustandsraum während des Backtrackings beschreibt. Wenn die Liste l mehr Elemente enthält als die bisher beste gefundene, dann soll eine Kopie der Liste l in dem lokalen Feld best angelegt werden (nutzen Sie hierfür unbedingt zum Klonen der Liste new LinkedList<>(l);). Sie sollen und dürfen die Methoden der vorherigen Teilaufgabe verwenden.