Skip to content

Instantly share code, notes, and snippets.

@C0deH4cker
Created February 11, 2015 21:18
Show Gist options
  • Save C0deH4cker/9ffd311a1a5e060fd81f to your computer and use it in GitHub Desktop.
Save C0deH4cker/9ffd311a1a5e060fd81f to your computer and use it in GitHub Desktop.
Determine all possible valid words that can be formed by shifting a valid word by one on a keyboard
//
// wordshift.cpp
// WordShift
//
// Created by C0deH4cker on 2/11/15.
// Copyright (c) 2015 C0deH4cker. All rights reserved.
//
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <set>
#include <cctype>
#include <algorithm>
struct KeyPos {
int r;
int c;
KeyPos(int row=0, int col=0)
: r(row), c(col) {}
};
const static std::string keyboard[3] = {
"qwertyuiop",
"asdfghjkl",
"zxcvbnm"
};
static KeyPos keypos[26];
/*
Delta arrays. For example, if the original key were an S, this
would try W, E, A, D, Z, and X.
*/
const static int dr[6] = {-1, -1, 0, 0, 1, 1};
const static int dc[6] = {0, 1, -1, 1, -1, 0};
bool validPos(KeyPos pos) {
return pos.r >= 0 && pos.r < 3 && pos.c >= 0 && pos.c < keyboard[pos.r].size();
}
std::string shiftKeys(const std::string& orig, int dr, int dc) {
std::string ret = "";
for(char c : orig) {
if(!isalpha(c)) {
return "";
}
KeyPos origPos = keypos[tolower(c) - 'a'];
KeyPos newPos(origPos.r + dr, origPos.c + dc);
if(!validPos(newPos)) {
return "";
}
ret += keyboard[newPos.r][newPos.c];
}
return ret;
}
int main(int argc, const char* argv[]) {
int minwordsize = 3;
if(argc == 2) {
if(std::all_of(argv[1], argv[1] + strlen(argv[1]), isnumber)) {
minwordsize = atoi(argv[1]);
}
else {
fprintf(stderr, "Usage: %s [min-word-size (default %d)]\n", argv[0], minwordsize);
return -1;
}
}
for(int row = 0; row < 3; row++) {
for(int col = 0; col < keyboard[row].size(); col++) {
keypos[keyboard[row][col] - 'a'] = KeyPos(row, col);
}
}
std::ifstream wordlist("/usr/share/dict/words");
std::set<std::string> dict;
while(wordlist) {
std::string word;
std::getline(wordlist, word);
if(word.size() < minwordsize) continue;
// Make sure the word is all alphabetical
if(!std::all_of(word.begin(), word.end(), isalpha)) continue;
// Convert the word to lower case
std::transform(word.begin(), word.end(), word.begin(), tolower);
dict.insert(word);
}
for(auto word : dict) {
for(int i = 0; i < 6; i++) {
std::string shifted = shiftKeys(word, dr[i], dc[i]);
if(!shifted.empty() && shifted > word && dict.find(shifted) != dict.end()) {
std::cout << "\"" << word << "\" shifted";
if(dr[i] < 0) {
std::cout << " up";
}
else if(dr[i] > 0) {
std::cout << " down";
}
if(dr[i] && dc[i]) {
std::cout << "-";
}
else {
std::cout << " ";
}
if(dc[i] < 0) {
std::cout << "left";
}
else if(dc[i] > 0) {
std::cout << "right";
}
std::cout << " is \"" << shifted << "\"" << std::endl;
}
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment