algorithm frage



  • Hi,
    ich habe eine frage wie ich folgendes problem loesen kann!?
    mein implementierter algo ist brute force, und hat leider noch einen bug...findet jemand das problem?

    /*
    Given two English words of the same length, say, "HEAD" and "TAIL", come up with a sequence of valid English words, starting with "HEAD", and ending with "TAIL", such that each word is formed by changing a single letter of the previous word.
    
    expected:
    head
    heal
    teal
    tell
    tall
    tail
    */
    
    #include <iostream>
    #include <unordered_set>
    #include <string>
    #include <vector>
    using namespace std;
    
    //#define DEBUG_INFO
    unordered_set<string> dictionary = {"heal", "teal", "tell", "tall", "tail", "cut", "bat", "but", "bun", "nut", "nat"};
    const string alphabet = "abcdefghijklmnopqrstuvwxyz";
    const int alphabet_size = 26;
    
    vector<string> getNextWords(string word) {
    	vector<string> nextWords;
    
    	for(int i = 0; i < word.size(); i++) {
    		int index = word[i] - 'A';
    
    		// replace first character with another character within the alphabet
    		for(int k = 0; k < alphabet_size; k++) {
    			int alphabet_index = (index + k + 1) % alphabet_size;
    			string tmp = word;
    			tmp[i] = alphabet[alphabet_index];
    			nextWords.push_back(tmp);
    		}
    	}
    
    	return nextWords;
    }
    
    bool insertSequence(unordered_set<string> &seq, string &newWord) {
    	auto found = seq.find(newWord);
    
    	if (found == seq.end()) {
    		seq.insert(newWord);
    		return true;
    	}	
    
    	return false;
    }
    
    unordered_set<string> wordChain(const string &word1, const string &word2) {
    	unordered_set<string> sequence;
    	string currentWord = word1;
    
    	while(currentWord != word2) {
    		#ifdef DEBUG_INFO
    			cout << "currentWord: " << currentWord << ", word2: " << word2 << endl;
    		#endif
    		vector<string> words = getNextWords(currentWord);
    
    		for (auto w : words) {
    			auto it = dictionary.find(w);
    
    			if (it != dictionary.end()) {
    				bool canInsert = insertSequence(sequence, w);
    
    				if (canInsert) {
    					currentWord = w;
    					break;
    				}
    			}
    		}
    	}
    
    	return sequence;
    }
    
    int main() {
    	// your code goes here
    
    	unordered_set<string> words = wordChain("head", "tail");
    	for(auto w : words) {
    		cout << w << endl;
    	}
    
    	words = wordChain("cut", "nat");
    	for(auto w : words) {
    		cout << w << endl;
    	}
    
    	return 0;
    }
    


  • ps. wie kann ich den algo optimieren?


  • Mod

    joko&klaas schrieb:

    mein implementierter algo ist brute force, und hat leider noch einen bug...findet jemand das problem?

    Herr Doktor, ich bin krank!

    Herr Automechaniker, mit meinem Auto stimmt was nicht!

    Herr Fachmann, mein Gerät funktioniert nicht!


  • Mod

    joko&klaas schrieb:

    ps. wie kann ich den algo optimieren?

    Das ist eine konkrete Frage, darauf kann man antworten:
    Das Problem nennt sich "word ladder". Die übliche Vorgehensweise wäre, dass du zunächst einmal dein Wörterbuch vorbereitest. Du kannst daraus einen Graphen erzeugen, welche Wörter mit welchen anderen verbunden sind. Danach kannst du, ausgehend von einem Start- und Endwert, eine Breitensuche auf diesem Graphen machen, um die kürzeste Verbindung zu finden.

    Bei einem (gedächtnislosen) Brute-Force Ansatz dürftest du hingegen das Problem bekommen, dass du leicht in irgendwelche Endlosschleifen gerätst. Ist das eventuell dein geheimnisvoller Bug, den du uns nicht verraten möchtest?



  • @SeppJ:
    bug war hier:

    if (w != word1 && it != dictionary.end()) {
    

    ich brauche noch ne art backtracking...
    tail -> tall -> tell -> teal -> heal ... ist ok

    nat -> bat -> but -> nut
    expected:
    "bat" -> "but" -> "bun" -> "nut" -> "nat"


  • Mod

    joko&klaas schrieb:

    ich brauche noch ne art backtracking...
    tail -> tall -> tell -> teal -> heal ... ist ok

    nat -> bat -> but -> nut
    expected:
    "bat" -> "but" -> "bun" -> "nut" -> "nat"

    😕 Entweder ist dein Beispiel unglücklich gewählt oder ich kapiere es nicht.

    Du meinst, du musst verhindern, dass du in eine Sackgasse läufst? Bzw., wenn du in eine Sackgasse läufst, musst du wieder hinaus kommen und eine andere Richtung wählen? Die klassische Vorgehensweise dafür wäre ein rekursiver Ansatz.

    Damit behebst du aber immer noch nicht das erwähnte Problem, dass du statt in eine Sackgasse auch in eine Schleife laufen könntest. Wie willst du das verhindern? Vergleich mit dem kompletten vorherigen Pfad? Möglich. Aber aufwendig.

    Weiteres Problem: Dein Ansatz findet nicht den kürzesten Weg. Auch wenn es nicht in der Aufgabenstellung verlangt ist, so wäre ich doch enttäuscht von einer Lösung, die bloß irgendeinen, aber nicht den besten Weg findet.

    Ich würde nicht versuchen, deinen Ansatz zu korrigieren. Da gibt es so viele Sonderfälle, die du alle speziell behandeln musst. Zumal du doch ohnehin einen besseren Ansatz suchst. Daher würde ich an deiner Stelle den von mir vorgeschlagenen Ansatz verfolgen. Der ist bewährt und halbwegs effizient.

    Kann es irgendwie sein, dass du ein paar vorherige Hausaufgaben "verpasst" hast? Die Aufgabenstellung ist nicht ganz einfach. Ich würde sie nicht jemandem stellen, ohne vorher Graphen behandelt zu haben. Oder jemandem, der nicht weiß, wie man Backtracking umsetzt. Und wenn man Graphen behandelt hat, dann liegt der von mir vorgeschlagene Ansatz doch nahe, oder?


  • Mod

    Vielleicht ein bisschen over-enginieered 🕶 :

    #include <iostream>
    #include <string>
    #include <cctype>
    #include <vector>
    #include <iterator>
    #include <fstream>
    #include <unordered_map>
    #include <unordered_set>
    #include <cstring>
    #include <queue>
    
    // Erst einmal jede Menge Framework, hauptsächlich Boilerplatecode: 
    // -Ein Klasse für Wörter mit fester Länge und nur aus Buchstaben bestehend. Groß-/Kleinschreibung ist egal.
    // -Eine spezialisierte Hashfunktion dafür.
    // -Ein- und Ausgabe für diese Klasse.
    template <unsigned N> class N_Letter_Word
    {
      char word[N];
    
    public:
      // Um den Graph zu bauen, brauchen wir später ein Sonderzeichen als Platzhalter:
      void set_placeholder(unsigned index)
      {
        word[index] = 'Z' + 1;
      }
    
      char operator[] (unsigned index) const { return word[index]; }
    
      friend bool operator==(const N_Letter_Word<N>& lhs, const N_Letter_Word<N>& rhs)
      {
        return !memcmp(lhs.word, rhs.word, N);
      }
    
      friend std::istream& operator>>(std::istream &in, N_Letter_Word<N> &w)
      {
        std::string word;
        in >> word;
        if (word.size() == N)
          {
            for(unsigned i = 0; i < N; ++i)
              {
                if(std::isalpha(word[i]))
                  {
                    w.word[i] = std::toupper(word[i]);
                  }
                else
                  {
                    in.setstate(std::ios::failbit);
                    return in;
                  }
              }
          }
        else
          in.setstate(std::ios::failbit);
        return in;
      }
      friend std::ostream& operator<<(std::ostream& out, const N_Letter_Word<N> &w)
      {
        return out.write(w.word, N);
      }
    };
    
    namespace std
    {
      template <unsigned N> struct hash<N_Letter_Word<N> >
      {
        std::size_t operator()(const N_Letter_Word<N>& word) const
        {
          std::size_t hash = 0;
          std::size_t prod = 1;
          for(unsigned i = 0; i < N; ++i)
            {
              hash += prod * (word[i] - 'A');
              prod *= 27;
            }
          return hash;
        }
      };
    }
    
    // Hier geht der eigentlich relevante Code los.
    // Die Suchfunktion ist eine Klasse, damit man nicht bei jeder Suche den Graph
    // und das Wörterbuch neu aufbauen muss.
    
    template<unsigned N> class Word_Ladder_Searcher
    {
      std::vector<N_Letter_Word<N> > dictionary;
      std::unordered_map<N_Letter_Word<N>, std::size_t> dictionary_index;
      std::unordered_map<std::size_t, std::vector<std::size_t> > graph;
    public:
      template<typename Iterator> Word_Ladder_Searcher<N>(Iterator begin, Iterator end)
      : dictionary(begin, end)
      { 
        // Baue den Graph auf. Zuerst werden alle Wörter die sich nur um einen Buchstaben unterscheiden
        // gemeinsam in eine List gepackt. Dies wird erreicht, indem man eine 
        // map aufbaut, in der die Kategorien die Wörter sind, wobei jeweils ein
        // Buchstabe durch einen Platzhalter ersetzt wurde. Wörter, die sich nur an der
        // Stelle unterscheiden, wo der Platzhalter ist, landen so in der gleichen Kategorie.
        // Alle Wörter in einer Kategorie sind dann durch genau eine Ersetzung verbunden
        // (nämlich an der Stelle, wo der Platzhalter steht).
        std::unordered_map<N_Letter_Word<N>, std::vector<std::size_t> > words;
        for (std::size_t i = 0; i < dictionary.size(); ++i)
          {
            for(unsigned j = 0; j < N; ++j)
              {
                N_Letter_Word<N> word = dictionary[i];
                word.set_placeholder(j);
                // Es werden nicht die Worte selber gespeichert. Das ganze Programm arbeitet
                // aus Effizienzgründen nur mit der Position eines Wortes in der Wörterliste
                words[word].push_back(i);
              }
            // Nebenbei noch einen Index anlegen, damit man später zu einem Wort schnell 
            // die Position im Wörterbuch finden kann, ohne das ganze Buch durchsuchen zu müssen.
            dictionary_index[dictionary[i]] = i;
          }
        // Die Kategorien wurden erzeugt. Der Graph wird durch eine Adjazenzliste
        // dargestellt. Zu jedem Vertex (also jedem Wort) gehört eine Liste benachbarter
        // Vertices/Worte.
        for (auto const& bucket: words)
          {
            const auto& wordlist = bucket.second;
            for (auto word1 : wordlist)
              for (auto word2 : wordlist)
                {
                  if (word1 != word2)
                    graph[word1].push_back(word2);
                }
          }
      }
    
      // Die eigentliche Suchfunktion. Sucht von begin nach end und schreibt das
      // Ergebnis in out.
      template<typename Iterator> Iterator search(const N_Letter_Word<N>& begin_word, const N_Letter_Word<N>& end_word, Iterator out)
      {
        std::size_t begin, end;
        {
          // Wenn die Suchworte gar nicht existieren, sparen wir uns die Suche:
          auto b_it = dictionary_index.find(begin_word);
          if (b_it == dictionary_index.end()) return out;
          auto e_it = dictionary_index.find(end_word);
          if (e_it == dictionary_index.end()) return out;
    
          begin = e_it->second;  // Wir suchen von hinten nach vorne, um hinterher leichter das Ergbenis ablesen zu können
          end = b_it->second;    // und dabei die Reihenfolge zu erhalten, die der Nutzer erwartet.
        }
    
        // Nun wird eine Breitensuche durchgeführt. Ganz naiver Algorithmus,
        // direkt von Wikipedia übernommen.
    
        // Als Ergebnis merken wir uns zu jedem Wort den Vorgänger bei der Suche.
        // Als Vorgänger des Startwortes nehmen wir den Sonderwert -1.
        std::unordered_map<std::size_t, std::size_t> bfs_tree;
        bfs_tree[begin] = -1;
    
        // Gib der Warteschlange der zu besuchenden Vertices den Startvertex als Anfangswert:
        std::queue<std::size_t> queue;
        queue.push(begin);
    
        while(!queue.empty())  // Solange noch Vertices zu besuchen sind...
          {
            auto current_vertex = queue.front();  // ...nehme den Vertex...
            if (current_vertex == end) // Falls wir beim Ziel angekommen sind, brechen wir sofort ab
              {
                break;
              }
            for (auto adjacent_vertex : graph[current_vertex])  // ...und untersuche alle Nachbarn...
              {
                if(!bfs_tree.count(adjacent_vertex))   // ...teste, ob wir den Nachbar schon besucht haben...
                  {
                    bfs_tree[adjacent_vertex] = current_vertex;  // ...falls nicht, füge ihn der Ergebnisliste hinzu....
                                                                 // ...Sein Vorgänger ist der aktuelle Vertex....
                    queue.push(adjacent_vertex);                 // ...Füge ihn in die Liste der zu besuchenden Vertices ein.
                  }
              }
            queue.pop(); // Entferne den aktuellen Vertex aus der Warteschlange
          }
    
        if (queue.empty()) return out;  // Warteschlange leer, bedeutet wir konnten keine Verbindung finden.
    
        // Gebe vom Ende anfangend jeweils den Vorgänger im Suchbaum aus. 
        // Konstruktionsbedingt hat jeder Vertex genau einen Vorgänger und wir werden
        // garantiert beim Anfang (-1) ankommen.
        for(std::size_t it = end; it != -1; it = bfs_tree[it])
          {
            *(out++) = dictionary[it];
          }
        return out;
      }
    };
    
    int main()
    {
      std::ifstream word_list("4_letter_words.txt");
      std::istream_iterator<N_Letter_Word<4>> it(word_list), end;
      Word_Ladder_Searcher<4> wls(it, end);
    
     std::ostream_iterator<N_Letter_Word<4>> out(std::cout, "\n");
      for (N_Letter_Word<4> begin, end; std::cin >> begin >> end; )
        {  
          wls.search(begin, end, out);
        }
    }
    

    Gefüttert wird das mit einer Wörterliste für Scrabblespieler:
    http://www.poslarchive.com/math/scrabble/lists/index.html

    Mit der "TWL98 four-letter words"-Liste ergibt sich beispielsweise:

    head
    tail
    HEAD
    HEAL
    HEIL
    HAIL
    TAIL
    hope
    lost
    HOPE
    HOSE
    HOST
    LOST
    

    Wenn jemand Spaß hat, möge er herausfinden, welches die längste Leiter sind, ob die Gruppe zusammenhängend ist, und so weiter. Man begibt sich dabei auf die Spuren von keinem geringeren als Donald Knuth, der das (laut Wikipedia) für 5-buchstabige Wörter gemacht hat. Das Programm sollte einfach genug erweiterbar sein, aber ich habe gerade keine Zeit mehr dafür. Im Prinzip kann man ja jedes Wort mit jedem anderen verbinden und das Resultat ansehen. Es wäre natürlich schicker, wenn man die Suchfunktion selber erweitert, so dass nicht jedes Mal der mühsam aufgebaute Suchbaum weg geworfen wird, obwohl man ja mehrmals mit der gleichen Wurzel anfangen würde*.

    *: Einer der Gründe, warum ich den Suchbaum nirgendwo abspeichere, ist, dass ich dann einen Mutexlock hätte einbauen müssen. Aber ich wollte nicht grundlos Multithreadingkomplexität in ein Beispielprogramm einbauen.

    edit: Noch ein paar Kommentare eingefügt, damit's verständlich wird.


Log in to reply