Laden...

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.544 Views
2.891 Beiträge seit 2004
vor 11 Jahren

OrderBy

Naja, ein OrderBy speichert allerdings erst die gesamte Auflistung zwischen und gibt sie dann an First weiter. Verstößt gegen die zweite Regel.

D
216 Beiträge seit 2009
vor 11 Jahren

Ich glaube meine Methode sollte funktionieren.

public static T PickRandom<T>(IEnumerable<T> source)
{
  Random r = new Random();

  int count = 0;
  T selected = default(T);

  foreach (T t in source)
  {
    count++;
    if (r.Next(count) == 0)
      selected = t;
  }

  if (count == 0)
    throw new Exception("source was empty");

  return selected;
}

Ich laufe jedes Element der Auflistung durch und zähle dabei count hoch. Mit einer Wahrscheinlichkeit von 1/count überschreibe ich das Element in selected, dass heißt das erste Element überschreibt mit einer Wahrscheinlichkeit von 1/1 -> es wird auf jedenfall gewählt. Das 2. Element wird mit einer Wahrscheinlichkeit von 1/2 gewählt.
Das 3. Element überschreibt mit einer Wahrscheinlichkeit von 1/3 das Element, das davor gewählt wurde. Mit einer Wahrscheinlichkeit von 1/3 ist also das dritte Element das gewählte. Die restlichen 2/3 teilen sich die ersten beiden Elemente, die dadurch beide auch jeweils 1/3 Wahrscheinlichkeit haben.
Das n. Element wird mit einer Wahrscheinlichkeit von 1/n gewählt. Dadurch hat insgesamt jedes Element die Wahrscheinlichkeit 1/n, da das Element davor mit einer Wahrscheinlichkeit von 1/n überschrieben wird und die Elemente davor alle eine Wahrscheinlichkeit von 1/(n-1) hatten.

Nach dem Schleifendurchlauf prüfe ich dann noch ob count 0 war, damit ich dann wie in der Aufgabe gefordert eine Exception werfen kann.

Und falls ich nichts übersehen habe und meine Antwort richtig ist, darf wer anders die nächste Frage stellen.

Darth Maim

2.891 Beiträge seit 2004
vor 11 Jahren

Und falls ich nichts übersehen habe und meine Antwort richtig ist, darf wer anders die nächste Frage stellen.

Das ist die Antwort, die ich gesucht habe. 😃
Der Nächste ist dran!

111 Beiträge seit 2011
vor 11 Jahren

OK wenn der nächste darf geb ich mal was neues vor.

Ich möchte ein Quine also ein Programm, das sich selber ausgibt (also den Quelltext)

Ich gebe mal folgende Klasse vor:

class Program
  {
    static void Main(string[] args)
    {
       Console.WriteLine("...");
    }
  }

Wie ihr seht will ich keine gigantische Anwendung belasst es bei einer kleinen Ausgabe da ihr euch sonst nur noch mehr Arbeit aufhalst.
Bearbeitet die Main so dass alles von class bis } ausgegeben wird.

