solver Namespace Reference

Classes to solve a wordsearch. More...

Classes
class	SolverDictWrapper
	A type erased wrapper around a particular solver dictionary implementation. More...
class	SolverDictFactory
	This class can be used to check if a particular dictionary solver implementation exists, and create an instance of one with a particular dictionary. More...

Typedefs
using	Index = matrix2d::Index
	2 element coordinate
using	Tail = std::vector< Index >
using	ListOfListsOfIndexes = std::vector< Tail >
using	WordToListOfListsOfIndexes = std::unordered_map< std::string, ListOfListsOfIndexes >
using	WordsearchGrid = matrix2d::Matrix2d< char >
template<class T , std::size_t N>
using	static_vector = boost::container::static_vector< T, N >

Functions
template<class SolverDict >
void	solve_index (const SolverDict &solver_dict, const WordsearchGrid &grid, const Index start_index, WordToListOfListsOfIndexes &word_to_list_of_indexes)
	Find all possible words using solver_dict that may start at start_index in grid, and write them out to word_to_list_of_indexes. More...
template<class SolverDict >
WordToListOfListsOfIndexes	solve (const SolverDict &solver_dict, const WordsearchGrid &grid)
	Runs solve_index() on every element of grid to solve the whole wordsearch. More...
WordsearchGrid	make_grid (const std::vector< std::string > &lines)
	Helper function to construct a WordsearchGrid

Detailed Description

Classes to solve a wordsearch.

See example usage as in example/example.cpp

#include "wordsearch_solver/wordsearch_solver.hpp"
 
#include <fmt/core.h>
#include <fmt/format.h>
#include <fmt/ranges.h>
 
#include <initializer_list>
#include <string>
#include <string_view>
#include <vector>
 
int main() {
  // Define a wordsearch
  // clang-format off
  const std::vector<std::string> wordsearch = {
    "adg",
    "beh",
    "cfi",
  };
  // clang-format on
 
  // Define a container of string-like objects that is the dictionary
  const std::initializer_list<std::string_view> dictionary = {"zoo", "badge",
                                                              "be", "beg"};
  // const auto dictionary = utility::read_file_as_lines("path/to/dict");
 
  const auto solver = solver::SolverDictFactory{}.make("trie", dictionary);
  const auto grid = solver::make_grid(wordsearch);
 
  // Solve the wordsearch
  const solver::WordToListOfListsOfIndexes answer = solver::solve(solver, grid);
 
  for (const auto& [word, indexes] : answer) {
    fmt::print("{}: {}\n", word, indexes);
  }
  // [0, 0] is top left, 'a'. [1, 0] is 'b'. [2, 1] is 'f'.
  // Prints:
  // beg: {{[1, 0], [1, 1], [0, 2]}}
  // be: {{[1, 0], [1, 1]}}
  // badge: {{[1, 0], [0, 0], [0, 1], [0, 2], [1, 1]}}
}

Function Documentation

solve()

template<class SolverDict >

WordToListOfListsOfIndexes solver::solve	(	const SolverDict &	solver_dict,
		const WordsearchGrid &	grid
	)

Runs solve_index() on every element of grid to solve the whole wordsearch.

Parameters

[in]	solver_dict	The solver dictionary implementation to use, for example SolverDictWrapper
[in]	grid	The wordsearch matrix/grid to solve

Returns

The map from words to lists of indexes that results are written out to

solve_index()

template<class SolverDict >

void solver::solve_index	(	const SolverDict &	solver_dict,
		const WordsearchGrid &	grid,
		const Index	start_index,
		WordToListOfListsOfIndexes &	word_to_list_of_indexes
	)

Find all possible words using solver_dict that may start at start_index in grid, and write them out to word_to_list_of_indexes.

Parameters

[in]	solver_dict	The solver dictionary implementation to use, for example SolverDictWrapper
[in]	grid	The wordsearch matrix/grid to solve
[in]	start_index	The start/first letter of the word to solve
[out]	word_to_list_of_indexes	The map from words to lists of indexes that results are written out to