OK scheint mir minimal anders gemacht zu sein als meine Version aber das Ergebnis ist einwandfrei du darfst die neue Aufgabe stellen wenn du noch kurz sagst was das darstellt hast du nämlich vergessen ;)
Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!
dargestellt werden zahlen (0-1023) in binärform. jeweils eine Spalte (1 pixel) stellt eine zahl dar. das niederwertigste bit ist unten, das höchstwertige oben.
Ok.. Man nehme ein Schachbrett und ein Pferd. Das Pferd soll per Rösselsprung von einem beliebigen Feld mit möglichst wenigen Zügen auf ein beliebiges anders Feld springen. Fülle die vorgegebene Methode mit Leben.
Schreibe (ausnahmsweise ohne dabei die Klasse Regex zu verwenden) eine Methode [TT]public static bool FullMatch (String input, String pattern)[/TT], die zurückliefert, ob ein Pattern, der die Platzhalterzeichen ? (Fragezeichen passt auf genau ein beliebiges Zeichen) und * (Stern passt auf beliebig viele Zeichen, also 0, 1 oder mehr Zeichen) enthalten kann, auf den kompletten Text passt.
A passt auf A
A passt nicht auf AB
a passt nicht auf A
HALLO passt auf HALLO
? passt auf A
? passt auf B
? passt auf ?
? passt auf * (im Text haben die Platzhalterzeichen keine Sonderbedeutung)
? passt nicht auf den leeren String
? passt nicht auf AB
?? passt nicht auf A
?? passt auf AA
?? passt auf AB
?? passt nicht auf ABC
??C passt auf ABC
??C passt auf CCC
??C passt nicht auf CCCC
??C passt nicht auf ABD
??C passt nicht auf AC
* passt auf alle Texte, auch auf den leeren Text
A* passt auf alle Texte, die mit A anfangen, auch auf den Text A allein
*A passt auf alle Texte, die A enden, auch auf den Text A allein
*A* passt auf alle Texte, die mindestens ein A enthalten, auch auf den Text A allein
*A*B* passt auf alle Texte, die mindestens ein A und irgendwo danach mindestens ein B enthalten, auch auf den Text AB allein, aber nicht auf BA
A*B passt auf alle Texte, die mit A anfangen und mit B enden, auch auf den Text AB allein
A*A passt auf alle Texte, die mit A anfangen und mit A enden, auch auf den Text AA allein, aber nicht auf A allein
Wie man sieht, macht es einen Unterschied, ob man ein Fragezeichen oder mehrere Fragezeichen direkt hintereinander verwendet. Es macht aber keinen Unterschied, ob man einen Stern oder mehrere Sterne direkt hintereinander verwendet. A*B und A******B passen also auf exakt die gleichen Texte. Es kann die Implementierung der Methode vereinfachen, wenn man zu Anfang im Pattern jede Folge von mehreren direkt aufeinander folgenden Sternen durch jeweils einen einzelnen Stern ersetzt.
[EDIT2018]Man kann sogar noch weiter gehen: Eine beliebige Folge aus Sternen und/oder Fragezeichen kann man ersetzen durch einen String mit der gleichen Anzahl von Fragezeichen, gefolgt von einem einzelnen Stern, sofern in der ursprünglichen Folge mindestens ein Stern enthalten war, z.B. [TT]*?***?*?[/TT] => [TT]???*[/TT].[/EDIT2018]
ich habe einen Fall gefunden, in dem die Methode noch nicht das richtige Ergebnis liefert, nämlich bei
FullMatch("", "*")
Wie auch in den Beispielen steht, "passt * auf alle Texte, auch auf den leeren Text". Möglicherweise gibt es weitere Fälle, die noch nicht passen.
Hallo zusammen,
eine rekursive Lösung ist sicher möglich, aber ebenso sicher nicht nötig. Wenn ich nichts übersehe, was ich nicht glaube, dann kann man das Problem vollständig ohne Backtracking lösen, wenn man alle Sterne bis auf den letzten auf den jeweils kürzesten Match passen lässt (lazy) und den letzten Stern auf den längsten Match (greedy).
nein, leider noch nicht ganz. :-) Ich habe mittlerweile ca. 50 Testfälle für Pattern mit einem oder mehreren Sternen erstellt, bei denen deine Methode zweimal das falsche Ergebnis liefert und achtmal eine Exception wirft.
Einer der Testfälle mit falschem Ergebnis ist:
FullMatch("ABC1XYZLMNLMN", "ABC*X?Z*LMN")
Einer der Testfälle mit Exception ist:
FullMatch("A", "*B")
NullReferenceExceptions bei der Übergabe von null für input und/oder pattern habe ich nicht berücksichtigt, weil man diese durch folgenden Code am Anfang der Methode leicht verhindern kann:
if (input == null) { input = ""; }
if (pattern == null) { pattern = ""; }
so pingelig finde ich mich gar nicht. So sage ich z.B. nichts gegen die Fälle, bei denen mindestens ein Parameter null ist. Das ist eine Definitionsfrage, die ich offen gelassen habe. Deshalb ist es ok, dass FullMatch(null, "") und FullMatch("", null) bei dir false liefert, obwohl ich persönlich da entweder true liefern oder eine ArgumentNullException werfen würde. Aber bei allen anderen (normalen) Pattern sollte die Methode schon das in der Aufgabe beschriebene machen. :-) Und wenn sie das auch nur für einen Pattern nicht macht, dann ist sie eben noch nicht korrekt. :-)
Aber jetzt bist du schon sehr nahe dran. Ich habe noch zwei Fälle, die nicht klappen:
Das liegt daran, dass du in dem Fall, in dem das aktuelle Zeichen ein Stern ist, noch nicht berücksichtigst, dass das nächste Zeichen ein Fragezeichen sein kann. Diese Fälle sind aber nicht ungewöhnlich, denn wenn man beliebig viele, aber mindestens ein Zeichen matchen möchte, muss man bei der Pattern-Syntax aus der Aufgabe ?* oder eben *? benutzen.
Gratulation! Was lange währt, wird endlich gut. Alle meine bisherigen Tests laufen erfolgreich durch und ich kann auch bei der Durchsicht des Codes keinen Fall konstruieren, der fehlschlägt. Die Aufgabe ist damit gelöst. Du bist dran.
Hier noch meine Lösung, die einem etwas anderen Ansatz folgt. Ich teile den Pattern bei jedem Stern auf, so dass die Teile selbst keinen Stern mehr, sondern als Platzhalter maximal noch Fragezeichen enthalten können. Für den Test, ob so ein Teil an einer bestimmten Stelle passt, habe ich die Methode PartMatch geschrieben. Die Methode FullMatch unterscheidet dann drei Fälle: Der erste Part muss genau am Anfang, der letzte Part muss genau am Ende passen und für jeden Part dazwischen wird ausgehend von der aktuellen Position die nächste mögliche Position ermittelt, an der er passt. Das return am Ende der Methode fängt den Fall ab, dass es nur einen Part gibt, der erste Part also gleichzeitig der letzte ist, also gleichzeitig auch am Ende passen muss, bzw. genauer gesagt sich bis zum Ende erstrecken muss.
Wie ich finde eine ganz nette Architektur, aber leider wegen der vielen Index- und Offset-Berechnungen letztlich doch nicht ganz so lesbar, wie man sich das wünschen würde. Deshalb würde ich in der Praxis Regex vorziehen:
Die Kürze dieser Methode macht dann auch klar, warum Regex für die Aufgabe ausgeschlossen war. :-)
[EDIT2018]
Die im Tipp zur Aufgabe angesprochene Normalisierung des Pattern bezüglich beliebiger Folgen aus Sternen und/oder Fragezeichen leistet die folgende Methode. Meine FullMatch-Methode arbeitet auch ohne die Normalisierung korrekt. Trotzdem kann man diese Normalisierung vor dem Splitten einbauen/aufrufen, da sie in bestimmten Fällen den Laufzeitaufwand der FullMatch-Methode um eine Aufwandsklasse reduziert.
private static String NormalizePattern (String pattern)
{
return Regex.Replace (pattern, @"[?*]{2,}", m => new String ('?', m.Value.Count (c => c == '?')) + (m.Value.Contains ('*') ? "*" : ""));
}
[/EDIT2018]
herbivore
PS: Deinen Code, um sicherzustellen, dass input und pattern nicht null sind, ist nett kurz, führt aber m.E. dazu, dass der komplette Text (und Pattern) einmal umkopiert wird:
Vielen Dank für deine Lösung - ich hab die Aufgabe offenbar anfänglich zu einfach eingeschätzt. :)
Meine Aufgabe ist nun nicht sonderlich ausgefallen, weil es sich ebenfalls um eine Textsuche handelt aber sie ist dennoch interessant wie ich finde:
Ausgehend vom ReSharper der meiner Meinung nach eine unglaublich tolle File-, Member- und IntelliSense- Suche hat, habe ich einmal für ein Projekt versucht ähnliches Suchverhalten umzusetzen und bin von dem Resultat sehr begeistert. Algorithmisch ists zwar nur eine Textsuche kann aber trotzdem recht knifflig sein:
Das ist die Testumgebung:
static void Main(string[] args)
{
/*
* Ein Match ist dann erfolgreich, wenn alle Zeichen aus dem Pattern im Input gefunden wurden.
* - falls der Match nicht klappt - wird ein leerer Match zurückgegeben -> eben kein Match
* Dabei werden groß/klein-Schreibung sowie Whitespaces im Pattern ignoriert.
* Ein leerer Pattern ist automatisch ein leerer Match.
* Das Pattern kann potentiell in mehreren Varianten passen aber nur die "Beste" soll zurückgegeben werden.
* Dabei sollen die Teilergebnisse gewichtet werden:
* - Matches mit weniger Parts werden anderen mit mehreren bevorzugt
* - Bei gleicher Partanzahl, gewinnt der Match der mehr Anfangsbuchstaben in den Parts hält
* -> Als Anfangsbuchstaben werden alle Großbuchstaben nach einem Kleinbuchstaben und alle Buchstaben, vor denen kein Buchstabe steht, gewertet. "Hallo Welt", "HalloWelt" - beide Varianten haben zwei Wortanfänge
* - Beim Auswerten der Anfangsbuchstaben sollen Großbuchstaben den Kleinbuchstaben bevorzugt werden
* - Bei gleicher Partanzahl und gleicher Anfangsbuchstabenanzahl, gewinnt der Match bei dem die Parts weiter am Anfang stehen.
*/
TestAndPrintMatch("Das ist ein Auto", "aa", "D[a]s ist ein [A]uto");
TestAndPrintMatch("Hallo Welt", "Hallo Welt", "[Hallo] [Welt]");
TestAndPrintMatch("Hawai hat schöne Wellen", "hw", "[H]awai hat schöne [W]ellen");
TestAndPrintMatch("Hallo Welt", "hw", "[H]allo [W]elt");
TestAndPrintMatch("H a l l o Hallo", "halo", "H a l l o [Hal]l[o]");
TestAndPrintMatch("DasIstIrgendEinText", "irgend", "DasIst[Irgend]EinText");
TestAndPrintMatch("Jetzt ists aus mit der Maus", "aus", "Jetzt ists [aus] mit der Maus");
TestAndPrintMatch("Das ist mein Auto", "a u t o", "Das ist mein [Auto]");
TestAndPrintMatch("Das ist mein Auto", "ma", "Das ist [m]ein [A]uto");
TestAndPrintMatch("Ohne Treffer", "xx", "Ohne Treffer");
TestAndPrintMatch("Hier steht mein Haus", "iHaus", "H[i]er steht mein [Haus]");
TestAndPrintMatch("Peter Müller träumte von Peter Pan", "Peter Pan", "[Peter] Müller träumte von Peter [Pan]");
TestAndPrintMatch(new String('a', 200), new String('a', 100), "");
Match match1 = TextSearch.FindMatch("Anna und Toni können sich zusammenraufen", "autokauf");
Match match3 = TextSearch.FindMatch("Ich habe mir kein Auto gekauft", "autokauf");
Match match2 = TextSearch.FindMatch("Autos kauft man nicht im Supermarkt", "autokauf");
List<Match> matches = new List<Match> { match1, match2, match3 };
matches.Sort();
Console.WriteLine(matches[0] == match2);
Console.WriteLine(matches[1] == match3);
Console.WriteLine(matches[2] == match1);
}
private static void TestAndPrintMatch(string input, string pattern, string expected)
{
Match match = TextSearch.FindMatch(input, pattern);
int offset = 0;
foreach (MatchPart part in match)
{
input = input.Insert(part.Index + offset++, "[");
input = input.Insert(part.Index + offset++ + part.Length, "]");
}
PrintText("Soll: ", expected);
PrintText("Ist : ", input);
Console.WriteLine();
}
private static void PrintText(string preText, string expected)
{
ConsoleColor defaultColor = Console.ForegroundColor;
Console.Write(preText);
foreach (char c in expected)
{
Console.ForegroundColor = (c == '[' || c == ']') ? ConsoleColor.Red : defaultColor;
Console.Write(c);
}
Console.ForegroundColor = defaultColor;
Console.WriteLine();
}
und hier soll die Implementierung rein:
public class TextSearch
{
public static Match FindMatch(string input, string pattern)
{
//implement this method
}
}
public class Match : Collection<MatchPart>, IComparable<Match>, IComparable
{
public int CompareTo(Match other)
{
//and this method
}
public int CompareTo(object obj)
{
return CompareTo(obj as Match);
}
}
public struct MatchPart
{
public int Index { get; set; }
public int Length { get; set; }
}
Zu implementieren ist die Methode FindMatch. Bei Bedarf kann auch die Klasse Match bzw. MatchPart angepasst werden.
Lg und viel Vergnügen,
XXX
//Edit: Match angepasst - die CompareTo Methode wird fürs Sortieren gebraucht um später mehrere Treffer nach besten Treffern sortieren zu können.
//Edit²: Main Methode angepasst um noch einen weiteren Testfall(Sortierung) sowie die Vorgaben etwas mehr fixiert: Bei gleicher durchschnittlicher Textlänge und gleicher Anfangs und Endbuchstabenanzahl gewinnt das Ergebnis bei denen die Teiltreffer weiter links angeordnet sind.Bei gleicher Partanzahl und gleicher Anfangsbuchstabenanzahl, gewinnt der Match bei dem die Parts weiter am Anfang stehen.
//Edit³: Bedingungen leicht umformuliert und angepasst: Wortenden werden jetzt nicht sonderlich bewertet
//Edit die 4.: Bedingungen nochmals erweitert - Beim Finden von Anfangsbuchstaben werden Großbuchstaben den Kleinbuchstaben bevorzugt behandelt.
Dieser Beitrag wurde 14 mal editiert, zum letzten Mal von xxxprod am .
die Aufgabe hat es wirklich in sich. Zumindest wenn man nach einer effizienten Lösung sucht. Natürlich könnte man es sich einfach machen, und alle Kombinationen, in denen der Pattern auf den Text passt, ermitteln und dann durch die resultierende Liste gehen und - mit dem passenden Comparer - den besten Treffer suchen. Aber damit bekommt man einen explodierenden Aufwand, der schon bei relativ kurzen Texten und Pattern dazu führen kann, dass die Methode (weit) länger als ein paar Sekunden benötigt.
Hier zeigt sich die Ähnlichkeit zu dem verwandten Longest common subsequence problem, das NP-schwierig ist. Obwohl das Grundproblem der aktuellen Aufgabe, nämlich überhaupt irgendeinen Treffer zu finden, mit linearem Aufwand im Vergleich zur Länge n des Texts zu lösen ist (O(n)) und damit sogar schneller als eine einfache String-Suche, die immerhin einen maximalen Aufwand von O(m*n) hat, wobei m die Länge des Pattern ist.
Eine simple String-Suche - bei der der Pattern (halb) solang wie der Text ist - kann also einen quadratischen Aufwand haben. Wenn man z.B. den Pattern new String ('a', n/2) + "b" in dem Text new String ('a', n) sucht (wahlweise mit "b" am Ende oder auch nicht) und n in gleichmäßigen Schritten erhöht, wird man sehen, wie die Laufzeit quadratisch wächst und im Bereich von ca. n=100.000 bis 1.000.000 langsam unerträglich wird. Das liegt daran, dass es n/2 Stellen gibt, in denen fast der ganze Pattern passt, also auf einer Länge von n/2 geprüft wird, und damit (mindestens) (n/2)^2 Zeichenvergleiche durchgeführt werden.
Wer es nicht glaubt, kann ja mal folgenden Code laufen lassen:
for (int i = 0; ; i += 10000) {
String text1 = new String ('a', i);
String pattern1 = new String ('a', i/2) + "b";
Console.Write (i);
Console.Write (": ");
Console.WriteLine (text1.Contains (pattern1)); // Auf das Contains kommt es an
}
Aber zurück zu der aktuellen Aufgabe: Quadratischer Aufwand ist nichts gegen den Aufwand bei der oben genannten simplen Implementierung der aktuellen Aufgabe, erst alle Kombinationen zu suchen und aus diesen dann den besten Treffer zu suchen. Das kann man sich wieder an dem Pattern new String ('a', n/2) + "b" überlegen, nur dass man als Text jetzt n mal direkt hintereinander die Zeichenfolge "a|" verwendet (also ein Text der Länge 2*n). Wer mag kann ja mal die möglichen Kombinationen ausrechnen, in denen der Pattern überhaupt auf den Text passt.
Wenn man in der aktuellen Aufgabe das Kriterium der Wortanfänge weglässt habe ich momentan eine Lösung gefunden, deren maximaler Aufwand - wenn ich mich nicht vertue - im Bereich O(n*(m^3)) liegt. Der durchschnittliche Aufwand dürfte sogar eher im Bereich von n oder n*m liegen. Aber das ist nur grob geschätzt.
Zumindest wenn man das Kriterium mit den Wortanfängen weglässt, gibt es also eine Lösung mit polynomieller Laufzeit und wenn es nach mir geht, sollte eine Forderung nach Effizienz in die Aufgabestellung aufgenommen werden. Allerdings überlege momentan noch, wie ich das Kriterium mit den Wortanfängen in meine momentane Lösung einbauen kann. Dabei bin ich mir noch nicht sicher, ob es dafür überhaupt eine Lösung mit polynomieller Laufzeit gibt. Das ist, wie ich finde, eine sehr spannende Frage. Leider ist es schwer, eine präzise Formulierung des Effizienzkriteriums zu finden, solange man nicht weiß, eine wie effiziente Lösung überhaupt möglich ist.
Ich weiß natürlich nicht, warum noch keiner eine Lösung gepostet hat. Weil es verhältnismäßig schwierig ist, eine effiziente Lösung zu finden? Oder weil die Aufgabe keinen interessiert? Ich persönlich halte die Aufgabe für sehr spannend und würde mich freuen, wenn ihr euch auf die Suche nach eine effizienten(!) Lösung macht. Um euch nicht zu sehr in eine bestimmte Richtung zu lenken, poste ich heute noch keine (Zwischen-)Lösung.
ich kann dazu nur sagen, dass meine ursprüngliche Implementierung eine sehr naive war und ich auch nur in relativ kurzen Texten relativ eindeutige Textpassagen suchen lasse wodurch der Aufwand nie ein Problem war. Nachdem mir herbivore aber nun die Schwierigkeiten aufgezeigt hat, bin ich nun selbst auch wieder am Werken um eine optimalere Lösung zu finden.
gut Ding will Weile haben. Hier kommt meine Lösung. Obwohl ich nicht die Zeit gefunden habe, sie intensiver zu testen, hoffe ich, dass die korrekt ist. Sie erfüllt alle Kriterien bis auf das nachträglich hinzugefügte Kriterium mit der Präferenz von Großbuchstaben.
Das Kriterium der möglichst weit links stehenden Parts kann man unterschiedlich interpretieren. Ich verwende leicht andere Interpretation(*), als die, die xxxprod beim Stellen der Aufgabe im Sinn hatte. Ich habe bereits mit ihm gesprochen und er sieht diese Abweichung in der Auslegung als akzeptabel an.
(*) Kurz gesagt bevorzuge ich bei der Suche längere Parts gegenüber kürzeren. Dadurch bevorzugt meine Implementierung bei der Suche nach "halo" in "Hallo" den Treffer "[Hal]l[o]" vor "[Ha]l[lo]". Im diesem Beispiel ist bei mir also die Summe aller Part.Index-Werte um eins höher (0+4=4 statt 0+3=3). Im Gegenzug ist bei mir die Summe alle Index-Werte aller Zeichen in den Parts um eins geringer (0+1+2+4=7 statt 0+1+3+4=8). Man kann sicher darüber streiten, nach welcher Definition die Parts nun weiter links stehen. Bei mir stehen alle Buchstaben im Treffer und damit die Parts als ganzes möglichst weit links, bei xxxprod sind es die Part-Anfänge, die möglichst weit links stehen, was die bewusste Abweichung in dem genannten Testfall erklärt. Bei Bedarf würden sich Treffer nach der einen Definition in einem schnellen Postprocessing-Schritt einfach in Treffer nach der anderen Definition überführen lassen.
Nach dieser Klarstellung, kurz zur Funktionsweise meines Codes. Zur Vereinfachung beschreibe ich erstmal das Prinzip der Suche, die keine Wortanfänge berücksichtigt:
Ich beginne mit einem leeren Match (im folgenden Treffer genannt; mit Teiltreffer sind im folgenden Matches gemeint, die noch nicht komplett sind). Jetzt suche ich alle Stellen im Text, an denen der Anfang des Patterns beginnt. An jeder dieser Stellen schaue ich bzw. die Methode FindParts, wie weit die zusammenhängende Übereinstimmung jeweils maximal geht. Es werden also überhaupt nur Parts berücksichtigt, die maximal sind, also die an ihrer Stelle die maximal mögliche Übereinstimmung mit dem Pattern haben. Außerdem wird ein weiter rechts stehender Part nur dann berücksichtigt, wenn er länger ist als alle vorher gefundenen Parts.
Beispiel: Bei der Suche nach "abcdef" in "xy bcd abc ab abc defe abcdex a f" liefert FindParts nur zwei Parts, nämlich das erste "abc" und das eine "abcde". Alle anderen Part sind nicht länger als der jeweils längste vorher gefundene Part und können daher ignoriert werden.
Wir sind gedanklich noch im ersten Durchlauf, in dem gerade zwei Parts gefunden wurden. Deshalb wird nun der leere Treffer zweimal dupliziert und das eine Duplikat um den Part "abc" verlängert und das andere um den Part "abcde". Es entstehen also zwei neue Teiltreffer, die weiter untersucht werden müssen. In späteren Durchläufen werden natürlich immer die schon erreichten Teiltreffer dupliziert und um die jeweils gefundenen Parts erweitert.
Es gibt für jede erreichte Teiltrefferlänge (im Beispiel 3 und 5) zu jedem folgenden Zeitpunkt genau einen besten (Teil-)Treffer. Und bei jedem neuen Durchlauf i von 1 bis maximal m (m = Länge des Pattern) werden die besten Teiltreffer aus dem vorigen Durchlauf um jeweils einen weiteren Part verlängert. Dabei werden nur die Teiltreffer berücksichtigt, die genau i-1 Parts haben, denn alle anderen wurden ja schon in einem der vorhergehenden Durchläufe verlängert. Jeder Teiltreffer wird um alle gefundenen "besten" Parts verlängert. Wenn für einen Teiltreffer zum Beispiel drei beste Parts gefunden wurden, entstehen daraus drei neue Teiltreffer, die alle eine unterschiedliche Teiltrefferlänge haben. Diese ist jeweils um mindestens eins länger, als die des Teiltreffers, auf dem sie aufbaut.
Ein so entstandener verlängerter Teiltreffer ist nur dann besser als ein bereits vorher gefundener Teiltreffer gleicher Länge (ja, sowas kann es geben), wenn er weiter links endet. Endet er an der gleichen Stelle oder weiter rechts, wird er als irrelevant verworfen. Das Ganze wird solange vorgesetzt, bis man am Ende des aktuellen Durchlaufs einen Treffer der Länge m - also einen kompletten Treffer - erreicht hat oder bis am Ende des aktuellen Durchlaufs keiner der bisherigen Teiltreffer weiter verlängert werden konnte. Also eigentlich ganz einfach. :-)
Hier der Code ohne Berücksichtigung der Wortanfänge:
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
public class TextSearch
{
public static Match FindMatch (String input, String pattern)
{
input = (input ?? "").ToLower ();
pattern = (pattern ?? "").ToLower ();
pattern = System.Text.RegularExpressions.Regex.Replace (pattern, @"\s+", @"");
if (pattern == "") { return new Match (); }
Match [] matches = new Match [pattern.Length + 1];
matches [0] = new Match ();
MatchPart [] parts = new MatchPart [pattern.Length + 1];
int partCount = 0;
int maxMatchLength = 0;
int minMatchLength = 0;
do {
int newMinMatchLength = Int32.MaxValue;
for (int matchLength = maxMatchLength; matchLength ≥ minMatchLength; --matchLength) {
Match match = matches [matchLength];
if (match == null || match.Count < partCount) { continue; }
int maxPartLength;
int minPartLength;
FindParts (input, match.Right, pattern, matchLength, parts, out minPartLength, out maxPartLength);
for (int partLength = minPartLength; partLength ≤ maxPartLength; ++partLength) {
MatchPart part = parts [partLength];
if (part == null) { continue; }
parts [partLength] = null;
int newMatchLength = matchLength + partLength;
if (matches [newMatchLength] != null
&& matches [newMatchLength].Right < part.Index + partLength) {
continue;
}
matches [newMatchLength] = new Match (match);
matches [newMatchLength].Add (part);
if (newMatchLength > maxMatchLength) { maxMatchLength = newMatchLength; }
if (newMatchLength < newMinMatchLength) { newMinMatchLength = newMatchLength; }
}
}
if (newMinMatchLength == Int32.MaxValue) {
return new Match ();
}
++partCount;
minMatchLength = newMinMatchLength;
} while (matches [pattern.Length] == null);
return matches [pattern.Length];
}
private static void FindParts (String input, int inputIndex, String pattern, int patternStartIndex, MatchPart [] parts, out int minPartLength, out int maxPartLength)
{
char characterAtPatternStartIndex = pattern [patternStartIndex];
minPartLength = 1;
int previousPartLength = 0;
for (; inputIndex < input.Length; ++inputIndex) {
if (characterAtPatternStartIndex == input [inputIndex]) {
int partLength = 1;
while (patternStartIndex + partLength < pattern.Length
&& inputIndex + partLength < input.Length
&& pattern [patternStartIndex + partLength] == input [inputIndex + partLength]) {
++partLength;
}
if (partLength > previousPartLength) {
if (previousPartLength == 0) {
minPartLength = partLength;
}
previousPartLength = partLength;
parts [partLength] = new MatchPart (inputIndex, partLength);
}
}
}
maxPartLength = previousPartLength;
}
}
public class Match : Collection<MatchPart>
{
public Match () {}
public Match (Match match) : base (new List <MatchPart> (match)) {}
public int Right
{
get {
if (Count ≤ 0) { return 0; }
return this [Count - 1].Right;
}
}
}
public class MatchPart
{
public MatchPart (int index, int length) { Index = index; Length = length; }
public int Index { get; set; }
public int Length { get; set; }
public int Right { get { return Index + Length; } }
}
Aus der Struktur MatchPart ist eine Klasse geworden. Außerdem sind ein paar einfache Member (Konstruktoren und Properties) hinzugekommen. Den Comparer habe ich nicht implementiert, weil ich ihn gar nicht benötige. Zwar muss auch mein Code bestimmen, ob ein Teiltreffer besser ist als ein anderer, aber dafür gelten etwas schwächere und auch etwas andere Kriterien, als sie in einem Comparer, der beliebige Treffer nach ihrer Güte vergleichen kann, nötig sind. Das ist ebenfalls mit xxxprod besprochen.
Die Komplexität der Suche ist polynomiell. Nach spätestens m Durchläufen ist der beste Treffer gefunden oder festgestellt, dass es keinen Treffer gibt. Dabei müssen in jedem Durchlauf maximal m Teiltreffer untersucht werden. Für jeden Teiltreffer müssen neue Parts zum Verlängern des Teiltreffers gesucht werden. Diese Suche nach den Parts hat einen maximalen Aufwand von O(n*m) (n=Textlänge, m=Länge des Pattern). Wenn man das Suchen nach neuen Parts als den wesentlichen Aufwandsfaktor bei Behandlung eines Teiltreffers ansieht und alles andere der Einfachheit halber unter den Tisch fallen lässt und noch im Kopf hat, dass die Suche nach den Parts in maximal m Durchläufen für jeweils maximal m Teiltreffer erfolgten muss, dann kommt man auf einen Gesamtaufwand von O(n*m^3). Das klingt viel, ist aber auch nur der theoretische Maximalaufwand. In der Praxis sind meistens weniger als m Durchläufe nötig und vor allem werden pro Durchlauf im Schnitt viel weniger als m Teiltreffer bearbeitet. Auch wird der Suchaufwand für die Parts im Schnitt mehr von n, als von m abhängen, so dass im Ergebnis der Aufwand für praktische Fälle eher in Richtung n oder n*m tendieren wird.
Da im bisherigen Code noch keine Wortanfänge berücksichtigt werden, wird beim Testfall der Suche nach "hw" in "Hawaii hat schöne Wellen" der Treffer "[H]a[w]aii hat schöne Wellen" statt "[H]awaii hat schöne [W]ellen" gefunden. Diese Problem behebt die folgende Erweiterung.
Bei dieser steigt der Aufwand leider nochmal. Vor allem reicht es pro Durchlauf nicht mehr, pro Teiltrefferlänge einen Pattern zu untersuchen, sondern man muss im schlimmsten Fall für jede Kombination aus Teiltrefferlänge und Anzahl der Wortanfänge im Teiltreffer je einen Teiltreffer untersuchen. Das liegt daran, dass ein Teiltreffer, der zu Beginn weniger Wortanfänge hat, sich gegen Ende trotzdem noch als der bessere herausstellen kann, wenn er gegen Ende viele Parts enthält, die an Wortanfängen beginnen.
Im Beispiel der Suche von "abcdefghij" in "xab xcd ef gh ij ab cd xef xgh xij" hat "x[ab] x[cd] [ef] [gh] [ij] ab cd xef xgh xij" drei Wortanfänge gegenüber nur zwei bei ""xab xcd ef gh ij [ab] [cd] x[ef] x[gh] x[ij]". Beide Varianten müssen also bis zum Ende verfolgt werden, weil sich erst beim letzten Part herausstellt, welche der beiden Varianten hinsichtlich der Wortanfänge besser abschneidet.
Trotzdem bleibt auch bei der Erweiterung der Aufwand polynomiell, wenn auch mit höherem Exponenten beim m. Für praktische Fälle dürfte aber auch hier der Aufwand oft im Bereich von n*m liegen. Wenn man dann noch berücksichtigt, dass der Pattern üblicherweise nicht nur viel kürzer als der Text ist, sondern praktisch eine bestimmte Länge nicht überschreiten wird, wird man für viele praktische Fälle ein lineares Verhalten beobachten können.
Bevor wir zum Code kommen, war noch das Problem zu lösen, dass die Implementierung ohne Wortanfänge, immer maximal lange Parts vorzieht, was im Beispiel der Suche von "abcdef" in "abcd cdef" zum Übersehen eines Treffers mit zwei Wortanfängen führen würde, da "[abcd] cd[ef]" im Gegensatz zum optimalen Ergebnis "[ab]cd [cdef]" nur einen Wortanfang hat. Diese Problem habe ich dadurch gelöst, dass FindParts nun nicht nur nach Parts mit Wortanfang und ohne Wortanfang unterscheidet, sondern bei Parts ohne Wortanfang durch eine Rückwärtssuche die Trennstelle zum vorangegangen Part im Teiltreffer soweit zurückzuverschieben versucht, dass sie auf einen Wortanfang fällt. Im genannten Beispiel würde im zweiten Durchlauf zwar zunächst nur nach "ef" gesucht, aber dort wo dies gefunden wird, wird festgestellt, dass dort kein Wortanfang ist und dann die Rückwärtssuche eingeleitet. Diese stellt fest, dass einige der im Pattern vor "ef" stehenden Zeichen auch im Text zusammenhängend vor dem "ef" stehen und eins von diesen Zeichen, nämlich das c, auf einen Wortanfang fällt. Im Ergebnis wird als neuer Part "cdef" geliefert und beim Zusammenfügen des Parts mit dem Teiltreffer der vorhergehende Part im Teiltreffer entsprechend von "abcd" zu "ab" verkürzt.
Bleibt noch zu sagen, dass im folgenden Code in FindPart eine Reihe von Debug.Assert-Anweisungen enthalten sind. Das dient vor allem dazu, dass man eine Vorstellung hat, was der Wertebereich der einzelnen Parameter ist. Ich verwende Debug.Assert, da FindParts eine interne Methode ist und die Implementierung der aufrufenden Methode sicherstellt, dass immer korrekte Parameterwerte übergeben werden. Deshalb ist in der Release-Version eine Prüfung der Parameter zur Laufzeit nicht nötig.
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
public class TextSearch
{
private static bool [] wordBegin;
private static bool [] upperCase;
public static Match FindMatch (String input, String pattern)
{
Match finalMatch = null;
input = (input ?? "");
wordBegin = new bool [input.Length];
upperCase = new bool [input.Length];
bool inWord = false;
for (int i = 0; i < input.Length; ++i) {
if (char.IsLetterOrDigit (input [i])) {
upperCase [i] = char.IsUpper (input [i]);
if (!inWord) {
wordBegin [i] = inWord = true;
} else if (upperCase [i] && !upperCase [i-1]) {
wordBegin [i] = true;
}
} else {
inWord = false;
}
}
input = input.ToLower ();
pattern = (pattern ?? "").ToLower ();
pattern = System.Text.RegularExpressions.Regex.Replace (pattern, @"\s+", @"");
if (pattern == "") { return new Match (); }
Match [,] matches = new Match [pattern.Length + 1, pattern.Length + 1];
matches [0, 0] = new Match ();
MatchPart [,] parts = new MatchPart [pattern.Length + 1, 2];
int partCount = 0;
int maxMatchLength = 0;
int minMatchLength = 0;
int maxMatchWordBegins = 0;
int minMatchWordBegins = 0;
do {
int newMinMatchLength = Int32.MaxValue;
int newMinMatchWordBegins = Int32.MaxValue;
for (int matchLength = maxMatchLength; matchLength ≥ minMatchLength; --matchLength) {
for (int numMatchWordBegins = maxMatchWordBegins; numMatchWordBegins ≥ minMatchWordBegins; --numMatchWordBegins) {
Match match = matches [matchLength, numMatchWordBegins];
if (match == null || match.Count < partCount) { continue; }
int maxPartLength;
int minPartLength;
FindParts (input, match.Right, pattern, matchLength, match.LastPartLength, parts, out minPartLength, out maxPartLength);
for (int partLength = minPartLength; partLength ≤ maxPartLength; ++partLength) {
for (int numPartWordBegins = parts.GetLength (1) - 1; numPartWordBegins ≥ 0; --numPartWordBegins) {
if (parts [partLength, numPartWordBegins] == null) { continue; }
MatchPart part = parts [partLength, numPartWordBegins];
parts [partLength, numPartWordBegins] = null;
int numSumWordBegins = numMatchWordBegins + numPartWordBegins;
int newMatchRight = part.Right;
int newMatchLength = matchLength + partLength;
bool betterMatchFound = false;
for (int numComparingWordBegins = newMatchLength; numComparingWordBegins ≥ numSumWordBegins; --numComparingWordBegins) {
if (matches [newMatchLength, numComparingWordBegins] != null
&& matches [newMatchLength, numComparingWordBegins].Right < newMatchRight) {
betterMatchFound = true;
break;
}
}
if (betterMatchFound) { continue; }
for (int numComparingWordBegins = numSumWordBegins - 1; numComparingWordBegins ≥ 0; --numComparingWordBegins) {
if (matches [newMatchLength, numComparingWordBegins] != null
&& matches [newMatchLength, numComparingWordBegins].Right ≥ newMatchRight) {
matches [newMatchLength, numComparingWordBegins] = null;
}
}
Match newMatch = matches [newMatchLength, numSumWordBegins] = new Match (match);
if (part.Length > partLength) {
newMatch [newMatch.Count - 1].Length -= part.Length - partLength;
}
newMatch.Add (part);
if (newMatchLength > maxMatchLength) { maxMatchLength = newMatchLength; }
if (newMatchLength < newMinMatchLength) { newMinMatchLength = newMatchLength; }
if (numSumWordBegins > maxMatchWordBegins) { maxMatchWordBegins = numSumWordBegins; }
if (numSumWordBegins < newMinMatchWordBegins) { newMinMatchWordBegins = numSumWordBegins; }
}
}
}
}
if (newMinMatchLength == Int32.MaxValue) {
return new Match ();
}
++partCount;
minMatchLength = newMinMatchLength;
minMatchWordBegins = newMinMatchWordBegins;
for (int numMatchWordBegins = maxMatchWordBegins; numMatchWordBegins ≥ minMatchWordBegins; --numMatchWordBegins) {
if (matches [pattern.Length, numMatchWordBegins] != null) {
finalMatch = matches [pattern.Length, numMatchWordBegins];
break;
}
}
} while (finalMatch == null);
return finalMatch;
}
private static void FindParts (String input, int inputIndex, String pattern, int patternStartIndex, int previousPartLength, MatchPart [,] parts, out int minPartLength, out int maxPartLength)
{
Debug.Assert (input != null);
Debug.Assert (inputIndex ≥ 0);
Debug.Assert (inputIndex < input.Length);
Debug.Assert (pattern != null);
Debug.Assert (patternStartIndex ≥ 0);
Debug.Assert (patternStartIndex < pattern.Length);
Debug.Assert (inputIndex ≥ patternStartIndex);
Debug.Assert (previousPartLength ≥ 0);
Debug.Assert (previousPartLength ≤ patternStartIndex);
char characterAtPatternStartIndex = pattern [patternStartIndex];
minPartLength = Int32.MaxValue;
int previousNonWordBeginPartLength = 0;
int previousWordBeginPartLength = 0;
for (; inputIndex < input.Length; ++inputIndex) {
if (characterAtPatternStartIndex == input [inputIndex]) {
int partLength = 1;
while (patternStartIndex + partLength < pattern.Length
&& inputIndex + partLength < input.Length
&& pattern [patternStartIndex + partLength] == input [inputIndex + partLength]) {
++partLength;
}
int negativePartLength = 0;
bool wordBeginFound = wordBegin [inputIndex];
if (!wordBeginFound) {
while (negativePartLength < previousPartLength - 1
&& pattern [patternStartIndex - negativePartLength - 1] == input [inputIndex - negativePartLength - 1]) {
++negativePartLength;
if (wordBegin [inputIndex - negativePartLength]) {
wordBeginFound = true;
break;
}
}
}
if (wordBeginFound) {
if (partLength > previousWordBeginPartLength) {
if (previousWordBeginPartLength == 0 && partLength < minPartLength) {
minPartLength = partLength;
}
previousWordBeginPartLength = partLength;
parts [partLength, 1] = new MatchPart (inputIndex - negativePartLength, partLength + negativePartLength);
}
} else {
if (partLength > previousNonWordBeginPartLength && partLength > previousWordBeginPartLength) {
if (previousNonWordBeginPartLength == 0 && partLength < minPartLength) {
minPartLength = partLength;
}
previousNonWordBeginPartLength = partLength;
parts [partLength, 0] = new MatchPart (inputIndex, partLength);
}
}
}
}
maxPartLength = previousWordBeginPartLength > previousNonWordBeginPartLength ? previousWordBeginPartLength : previousNonWordBeginPartLength;
}
}
Die Match- und MatchPart-Klassen sind wie oben, nur in der Match-Klasse ist noch die folgende Property hinzukommt:
public int LastPartLength
{
get {
if (Count ≤ 0) { return 0; }
return this [Count - 1].Length;
}
}
herbivore
PS: Als Datenstrukturen für die Matches und Parts verwende ich momentan (zweidimensionale) Arrays. Diese Datenstrukturen sind möglicherweise nicht optimal, da sie für viele Suchanfragen nur sehr wenige Elemente enthalten werden (sparse array). Das führt nicht nur zu unnötigen Speicherverbrauch, sondern auch zu höheren Laufzeiten. Deshalb habe ich auch Berechnungen im Code, um immer nur die Bereiche der Arrays zu durchlaufen, in denen aktuelle Werte enthalten sind. Das hat tatsächlich eine erhebliche Beschleunigung bei aufwändigen Suchanfragen gebracht. Möglicherweise ließe sich noch mehr herausholen, wenn man spezielle sparse-Datenstrukturen verwenden würde.
bis auf die von mir im Nachhinein hinzugefügte Bedingung mit den großen Anfangsbuchstaben vor Kleinbuchstaben erfüllt deine Lösung alle Kriterien und ist so nebenbei meistens um mindestens den Faktor 2 schneller als meine. :)
Sehr gut gemacht - du bist nun also wieder dran die nächste Aufgabe zu stellen.
Lg, XXX
//Edit: Hier noch meine Lösung:
Zur Erklärung: In jedem Durchgang suche ich mit dem für jeden Match eigens übriggebliebenen RestPattern die Teiltreffer mit den längsten zusammenhängenden Zeichenfolgen raus und gehe mit denen in die nächste Runde um weiter zu suchen. Bevor ein Durchgang jedoch endet, werden die gefundenen Treffer mit der CompareTo Methode in "Match" nach ihrer Güte sortiert und es wird also immer mit den aktuell besten Treffern weitergesucht. Das wird solange durchgeführt, bis der aktuelle beste Treffer, kein RestPattern mehr übrig hat und somit die Suche beendet wurde.
Ich bin mir nicht sicher, ob meine Lösung garantiert immer die beste Variante findet aber zumindest tut sie es in meinen kleinen Testszenarios. Im Bezug auf den Aufwand, habe ich, wie vorhin erwähnt, keine so performante Lösung geschaffen wie Herbivore. In extremen Beispielen läuft mein Algorithmus ins Unendliche wodurch ich eine kleine Schummellösung eingebaut habe:
Wenn die zu durchsuchenden TeilMatches einen Wert überschreiten(hier matchesCount>50000) dann soll nach einem sehr einfachen Prinzip first-match->result gesucht werden. Diese einfache Methode "FindQuickMatch" sucht demnach klarerweise nicht nach allen Regeln aber das nehme ich hier in Kauf. Es wird ja trotzdem ein Match gefunden, nur eben nicht der idealste. :)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
public static class TextSearch
{
private class MatchPattern : IComparable<MatchPattern>
{
internal Match Match { get; private set; }
internal string PatternRest { get; private set; }
public MatchPattern(Match match, string patternRest)
{
Match = match;
PatternRest = patternRest;
}
public int CompareTo(MatchPattern other)
{
return Match.CompareTo(other.Match);
}
}
public static Match FindMatch(string input, string pattern)
{
if (input == null || pattern == null)
return new Match();
var wordStarts = new bool[input.Length];
var startCapitals = new bool[input.Length];
for (int i = 0; i < input.Length; i++)
{
if (i == 0 || (char.IsLetter(input[i]) && (!char.IsLetter(input[i - 1]) || char.IsUpper(input[i]) && char.IsLower(input[i - 1]))))
{
wordStarts[i] = true;
startCapitals[i] = char.IsUpper(input[i]);
}
}
return FindMatch(input.ToLower(), Regex.Replace(pattern, @"\s+", "").ToLower(), wordStarts, startCapitals);
}
private static Match FindMatch(string input, string pattern, bool[] wordStarts, bool[] startCapitals)
{
var matches = new List<MatchPattern> { new MatchPattern(new Match(), pattern) };
int matchesCount = 0;
do
{
MatchPattern match = matches[0];
matches.Remove(match);
IEnumerable<MatchPattern> newMatches = input.FindIndices(match.PatternRest[0], match.Match.RightIndex)
.Select(i => CreateMatch(match.Match, input, i, match.PatternRest, wordStarts, startCapitals));
matches.AddRange(newMatches);
if (matches.Count == 0)
return new Match();
if ((matchesCount += matches.Count) > 50000)
return FindQuickMatch(input, pattern);
var maxLength = matches.Select(m => m.Match.TotalLength)
.OrderByDescending(length => length)
.Take(2)
.OrderBy(length => length)
.FirstOrDefault();
matches.RemoveAll(mp => mp.Match.TotalLength < maxLength);
matches.Sort();
} while (matches[0].PatternRest.Length > 0);
return matches[0].Match;
}
private static Match FindQuickMatch(string input, string pattern)
{
var match = new Match();
for (int i = 0, offset = 0, lastOffset = -1; i < pattern.Length; i++, lastOffset = ++offset)
{
if ((offset = input.IndexOf(pattern[i], offset)) < 0)
return new Match();
if (lastOffset == offset)
{
var oldPart = match[match.Count - 1];
match.Remove(oldPart);
match.Add(new MatchPart(oldPart.Index, oldPart.Length + 1));
}
else match.Add(new MatchPart(offset, 1));
}
return match;
}
private static MatchPattern CreateMatch(IEnumerable<MatchPart> parts, string input, int i, string pattern, bool[] wordStarts, bool[] startCapitals)
{
int length = GetLength(input.Substring(i), pattern);
var match = new Match(parts)
{
new MatchPart(i, length, wordStarts[i], startCapitals[i])
};
return new MatchPattern(match, pattern.Substring(length));
}
private static int GetLength(string input, string pattern)
{
int length = 0;
for (int p = 0; p < input.Length && p < pattern.Length && input[p] == pattern[p]; p++)
length++;
return length;
}
private static IEnumerable<int> FindIndices(this string text, char c, int indexFrom = 0)
{
while ((indexFrom = text.IndexOf(c, indexFrom)) ≥ 0)
yield return indexFrom++;
}
}
Match wurde bei mir auch viel mehr erweitert, weil sich hier die ganze Bewertung eines Matches abspielt. Hier kann man im Gegensatz zu Herbivores Lösung sehr flexibel an den Bedingungen schrauben ohne den eigentlichen Algorithmus anpassen zu müssen.(Was ich ja durch Pperformanceeinbußen in Kauf nehme)
using System;
using System.Collections.ObjectModel;
using System.Linq;
using System.Collections.Generic;
public class Match : ObservableCollection<MatchPart>, IComparable<Match>, IComparable
{
public Match() { }
public Match(IEnumerable<MatchPart> match) : base(match.Select(part => new MatchPart(part))) { }
public int RightIndex { get { return Count == 0 ? 0 : this[Count - 1].Right; } }
public int TotalLength { get; private set; }
private double _averageLength;
private int _boundaries;
private int _capitalLetters;
private int _distance;
private double _index;
private bool _partsChanged;
protected override void OnCollectionChanged(System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
{
_partsChanged = true;
TotalLength = (Count == 0) ? 0 : this.Sum(p => p.Length);
base.OnCollectionChanged(e);
}
public int CompareTo(object obj)
{
return CompareTo(obj as Match);
}
public int CompareTo(Match other)
{
return Compare(this, other);
}
private static int Compare(Match x, Match y)
{
if (x.Count == 0 && y.Count > 0)
return -1;
if (x.Count > 0 && y.Count == 0)
return 1;
if (x._partsChanged)
x.CalculateComparisonValues();
if (y._partsChanged)
y.CalculateComparisonValues();
int averageLenght = x._averageLength.CompareTo(y._averageLength);
if (averageLenght != 0)
return -averageLenght;
int boundaries = x._boundaries.CompareTo(y._boundaries);
if (boundaries != 0)
return -boundaries;
int capitalLetters = x._capitalLetters.CompareTo(y._capitalLetters);
if (capitalLetters != 0)
return -capitalLetters;
int distance = x._distance.CompareTo(y._distance);
if (distance != 0)
return distance;
int index = x._index.CompareTo(y._index);
if (index != 0)
return index;
return 0;
}
private void CalculateComparisonValues()
{
_partsChanged = false;
_index = 0;
_averageLength = 0;
_boundaries = 0;
_capitalLetters = 0;
_distance = 0;
if (Count > 0)
{
foreach (MatchPart part in Items)
{
_index += part.Index;
if (part.IsWordStart)
_boundaries++;
if (part.IsStartLetterCapital)
_capitalLetters++;
}
_index /= Count;
_averageLength += TotalLength / (double)Count;
_distance = this[Count - 1].Index - this[0].Index;
}
}
}
public struct MatchPart
{
public MatchPart(MatchPart other)
: this(other.Index, other.Length, other.IsWordStart, other.IsStartLetterCapital) { }
public MatchPart(int index, int length) : this(index, length, false, false) { }
public MatchPart(int index, int length, bool isWordStart, bool isStartLetterCapital)
: this()
{
Index = index;
Length = length;
IsWordStart = isWordStart;
IsStartLetterCapital = isStartLetterCapital;
}
public int Index { get; private set; }
public int Length { get; private set; }
public int Right { get { return Index + Length; } }
public bool IsWordStart { get; private set; }
public bool IsStartLetterCapital { get; private set; }
}
//Edit²: Die 50 Zeilen Grenze für Aufgaben hier hatte ich erst nachdem ich diese gestellt hatte gelesen^^
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von xxxprod am .
hier kommt die neue Aufgabe. Nicht so schwer wie die letzte, aber auch nicht vollkommen trivial:
Schreibt eine (Erweiterungs-)Methode SubtractEx, die zwei DateTimes bekommt und ein Dictionary <DayOfWeek, IList<TimeSpan>> und die einen TimeSpan liefert. Die Methode soll die Differenz der beiden Zeitpunkte liefern, aber nur innerhalb der angegebenen Zeiten pro Tag.
Das Dictionary darf nicht null sein. Es kann für beliebige und beliebig viele Wochentage einen Eintrag haben, mindestens jedoch für einen. Die zugeordneten ILists dürfen nicht null sein und müssen eine Länge größer als 0 haben, die ein Vielfaches von 2 beträgt. Alle enthaltenen TimeSpans müssen zwischen 0 und 24 Stunden liegen. Jeder TimeSpan in einer Liste muss echt größer sein als sein Vorgänger. Jedes Paar definiert einen Zeitraum. Alle diese Bedingungen könnt ihr prüfen oder als gegeben ansehen, wie ihr wollt.
Beispiel für eine Berechnung: Sei für jeden Tag von Montag bis Freitag dieselbe Liste eingetragen, die die beiden TimeSpans 8 Stunden und 16 Stunden enthält. Dann würde die Methode für den 1.10.2012 9:00 bis 3.10.2012 14:00 einen TimeSpan von 7 + 8 + 6 = 21 Stunden liefern.
Die Methode soll auch dann effizient sein, wenn sie für jahrhundertelange Zeiträume aufgerufen wird. Geht also für Zeiträume von mehr als ein oder zwei Wochen nicht einfach in einer Schleife alle Tage durch, um deren Stunden einzeln zu addieren.
Zeitzonen, Sommerzeitumstellungen u.ä. braucht ihr nicht zu berücksichtigen.
Beachtet aber wie die "echte" [URL]DateTime.Subtract-Methode[/URL], ob das eine Datum vor dem anderen liegt oder ob es andersherum ist.
Ein zu lösendes Teilproblem wird vermutlich sein, zu erkennen, wann sich zwei Zeiträume überlappen. Mit ein bisschen nachdenken schafft man das mit nur zwei Vergleichen.
Ich bin gespannt auf eure Lösungen. Viel Spaß mit der Aufgabe!
Darüber, dass du davon ausgehst, dass in dem Dictionary für jeden Wochentag ein Eintrag vorhanden ist, worauf man sich nach der Aufgabenstellung nicht verlassen kann, würde ich glatt hinwegsehen, zumal sich das minimalinvasiv durch eine Umstellung auf Dictionary.TryGetValue beheben lässt.
Da du jedoch entgegen des expliziten Hinweises einfach eine Schleife über alle Tage gemacht hast, kann ich diese Lösung nicht als richtig anerkennen. Ich bin mir aber sicher, dass du eine extra Behandlung für längere Zeiträume auch noch eingebaut bekommst.
Ich persönlich finde die Tatsache, dass du die Variable time mehrfach innerhalb eines Tages anpasst, etwas verwirrend. Ich fände es schöner, wenn innerhalb eines Tages immer nur result verändert werden würde. Aber Schönheit war nicht gefragt. Daher ist es dir überlassen, ob du das so beibehalten oder umstellen willst.