Und das alles ohne Reflection und in max. 5 Zeilen (soviele braucht man gar nicht denke ich.
Have fun

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

Q
49 Beiträge seit 2010
vor 11 Jahren

In der Vorlage fehlen Namespaces...

class Program
{
    static void Main(string[] args)
    {
       string o = "class Program{{static void Main(string[] args){{string o={1}{0}{1};System.Console.WriteLine(o, o, (char)34);}}}}";
       System.Console.WriteLine(o, o, (char)34);
    }
}

btw so ists angenehmer

class Program
{
    static void Main(string[] args)
    {
        string o = "class Program{{static void Main(string[] args){{string o={1}{0}{1};System.Console.WriteLine(o, o, (char)34);System.Console.ReadLine();}}}}";
       System.Console.WriteLine(o, o, (char)34);
       System.Console.ReadLine();
    }
}

111 Beiträge seit 2011
vor 11 Jahren

Erstaunlich nahe an meinem Code 👍
Jop naja namespace hin oder her die Vorlage sollte nur hinweisen dass ich nicht gleich ein 100 Zeilenprogramm sehen will weil das beim schreiben und lesen sonst zu depressionen geführt hätte
Richtig gemacht du bist dran

Edit:
Achso hab ich zwar nicht gesagt aber schön wäre ein Environment.NewLine für Zilenumbrüche gewesen schließlich will man den Code ja am ende auch wieder lesen können 😉

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

Q
49 Beiträge seit 2010
vor 11 Jahren

Meinst du so:


class Program
{
    static void Main(string[] args)
    {
        string o = "class Program{2}{{{2}static void Main(string[] args){2}{{{2}string o={1}{0}{1};{2}System.Console.WriteLine(o, o, (char)34, System.Environment.NewLine);{2}System.Console.ReadLine();{2}}}{2}}}";
        System.Console.WriteLine(o, o, (char)34, System.Environment.NewLine);
        System.Console.ReadLine();
    }
}

und kann bitte jemand anderes die neue aufgabe posten??

Q
49 Beiträge seit 2010
vor 11 Jahren
Hinweis von herbivore vor 11 Jahren

Diese Lösung bezieht sich auf die Aufgabe von Stalky13 weiter oben.

@Stalky13

Noch so ein Fraktalbegeisteter, der hier rumläuft 😄

Hier die Lösung: (siehe unten)

Guck dir dazu auch mein Programm **XFract **an:

XFract - Fraktalgenerator für Julia- und Mandelbrotmengen - NEUE VERSION

Und meine **Facharbeit **zum Thema Fraktale:

http://fraktale.quadsoft.org

/// <summary>
        /// Zeichnet ein Mandelbrot Apfelmännchen.
        /// </summary>
        /// <param name="gfx">Grafikausgabe.</param>
        /// <param name="frontColor">Farbton, der für das Zeichnen verwendet werden soll.</param>
        /// <param name="backColor">Hintergrundfarbe.</param>
        /// <param name="sectionLeft">Gibt den linken Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
        /// <param name="sectionTop">Gibt den oberen Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
        /// <param name="sectionRight">Gibt den rechten Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
        /// <param name="sectionBottom">Gibt den unteren Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
        /// <param name="deep">Gibt die maximale Anzahl Iterationen an.</param>
        public static void DrawMandelbrot(Graphics gfx, Color frontColor, Color backColor, double sectionLeft, double sectionTop, double sectionRight, double sectionBottom, int deep)
        {
            SolidBrush front = new SolidBrush(frontColor);
            SolidBrush back = new SolidBrush(backColor);

            System.Numerics.Complex  z, c;

            for (int x = 0; x < (int)gfx.VisibleClipBounds.Width; x++)
            {
                for (int y = 0; y < (int)gfx.VisibleClipBounds.Height; y++)
                {
                    z = new System.Numerics.Complex(0,0);
                    c = new System.Numerics.Complex(sectionLeft + (sectionRight - sectionLeft) * (x / gfx.VisibleClipBounds.Width),
                        sectionTop + (sectionBottom - sectionTop) * (y / gfx.VisibleClipBounds.Height));

                    int i = 0;

                    while (true)
                    {
                        i++;
                        z = z * z + c;

                        if (z.Magnitude > 2.0)
                        {
                            gfx.FillRectangle(back, x, y, 1, 1);
                            break;
                        }
                        else if (i == deep)
                        {
                            gfx.FillRectangle(front, x, y, 1, 1);
                            break;
                        }
                    }
                }
            }
        }
4 Beiträge seit 2012
vor 11 Jahren

Hi,

die Lösung von Quadsoft entspricht genau der Aufgabe und ist somit völlig korrekt.
Mit Einfarbig hatte ich eigendlich einen Farbverlauf von der Fordergrund zur Hintergrund Farbe gemeint, beim erneuten durch lesen der Aufgabe, ist mir allerdings erst jetzt aufgefallen, das ich diesen Punkte hätte besser definieren sollen.

Wie auch immer, ich freue mich, dass nun doch eine Lösung gekommen ist 😁

@Quadsoft

Ich werd mir dein Programm und deine Facharbeit auf jeden Fall ansehen, aber erst morgen ich muss nämlich gleich los.
Ach ja und da deine Antwort richtig ist, darfst du vor 2 Monaten eine neue Aufgabe stellen 😉

Aus großer Macht folgt große Verantwortung!

J
6 Beiträge seit 2012
vor 11 Jahren

Wenn eine Woche seit dem jeweils letzten Beitrag vergangen ist, ist der Thread wieder frei für eine neue Aufgabe (egal wer die neue Aufgabe stellen möchte und egal ob dieser letzte Beitrag nun eine Aufgabe, eine Nachfrage oder eine Lösung ist und egal ob die Lösung richtig oder falsch war, also einfach: eine Woche Inaktivität = neue Aufgabe erlaubt).

Damit möchte ich auch gleich den Thread mal wieder aus der Versenkung holen.

Es ist eine kleine Aufgabe, ihr könnt sie als Code oder auch mit Code und Papier lösen.
Wie ihr das macht ist ja im Endeffekt euch überlassen.

Hinter folgender Zahl ist ein Wort versteckt, welches ich gerne von euch wissen möchte:
110098088072122105107

2 kleine Tipps:

  • Das Wort besteht aus 7 Buchstaben.
  • Sobald ihr aus den Zahlen Buchstaben gemacht habt müsst ihr verkehrt herum denken.

Viel Spaß beim Lösen!

A
764 Beiträge seit 2007
vor 11 Jahren

@ Patrick R.

myCSarp

J
6 Beiträge seit 2012
vor 11 Jahren

Da ist mir doch glatt selbst ein Fehler beim Umschreiben unterlaufen. Peinlich, Peinlich...
Aber ja, in diesem Fall stimmt das dann.

War wie gesagt nur etwas sehr kleines, damit der Thread mal wieder aus der Versenkung erscheint.

@Alf Ator It's your turn.

A
764 Beiträge seit 2007
vor 11 Jahren

Da ist mir doch glatt selbst ein Fehler beim Umschreiben unterlaufen.

Ich dachte schon, dass war Absicht, um uns zu testen.

Also ich überlege mir eine Aufgabe. Aber** jeder der will und eine Aufgabe hat, kann eine Posten**. Dann mach ich meine Aufgabe später.

2.891 Beiträge seit 2004
vor 11 Jahren

Könntet ihr bitte noch einen kurzen Satz hinterlassen, wie man denn nun von den Zahlen auf das Wort kommt?

A
764 Beiträge seit 2007
vor 11 Jahren

Oh, natürlich, sorry.

🤔

Also 7 Buchstaben-Wort und 21 Zahlen -> 3 Ziffern pro Buchstabe. Das ganze in der Asciitabelle nachschlagen und dann die herausgefundenen Buchstaben, von hinten abzählen. Also X wird zu C.
Die Tipps habens sehr einfach gemacht.

T
708 Beiträge seit 2008
vor 11 Jahren

Hallo "Spieler" 😁

da sich noch keiner erbarmt hat und** Alf Ator** es freigestellt hat sich dazwischen zu drängeln, hier eine Aufgabe aus dem Alltag.

Letzte Woche stand ich vor folgendem Problem:

Eine Erinnerungsfunktion sollte um eine Sprachausgabe erweitert werden und mir ein paar Informationen nennen.
Darunter die aktuelle Uhrzeit und die Dauer zum nächsten Termin.

Wie spreche ich nun also nach allen Regeln der deutschen Sprache korrekt ganze Zahlen aus?

Ganz klar, folgende Wörter sind obligatorisch:

string [] bis20 = new string[]{"Null", "ein", "zwei", "drei", "vier", "fünf",
              "sechs", "sieben", "acht", "neun", "zehn", "elf",
              "zwölf", "dreizehn", "vierzehn", "fünfzehn",
              "sechzehn", "siebzehn", "achtzehn", "neunzehn"};

string[] zehner = new string[]{"Null", "zehn", "zwanzig", "dreissig", "vierzig",
                "fünfzig", "sechzig", "siebzig", "achtzig", "neunzig"};

Um es noch etwas schwieriger zu machen, brauchen wir auch noch Hunderter, Tausender, bis zur einer Milliarde (Zahlennamen).
(Es hat einen speziellen Grund, weshalb ich diese nicht als string[] oben mit eingefügt habe)

Nun kann man schon fleißig los programmieren und schnell wird klar, dass noch ein und her muss. Die Ausgaben scheinen auch schon zu funktionieren:

Fünfhundertsechsundzwanzig
Zweihundertsieben ("und" bei einer Null an der Zehnerstelle nicht unbedingt notwendig)
Hundertein => Fehler!

Also noch eine Unterscheidung mehr und wir sind am Ende angekommen.

Oder? 🤔

[EDIT] Auf Anraten von herbivore möchte ich die Aufgabe auf folgenden Zahlenbereich deckeln:
0 bis 1 000 000 000 (eine Millarde).
Den Bereich noch weiter zu erhöhen ist schließlich nur Fleißarbeit.

T
708 Beiträge seit 2008
vor 11 Jahren

Da sich bisher noch niemand gemeldet hat, gebe ich noch schnell zwei entscheidende Tipps:
(Wer sich dessen schon angenommen hat, sollte hier ggf. nicht weiterlesen 😁 )
*Die Hunderter, Tausender, usw. habe ich absichtlich weggelassen, da diese optimaler Weise auf zwei Arrays aufgeteilt werden müssen. Und zwar in singular & plural. *Die Eingabe wird in Dreiergruppen aufgespaltet und verarbeitet!

Ansonsten: Kritik oder Anregungen?
Zu einfach, zu langweilig, gibt es schon 100fach im Internet?

69 Beiträge seit 2009
vor 11 Jahren

Hallo trib,

Hier mal meine Lösung, basierend auf deinen Tipps:

public class NumberToTextConverter
{
  private string[] _lessThan20 = new string[]{ "null", "eins", "zwei", "drei", "vier", "fünf", "sechs", "sieben", "acht", "neun", "zehn", "elf", "zwölf", "dreizehn", "vierzehn", "fünfzehn", "sechzehn", "siebzehn", "achtzehn", "neunzehn" };
  private string[] _magnitude1 = new string[] { "", "ein", "zwei", "drei", "vier", "fünf", "sechs", "sieben", "acht", "neun" };
  private string[] _magnitude10 = new string[] { "", "zehn", "zwanzig", "dreissig", "vierzig", "fünfzig", "sechzig", "siebzig", "achtzig", "neunzig" };
  private string[] _magnitudesSingular = new string[] { "hundert", "tausend", " million ", " milliarde " };
  private string[] _magnitudesPlural = new string[] { "hundert", "tausend", " millionen ", " milliarden " };

  public string NumberToText(int number)
  {
    StringBuilder resultBuilder = new StringBuilder();
    string result = string.Empty;
    string numberText = number.ToString();
    int orderOfMagnitude = 0;

    if (number < 20)
      result = _lessThan20[number];
    else
    {
      while (numberText.Length > 2)
      {
        result = this.NumberPartToText(numberText.Substring(numberText.Length - 3, 3), orderOfMagnitude++) + result;
        numberText = numberText.Remove(numberText.Length - 3);
      }
      result = this.NumberPartToText(numberText.PadLeft(3, '0'), orderOfMagnitude++) + result;
    }

    foreach (string word in result.Split(' '))
      if (word.Length > 0)
        resultBuilder.Append(word.Substring(0, 1).ToUpper() + word.Substring(1) + " ");

    return resultBuilder.ToString(); 
  }

  private string NumberPartToText(string numberPart, int orderOfMagnitude)
  {
    string result = string.Empty;

    if (numberPart == "000")
      return string.Empty;

    if (numberPart == "001" && orderOfMagnitude > 0)
      return (orderOfMagnitude == 1 ? "ein" : "eine") + _magnitudesSingular[orderOfMagnitude];

    if (numberPart[0] != '0')
      result = _magnitude1[int.Parse(numberPart[0].ToString())] + _magnitudesSingular[0];

    result += this.TwoDigitsToText(numberPart.Substring(1, 2));
    if (orderOfMagnitude > 0)
      result += int.Parse(numberPart) > 1 ? _magnitudesPlural[orderOfMagnitude] : _magnitudesSingular[orderOfMagnitude];

    return result;
  }

  private string TwoDigitsToText(string twoDigits)
  {
    string result = string.Empty;
    int value = int.Parse(twoDigits);

    if (twoDigits == "00")
      return string.Empty;

    if (value < 20)
      return _lessThan20[value];

    if (twoDigits[1] != '0')
      result += _magnitude1[int.Parse(twoDigits[1].ToString())] + "und";
    result += _magnitude10[int.Parse(twoDigits[0].ToString())];

    return result;
  }
}

Viel kürzer krieg ich's aufgrund der ganzen Spezialfälle nicht hin ... schon erstaunlich, wie "unregelmässig" das ist, wenn man genau hinschaut 🙂 Zum Testen hab ich folgenden Code genommen:

static void Main(string[] args)
{
  NumberToTextConverter num = new NumberToTextConverter();
  int[] test = new int[] {
    0, 1, 19, 30, 99, 
    100, 201, 311, 420, 543,
    1000, 2001, 3012, 4300, 5430, 5432, 
    10000, 20001, 30012, 55555, 99200,
    100000, 200001, 333333, 550055, 444000, 333301,
    1000000, 2000001, 1234567, 5000000, 7050011, 
    10000000, 30000001, 12345678, 87654321, 1000000000, int.MaxValue };

  for (int i = 0; i < test.Length; i++)
    Console.WriteLine("{0}: {1}", test[i].ToString().PadRight(10), num.NumberToText(test[i]));

  Console.ReadLine();
}

Und die Ausgabe sieht in dem Fall so aus (ob die Spaces da jetzt überall Sinn machen, weiss ich nicht, aber das wäre ja schnell geändert - und vorgegeben war es auch nicht):

0         : Null
1         : Eins
19        : Neunzehn
30        : Dreissig
99        : Neunundneunzig
100       : Einhundert
201       : Zweihunderteins
311       : Dreihundertelf
420       : Vierhundertzwanzig
543       : Fünfhundertdreiundvierzig
1000      : Eintausend
2001      : Zweitausendeins
3012      : Dreitausendzwölf
4300      : Viertausenddreihundert
5430      : Fünftausendvierhundertdreissig
5432      : Fünftausendvierhundertzweiunddreissig
10000     : Zehntausend
20001     : Zwanzigtausendeins
30012     : Dreissigtausendzwölf
55555     : Fünfundfünfzigtausendfünfhundertfünfundfünfzig
99200     : Neunundneunzigtausendzweihundert
100000    : Einhunderttausend
200001    : Zweihunderttausendeins
333333    : Dreihundertdreiunddreissigtausenddreihundertdreiunddreissig
550055    : Fünfhundertfünfzigtausendfünfundfünfzig
444000    : Vierhundertvierundvierzigtausend
333301    : Dreihundertdreiunddreissigtausenddreihunderteins
1000000   : Eine Million
2000001   : Zwei Millionen Eins
1234567   : Eine Million Zweihundertvierunddreissigtausendfünfhundertsiebenundsechzig
5000000   : Fünf Millionen
7050011   : Sieben Millionen Fünfzigtausendelf
10000000  : Zehn Millionen
30000001  : Dreissig Millionen Eins
12345678  : Zwölf Millionen Dreihundertfünfundvierzigtausendsechshundertachtundsiebzig
87654321  : Siebenundachtzig Millionen Sechshundertvierundfünfzigtausenddreihunderteinundzwanzig
1000000000: Eine Milliarde
2147483647: Zwei Milliarden Einhundertsiebenundvierzig Millionen Vierhundertdreiundachtzigtausendsechshundertsiebenundvierzig
T
708 Beiträge seit 2008
vor 11 Jahren

Hallo jannemann13 ,

vorab: Getestet und für gut befunden 😃
Du bist dran!

Zum Code:
Der sieht für mich vollkommen in Ordnung aus. Mir ist nur aufgefallen, dass ich mit einem Array weniger ausgekommen bin. "_magnitude1" ist ja quasi bis auf ein/eins in "_lessThan20" enthalten.

Meine Lösung:
Die Arrays:

        static string [] upTo20 = new string[]{"Null", "ein", "zwei", "drei", "vier", "fünf",
              "sechs", "sieben", "acht", "neun", "zehn", "elf",
              "zwölf", "dreizehn", "vierzehn", "fünfzehn",
              "sechzehn", "siebzehn", "achtzehn", "neunzehn"};

        static string[] ten = new string[]{"Null", "zehn", "zwanzig", "dreissig", "vierzig",
                "fünfzig", "sechzig", "siebzig", "achtzig", "neunzig"};

        static string[] singular = new string[]{"s", "tausend", "e Million", "e Milliarde",
                    "e Billion", "e Billiarde", "e Trillion", "e Trilliarde",
                    "e Quadrillion", "e Quadrilliarde"};

        static string[] plural = new string[]{" ", "tausend", " Millionen", " Milliarden",
                    " Billionen", " Billiarden", " Trillionen", " Trilliarden",
                    " Quadrillionen", " Quadrilliarden"};

Dreier-Pakete schnüren:

        private static string Speak(long number)
        {
            string result = string.Empty;
            double maxNo = Math.Pow(10, (3 * singular.Length)); //10*3*10
            if(number >= maxNo)
		        return "Nummer ist zu groß!!!";

            if (number == 0)
                return "null";

           //number in Dreiergruppen aufspalten:
	        int[] group = new int[(number.ToString().Length / 3)+1];
	        int i = 0;
	        while( number > 0)
            {			        
		        group[i++] = Convert.ToInt32(number % 1000);
                number = number / 1000;
	        }

            //Dreiergruppen von links nach rechts aussprechen:	        
            i = group.Length -1;
	        while(i >= 0)
            {
                result += SpeakTrifurcator(group[i], i) + "\n";
                i--;
	        }
            return result;
        }

Dreier-Zahlen aussprechen:


        private static string SpeakTrifurcator(int number, int position)
        {
            string result = string.Empty;
            
            if(number == 0)                
                return string.Empty;
            if (number == 1)
                return upTo20[number] + singular[position];
            
            int hundred = number / 100;
            int rest = number % 100;
            int tenth = rest / 10;
            int first = number % 10;

            //Make it speak
            if (hundred > 0)
                result += upTo20[hundred] + "hundert";
	
            //Do the rest
            if (rest > 0)
            {                
                // Sonderfall: number endet auf 01,
                // ist aber ungleich 1
                if (rest == 1)
                    result += "eins";
                else
                    if (rest < 20)
                        result += upTo20[rest];
                    else
                    {
                        if (first > 0)
                            result += upTo20[first];
                        // sage "und", wenn es Einer-
                        // und Zehneranteile vorhanden
                        if (tenth > 0 & first > 0)
                            result += "und";
                        // Zehneranteil aussprechen:
                        if (tenth > 0)
                            result += ten[tenth];
                    }
            }
            return result + plural[position];
        }
69 Beiträge seit 2009
vor 11 Jahren

Der sieht für mich vollkommen in Ordnung aus. Mir ist nur aufgefallen, dass ich mit einem Array weniger ausgekommen bin. "_magnitude1" ist ja quasi bis auf ein/eins in "_lessThan20" enthalten.

Ja stimmt, das hätte man noch etwas kürzen können ... wären aber wieder mehr Spezialfälle geworden 🙂

Du bist dran!

OK, der Thread deckt ja jetzt schon eine Menge ab und mir fällt grade keine wirklich neue Aufgabe ein, also machen wir doch das Naheliegende 🙂

Und nochmal rückwärts

Erstelle einen Parser, der aus einer komplett ausgeschriebenen Zahl den passenden Zahlenwert ermittelt. Das Ergebnis sollte eine Methode mit folgender Signatur sein:

int TextToNumber(string numberText);

Beispiele:

Eingabe "Eins" --> Ausgabe: 1
Eingabe "Zweiundvierzig" --> Ausgabe: 42
Eingabe "Acht Millionen Zweihundertachtunddreissigtausendvierhundertsechsundneunzig" --> Ausgabe: 8238496

Der Rahmen für die gültigen "Zahlentexte" soll auch hier wieder 0 bis 1 Milliarde umfassen, also genau wie in der letzten Aufgabe, nur eben umgekehrt. Zum Erzeugen von Testeingaben kann dann praktischerweise meine Klasse oder tribs Code verwendet werden ... Viel Spass 8)

