Programmierübung "Wechstaben-verbuchsler" (aus Buchstabensammlung mache sinnvolles Wort)

[wira 4]

Hallo

Ein Gewinnspiel auf einer Pizzaschachtel hat mich angeregt, mal die Programmierkenntnisse zu erweitern.

Aus aufgedruckten Buchstaben soll ein sinnvolles Wort gebildet werden, also z.B. aus "aahrstu" kann man "Hausrat" machen (oder "Rathaus").

Alle Buchstaben müssen verbraucht werden, nur "Haus" ist also keine Lösung.

Das ganze ist eine ÜBUNG, muss also "Donausdampfschiffahrtskapitän" nicht zusammenstückeln können.

Es geht mir um das Programmieren, bin mehr ein FI-SI.

Wie würdet ihr daran gehen?

Tschüss

Bearbeitet 9. September 2019 von wira
...

[KeeperOfCoffee 854]

Viel Spass  hier hast du "ein paar" Daten

https://raw.githubusercontent.com/davidak/wortliste/master/wortliste.txt

Edit: Du würdest den vorgegebenen String einfach analysieren und einen Abgleich mit deinen Daten (Wörterliste) machen. Zuallererst würdest du allerdings die Liste einschränken (z.B. mit der Länge des Wortes)

Damit du auch noch schneller suchst, wirst du wohl mit Multithreading arbeiten müssen...sprich du unterteilst die große Liste in mehrere kleinere Listen und durchsuchst mit mehreren Threads je eine Liste.

Auch ein Compressed suffix tree wäre interessant:

https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

Bearbeitet 9. September 2019 von KeeperOfCoffee

[allesweg 744]

Die Anzahl der Buchstaben als erste Einschränkung nehmen.

Dann die Buchstaben im String sortieren.

[Mttkrb 72]

Ich würde wie folgt vorgehen:

• zu suchende Zeichen eingeben
• Zeichen sortieren
• Großbuchstaben durch kleinbuchstaben ersetzen
• mögliche Wörter aus Datei oder db laden
• zu jedem Wort einen Sortierstring speichern und hier Zeichen sortieren und Groß-durch kleinbuchstaben ersetzen
• alle Einträge mit dem Sortierstring vergleichen
• Ersten oder alle Treffer ausgeben. (Je nach Fragestellung)

Mit C# wären die Linq-Methoden AsParallel, Where, OrderBy, und SequenceEqual,  bzw. string.ToLower hilfreich. Dann sind das nur ein paar Zeilen.

Bearbeitet 9. September 2019 von Mttkrb

[KeeperOfCoffee 854]

@Mttkrb wenn du aber ein Wörterbuch wie ich oben hernehmen würdest, würde schon alleine das .ToLower() lange dauern ?

[Mttkrb 72]

Hatte ich auch gedacht. Ging aber überraschend schnell.

 class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Bitte Zeichen eingeben: ");
            var characters = Console.ReadLine();
            var sorted =characters.ToLower().OrderBy(o=>o).ToArray();
            var lines = File.ReadLines("wortliste.txt");
            var result = lines.AsParallel().Where(f => f.ToLower().OrderBy(o => o).SequenceEqual(sorted));
            Console.WriteLine($"Mögliche Wörter sind: {string.Join(", ",result)}");
            Console.ReadKey();
        }
    }

 

[Whiz-zarD 523]

Hmm, interessant. Hätte jetzt nicht gedacht, dass Variante so schnell ist.

[Whiz-zarD 523]

Der vergleich nach Strings ist sogar schneller:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Bitte Zeichen eingeben: ");
        var characters = Console.ReadLine();
        var sorted = Sort(characters);
        var lines = File.ReadLines("wortliste.txt");
        var result = lines.AsParallel().Where(x => Sort(x) == sorted);
        Console.WriteLine($"Mögliche Wörter sind: {string.Join(", ",result)}");
        Console.ReadKey();
    }
    
    static string Sort(string s) => new string(s.ToLower().OrderBy(x => x).ToArray());
}

 

[Mttkrb 72]

Jetzt bleibt nur noch die frage, ob es mit .net oder .netCore schneller ist ?

[KeeperOfCoffee 854]

vor 41 Minuten schrieb Mttkrb:

Jetzt bleibt nur noch die frage, ob es mit .net oder .netCore schneller ist ?

Geht sicherlich auch mit ML.NET

Aber nächstes Jahr kommt ja .NET 5

Bearbeitet 11. September 2019 von KeeperOfCoffee