Scramble challenge entry

scramble.cc

// scramble.cc
// Leonhard Markert
//
// This program finds words in a character matrix. The words are read from a
// `dictionary` file and the character matrix from a `scramble` file.
//
// Compile with
// $ clang++ -std=c++11 -DNDEBUG -O3 -Wall -W -Werror -o scramble scramble.cc
//
// Run as
// $ ./scramble scramble.txt dictionary.txt

#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>

// -----
// Types
// -----

// record choice point for switch/case matching in find_word
enum choice { UP_C, DOWN_C, LEFT_C, RIGHT_C, DONE_C };
// a position (relative or absolute) in the scramble
typedef struct { int row; int col; } position;
// `match` represents an instance of a tuple of letters in the scramble grid by
// giving the position of the first letter and the direction (as a relative
// position) to follow to find the second letter
typedef struct { position pos; position dir; } match;
// elements of the stack in find_word -- the `dir` values on the stack together
// give the path that is currently explored
typedef struct { position dir; position end; choice next; } context;

// ------
// Macros
// ------

// letters a-z (26) and digits 0-9 (10)
#define ALPHABET        (36)
// transform an ASCII character into an index
#define COORD(N)        ((N) >= 97 ? (N) - 97 : (N) - 48)
// index into scramble grid
#define GRID(R,C)       M[(R)*scramble_len + (C)]
// add an absolute position `P` and a direction (relative position) `D` to get
// a new absolute position
#define SUM_POS(P, D)   { .row = (P).row + (D).row, .col = (P).col + (D).col }
// is this position equal to zero?
#define POS_ZERO(P)     ((P).row == 0 && (P).col == 0)

// ----------------
// Global constants
// ----------------

// directions as relative positions
const position UP    = { .row = -1, .col =  0 };
const position DOWN  = { .row =  1, .col =  0 };
const position LEFT  = { .row =  0, .col = -1 };
const position RIGHT = { .row =  0, .col =  1 };

// ----------------
// Global variables
// ----------------

// for any two characters a and b, S[a][b] gives the list of matches for "ab"
// in the scramble grid
std::vector<match> S[ALPHABET][ALPHABET];
// `M` is just a copy of the scramble grid, line by line
std::string M;
// the number of rows (and columns) of the scramble grid
int scramble_len;

// --------------------
// Simple sanity checks
// --------------------

// sanity check: is the total number of matches in `S` is as it should be?
bool verify_state_machine() {
    int sum = 0;
    for (int i = 0; i < ALPHABET; ++i) {
        for (int j = 0; j < ALPHABET; ++j) {
            sum += S[i][j].size();
        }
    }
    return 4 * scramble_len * (scramble_len-1) == sum;
}

// sanity check: can the given word actually be found on this path?
bool verify_stack(position pos, const std::vector<context> &stack, const std::string &word) {
    assert(word.size() == 1 + stack.size());
    auto stack_it = stack.cbegin();
    auto word_it = word.cbegin();
    for ( ; word_it != word.cend(); ++stack_it, ++word_it) {
        // is the next character actually there?
        if (GRID(pos.row, pos.col) != *word_it) { return false; }
        pos = SUM_POS(pos, stack_it->dir);
    }
    return true;
}

// ----------------
// Helper functions
// ----------------

// assuming that the directions in `stack` do not contain a cycle, does adding
// `d` generate one?
bool has_cycle(const std::vector<context> &stack, position dir) {
    for (auto it = stack.crbegin(); it != stack.crend(); ++it) {
        dir = SUM_POS(dir, it->dir);
        if (POS_ZERO(dir)) { return true; }
    }
    return false;
}

// convert `stack` into a string for printing
std::string stack_to_string(const std::vector<context> &stack) {
    std::string s;
    for (auto it = stack.cbegin(); it != stack.cend(); ++it) {
        s.push_back(
                it->dir.row == 0 ? (it->dir.col == -1 ? 'l' : 'r')
                                 : (it->dir.row == -1 ? 'u' : 'd'));
    }
    return s;
}

// --------------
// Initialisation
// --------------

// generate `S` and `M` from the given scramble file
void build_state_machine(const char *scramble_fname) {
    std::string prev, cur;
    std::ifstream scramble(scramble_fname);

    // read scramble dimensions
    scramble >> scramble_len;
    M.reserve(scramble_len * scramble_len);

    // seek to beginning of next line
    scramble.seekg(1, std::ios_base::cur);

    // read in first line of scramble
    std::getline(scramble, prev);
    M.append(prev);

    // extra handling for first row
    for (int col = 1; col != scramble_len; ++col) {
        const position pos = { .row = 0, .col = col };
        const int c = COORD(prev[col]);
        const int l = COORD(prev[col - 1]);

        S[c][l].push_back({ .pos = pos, .dir = LEFT });
        S[l][c].push_back({ .pos = SUM_POS(pos, LEFT), .dir = RIGHT });
    }

    // loop over entire file, line by line
    for (int row = 1; std::getline(scramble, cur); ++row) {
        M.append(cur);
        for (int col = 0; col != scramble_len; ++col) {
            const position pos = { .row = row, .col = col };
            const int c = COORD(cur[col]);
            const int u = COORD(prev[col]);

            // extra handling for first column
            S[c][u].push_back({ .pos = pos, .dir = UP });
            S[u][c].push_back({ .pos = SUM_POS(pos, UP), .dir = DOWN });
            if (!col) { continue; }

            const int l = COORD(cur[col - 1]);
            S[c][l].push_back({ .pos = pos, .dir = LEFT });
            S[l][c].push_back({ .pos = SUM_POS(pos, LEFT), .dir = RIGHT });
        }
        prev = cur;
    }
    assert(verify_state_machine());
}

// ------
// Search
// ------

// try to find a word in the scramble grid using `S` and `M`
bool find_word(const std::string &word) {
    // these static variables contain the state where we left off the last time
    // this procedure was called
    static std::string prev_word;
    static std::vector<context> prev_stack;
    static std::vector<match> prev_matches;

    const int wlen = word.size();
    const int prev_wlen = prev_word.size();

    std::vector<context> stack;
    std::vector<match> matches;

    if(prev_wlen && prev_wlen < wlen &&
            std::equal(prev_word.begin(), prev_word.end(), word.begin())) {
        // the previous word was a prefix of the current one
        if(!prev_stack.size()) {
            // if the prefix is not in the scramble than the current word won't
            // be either
            return false;
        } else {
            // continue where we left off
            stack = prev_stack;
            matches = prev_matches;
        }
    } else {
        // initialise matches
        matches = S[COORD(word[0])][COORD(word[1])];
    }

    stack.reserve(wlen-1);

    // loop through all matches for the first two letters
    while (matches.size()) {
        const match m = matches.back();
        matches.pop_back();

        const position start = m.pos;
        if (!stack.size()) {
            // skip if stack was initialised to prev_stack
            stack.push_back({ .dir = m.dir, .end = SUM_POS(m.pos, m.dir), .next = UP_C });
        }

        // do a depth-first search on the stack
        while (stack.size()) {
            const int i = stack.size() + 1;

            if (i == wlen) {
                // found a path!
                assert(verify_stack(start, stack, word));
                std::cout << word << "\t"
                    << start.row << "\t"
                    << start.col << "\t"
                    << stack_to_string(stack) << std::endl;

                // save the state for next time
                prev_word = word;
                prev_stack = stack;
                prev_matches = matches;
                prev_matches.push_back(m);

                return true;
            }

            const context ctx = stack.back();
            const int r = ctx.end.row;
            const int c = ctx.end.col;
            const char l = word[i];

            // consider possible next moves, starting from where we left off
            // note that all the case statements fall through: we only break
            // out when a match has been found
            switch(ctx.next) {
                case UP_C:
                    // peek at character above current position
                    if (r && GRID(r-1, c) == l && !has_cycle(stack, UP)) {
                        stack.back().next = DOWN_C;
                        stack.push_back({
                                .dir = UP,
                                .end = SUM_POS(ctx.end, UP),
                                .next = UP_C });
                        break;
                    }

                case DOWN_C:
                    // peek at character below current position
                    if (r < scramble_len-1 && GRID(r+1, c) == l && !has_cycle(stack, DOWN)) {
                        stack.back().next = LEFT_C;
                        stack.push_back({
                                .dir = DOWN,
                                .end = SUM_POS(ctx.end, DOWN),
                                .next = UP_C });
                        break;
                    }

                case LEFT_C:
                    // peek at character left of the current position
                    if (c && GRID(r, c-1) == l && !has_cycle(stack, LEFT)) {
                        stack.back().next = RIGHT_C;
                        stack.push_back({
                                .dir = LEFT,
                                .end = SUM_POS(ctx.end, LEFT),
                                .next = UP_C });
                        break;
                    }

                case RIGHT_C:
                    // peek at character right of the current position
                    if (c < scramble_len-1 && GRID(r, c+1) == l && !has_cycle(stack, RIGHT)) {
                        stack.back().next = DONE_C;
                        stack.push_back({
                                .dir = RIGHT,
                                .end = SUM_POS(ctx.end, RIGHT),
                                .next = UP_C });
                        break;
                    }

                default:
                    // no match found: backtrack
                    stack.pop_back();
            }
        }
    }

    // don't care about prev_matches if search failed
    prev_word = word;
    prev_stack = stack;
    return false;
}

// try to find all the words in the given file
void find_words(const char *dict_fname) {
    std::string word;
    std::ifstream dict(dict_fname);

    // skip first line containing the size of the dictionary
    std::getline(dict, word);

    // loop over dictionary
    while (std::getline(dict, word)) { find_word(word); }
}

// --------------
// Running it all
// --------------

int main(const int argc, const char **argv) {
    // expect two command line arguments: the name of the scramble file and the
    // name of the dictionary file
    if (argc != 3) { return 1; }
    build_state_machine(argv[1]);
    find_words(argv[2]);
    return 0;
}