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

[wira 0]

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 von wira
...

[KeeperOfCoffee 541]

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 von KeeperOfCoffee

[allesweg 455]

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 von Mttkrb

[KeeperOfCoffee 541]

@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 392]

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

[Whiz-zarD 392]

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 541]

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 von KeeperOfCoffee