4 ms·
I have a short program to solve letterboxed. I can't measure how fast it is. #include <array> #include <algorithm> #include <bitset> #include <iostrea
by angiosperm 3y ago
I have a short program to solve letterboxed. I can't measure how fast it is.
#include <array>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <string_view>
#include <vector>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
struct Word {
using Bits = std::bitset<32>; // A bit for each a..z, plus an "error" bit at index 26.
using Rules = std::array<Bits, 27>; // Map from letter indices to forbidden letters (plus a spare).
std::string_view str;
Bits bits;
static unsigned ix(char c) { return c - 'a'; }; // 'a'..'z' -> 0..25; others -> >25
bool ok() const { return !bits.test(26) && str.size() > 1; }
explicit Word(std::string_view s, Bits accept = {0x3ffffff}, Rules const& rules = {}) : str(s) {
for (unsigned i = 0, prev_ix = 26, bit_ix = 0; i != str.size(); prev_ix = bit_ix, ++i) {
bit_ix = std::min(ix(str[i]), 26u);
if (accept.test(bit_ix) && !rules.at(prev_ix).test(bit_ix)) { bits.set(bit_ix); }
else { bits.set(26); return; }}}
};
int main(int ac, char** av) {
auto usage = [av](){ std::cerr << "usage: " << av[0] << " abcdefghijkl [<wordlist>]\n"; };
if (ac != 2 && ac != 3) { return usage(), 1; }
char const* const name = (ac == 3) ? av[2] : "/usr/share/dict/american-english-large";
const int fd = ::open(name , O_RDONLY);
if (fd < 0) { return std::cerr << av[0] << ": failed to open " << name << '\n', 3; }
const std::size_t file_size = ::lseek(fd, 0, SEEK_END);
void const* const addr = ::mmap(nullptr, file_size, PROT_READ, MAP_SHARED, fd, 0);
if (addr == MAP_FAILED) { return std::cerr << av[0] << ": failed to open " << name << '\n', 3; }
const auto target = Word{av[1]};
if (target.bits.test(26) || target.str.size() != 12 || target.bits.count() != 12)
{ return usage(), 3; }
const auto rules = [w=target.str, ix=Word::ix](Word::Rules rules = {}) {
for (int i = 0; i < 12; i += 3)
rules.at(ix(w[i])) = rules.at(ix(w[i+1])) = rules.at(ix(w[i+2])) = Word(w.substr(i, 3)).bits;
return rules;
}();
const auto candidates = [&](std::array<std::vector<Word>, 26> candidates = {}) {
for (std::string_view in = {static_cast<char const*>(addr), file_size}; !in.empty();) {
const Word word{in.substr(0, in.find('\n')), target.bits, rules};
if (word.ok()) { candidates.at(Word::ix(word.str.front())).push_back(word); }
in = in.substr(word.str.size() + 1); // Skip past '\n' if present (might not be, at EOF).
}
return candidates;
}();
for (auto const& firsts : candidates) {
for (const auto first : firsts) {
for (const auto second : candidates.at(Word::ix(first.str.back()))) {
if ((first.bits | second.bits) == target.bits) {
std::cout << first.str << ' ' << second.str << '\n'; }}}}
}