Aha! Excellent book…
Ξ May 5th, 2012 | → 0 Comments |
∇ Books | ∇ Algorithms, Book, Pearls, Programming |
I’ve been reading some of the classics, including the amazing Jon Bentley’s Programming Pearls (2nd Edition). The book provides awesome insight to the mind of a programmer. Moreover, by providing an excellent list of problems the author incites the reader to experiment with the contents of the book.
Here’s my version of the anagram finder from Column 2: “Aha! Algorithms”.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
typedef std::vector<std::string> anagram_vector_t;
typedef std::unordered_map<std::string, anagram_vector_t> anagram_map_t;
void
load_words_from_stream(anagram_vector_t& words, std::istream& input)
{
std::string word;
while(input >> word)
{
words.push_back(word);
}
}
void
load_words_from_file(anagram_vector_t& words, const std::string& filename)
{
std::ifstream input(filename);
load_words_from_stream(words, input);
}
void
process_anagrams(const anagram_vector_t& words, anagram_map_t& anagrams)
{
std::for_each(std::begin(words),
std::end(words),
[&anagrams](const std::string& word) {
// get key by sorting the string value
std::string key = word;
std::sort(key.begin(), key.end());
// store (key, value)
anagrams[key].push_back(word);
});
}
void
print_anagrams(const anagram_map_t& anagrams)
{
for(auto i = std::begin(anagrams); i != std::end(anagrams); ++i)
{
const anagram_vector_t& words = i->second;
if( words.size() > 1 )
{
std::for_each(std::begin(words),
std::end(words),
[&anagrams](const std::string& word) {
std::cout << word << " ";
});
std::cout << std::endl;
}
}
}
void do_anagrams(const std::string& filename)
{
anagram_map_t anagrams;
anagram_vector_t words;
load_words_from_file(words, filename);
process_anagrams(words, anagrams);
print_anagrams(anagrams);
}
int main(int argc, char *argv[])
{
if( argc != 2 )
{
std::cout << "Usage: " << argv[0] << " <words-file>" << std::endl;
return -1;
}
do_anagrams(argv[1]);
return 0;
}