Hinweis von gfoidl vor 11 Jahren

Das ist die 100. Aufgabe 🙂

111 Beiträge seit 2011
vor 11 Jahren

Hallo
Nach einem Monat ohne Aktion hier mal was neues:

Was ist auf diesem Bild zu sehen und wie kann man das in unter 10 Zeilen Code selbst zeichnen?

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

A
764 Beiträge seit 2007
vor 11 Jahren

int width = 1024, height = 16;
Bitmap bitmap = new Bitmap(width, height * 2);
Graphics graphics = Graphics.FromImage(bitmap);
graphics.FillRectangle(Brushes.Green, 0, 0, width, height * 2);
for (int widthCounter = 0; widthCounter < width; widthCounter++)
{
    BitArray bitArray = new BitArray(new int[] { widthCounter });
    for (int heightCounter = 0; heightCounter < bitArray.Length; heightCounter++)
        if (bitArray[heightCounter])
            graphics.FillRectangle(Brushes.Orange, widthCounter, (height - heightCounter) * 2, 1, 1 * 2);
}
bitmap.Save(@"c:\test.png", System.Drawing.Imaging.ImageFormat.Png);

111 Beiträge seit 2011
vor 11 Jahren

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!

A
764 Beiträge seit 2007
vor 11 Jahren

das war ne tolle aufgabe 😃

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.

111 Beiträge seit 2011
vor 11 Jahren

Richtig (aber es sind die zahlen 0-512 sonst wäre das bild zu lang geworden) das ging ziemlich schnell 👍
Alf Ator ist am Zug

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

A
764 Beiträge seit 2007
vor 11 Jahren

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.


static void Main(string[] args)
{
    BerecheneKleinsteZugfolge("A1", "F8").ForEach(item => Console.WriteLine(item));
    Console.ReadLine();
}

private static List<string> BerecheneKleinsteZugfolge(string start, string ziel)
{
    // ...
}

@thedruedon: genau, es sind 1024 zahlen 😄

309 Beiträge seit 2008
vor 11 Jahren

Kurze Frage:

Für beliebig große Schachbretter oder genügt das klassische 8x8 Brett?

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

A
764 Beiträge seit 2007
vor 11 Jahren

Hallo Scavanger, das klassische 8x8 reicht aus.

1.378 Beiträge seit 2006
vor 11 Jahren

        static void Main(string[] args)
        {
            BerecheneKleinsteZugfolge("G1", "A7").ForEach(item => Console.WriteLine(item));
            Console.ReadLine();
        }

        private static List<string> BerecheneKleinsteZugfolge(string start, string ziel)
        {
            int minCount = -1;

            List<string> kleinsteZugfolge = BerechneAlleZugfolgen(start, ziel, new Stack<string>(), ref minCount)
                .OrderBy(list => list.Count)
                .FirstOrDefault();

            return kleinsteZugfolge.ToList();
        }

        private static IEnumerable<List<string>> BerechneAlleZugfolgen(string start, string ziel, Stack<string> previous, ref int minCount)
        {
            var result = new List<List<string>>();

            if (start == null || previous.Contains(start) || (minCount > 0 && minCount == previous.Count))
                return result;

            if (start == ziel)
            {
                result.Add(new List<string>(previous.Reverse()) { ziel });
                minCount = previous.Count;

                return result;
            }

            previous.Push(start);

            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, 2, -1), ziel, previous, ref minCount));
            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, 2, 1), ziel, previous, ref minCount));

            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, -2, -1), ziel, previous, ref minCount));
            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, -2, 1), ziel, previous, ref minCount));

            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, 1, -2), ziel, previous, ref minCount));
            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, 1, 2), ziel, previous, ref minCount));

            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, -1, -2), ziel, previous, ref minCount));
            result.AddRange(BerechneAlleZugfolgen(MoveTo(start, -1, 2), ziel, previous, ref minCount));

            previous.Pop();

            return result;
        }

        private static string MoveTo(string position, int deltaX, int deltaY)
        {
            int x = position[0] - (65 + 1) + deltaX;
            int y = position[1] - 48 + deltaY;

            if (x < 1 || x > 8 || y < 1 || y > 8)
                return null;

            char xChar = (char)(x + (65 - 1));
            char yChar = (char)(y + 48);
            
            return "" + xChar + yChar;
        }

