kleemans.ch

Eine Lotterie teilt 1 Milliarde Lose aus, nummeriert von 000'000'000 bis 999'999'999. Gegeben sind eine bestimmten Anzahl "guten" Suffixe/Endungen in goodSuffixes, welche angeben, ob der betreffende einen Preis gewonnen hat. Die Aufgabe besteht darin, auszurechnen, wie hoch die Gewinnchancen für ein zufälliges Los sind, wenn die "guten" Suffixe bekannt sind.

Beispiel:

• goodSuffixes = {"4"} –> Alle Lose mit Endziffer -4 gewinnen. Die Wahrscheinlichkeit, mit einem beliebigen Los zu gewinnen, beträgt daher 0.1 oder 10%.
• goodSuffixes = {"12", "23", "3", "6"} –> Alle Lose mit Endziffern -12, -3 und -6 gewinnen (Suffix "23" ist redundant; Diese Lose werden bereits mit "3" miteinberechnet) -> 0.21

Lösungsansatz

• Entferne alle doppelte Suffixe ("054","054")
• Entferne alle redundanten Suffixe ("0302","02")
• Zähle die verbleibenden Suffixe mit entsprechender Gewichtung.

Um sinnvoll an die Aufgabe heranzugehen, benutze ich 2 Hilfsfunktionen.

a.) Element aus String-Array entfernen

Funktionsweise: Kopiere solange die Elemente eines Arrays a in ein Array b, bis das Element erreicht wird, welches entfernt werden soll. Überspringe dieses und kopiere die restlichen Elemente.

public String[] removeElement(String[] a, int del) {
  String[] b = new String[a.length-1];

  int i = 0;
  int j = 0;
  while (i < a.length && j < b.length) {
    if (i == del) i++;
    else {
      b[j] = a[i];
      i++;
      j++;
    }
  }
   return b;
}

b.) Überprüfen, ob 2 Strings denselben Suffix haben

Funktionsweise: Ermittle die kürzere Länge der beiden Eingabestrings, schneide den Rest beim längeren String vorne ab und vergleiche die beiden Strings auf Gleichheit (boolescher Test a.equals(b)).

public boolean sameStringSuffix (String a, String b) {
  int len = Math.min(a.length(), b.length());
  a = a.substring(a.length()-len, a.length());
  b = b.substring(b.length()-len, b.length());
  return a.equals(b);
}

Lösung (Sourcecode)

Der Code "säubert" zuerst die Eingabe auf gleiche oder redundante Elemente, entfernt sie wenn nötig, und rechnet am Schluss die summierende Wahrscheinlichkeit (Variable prob) aus. Die kürzeren Elemente werden entsprechend höher gewichtet (da sie eine höhere Anzahl an Losen abdecken).

public double find(String[] gS) {
  double prob = 0;

  //clear goodSuffixes
  for (int i=0; i < gS.length; i++) {
    for (int j=i+1; j < gS.length; j++) {
      //redundant elements
      if (sameStringSuffix(gS[i], gS[j])){
        gS = removeElement(gS, gS[i].length() > gS[j].length() ? i : j);
        i=0;
        j=0;
      }
    }
  }

  // calculate probability
  for (int i=0; i < gS.length; i++) {
    prob += 1/(Math.pow(10,(gS[i].length())));
  }

  return prob;
}

Dieses Problem wurde beim SRM 502 auf Topcoder als Aufgabe formuliert (siehe Problemstellung).