In this article, I’d like to share how to build an application to visualize the solution to a word search problem. It uses a process like backtracking. Feel free to follow along, but I will provide the GitHub repo at the end. Here’s an example of how our app will work.
Prerequisites
To build this React app, I would expect you to have the following:
Setting up
To set up our application, we are going to use Create React App and TypeScript:
npx create-react-app wordsearch-solver --template typescript
Setting types
We can use some types to define the structure of the data we'll be working with. Create a new file named types.ts in the src folder and add the following code:
export interface IWordsearch {
grid: string[][]; // 2d array containing letters
words: string[]; // The words to be found
width: number; // Number of columns in the grid
height: number; // Number of rows in the grid
}
// [row, column]
export type GridCell = [number, number];
// Array containing adjacent grid locations
export type WordMatch = GridCell[];
Implementing the algorithm
Here we can write the 100 lines of code which will be the main part of the project. Create a new wordsearch.ts file in the src folder. This will contain the code for representing a word search puzzle, using a class. Start by importing the types defined earlier.
import { WordMatch, IWordsearch, GridCell } from "./types";
We'll also need to define a helper to case-insensitively compare two strings. This will be useful for matching the letters in the puzzle.
const compareStrings = (string1: string, string2: string) =>
string1.toLowerCase() === string2.toLowerCase();
Now begin to implement the class, and define its constructor:
export class Wordsearch implements IWordsearch {
constructor(
public grid: string[][],
public words: string[],
public width: number,
public height: number
) {}
...
}
Define the solve method our main view will run when the user clicks a button. It should return an array of the location of each word we have inputted.
solve() {
let matches: WordMatch[] = [];
for (let word of this.words) {
matches.push(this.findWord(word));
}
return matches;
}
Now we can get on to how the findWord method will work, so here is an explanation of the process.
Find every occurrence of the word's first letter in the grid
Loop through each first letter location
Loop through every possible direction the word can be in
Look through every adjacent grid cell in that direction, keeping track of the number of locations seen
Check whether the letter at that cell is the same as the letter in the word at the same position (e.g. if the letter at the 2nd cell seen is the same as the 2nd letter of the word)
If this is the case, store the cell in an array containing the locations of each matching letter found, which would start with the location of the first letter
Otherwise, move on to a new direction
If the number of cell locations in our array is the same as the number of letters in the word, then we have found all the matching letters for the word, and we can return our array
If we manage to reach the end of the loop of first letter locations, then the word has not been found, and an error is thrown
Start by defining the findLetter method. It will make use of the compareStrings method from earlier.
findLetter(letter: string) {
let output: GridCell[] = [];
for (let i = 0; i < this.height; i++) {
for (let j = 0; j < this.width; j++) {
if (compareStrings(this.grid[i][j], letter)) {
output.push([i, j]);
}
}
}
return output;
}
Then, define a method named getNeighbourCell. We will give it a grid location and a direction. Then it will return either an adjacent cell in the given direction or nothing if that location is out of bounds.
getNeighbourCell(cell: GridCell, dir: number): GridCell | undefined {
const offset = DIRECTION_MAPPINGS[dir];
let i = cell[0] + offset[0];
let j = cell[1] + offset[1];
// If the new location is within the bounds of the grid
if (i >= 0 && i < this.height && j >= 0 && j < this.width) {
return [i, j];
}
}
But where does this DIRECTION_MAPPINGS array come from? Well, it contains offsets in the X and Y axes that correspond to a direction from 0 - 7. We will include it near the top of the file, right above our compareStrings function.
const DIRECTION_MAPPINGS = [
[-1, 0],
[-1, 1],
[0, 1],
[1, 1],
[1, 0],
[1, -1],
[0, -1],
[-1, -1]
];
So what would this mean?
At direction 0, the offset is at position 0 in the array, which is
[-1, 0]The offset decreases the row number by 1, and the column number stays the same
Since the position at row 0 column 0 corresponds to the top left of the grid, the offset would move a cell up 1 row only
so direction 0 means "up"
And for direction 1, the offset [-1, 1] would move a cell up 1 row and right 1 column. This means direction 1 translates to diagonally up and right.
Finally, define the findWord method which takes a word as input. It will return an array of adjacent grid locations that match with the word or throw an error if it's not found.
findWord(word: string) {
let startPositions = this.findLetter(word[0]);
let path: GridCell[] = [];
for (let startPosition of startPositions) {
for (let dir = 0; dir < 8; dir++) {
path = [startPosition];
// Since letter 0's position is already known
let letterIndex = 1;
let currentCell = startPosition;
while (letterIndex < word.length) {
// Gets the next cell in the current direction
let newCell = this.getNeighbourCell(currentCell, dir);
// Checks if the next cell corresponds to the next letter
if (
newCell &&
compareStrings(this.grid[newCell[0]][newCell[1]], word[letterIndex])
) {
currentCell = newCell;
path.push(currentCell);
} else {
break;
}
letterIndex++;
}
// If the while loop had reached its end
if (letterIndex >= word.length) return path;
// Can also be if (path.length === word.length)
}
}
throw new Error("Puzzle has no solution");
}
Coding helper functions
We will display our grid with a <canvas> element. Also, we need to define functions to execute drawing operations on the canvas.
Start by creating a file named util.ts. Then, import the types we need. This includes our Wordsearch class for creating an object from file data
import { GridCell, WordMatch } from "./types";
import { Wordsearch } from "./wordsearch";
Define two constants LETTER_PADDING and LETTER_MARGIN. These will decide how far apart we draw each letter on the canvas.
const LETTER_PADDING = 0.5;
const LETTER_MARGIN = 50;
Now define a function called parseFile which will take a File object as input. It then returns a Promise which will resolve with a new configured Wordsearch object. The structure of the text file should be like the following:
joptvision
agxrocuhed
television
lmeasurens
erusuallyy
ileusualti
sasrkfvuzm
upleasurei
rvoccasion
edivisionw
///
pleasure
vision
usually
lua
measure
casio
The text above the /// contains the grid of letters, with no spaces. Below the delimiter is the list of words which need to find (1 word per line).
Add the code below:
export const parseFile = (file: File): Promise<Wordsearch> => {
const reader = new FileReader();
return new Promise((resolve, reject) => {
reader.addEventListener("load", () => {
let result = reader.result as string;
let lines = result.trim().split("\n");
let grid: string[][] = [];
let words: string[] = [];
let pastDelimiter = false;
for (let i = 0; i < lines.length; i++) {
let line = lines[i].trim();
if (line === "///") {
pastDelimiter = true;
continue;
}
if (pastDelimiter) {
words.push(line);
} else {
// Splits up the string of letters into an array
grid.push(line.split(""));
// If the length of the last line is not
// the same as the length of this line
if (grid[i - 1] && grid[i].length !== grid[i - 1].length) {
throw new Error("Invalid grid");
}
}
}
if (words.length === 0) {
throw new Error("No words provided");
}
// We now know that each row has the same length
let width = grid[0].length;
let height = grid.length;
let puzzle = new Wordsearch(grid, words, width, height);
resolve(puzzle);
console.log(puzzle);
});
reader.readAsText(file);
});
};
We wrap the event handler with a Promise to call await on this function. This is so we can wait for the function to return the object, for storing in React state.
Now define a simple utility function toCanvasCoords . It takes a grid location as input and returns a pixel location. We will use this to draw on the canvas, along with our spacing constants.
const toCanvasCoords = (position: GridCell) => {
return [
(position[0] + LETTER_PADDING) * LETTER_MARGIN,
(position[1] + LETTER_PADDING) * LETTER_MARGIN
];
};
We can now define two more functions. One we'll name resizeCanvas which we will use each time we load a new word search file. This is to scale the canvas element to the amount of space the grid will take up. The other - clearGrid - will set the canvas width and height to 0, makes the canvas element appear hidden. We also need to export clearGrid as we will make a button that calls this function within another file.
const resizeCanvas = (
canvas: HTMLCanvasElement,
width: number,
height: number
) => {
let [canvasWidth, canvasHeight] = toCanvasCoords([width, height]);
canvas.width = canvasWidth;
canvas.height = canvasHeight;
};
export const clearGrid = (canvas: HTMLCanvasElement) => {
const ctx = canvas.getContext("2d");
if (!ctx) return;
canvas.width = 0;
canvas.height = 0;
};
Then, define a function named drawGrid. It will take a canvas element and Wordsearch object as input. Then it will draw every letter in the puzzle's grid onto the canvas.
export const drawGrid = (canvas: HTMLCanvasElement, puzzle: Wordsearch) => {
const ctx = canvas.getContext("2d");
if (!ctx) return;
// Also clears the grid
resizeCanvas(canvas, puzzle.width, puzzle.height);
// Set up font attributes
ctx.font = "30px monospace";
ctx.textBaseline = "middle";
ctx.textAlign = "center";
for (let i = 0; i < puzzle.height; i++) {
let row = puzzle.grid[i];
for (let j = 0; j < puzzle.width; j++) {
// Remember [row, column]?
const [x, y] = toCanvasCoords([j, i]);
ctx.fillText(row[j], x, y);
}
}
};
Now let's complete the file with drawMatch. It will take a canvas element and a WordMatch as input. Then it will draw a line from the first grid location in the match to the last.
export const drawMatch = (canvas: HTMLCanvasElement, match: WordMatch) => {
const ctx = canvas.getContext("2d");
if (!ctx) return;
let startPosition = toCanvasCoords(match[0]);
let endPosition = toCanvasCoords(match[match.length - 1]);
// To show up behind the grid
ctx.globalCompositeOperation = "destination-over";
// Red with 40% opacity
ctx.strokeStyle = "rgba(255, 0, 0, 0.4)";
ctx.lineCap = "round";
ctx.lineWidth = 30;
ctx.beginPath();
// Position is in the format [row (y), column (x)]
// , but we need the x component, and then the y
ctx.moveTo(startPosition[1], startPosition[0]);
ctx.lineTo(endPosition[1], endPosition[0]);
ctx.stroke();
};
Creating the App component
Open up the src/App.tsx file and replace its contents with the following code. This imports our utility functions and the Wordsearch class.
But first, delete the following files within the src folder:
logo.svg
setupTests.ts
App.test.tsx
import React, { useEffect, useRef, useState } from "react";
import uploadIcon from "./icons/upload.svg";
import { clearGrid, drawGrid, drawMatch, parseFile } from "./util";
import { Wordsearch } from "./wordsearch";
import "./App.css";
export default function App() {
...
}
Declare two ref objects which we will use to interact with the HTML elements in our component code.
const canvas = useRef<HTMLCanvasElement>(null);
const fileInput = useRef<HTMLInputElement>(null);
Now declare a state named puzzle which will store the current word search puzzle object.
const [puzzle, setPuzzle] = useState<Wordsearch>();
We will now need to define event handlers for the HTML elements in our component. The first will be openFileInput, triggered by a button click to open a file dialog.
const openFileInput = () => {
fileInput.current?.click();
};
And once a user selects their word search file, we will need to pass it into the parseFile. This will then return an instance of Wordsearch which we will store in the state.
const onFileChange = async () => {
var file = fileInput.current?.files?.[0];
if (!file) return;
let wordsearch = await parseFile(file);
setPuzzle(wordsearch);
};
Define a function which calls solve on the puzzle object. It then draws any matches found onto the canvas.
const solvePuzzle = () => {
if (!(canvas.current && puzzle)) return;
const matches = puzzle.solve();
for (let match of matches) {
if (match.length > 0) {
drawMatch(canvas.current, match);
}
}
};
Now define a function which clears the state variable and clears the grid from the canvas. It will then remove any files stored in the file input element.
const clearPuzzle = () => {
if (!(canvas.current && puzzle)) return;
setPuzzle(undefined);
clearGrid(canvas.current);
if (fileInput.current) {
fileInput.current.value = "";
}
};
When our puzzle object changes, we will need to reflect that change by re-drawing the grid object. We can do that with useEffect:
useEffect(() => {
if (!(canvas.current && puzzle)) return;
drawGrid(canvas.current, puzzle);
}, [puzzle]);
Here we can start to create the JSX code for the main display. There will be an icon button (you can download it here) which calls openFileInput to get the file from the user. There is also a hidden file input element which makes the dialog only accept text files.
Then we need one button to solve the puzzle, and another to clear the grid if necessary. The "solve" button will call solvePuzzle to solve the puzzle and draw the solution. Then the "clear" button will call clearPuzzle to clear the canvas.
And of course, we will need a canvas element with our ref object attached.
And return the following:
<div className="App">
<header className="App-header">Wordsearch Solver</header>
<input
type="file"
accept="text/plain"
ref={fileInput}
onChange={onFileChange}
style={{ display: "none" }}
/>
<button type="button" onClick={openFileInput} className="App-fileInput">
<img src={uploadIcon} alt="Upload a file" className="App-icon" />
</button>
<div className="App-buttons">
{puzzle && (
<>
<button type="button" onClick={solvePuzzle}>
Solve
</button>
<button type="button" onClick={clearPuzzle}>
Clear
</button>
</>
)}
</div>
<canvas ref={canvas} />
</div>
Wrapping up
I've added some example puzzle files to the GitHub repository which you can use to try out the live demo below.
And you can find the source code on the repository here.
If you have any questions, feel free to ask in the comments, and if you found this article helpful, stay tuned for more.