A1
C2
D4
E6
F8

Bzgl. weiterer Aufgabe hab ich zurzeit keine Idee - kann also posten wer will.

A
764 Beiträge seit 2007
vor 11 Jahren

Da gibts irgendwie noch ein Problem mit z.B.:

BerecheneKleinsteZugfolge("G1", "A7")
1.378 Beiträge seit 2006
vor 11 Jahren

Jap, da hab ich wohl zu schleißig getestet. 😛 Habs im vorigen Post ausgebessert - Beim Characterparsen hat was nicht hingehaun.

Lg, XXX

A
764 Beiträge seit 2007
vor 11 Jahren

Tolle Lösung. du bist dran.

1.378 Beiträge seit 2006
vor 11 Jahren

Ich habe gerade keine Idee - kann also posten wer will.

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Community,

die Aufgabe selbst ist kurz und knapp:

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]

herbivore

1.378 Beiträge seit 2006
vor 11 Jahren

Eine ähnliche Aufgabe hab ich mir auch überlegt aber ich dachte mir sie wäre zu aufwendig - kommt dafür als nächstes. 😃


        static void Main(string[] args)
        {
            Console.WriteLine(FullMatch("A", "A"));
            Console.WriteLine(!FullMatch("AB", "A"));
            Console.WriteLine(!FullMatch("A", "a"));
            Console.WriteLine(FullMatch("HALLO", "HALLO"));
            Console.WriteLine(FullMatch("HALLO", "HA**O"));
            Console.WriteLine(FullMatch("HALLO", "HA*"));

            Console.WriteLine(FullMatch("A", "?"));
            Console.WriteLine(FullMatch("B", "?"));
            Console.WriteLine(FullMatch("?", "?"));
            Console.WriteLine(FullMatch("*", "?"));// (im Text haben die Platzhalterzeichen keine Sonderbedeutung)
            Console.WriteLine(!FullMatch("den leeren String", "?"));
            Console.WriteLine(!FullMatch("AB", "?"));
            Console.WriteLine(!FullMatch("A", "??"));
            Console.WriteLine(FullMatch("AA", "??"));
            Console.WriteLine(FullMatch("AB", "??"));
            Console.WriteLine(!FullMatch("ABC", "??"));
            Console.WriteLine(FullMatch("ABC", "??C"));
            Console.WriteLine(FullMatch("CCC", "??C"));
            Console.WriteLine(FullMatch("CC*C", "??*C"));
            Console.WriteLine(!FullMatch("CCCC", "??C"));
            Console.WriteLine(!FullMatch("ABD", "??C"));
            Console.WriteLine(!FullMatch("AC", "??C"));
        }

        private static bool FullMatch(string input, string pattern)
        {
            return FullMatchInternal(input, pattern, false);
        }

        private static bool FullMatchInternal(string input, string pattern, bool findAny)
        {
            if (input.Length == 0 && pattern.Length == 0)
                return true;

            if (input.Length == 0)
                return false;

            if (findAny)
            {
                if (pattern.Length == 0)
                    return true;

                return FullMatchInternal(input.Substring(1), pattern, input.Substring(1)[0] != pattern[0]);
            }

            if (pattern.Length == 0)
                return false;

            if (pattern[0] == '?')
                return FullMatch(input.Substring(1), pattern.Substring(1));

            if (pattern[0] == '*')
                return FullMatchInternal(input, pattern.Substring(1), pattern.Substring(1).Length == 0 || pattern.Substring(1)[0] != '*');

            if (pattern[0] == input[0])
                return FullMatch(input.Substring(1), pattern.Substring(1));

            return false;
        }

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo xxxprod,

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).

