This was a program I made for a potential job interview in
C#.
Please find the full .NET solution here: empowr_puzzle.zip
This is a simple C# application that I made to find all the words in a word search puzzle with a limited dictionary. You can download the full source code here.
Here are the examples to take a look at:
Main File
/***************************************************************************************************
* Author : Joe Churchwell (joechurchwell@gmail.com)
* Date : 2015/05/12
****************************************************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace empowr_puzzle
{
class Program
{
static void Main(string[] args)
{
// Make sure we have arguments to use as a puzzle to find words from
if (args.Length == 0)
{
Console.WriteLine("Invalid usage: No Input has been passed as an argument.");
Console.WriteLine("Input should follow the format:\n>{0} CAT XZT YOT\n",
System.AppDomain.CurrentDomain.FriendlyName);
}
// Make sure all of the input arguments are of the same size
else if (JaggedArrayDetected(args))
{
Console.WriteLine("Invalid usage: Elements must be of the same size.");
Console.WriteLine("Input should follow the format:\n>{0} CAT XZT YOT\n",
System.AppDomain.CurrentDomain.FriendlyName);
}
else // We have arguments to process so run the program
{
try{
RunProgram(args);
}catch{
Console.WriteLine("Oh No! This appears to be broken.");
}
}
// Wait for the user
Console.WriteLine("\nPress the 'Enter' key to continue");
Console.ReadLine();
}
/* Function used to determine if the input represents a
* jagged array which is not included in the implementation
*/
static bool JaggedArrayDetected(string[] args)
{
int firstSize = 0;
foreach (string element in args)
{
if (firstSize == 0)
firstSize = element.Length;
else if (firstSize != element.Length)
return true;
}
return false;
}
// Subroutine to run the programming puzzle
static void RunProgram(string[] args)
{
int retVal;
// Create a new 2-dimensional char array to pass to 'FindWords'
char[,] puzzle = new char[args.Length, args[0].Length];
char[] intermediateCharArray; // Temp array used for inner loop
// Loop through all the elements in the passed arguments array
for (int i = 0; i < args.Length; i++)
{
// Get the argument elements and set the puzzle to the char'ed elements
intermediateCharArray = args[i].ToCharArray();
for (int j = 0; j < args[i].Length; j++)
{
puzzle[i, j] = intermediateCharArray[j];
}
}
// Call 'FindWords' to solve the puzzle
retVal = PuzzleSolver.FindWords(puzzle);
// Output the solution to the console
Console.WriteLine("Words Found: {0}", retVal);
}
}
}
Puzzle Class
/**************************************************************************************************** * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 ****************************************************************************************************/using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace empowr_puzzle
{public static class PuzzleSolver
{public static string[] DICTIONARY = { "OX", "CAT", "TOY", "AT", "DOG", "CATAPULT", "T" };
static bool IsWord(string testWord)
{if (DICTIONARY.Contains(testWord))
return true;
return false;
} /*******************************************************************
* Function Name: FindWords * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Definition : * FindWords should return the number of all non-distinct * occurrences of the words found in the array, horizontally, * vertically or diagonally, and also the reverse in each direction. * * Detailed Description: * 1) FindWords has been implemented using a list (lstSearch) which * contains all potential word entries. * 2) The majority of the code finds all potential words so * as to naively perform an exhaustive search. Here is a listing * of functions created, for code readabiltiy, to find all * potential words: * GetAllHorizontal, GetAllVertical, GetAllBackslash, and * GetAllForeslash * 3) These potential words are later evaluated to determine * if they are indeed valid words, as defined by our dictionary, * and are also reversed to find the words situated in reverse * direction (GetAllValidWords). * 4) The helper function 'AddAllSubStrings' has been created to * get all of the potential sub-strings contained in one longer * string (i.e. long string = while line, column or diagonal). * * Notes: * StringBuilder was not used for this implementation but may be * considered in the future. * *******************************************************************/public static int FindWords(char[,] puzzle)
{ // Declaration for a list of all possible words
List<string> lstSearch = new List<string>();
// Declaration for a list of words found in the dictionary
List<string> lstFound = new List<string>();
// Non-diagonal search paths
GetAllHorizontal(puzzle, lstSearch); GetAllVertical(puzzle, lstSearch); /* The following code, to find diagonal words, does not
* produce singleton words since they have already been * covered in the previous verticle / horzontal functions */ GetAllBackslash(puzzle, lstSearch); GetAllForeslash(puzzle, lstSearch); /* Search through all potential words to determine if they are words
* NOTE: This could be done while performing the potential word finding * to improve performance and complexity. */ GetAllValidWords(lstSearch, lstFound); // Sort the found item list so that it will look nice for testing
lstFound.Sort(); // Finish off by returning the found list count
return lstFound.Count;
} /*******************************************************************
* Function Name: GetAllHorizontal * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * GetAllHorizontal gets all the potential words in the horizontal * puzzle orientation. *******************************************************************/private static void GetAllHorizontal(char[,] puzzle, List<string> lstSearch)
{string test;
int rows = puzzle.GetLength(0);
int cols = puzzle.GetLength(1);
// Get all the rows (horizontal)
for (int k = 0; k < cols; k++)
{// Loop to get all the sub-strings (including singletons)
for (int i = 0; i < rows; i++) // ROWS
{test = string.Empty;
for (int j = k; j < cols; j++) // COLUMNS
{ test += puzzle[i, j].ToString(); lstSearch.Add(test); } } } } /*******************************************************************
* Function Name: GetAllVertical * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * GetAllVertical gets all the potential words in the vertical * puzzle orientation. *******************************************************************/private static void GetAllVertical(char[,] puzzle, List<string> lstSearch)
{string test;
int rows = puzzle.GetLength(0);
int cols = puzzle.GetLength(1);
// Get all the columns (vertical)
for (int k = 0; k < rows - 1; k++)
{// Loop to get all the sub-strings
for (int j = 0; j < cols; j++) // COLUMNS
{test = string.Empty;
for (int i = k; i < rows; i++) // ROWS
{ test += puzzle[i, j].ToString();if (test.Length > 1) lstSearch.Add(test);
} } } } /*******************************************************************
* Function Name: GetAllBackslash * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * GetAllBackslash gets all the potential words in the backslash * CCW 45 degree direction. *******************************************************************/private static void GetAllBackslash(char[,] puzzle, List<string> lstSearch)
{string test;
int rows = puzzle.GetLength(0);
int cols = puzzle.GetLength(1);
// Upper half of the grid
for (int i = 0; i < cols; i++)
{test = string.Empty;
for (int j = 0; j < rows; j++)
{if (i + j > cols - 1) break;
test += puzzle[j, i + j];if (test.Length > 1) lstSearch.Add(test);
}// Find all combinations of the concatenated string
AddAllSubStrings(test, lstSearch); }// Lower half of the grid
// Start at i = 1 to avoid duplications
for (int i = 1; i < rows; i++)
{test = string.Empty;
for (int j = 0; j < rows; j++)
{// Ensure we do not exceed the array bounds
if (i + j > rows - 1) break;
if (j >= cols) break;
test += puzzle[i + j, j];if (test.Length > 1) lstSearch.Add(test);
}// Find all combinations of the concatenated string
AddAllSubStrings(test, lstSearch); } }// END /*** \\\ Parse diagonal backslash \\\ ***/
/*******************************************************************
* Function Name: GetAllForeslash * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * GetAllForeslash gets all the potential words in the forward slash * CW 45 degree direction. *******************************************************************/private static void GetAllForeslash(char[,] puzzle, List<string> lstSearch)
{string test;
int rows = puzzle.GetLength(0);
int cols = puzzle.GetLength(1);
// Upper half of the grid
for (int i = cols - 1; i >= 0; i--)
{test = string.Empty;
for (int j = 0; j < rows; j++)
{// Ensure we do not exceed the array bounds
if (i - j < 0) break;
test += puzzle[j, i - j].ToString();if (test.Length > 1) lstSearch.Add(test);
}// Find all combinations of the concatenated string
AddAllSubStrings(test, lstSearch); }// Lower half of the grid
for (int i = 1; i < rows; i++)
{test = string.Empty;
for (int j = cols - 1; j >= 0; j--)
{// Ensure we do not exceed the array bounds
if (i + cols - 1 - j >= rows) break;
test += puzzle[i + cols - 1 - j, j].ToString();
if (test.Length > 1) lstSearch.Add(test);
}// Find all combinations of the concatenated string
AddAllSubStrings(test, lstSearch); } }// END /*** /// Foreslash diagonal /// ***/
/*******************************************************************
* Function Name: GetAllValidWords * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * GetAllValidWords will return the parameter lstFound with the * contents of all valid words found from the potential search list *******************************************************************/private static void GetAllValidWords(List<string> lstSearch, List<string> lstFound)
{string test;
foreach (string element in lstSearch)
{// Check to see if the element is a word and add it to the found list
if (IsWord(element)) lstFound.Add(element);
// Also check the reverse case... but only if larger than 1 char
if (element.Length > 1)
{// Reverse the string to test to perform the reversal word check
test = new string(element.ToCharArray().Reverse().ToArray());
// Check to see if the reversed element is a word
if (IsWord(test)) lstFound.Add(test);
} } } /*******************************************************************
* Function Name: AddAllSubStrings * Author : Joe Churchwell (joechurchwell@gmail.com) * Date : 2015/05/12 * Detailed Description: * AddAllSubStrings is a support function used to add all contiguous * sub-strings contained in 'test' into 'lstSearch' *******************************************************************/private static void AddAllSubStrings(string test, List<string> lstSearch)
{// Get all combinations of sub-strings in 'test'
for (int k = 1; k < test.Length - 1; k++) // Second char to second to last char
{// Loop for length of string to change while there are chars left
for (int j = 2; j < (test.Length - k + 1); j++)
{ lstSearch.Add(test.Substring(k, j)); } } } } }