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

[wira]

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]

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]

Die Anzahl der Buchstaben als erste Einschränkung nehmen.

Dann die Buchstaben im String sortieren.

[Mttkrb]

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]

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

[Mttkrb]

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]

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

[Whiz-zarD]

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]

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

[KeeperOfCoffee]

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