herbivore

1.378 Beiträge seit 2006
vor 11 Jahren

So, nun nochmal eine iterative Lösung die den letzten Fall auch abdeckt:


        static void Main(string[] args)
        {
            Console.WriteLine(FullMatch("A", "A"));
            Console.WriteLine(!FullMatch("AB", "A"));
            Console.WriteLine(!FullMatch("A", "a"));
            Console.WriteLine(FullMatch("HALLO", "HALLO"));
            Console.WriteLine(FullMatch("HALLO", "HA**O"));
            Console.WriteLine(FullMatch("HALLO", "HA************O"));
            Console.WriteLine(FullMatch("HALLO", "HA*"));

            Console.WriteLine(FullMatch("A", "?"));
            Console.WriteLine(FullMatch("B", "?"));
            Console.WriteLine(FullMatch("?", "?"));
            Console.WriteLine(FullMatch("*", "?"));// (im Text haben die Platzhalterzeichen keine Sonderbedeutung)
            Console.WriteLine(!FullMatch("den leeren String", "?"));
            Console.WriteLine(!FullMatch("AB", "?"));
            Console.WriteLine(!FullMatch("A", "??"));
            Console.WriteLine(FullMatch("AA", "??"));
            Console.WriteLine(FullMatch("AB", "??"));
            Console.WriteLine(!FullMatch("ABC", "??"));
            Console.WriteLine(FullMatch("ABC", "??C"));
            Console.WriteLine(FullMatch("CCC", "??C"));
            Console.WriteLine(FullMatch("CC*C", "??*C"));
            Console.WriteLine(!FullMatch("CCCC", "??C"));
            Console.WriteLine(!FullMatch("ABD", "??C"));
            Console.WriteLine(!FullMatch("AC", "??C"));
            Console.WriteLine(FullMatch("", "*"));
            Console.WriteLine(!FullMatch("*", ""));
        }

        private static bool FullMatch(string input, string pattern)
        {
            string oldPattern = pattern;
            while ((pattern = pattern.Replace("**", "*")) != oldPattern)
                oldPattern = pattern;

            int j = 0;
            for (int i = 0; i < pattern.Length; i++, j++)
            {
                if (pattern[i] == '*')
                    j = pattern.Length == ++i ? input.Length : input.IndexOf(pattern[i], j);
                
                if (input.Length == j || pattern[i] != '?' && pattern[i] != input[j])
                    return pattern.Length == i;
            }
            return input.Length == j;
        }

