Last active
April 19, 2019 15:03
-
-
Save kenpusney/52863c8d034fac29d26f8febc7513b5b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cassert> | |
| #include <map> | |
| #include <set> | |
| #include <string> | |
| #include <algorithm> | |
| #include <iterator> | |
| #include <iostream> | |
| #include <fstream> | |
| using namespace std; | |
| using Anagrams = map<string, set<string>>; | |
| using Anagram = Anagrams::value_type; | |
| template <class Iter> | |
| Anagrams find_anagrams(Iter begin, Iter end) | |
| { | |
| Anagrams anagrams; | |
| for (auto &&word = begin; word != end; word++) | |
| { | |
| auto key = string{*word}; | |
| std::sort(key.begin(), key.end()); | |
| if (anagrams.find(key) != anagrams.end()) | |
| { | |
| anagrams[key].insert(*word); | |
| } | |
| else | |
| { | |
| anagrams[key] = set{*word}; | |
| } | |
| } | |
| for (auto &&iter = anagrams.begin(); iter != anagrams.end();) | |
| { | |
| if (iter->second.size() <= 1) | |
| { | |
| iter = anagrams.erase(iter); | |
| } | |
| else | |
| { | |
| iter++; | |
| } | |
| } | |
| return anagrams; | |
| } | |
| void test_find_anagrams() | |
| { | |
| auto &&words = set<string>{"players", "replays", "sparely"}; | |
| auto &&anagrams = find_anagrams(begin(words), end(words)); | |
| assert(anagrams["aelprsy"].size() == 3); | |
| for (auto &&w : anagrams["aelprsy"]) | |
| { | |
| cout << w << '\n'; | |
| } | |
| } | |
| Anagram longest(Anagrams anagrams) | |
| { | |
| return *max_element(anagrams.begin(), anagrams.end(), [](auto &x, auto &y) -> auto { | |
| return x.first.size() < y.first.size(); | |
| }); | |
| } | |
| Anagram most(Anagrams anagrams) | |
| { | |
| return *max_element(anagrams.begin(), anagrams.end(), [](auto &x, auto &y) -> auto { | |
| return x.second.size() < y.second.size(); | |
| }); | |
| } | |
| void test_longest_and_most() | |
| { | |
| auto &&words = set<string>{"players", "replays", "sparely", "longestword", "wordlongest"}; | |
| auto &&anagrams = find_anagrams(begin(words), end(words)); | |
| assert(longest(anagrams).first == "deglnoorstw"); | |
| assert(most(anagrams).first == "aelprsy"); | |
| } | |
| int main() | |
| { | |
| // test_find_anagrams(); | |
| // test_longest_and_most(); | |
| ifstream words_file{"words.txt"}; | |
| istream_iterator<string> word_stream{words_file}; | |
| auto &&anagrams = find_anagrams(word_stream, istream_iterator<string>()); | |
| auto longestAnagram = longest(anagrams); | |
| std::cout << "longest: " << longestAnagram.first << ", " << longestAnagram.first.size() << '\n'; | |
| auto mostAnagram = most(anagrams); | |
| std::cout << "most: " << mostAnagram.first << ", " << mostAnagram.second.size() << '\n'; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment