Hier ist sie nun die Lösung - auch wenn der Gehirnschmalz dahinter nicht von mir kommt, die Implementierung ist von mir. 😉
Damit wir im weiteren Verlauf einfach und übersichtlich arbeiten können brauchen wir zwei kleine Extras. Zum einen eine Extension-Method die aus einer IEnumerable von IGroupings wieder eine flache Liste macht:
public static class Extensions {
public static List<TOut> ToFlatList<TOut>(this IEnumerable<IGrouping<int, TOut>> grouping) {
var newList = new List<TOut>();
foreach (var group in grouping)
newList.AddRange(group);
return newList;
}
}
Als nächstes brauchen wir noch eine Datenstruktur die Zahlenpaare sowie deren Produkte, Summen und Differenzen halten kann:
private struct CalculationInfo {
public int X;
public int Y;
public int Product;
public int Sum;
public int Difference;
public override string ToString() {
return string.Format("CalculationInfo: X={0}, Y={1}, Product={2}, Sum={3}, Difference={4}", X, Y, Product, Sum, Difference);
}
}
Bis hierhin war's einfach. 😁
Für die Lösung des Rätsels brauchen wir eine Liste mit den Faktoren und Summanden. Sowohl Multiplikation als auch Addition sind Kommutativ (Das Zahlenpaar (X,Y) ist für die Lösung der Aufgabe identisch zum Paar (Y,X)). Zwar ist die Subtraktion nicht kommutativ, trotzdem kann man aufgrund der Aufgabenstellung davon ausgehen, dass der Betrag der Differenz interessant ist, denn Daniela erwähnt nichts von einer positiven oder negativen Zahl. Von daher können wir um unnötigen Rechenaufwand zu vermeiden für die Lösung auf Zahlenpaare zurückgreifen, bei denen die zweite Zahl größer oder gleich der ersten ist.
var workingList = new List<CalculationInfo>();
for (var x = 1; x <= 1000; x++)
for (var y = x; y <= 1000; y++)
workingList.Add(new CalculationInfo {
X = x,
Y = y,
Product = x * y,
Sum = x + y,
Difference = Math.Abs(x - y)
});
Berta sagt zu den anderen: "Ich kann die Lösung nicht nennen".
Was verannlasst Berta zu dieser Aussage? Antonia hat Berta das Produkt zweier Zahlen genannt. Wäre das Produkt kleiner als Tausend und eine Primzahl, dann würde Berta die Lösung kennen, denn dann kämen nur zwei Zahlen in Betracht: Die eins und das Produkt selber.
Berta würde die Lösung ebenfalls kennen, wenn die genannte Zahl größer als 1000 und das Produkt zweier Primzahlen wäre - denn dann würde die Lösung mit der eins nicht mehr greifen.
Die Zahl 5055 zum Beispiel ist in der Primfaktorenzerlegung 3 x 5 x 337. Soll das Produkt durch zwei Zahlen im Bereich von 1 bis 1000 dargestellt werden geht das nur als 15 x 337, denn sowohl bei 3 x 1685 als auch bei 5 x 1011 ist der zweite Faktor größer als 1000.
Wirklich aussagekräftig ist die Aussage von Berta also nicht, denn wir haben ja schon festgestellt, dass wir mit Primzahlen nicht weiterkommen.
Was wir aber wissen, ist, dass das Produkt, das Antonia Berta zugeflüstert hat mehrfach vorkommen muss, denn ansonsten wüsste Berta ja bereits was die Lösung wäre.
Diese Erkenntnis könnten wir jetzt ausnutzen um die Menge der verfügbaren Zahlenpaare einzugrenzen - tun wir aber nicht.
Christina antwortet: "Das wusste ich 😄"
Da scheint sich Christina ja ganz schön sicher zu sein. Dieser Hinweis ist - nunja - herausfordernd platziert. Den Christina wusste eigentlich schon von Anfang an, dass Berta die Lösung nicht kennen kann.
Was heißt das genau? Christina sieht eine Zahl, die man nur so aus zwei Summanden zusammensetzen kann, dass für alle Paare der Summanden gilt was zuvor bereits gesagt wurde. Kennt Christina zum Beispiel die Zahl 18, könnte die Lösung 1 + 17 sein. 17 ist allerdings eine Primzahl und deswegen könnte Berta die Lösung kennen. Also könnte im Falle der 18 Christina nicht schon vorher wissen das Berta die Lösung nicht kennt. Damit scheidet die 18 aus, und mit ihr alle Paare von Zahlen die addiert 18 ergeben.
Was lernen wir? Die Information das Christina weiß, dass Berta die Lösung nicht kennt ist viel Wertvoller als das Geständnis von Berta keine Ahnung zu haben.
Wir können jetzt aus unserer Arbeitsliste alle die Datensätze streichen bei denen eine oder mehrere Kombinationen von Summanden existieren mit denen man bei Kenntnis des Produktes auf die Lösung kommen würde.
Im Klartext heißt das: Wir suchen alle eindeutigen Produkte aus der Arbeitsliste, holen uns die dazugehörigen Summen und entfernen anschließend alle Werte mit diesen Summen aus der Arbeitsliste. Im Code sieht das dann so aus:
var sumsByUniqueProducts = workingList.GroupBy(value => value.Product)
.Where(item => item.Count() == 1)
.ToFlatList()
.GroupBy(value => value.Sum)
.Select(value => value.Key)
.ToArray();
workingList = workingList.Where(workingItem => !sumsByUniqueProducts.Contains(workingItem.Sum)).ToList();
Damit enthält die Worklist jetzt statt 500500 nur noch 27596 Einträge.
Darauf Berta: "Dann weiß ich jetzt die Lösung."
Dieser Hinweis ist deutlich einfacher auszuwerten als die vorhergehenden. Wir wissen jetzt, dass das Produkt der gesuchten Zahlen nur noch einmal in der Arbeitsliste vorkommt. Das wiederum erlaubt es uns alle einträge aus der Arbeitsliste zu entfernen, deren Produkt mehr als einmal in der Liste auftaucht.
workingList = workingList.GroupBy(value => value.Product)
.Where(item => item.Count() == 1)
.ToFlatList();
Die Arbeitsliste enthält jetzt noch 6984 Einträge.
Christina entgegnet: "Dann weiß ich sie jetzt auch."
Dieser Hinweis enthält eine ähnliche Annahme wie der vorangegangene von Berta. Nur das sich die Annahme hier auf die Summen und nicht auf die Produkte bezieht. Wir können also damit Fortfahren alle Einträge aus der Liste zu entfernen deren Summe mehr als einmal in der Liste auftaucht.
workingList = workingList.GroupBy(value => value.Sum)
.Where(item => item.Count() == 1)
.ToFlatList();
Jetzt bleiben noch niedliche 27 EInträge übrig.
Daniela sagt: "Ich nicht, aber ich habe eine Vermutung, was eine der beiden Zahlen wahrscheinlich ist."
Aus diesem Hinweis kann man zwei Schlussfolgerungen ziehen. Einerseits weist er darauf hin, dass in der Menge der Zahlenpaare aus denen man Danielas Differenz bilden könnte ein Wert häufiger vorhanden ist als andere.
Es gibt allerdings noch eine weitere Schlussfolgerung: Danielas Differenz ist in der Arbeitstabelle mehr als einmal vorhanden, denn sonst wüsste Sie das Ergebnis ja jetzt auch.
Genau genommen müssen für die infragekommende Differenz mehr als zwei Einträge vorhanden sein, denn sonst kann nicht einer der Werte häufiger vorhanden sein als alle anderen.
workingList = workingList.GroupBy(value => value.Difference)
.Where(item => item.Count() > 2)
.ToFlatList();
Unsere Arbeitsliste enthält jetzt noch genau 6 Einträge.
Berta sagt: "Ich weiß, was du vermutest, aber das ist falsch."
Von so einer Aussage lässt sich Daniela allerdings nicht unterkriegen. Wir wissen jetzt dass einer der Werte bei zwei Datensätzen der Arbeitsliste auftauchen muss. Das Ergebnis dieser Datensätze ist also die Differenz. Dazu zählen wir die Datensätze bei denen der doppelte Wert vorkommt und entfernen anschließend alle Datensätze die die dort berechnete Differenz nicht enthalten aus der Arbeitsliste.
var occurrences = new Dictionary<int, int>();
foreach (var difference in workingList) {
if (!occurrences.ContainsKey(difference.X))
occurrences.Add(difference.X, 0);
occurrences[difference.X]++;
if (!occurrences.ContainsKey(difference.Y))
occurrences.Add(difference.Y, 0);
occurrences[difference.Y]++;
}
var wrongNumber = occurrences.Where(item => item.Value == occurrences.Values.Max())
.First()
.Key;
workingList = workingList.Where(item => item.X != wrongNumber &&
item.Y != wrongNumber)
.ToList();
Wir erhalten eine Liste mit drei Werten. Jetzt ist auch Daniela stolz wie Oskar:
Daniela: "Dann kenne ich jetzt auch die Lösung."
Jetzt weiß auch Daniela dass ihre Differenz in der Arbeitsliste nur noch ein einziges Mal enthalten ist und kann so die überflüssigen Datensätze ausschließen:
workingList = workingList.GroupBy(value => value.Difference)
.Where(item => item.Count() == 1)
.ToFlatList();
Und endlich, endlich kennen auch wir den gesuchten Datensatz:
CalculationInfo: X=64, Y=73, Product=4672, Sum=137, Difference=9
Den Code habe ich nochmal als kompilierbare Datei an diesen Beitrag angehängt. Vielen Dank an fairymail.de für die Denkarbeit hinter der Lösung 😉