Lg, XXX

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo xxxprod,

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", "ABCX?ZLMN")

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 = ""; }

herbivore

1.378 Beiträge seit 2006
vor 11 Jahren

Pfff bist du aber genau 😛

Hier also eine erneut überarbeitete Version:^^


        private static bool FullMatch(string input, string pattern)
        {
            if(input==null || pattern==null)
                return false;

            string oldPattern = pattern;
            while ((pattern = pattern.Replace("**", "*")) != oldPattern)
                oldPattern = pattern;

            return FullMatch(input, pattern, 0, 0);
        }

        private static bool FullMatch(string input, string pattern, int i, int j)
        {
            if (j < 0)
                return false;

            for (; i < pattern.Length; i++, j++)
            {
                if (pattern[i] == '*')
                {
                    i++;

                    while ((j = pattern.Length == i ? input.Length : input.IndexOf(pattern[i], j)) >= 0)
                    {
                        if (FullMatch(input, pattern, i, j++))
                            return true;
                    }
                }

                if (j < 0 || input.Length == j || pattern[i] != '?' && pattern[i] != input[j])
                    return pattern.Length == i;
            }
            return input.Length == j;
        }

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo xxxprod,

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:

FullMatch("AABC", "AA*?"))
FullMatch("AA?BC", "A*?C")

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.

herbivore

1.378 Beiträge seit 2006
vor 11 Jahren

Pff das war jetzt aber eine schwere Geburt - hätte vorher nicht so vorlaut sein sollen von wegen soo einfach^^

