Skip to content

Instantly share code, notes, and snippets.

@adrian17
Last active August 24, 2016 22:20
Show Gist options
  • Save adrian17/b9efcfb0d3140a356be142d723886652 to your computer and use it in GitHub Desktop.
Save adrian17/b9efcfb0d3140a356be142d723886652 to your computer and use it in GitHub Desktop.
slightly simpler and slower anagram generator implementation
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <array>
#include <fstream>
#include <xmmintrin.h>
#include <experimental/string_view>
using namespace std;
using namespace std::experimental;
using Count = std::array<char, 32>;
std::map<Count, std::vector<std::string>> anagrams;
std::array<std::vector<Count>, 50> by_len;
const Count* stack[50];
Count empty_count() {
Count count;
for (auto &v : count)
v = 0;
return count;
}
Count make_count(string_view str) {
Count count = empty_count();
for (char c : str) {
c = tolower(c);
if (!islower(c))
continue;
count[c-'a']++;
}
return count;
}
bool add(const Count &c1, const Count &c2,
const Count &target, Count &res
) {
for(int i = 0; i < 32; ++i) {
res[i] = c1[i] + c2[i];
if (res[i] > target[i])
return true;
}
return false;
}
void print_solution(
const Count** stack_top,
const Count** curr=stack,
std::string text=""
) {
if (curr == stack_top)
printf("%s\n", text.c_str());
else for (const std::string &word : anagrams[**curr])
print_solution(stack_top, curr+1, text + word + ' ');
}
size_t sum;
void recurse(
const Count &target, int left, int last_n,
Count curr, const Count** stack_top
) {
Count next;
if (curr == target) {
sum++;
//print_solution(stack_top);
}
else for (int n = min(left, last_n); n > 0; --n) {
for (const Count &count : by_len[n]) {
bool over = add(curr, count, target, next);
if (over)
continue;
*stack_top = &count;
recurse(target, left-n, n, next, stack_top+1);
}
}
}
int main() {
ifstream f("enable1.txt");
string tmp;
while (getline(f, tmp)) {
Count count = make_count(tmp);
anagrams[count].push_back(tmp);
by_len[tmp.size()].push_back(count);
}
string_view test = "Help, someone stole my purse";
Count target = make_count(test);
int size = 0;
for(char c : target)
size += c;
recurse(target, size, size, empty_count(), stack);
printf("%lu\n", sum);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment