Fridge Magnet Crossword
At some point in grad school I took it upon myself to rearrange the fridge magnets into a crossword. It took a long time to come up with a solution. So, for fun, I automated the procedure using C++.
/// AlphabetSoup.cpp
/// Shaun Harker
/// 2016-05-10
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include "Word.h"
#include "Crossword.h"
/// Filter Wordlist
/// Return new wordlist where all unplayable words have been filtered out
WordList
filter_out_unplayable ( Crossword const& crossword, WordList const& wordlist ) {
WordList new_wordlist;
for ( Word const& word : wordlist ) {
Crossword::Status status = crossword . playable ( word );
if ( status != Crossword::Status::never ) new_wordlist . insert ( word );
}
return new_wordlist;
}
/// Recursive Algorithm
void
recursive ( Crossword const& crossword, WordList const& wordlist, std::vector<std::string> history ) {
static uint64_t searched_crosswords = 0;
++ searched_crosswords;
//crossword . draw ();
// Check if solved
if ( crossword . solved () ) {
if ( crossword . direction () == Crossword::Direction::horizontal ) {
std::cout << "(H) ";
} else {
std::cout << "(V) ";
}
for ( auto const& word : history ) std::cout << word << " ";
std::cout << "\n";
return;
}
// Filter out unplayable words
WordList new_wordlist = filter_out_unplayable ( crossword, wordlist );
// If words remaining are shy some required letter, prune
std::set<char> playable;
for ( std::string const& word : new_wordlist ) for ( char c : word ) playable . insert ( c );
for ( char c = 'a'; c <= 'z'; ++ c ) {
if ( crossword . played ( c ) ) continue;
if ( playable . count ( c ) > 0 ) continue;
//std::cout << "Backtracking because it is impossible to get " << c << ".\n";
return;
}
// Recurse on all currently playable words
WordList recurse_wordlist = new_wordlist;
history . push_back ( std::string () );
for ( Word const& word : new_wordlist ) {
if ( crossword . playable ( word ) == Crossword::Status::future ) continue;
Crossword new_crossword = crossword . play ( word );
history . back () = word;
recurse_wordlist . erase ( word );
recursive ( new_crossword, recurse_wordlist, history );
}
}
/// SearchForCrosswords
void
SearchForCrosswords ( WordList const& wordlist ) {
WordList recurse_wordlist = wordlist;
for ( Word const& word : wordlist ) {
recurse_wordlist . erase ( word );
Crossword horizontal ( word, Crossword::Direction::horizontal );
recursive ( horizontal, recurse_wordlist, {word} );
Crossword vertical ( word, Crossword::Direction::vertical );
recursive ( vertical, recurse_wordlist, {word} );
}
}
/// SearchForCrosswords
/// Search for crosswords with "start_word" as initial word
/// Note: assumes starting word is the lexicographical minimum
void
SearchForCrosswords ( std::string const& start_string, WordList const& wordlist ) {
Word start_word;
for ( Word const& word : wordlist ) {
if ( start_string == (std::string)word ) start_word = word;
}
if ( ((std::string)start_word).size() == 0 ) {
std::cout << "Starting word not in dictionary.\n";
abort ();
}
WordList recurse_wordlist = wordlist;
for ( Word const& word : wordlist ) {
if ( word < start_word ) recurse_wordlist . erase ( word );
}
std::cout << "Size wordlist = " << wordlist.size () << "\n";
std::cout << "Size recurse_wordlist = " << recurse_wordlist.size () << "\n";
Crossword horizontal ( start_word, Crossword::Direction::horizontal );
recursive ( horizontal, recurse_wordlist, {start_word} );
Crossword vertical ( start_word, Crossword::Direction::vertical );
recursive ( vertical, recurse_wordlist, {start_word} );
}
/// main
int main ( int argc, char * argv [] ) {
WordList wordlist = LoadWordList ();
if ( argc == 2 ) {
std::string word ( argv[1] );
SearchForCrosswords ( word, wordlist );
} else {
SearchForCrosswords ( wordlist );
}
return 0;
}
/// Crossword.h
/// Shaun Harker
/// 2016-05-11
#ifndef CROSSWORD_H
#define CROSSWORD_H
typedef std::pair<int,int> Position;
class Crossword {
public:
/// Direction
/// Type used to declare if first word is horizontal or vertical
/// "horizontal" means horizontal first word
/// "vertical" means vertical first word
enum Direction { horizontal, vertical };
/// Status
/// Type used as return type for member function "playable".
/// "never" : playable status meaning the word can never be played
/// "current" : playable status meaning the word can currently be played
/// "future" : playable status meaning the word cannot current be played,
/// but potentially can be in a future move
enum Status { never, current, future };
/// Crossword
/// Builds an initial crossword with a horizontally placed initial word
Crossword ( std::string initial_word ) {
direction_ = Direction::horizontal;
place_word_ ( initial_word, {0,0}, direction_ );
}
/// Crossword
/// Builds an initial crossword with a horizontally or vertically placed word
Crossword ( std::string initial_word, Direction direction ) {
direction_ = direction;
place_word_ ( initial_word, {0,0}, direction_ );
}
/// direction
/// Return direction of starting word
Direction
direction ( void ) const {
return direction_;
}
/// character
/// Given a position give the character on board
char
character ( Position const& pos ) const {
return char_by_position_ . find ( pos ) -> second;
}
/// position
/// Given a character give the position on board
Position
position ( char c ) const {
return position_by_char_ . find ( c ) -> second;
}
/// played
/// Check if a character has been played
bool
played ( char c ) const {
return position_by_char_ . find ( c ) != position_by_char_ . end ();
}
/// played
/// Check if a position has been played
bool
played ( Position const& pos ) const {
return char_by_position_ . find ( pos ) != char_by_position_ . end ();
}
/// playable
/// Given a word, return
/// "never" if it will never be playable,
/// "current" if it is currently playable,
/// "future" if it is not currently playable but perhaps could
/// be at a later move
Status
playable ( std::string const& word, Crossword * crossword = NULL ) const {
int L = word . size ();
int already_played = 0;
std::set<Position> horizontal_positions;
std::set<Position> vertical_positions;
for ( int i = 0; i < L; ++ i ) {
char c = word[i];
if ( played ( c ) ) {
++ already_played;
Position p = position ( c );
horizontal_positions . insert ( {p.first-i, p.second} );
vertical_positions . insert ( {p.first, p.second-i} );
}
}
if ( already_played == L ) return Status::never;
if ( already_played == 0 ) return Status::future;
// Check horizontal place possibility
if ( horizontal_positions . size () == 1 ) {
// Possible horizontal placement
bool possible = true;
Position p = *horizontal_positions.begin();
// Require blank spots before and after word
if ( played ( {p.first-1, p.second} ) ) possible = false;
if ( played ( {p.first+L, p.second} ) ) possible = false;
// Require played spots to be isolated along line
// Require played spots match word characters
// Require blank spots above and below new tiles being placed
for ( int i = 0; i < L; ++ i ) {
Position q = {p.first+i, p.second};
if ( played ( q ) && played ( {q.first+1,q.second} ) ) {
possible = false;
break;
}
if ( played ( q ) && character ( q ) != word[i] ) {
possible = false;
break;
}
if ( not played ( q ) && ( played ( {p.first+i, p.second-1}) || played ( {p.first+i, p.second+1}) ) ) {
possible = false;
break;
}
}
if ( possible ) {
if ( crossword != NULL ) crossword -> place_word_ ( word, p, Direction::horizontal );
return Status::current;
}
}
// Check vertical place possibility
if ( vertical_positions . size () == 1 ) {
// Possible vertical placement
bool possible = true;
Position p = *vertical_positions.begin();
// Require blank spots before and after word
if ( played ( {p.first, p.second-1} ) ) possible = false;
if ( played ( {p.first, p.second+L} ) ) possible = false;
// Require played spots to be isolated along line
// Require played spots match word characters
// Require blank spots above and below new tiles being placed
for ( int i = 0; i < L; ++ i ) {
Position q = {p.first, p.second+i};
if ( played ( q ) && played ( {q.first,q.second+1} ) ) {
possible = false;
break;
}
if ( played ( q ) && character ( q ) != word[i] ) {
possible = false;
break;
}
if ( not played ( q ) && ( played ( {p.first-1, p.second+i}) || played ( {p.first+1, p.second+i}) ) ) {
possible = false;
break;
}
}
if ( possible ) {
if ( crossword != NULL ) crossword -> place_word_ ( word, p, Direction::vertical );
return Status::current;
}
}
return Status::never;
}
/// play
/// Produce a new crossword where the input word has been played
/// Note: if word is not playable, undefined behavior
Crossword
play ( std::string const& word ) const {
Crossword new_crossword = *this;
playable ( word, &new_crossword );
return new_crossword;
}
/// solved
/// Check if all letters have been played
bool
solved ( void ) const {
if ( position_by_char_ . size () == 26 ) return true;
return false;
}
/// draw
void
draw ( void ) const {
int lower_y=26, lower_x=26, upper_y=-26, upper_x=-26;
for ( auto const& pair : position_by_char_ ) {
lower_x = std::min(lower_x, pair.second.first);
lower_y = std::min(lower_y, pair.second.second);
upper_x = std::max(upper_x, pair.second.first);
upper_y = std::max(upper_y, pair.second.second);
}
for ( int i = lower_x; i <= upper_x; ++ i ) {
std::cout << "##";
}
std::cout << "###\n";
for ( int j = lower_y; j <= upper_y; ++ j ) {
std::cout << "# ";
for ( int i = lower_x; i <= upper_x; ++ i ) {
Position p = {i,j};
if ( played ( p ) ) {
std::cout << char_by_position_ . find(p) -> second << " ";
} else {
std::cout << " ";
}
}
std::cout << "#\n";
}
for ( int i = lower_x; i <= upper_x; ++ i ) {
std::cout << "##";
}
std::cout << "###\n";
}
private:
/// place_word_
/// Place a word at given position and direction
/// note: Assumes placement results in a valid crossword
void
place_word_ ( std::string const& word, Position p, Direction direction ) {
//draw ();
//std::cout << word << "\n";
//std::cout << p.first << " , " << p.second << "\n";
int L = word . size ();
if ( direction == Direction::horizontal ) {
// Horizontal
for ( int i = 0; i < L; ++ i, p = {p.first+1,p.second} ) {
char c = word[i];
if ( played ( c ) && position ( c ) != p ) {
std::cout << "Placement error! (A)\n";
abort();
}
if ( played ( p ) && character ( p ) != c ) {
std::cout << "Placement error! (B)\n";
abort();
}
position_by_char_ [ c ] = p;
char_by_position_ [ p ] = c;
}
} else {
// Vertical
for ( int i = 0; i < L; ++ i, p = {p.first,p.second+1} ) {
char c = word[i];
if ( played ( c ) && position ( c ) != p ) {
std::cout << "Placement error! (C)\n";
abort();
}
if ( played ( p ) && character ( p ) != c ) {
std::cout << "Placement error! (D)\n";
abort();
}
position_by_char_ [ c ] = p;
char_by_position_ [ p ] = c;
}
}
}
Direction direction_;
std::map<Position,char> char_by_position_;
std::map<char,Position> position_by_char_;
};
#endif
/// Word.h
/// Shaun Harker
/// 2016-05-11
#ifndef WORD_H
#define WORD_H
#include <algorithm>
#include <functional>
#include <memory>
typedef std::shared_ptr<std::function<bool(char,char)>> CharComparator;
/// class Word
/// Stores word, along with shuffled version used to define a comparison.
class Word {
public:
/// Word
Word (void) {}
/// Word
Word ( std::string const& word, CharComparator compare ) : word_(word), compare_(compare) {}
/// operator <
bool
operator < ( Word const& rhs ) const {
std::string lhs_sorted = word_;
std::string rhs_sorted = rhs . word_;
std::sort(lhs_sorted.begin(),lhs_sorted.end(),*compare_);
std::sort(rhs_sorted.begin(),rhs_sorted.end(),*compare_);
if ( lhs_sorted == rhs_sorted ) return word_ < rhs.word_;
return std::lexicographical_compare(lhs_sorted.begin(),lhs_sorted.end(),
rhs_sorted.begin(),rhs_sorted.end(),
*compare_);
}
/// operator std::string
/// Allows to be casted as string
operator std::string () const {
return word_;
}
private:
std::string word_;
CharComparator compare_;
};
typedef std::set<Word> WordList;
/// LoadWordList
/// Obtain initial dictionary of words
inline WordList
LoadWordList ( void ) {
std::vector<std::string> goodwords;
std::ifstream infile ( "./data/words.txt" );
std::string line;
// Read all lines of file and keep "good" words.
// A word is "good" unless it is:
// (a) a 1-letter word
// (b) a word not consisting entirely of a-z
// (c) a word with repeated letters
while ( std::getline(infile, line) ) {
std::set<char> letters;
bool good = true;
if ( line . size () == 1 ) good = false; // (a)
for ( char c : line ) {
if ( c < 'a' || c > 'z' ) good = false; // (b)
if ( letters . count ( c ) ) good = false; // (c)
letters . insert ( c );
}
if ( good ) goodwords . push_back ( line );
}
// Sort characters by word frequency
std::shared_ptr<std::map<char, int>> char_frequency;
char_frequency . reset ( new std::map<char,int> );
for ( char c = 'a'; c <= 'z'; ++ c ) (*char_frequency) [ c ] = 0;
for ( std::string const& word : goodwords ) for ( char c : word ) ++ (*char_frequency) [ c ];
// Create character sorter lambda
CharComparator compare;
compare . reset ( new std::function<bool(char,char)> );
*compare = [=](char x, char y) {
if ( (*char_frequency)[x] == (*char_frequency)[y] ) return x < y;
return (*char_frequency)[x] < (*char_frequency)[y];
};
// Create wordlist
WordList wordlist;
for ( std::string const& word : goodwords ) wordlist . insert ( Word(word, compare) );
// Print wordlist
// for ( std::string const& word : wordlist ) {
// std::cout << word << "\n";
// }
return wordlist;
}
#endif
/// Flicker.cpp
/// Shaun Harker
/// 2016-05-10
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include "Crossword.h"
/// main
int main ( int argc, char * argv [] ) {
std::ifstream infile ( "solutions2.txt" );
std::string line;
while ( std::getline(infile, line) ) {
//std::cout << line << "\n";
std::stringstream ss ( line );
std::string type;
ss >> type;
Crossword::Direction direction = (type == "(H)") ? Crossword::Direction::horizontal : Crossword::Direction::vertical;
std::string word;
ss >> word;
Crossword cw ( word, direction );
//std::cout << word << "\n";
while ( 1 ) {
ss >> word;
if ( not ss . good () ) break;
//std::cout << word << "\n";
cw = cw . play ( word );
}
cw . draw ();
std::cout << "\n";
// for ( int i = -26; i < 26; ++ i ) {
// std::cout << "\x1b[A";
// }
// std::cout . flush ();
}
return 0;
}