Hier nun die (hoffentlich) endgültige und etwas leserlich aufbereitete Version:


        private static bool FullMatch(string input, string pattern)
        {
            input = "" + input;
            pattern = "" + pattern;

            string oldPattern = pattern;
            while ((pattern = pattern.Replace("**", "*")) != oldPattern)
                oldPattern = pattern;

            return FullMatch(input, pattern, 0, 0);
        }

        private static bool FullMatch(string input, string pattern, int iInput, int iPattern)
        {
            for (; iPattern < pattern.Length; iPattern++, iInput++)
            {
                if (pattern[iPattern] == '*')
                {
                    iPattern++;

                    do
                    {
                        if (pattern.Length == iPattern)
                            iInput = input.Length;
                        else
                        {
                            char nextCharacter = (iInput < input.Length && pattern[iPattern] == '?')
                                                     ? input[iInput]
                                                     : pattern[iPattern];

                            iInput = input.IndexOf(nextCharacter, iInput);

                            if (iInput < 0) return false;
                        }

                        if (FullMatch(input, pattern, iInput, iPattern))
                            return true;

                        iInput++;

                    } while (true);
                }

                if (iInput == input.Length || iInput < input.Length && pattern[iPattern] != '?' && pattern[iPattern] != input[iInput])
                    return false;
            }
            return input.Length == iInput;
        }

Lg, XXX

PS: Du bist sicherlich nicht zu pingelig sondern ich zu nachlässig - aber mit Try&Error bin ich noch immer sehr gut vorangekommen^^

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo xxxprod,

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.

public static bool FullMatch (String input, String pattern)
{
   if (input == null) { input = ""; }
   if (pattern == null) { pattern = ""; }

   String [] patternParts = pattern.Split ('*');

   int offset = 0;
   for (int partNo = 0; partNo < patternParts.Length; ++partNo) {
      String patternPart = patternParts [partNo];
      if (partNo == 0) {
         if (!PartMatch (input, 0, patternPart)) { return false; }
      } else if (partNo == patternParts.Length - 1) {
         return (offset <= input.Length - patternPart.Length
          && PartMatch (input, input.Length - patternPart.Length, patternPart));
      } else {
         while (!PartMatch (input, offset, patternPart)) {
            if (input.Length - offset < patternPart.Length) { return false; }
            ++offset;
         }
      }
      offset += patternPart.Length;
   }
   return offset == input.Length;
}

private static bool PartMatch (String input, int offset, String pattern)
{
   if (input.Length - offset < pattern.Length) { return false; }
   for (int i = 0; i < pattern.Length; ++i) {
      if (input [i + offset] != pattern [i] && pattern [i] != '?') {
         return false;
      }
   }
   return true;
}

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:

public static bool FullMatch (String input, String pattern)
{
   if (input == null) { input = ""; }
   if (pattern == null) { pattern = ""; }

   pattern = Regex.Escape (pattern).Replace (@"\*", @".*").Replace (@"\?", @".");

   return Regex.IsMatch (input, "^" + pattern + "$", RegexOptions.Singleline);
}

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:

input = "" + input;
pattern = "" + pattern;

Man könnte - ähnlich kurz, aber ohne Kopieraufwand - den null coalescing-Operator benutzen (siehe Kanntet ihr den ??-Operator? [null coalescing-Operator]):

input = input ?? "";
pattern = pattern ?? "";

Noch kürzer, besser und DRY wäre

input ??= "";
pattern ??= "";

Aber einen ??= Operator gibt es wohl leider nicht, siehe Kanntet ihr den ??-Operator? [null coalescing-Operator].

1.378 Beiträge seit 2006
vor 11 Jahren

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.

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo zusammen,

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.

herbivore

1.378 Beiträge seit 2006
vor 11 Jahren

Hallo zusammen,

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.

Lg, XXX

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo zusammen,

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(nm) (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(nm^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.

1.378 Beiträge seit 2006
vor 11 Jahren

Hallo herbivore,

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^^

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Community,

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!

herbivore

G
47 Beiträge seit 2011
vor 11 Jahren

Hi,

folgender Ansatz ist zumindest durch meine Tests gelaufen:


        public static TimeSpan SubtractEx( DateTime start, DateTime end, Dictionary<DayOfWeek, IList<TimeSpan>> timelist)
        {
            if (end < start)
                throw new ArgumentException("Das Enddatum muss nach dem Startdatum liegen.");
            DateTime time = start;
            TimeSpan result = new TimeSpan();

            IList<TimeSpan> todaysList;

            DateTime endofday;
            bool lastday = false;
            bool firstday = true;

            while (time < end)
            {
                todaysList = timelist[time.DayOfWeek];
                endofday = new DateTime(time.Year, time.Month, time.Day + 1);
                if (endofday > end)
                    lastday = true;
                if (todaysList != null)
                {
                    for (int i = 0; i < todaysList.Count; i += 2)
                    {
                        if (firstday)
                        {
                            if (time.TimeOfDay >= todaysList[i])
                            {
                                time = time.Subtract(todaysList[i]);
                                firstday = false;
                            }
                            else
                                if (time.TimeOfDay<todaysList[i+1])
                                    time = time.Subtract(time.TimeOfDay);
                        }
                        time = time.Add(todaysList[i]);
                        if (!lastday)
                        {
                            result = result.Add(todaysList[i + 1] - time.TimeOfDay);
                        }
                        else
                        {
                            if (time > end)
                                break;
                            result = result.Add(((todaysList[i + 1] < end.TimeOfDay) ? todaysList[i + 1] : end.TimeOfDay) - time.TimeOfDay);
                        }
                        time = time.Subtract(time.TimeOfDay);

                    }
                }
                time = endofday;
                firstday = false;
            }
            return result;
        }

Gruß Gwinn

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Gwinn,

schön, dass du dich der Aufgabe angenommen hast!

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.

herbivore