Generating A Word Search Puzzle Grid In Angular 9.1.4
Over the weekend, I felt like coding a little palette-cleanser - something that would take my mind in a different direction. I also don't want my Angular skills getting too rusty, what with the fact that I've been so focused on Lucee CFML lately. As such, I wanted to try writing a Word Search Puzzle generator in Angular 9.1.4.
Run this demo in my JavaScript Demos project on GitHub.
View this code in my JavaScript Demos project on GitHub.
A Word Search Puzzle is composed of a grid of letters in which connected strings of letters, in different directions, form words from a given list. The goal of the puzzle is to locate and highlight those words. For this Angular demo, I'm not providing any interactivity with the letter-grid itself (perhaps that can be a follow-up demo). Instead, this Angular application just takes a list of words and attempts to pack as many of them as it can into a letter-grid of the desired dimensions.
This is an Angular demo; but, it doesn't actually contain much Angular code. The bulk of the logic is codified within my WordPacker class, which is the class that populates the letter-grid that the Angular application eventually renders.
RANT: It's demos like this that showcase how ridiculous it is when inexperienced programmers try to claim that their framework of choice (ex, React) somehow forces them to learn "more JavaScript" than other frameworks. As you will see below, this demo is mostly JavaScript - the "Angular" part of this Angular application just provides the rendering logic and some small degree of interactions.
Before we look at what the WordPacker class is doing, let's just get the Angular code out of the way. The Angular code provides a textarea element for a list of words (which is pre-populated for the demo). And then, instantiates the WordPacker class, populates it, and renders the resultant letter-grid.
Here's the App component - the generateSearch() method is invoked by the user when they've populated the textarea with a list of words:
// Import the core angular services.
import { Component } from "@angular/core";
// Import the application components and services.
import { LetterGrid } from "./word-packer";
import { WordPacker } from "./word-packer";
// ----------------------------------------------------------------------------------- //
// ----------------------------------------------------------------------------------- //
@Component({
selector: "app-root",
styleUrls: [ "./app.component.less" ],
templateUrl: "./app.component.html"
})
export class AppComponent {
public letterGrid: LetterGrid | null;
public inputWords: string;
// I initialize the app component.
constructor() {
this.letterGrid = null;
this.inputWords = this.getInitialInput();
}
// ---
// PUBLIC METHODS.
// ---
// I generate a new Word Search using the given input value.
public generateSearch( rawValue: string ) : void {
this.inputWords = rawValue.trim();
var words = this.inputWords.split( /[\r\n]/g );
// The .createWordPacker() call is a STATIC method that will instantiate the
// WordPacker class for us and then pipe each word into the packer, attempting
// to sort the list for optimal results.
var wordPacker = WordPacker.createWordPacker(
words,
20, // Width of the letter-grid in characters.
16 // Height of the letter-grid in characters.
);
// Once the WordPacker has packed all the words into a letter-grid, let's
// extract the letter-grid so that we can render it.
this.letterGrid = wordPacker.getLetterGrid();
// When the WordPacker is packing words, not all of the words will be able to fit
// into the underlying letter-grid. Let's log out both the words that made the
// cut and the words that were omitted.
this.logWords(
wordPacker.getWords(),
wordPacker.getSkippedWords()
);
// Persist words to the location so that this list can be shared with others
// via the URL.
window.location.hash = words.join( "," );
}
// ---
// PRIVATE METHODS.
// ---
// I get an initial value for the list of words.
private getInitialInput() : string {
// If the hash has a value, we're going to assume it's a persisted list of words
// that we want to use as our source of truth.
if ( window.location.hash.length ) {
var words = window.location.hash.slice( 1 ).split( "," );
} else {
var words = [
"Arguments", "Array", "Async", "Await", "Bubble", "Capture", "Catch",
"Class", "Closure", "Const", "Continue", "Debugger", "Event", "Export",
"Extends", "Finally", "Function", "Generator", "Handler", "History",
"Hoisting", "Implements", "Import", "Interface", "Java", "JavaScript",
"JSON", "Let", "Location", "Null", "Object", "Observer", "Package", "Parse",
"Private", "Protected", "Public", "Serialize", "Static", "Stringify",
"Switch", "Throw", "Trigger", "Try", "Undefined", "Yield"
];
}
return( words.join( "\n" ) );
}
// I log the word search values to the console.
private logWords( words: string[], skippedWords: string[] ) : void {
if ( words.length ) {
console.group( "%cWords in the Word Search", "color: green ;" );
console.log( words.join( ", " ) );
console.groupEnd();
}
if ( skippedWords.length ) {
console.group( "%cWords that did not get packed in the Word Search", "color: red ;" );
console.log( skippedWords.join( ", " ) );
console.groupEnd();
}
}
}
As you can see, the generateSearch() method uses the static method WordPacker.createWordPacker() to instantiate and populate a WordPacker class instance. This automatically generates a letter-grid (a two-dimensional array of letters), which we then store into this.letterGrid.
This letterGrid is then rendering in the App component's view-template:
<div class="columns">
<div class="column-1">
<textarea
#wordList
[value]="inputWords"
(keydown.Meta.Enter)="generateSearch( wordList.value )"
class="word-list">
</textarea>
<button
(click)="generateSearch( wordList.value )"
class="generate">
Generate Search
</button>
</div>
<div *ngIf="letterGrid" class="column-2">
<table class="word-search">
<tr *ngFor="let row of letterGrid">
<td *ngFor="let letter of row">
{{ letter }}
</td>
</tr>
</table>
</div>
</div>
Nothing much going on here - we're just taking the letterGrid view-model and rendering it using a traditional table element.
If we run this Angular demo, using the default set of JavaScript-oriented words, and then hit the "Generate Search" button a few times, we get the following output:
As you can see, each click of the "Generate Search" button generates a new, random arrangement of letters. And, since the arrangement is random, not all of the words will make it into each instance of the puzzle. If we look at the Console logging, we can see which words made it and which words were omitted:
As you can see, in the first puzzle, "Throw", "Yield", and "Java" were all omitted. However, in the second puzzle - due to random chance - only the word "Java" was omitted.
Now that we understand what the Angular application is doing, and roughly what a Word Search Puzzle is, let's look at the WordPacker class.
When you add a word to the WordPacker class, it uses the following brute-force algorithm:
Randomly select a Row-Column coordinate in the letter-grid.
Starting at said coordinate, try to add the word in every direction (Up, Down, Left, Right, Diagonal).
If the word cannot fit at the given location, move onto to the next location in the letter-grid using a "linear" scan.
Continue trying each location until every location in the letter-grid has been visited.
If the word cannot fit at any location, it is omitted from the letter-grid.
There's a good deal of code here. But, the bulk of the algorithm is implemented in the following methods:
tryToAddWord(), which turns around and calls:tryToAddLettersInDirection()
export type LetterGrid = string[][];
interface Direction {
rowIncrement: number;
columnIncrement: number;
}
var EMPTY_LETTER = "";
// I pack words into a two-dimension letter-grid, randomizing the location and the
// orientation of the characters that compose the packed words.
export class WordPacker {
private directions: Direction[];
private letterGrid: LetterGrid;
private height: number;
private skippedWords: string[];
private width: number;
private words: string[];
// I initialize the word packer with the given grid dimensions.
constructor( width: number, height: number ) {
this.width = width;
this.height = height;
this.words = [];
this.skippedWords = [];
this.letterGrid = this.initializeLetterGrid();
// As we try to add words to the underlying letter-grid, we're going to try and
// apply them in different directions. The following collection represents the
// ROW and COLUMN increments for each direction that we are going to try.
this.directions = [
{ // North.
rowIncrement: -1,
columnIncrement: 0
},
{ // North-East.
rowIncrement: -1,
columnIncrement: 1
},
{ // East.
rowIncrement: 0,
columnIncrement: 1
},
{ // South-East.
rowIncrement: 1,
columnIncrement: 1
},
{ // South.
rowIncrement: 1,
columnIncrement: 0
},
{ // South-West.
rowIncrement: 1,
columnIncrement: -1
},
{ // West.
rowIncrement: 0,
columnIncrement: -1
},
{ // North-West.
rowIncrement: -1,
columnIncrement: -1
}
];
}
// ---
// STATIC METHODS.
// ---
// I create a WordPacker for the given words using a grid with the given dimensions.
// Returns the populated WordPacker instance.
static createWordPacker(
words: string[],
width: number,
height: number
) : WordPacker {
var packer = new WordPacker( width, height );
// Sort the words with the longest values first. This will increase the chances
// of us being able to add more words to the grid (since smaller words can act
// more easily as "filler words", packing in the empty spaces).
var sortedWords = words.slice().sort(
( a, b ) => {
return( b.length - a.length );
}
);
for ( var word of sortedWords ) {
packer.addWord( word );
}
// Fill in the rest of the empty spaces with random words.
packer.finalize();
return( packer );
}
// ---
// PUBLIC METHODS.
// ---
// I add the given word to the packer. Returns a boolean indicating whether or not
// the given word could be packed into the two-dimensional letter-grid.
public addWord( word: string ) : boolean {
var normalizedWord = word.toUpperCase();
// If the given word can be wholly subsumed by one of the words that's already
// been packed into the letter-grid, it should be skipped since including it
// would lead to a confusing user experience (UX).
if ( this.wordOverlapsCompletely( normalizedWord ) ) {
console.warn( `Skipping [${ word }] because it overlaps completely with another word that's already been packed.` );
this.skippedWords.push( word );
return( false );
}
if ( this.tryToAddWord( normalizedWord ) ) {
this.words.push( word );
return( true );
} else {
console.warn( `Skipping [${ word }] because it could not fit into the current letter-grid.` );
this.skippedWords.push( word );
return( false );
}
}
// I finalize the two-dimensional letter-grid, filling-in any remaining spaces with
// random letters (A-Z).
public finalize() : void {
for ( var rowIndex = 0 ; rowIndex < this.height ; rowIndex++ ) {
for ( var columnIndex = 0 ; columnIndex < this.width ; columnIndex++ ) {
// If this grid-location is filled-in, move onto the next location.
if ( this.letterGrid[ rowIndex ][ columnIndex ] ) {
continue;
}
this.letterGrid[ rowIndex ][ columnIndex ] = this.randLetter();
}
}
}
// I return the two-dimensional letter-grid.
public getLetterGrid() : LetterGrid {
// In order to prevent our internal data-model from leaking out in a mutable
// fashion (ie, such that our internal structure could be mutated by an external
// context), we need to return a DEEP COPY of the letter grid.
return( this.letterGrid.map( row => row.slice() ) );
}
// I return the words that could not be packed into the letter-grid.
public getSkippedWords() : string[] {
return( this.skippedWords.slice() );
}
// I return the words that were packed into the letter-grid.
public getWords() : string[] {
return( this.words.slice() );
}
// ---
// PRIVATE METHODS.
// ---
// I create an empty letter-grid for the current letter-packer.
private initializeLetterGrid() : LetterGrid {
var row: string[] = new Array( this.width )
.fill( EMPTY_LETTER )
;
// The empty grid will use a row-first orientation (since this is easier to
// render in the HTML markup).
var emptyGrid = new Array( this.height )
.fill( EMPTY_LETTER )
.map(
() => {
return( row.slice() );
}
)
;
return( emptyGrid );
}
// I return a random letter between A-Z.
private randLetter() : string {
// The ASCII code for A-Z is 65-90. As such, we can generate a random letter by
// picking random values in this range.
// --
// NOTE: We're adding +1 because the randomizer is not inclusive of the last
// value. As such, we need to add +1 to get "Z" in the randomization.
var valueBase = 65;
var valueSpan = ( 90 - 65 + 1 );
return( String.fromCharCode( valueBase + this.randRange( valueSpan ) ) );
}
// I return a random value between 0 (inclusive) and the given value (exclusive).
private randRange( maxValue: number ) : number {
return( Math.floor( Math.random() * maxValue ) );
}
// I shuffle the given array of values in place.
private shuffle<T>( values: T[] ) : T[] {
for ( var i = 0, length = values.length ; i < length ; i++ ) {
var randomIndex = this.randRange( length );
// Swap the values in the current index and the random index.
var temp = values[ i ];
values[ i ] = values[ randomIndex ];
values[ randomIndex ] = temp;
}
return( values );
}
// I try to add the given letters in the given direction at the given location on the
// letter-grid. Returns boolean indicating whether or not the letter-grid has been
// updated with the letters.
private tryToAddLettersInDirection(
letters: string[],
rowStart: number,
columnStart: number,
direction: Direction
) : boolean {
var rowIndex = rowStart;
var columnIndex = columnStart;
// Before we mutate the letter-grid, let's see if the collection of letters will
// fit on the letter-grid using the given direction.
for ( var letter of letters ) {
// If the current location has gone off the grid, we've run out of room for
// the letters in the given direction.
if (
( rowIndex < 0 ) ||
( rowIndex >= this.height ) ||
( columnIndex < 0 ) ||
( columnIndex >= this.width )
) {
return( false );
}
// If the current location is already populated with a non-matching letter,
// we've overlapped with an incompatible word.
if (
( this.letterGrid[ rowIndex ][ columnIndex ] !== EMPTY_LETTER ) &&
( this.letterGrid[ rowIndex ][ columnIndex ] !== letter )
) {
return( false );
}
rowIndex += direction.rowIncrement;
columnIndex += direction.columnIncrement;
}
// ASSERT: At this point, if we've made it this far, it means that all of the
// letters will fit into the letter-grid using the given direction. At this
// point, we can move ahead with applying the letters, MUTATING the letter-grid.
// Move back to the starting location and add each letter in turn.
rowIndex = rowStart;
columnIndex = columnStart;
for ( var letter of letters ) {
this.letterGrid[ rowIndex ][ columnIndex ] = letter;
rowIndex += direction.rowIncrement;
columnIndex += direction.columnIncrement;
}
return( true );
}
// I try to add the given word to letter-grid. Returns a boolean indicating whether
// or not the letter-grid has been updated with the given word.
private tryToAddWord( word: string ) : boolean {
var letters = word.split( "" );
// To reduce the chances that every word is added in the same direction, we're
// going to randomize the order of the directions that we're going try for this
// word at the various locations on the letter-grid.
this.shuffle( this.directions );
// Randomly select the starting location on the letter-grid. From there, we will
// begin a linear scan of the grid, looking for a fitting location for the
// letters in the word.
var rowIndex = this.randRange( this.height );
var columnIndex = this.randRange( this.width );
// Performing a liner scan on a two-dimensional grid is a little tricky as we
// have to wrap the scan across rows and columns. We know that the MAX NUMBER of
// locations is equal to the TOTAL AREA of the grid.
var maxAttempts = ( this.width * this.height );
for ( var attempt = 0 ; attempt < maxAttempts ; attempt++ ) {
// At each grid-location, we're going to try fitting the word in every
// direction, taking the first one that matches.
for ( var direction of this.directions ) {
if ( this.tryToAddLettersInDirection( letters, rowIndex, columnIndex, direction ) ) {
return( true );
}
}
// If the current grid location didn't have room for the letters, we have to
// move onto the next "linear" location, performing a column-first scan.
// --
// CAUTION: Using PRE-INCREMENT operations here in order to increment the
// indices BEFORE consuming them in the equality-comparison.
if ( ++columnIndex === this.width ) {
columnIndex = 0;
if ( ++rowIndex === this.height ) {
rowIndex = 0;
}
}
}
// If we made it this far, the word could not fit into any of the scanned
// locations on the letter-grid.
return( false );
}
// I determine if the given word can be subsumed by (or can subsume) one of the words
// that's already been packed into the letter-grid (ex, "happy" can be wholly subsumed
// by "unhappy"). We can't allow for fully-overlapping words as it would be confusing
// for the consumer of the letter-grid.
private wordOverlapsCompletely( word: string ) : boolean {
// Get Upper-Case versions of our operands so that we don't have to worry about
// differences in case.
var normalizedWord = word.toUpperCase();
var normaliezdPackedWords = this.words.map(
( packedWord ) => {
return( packedWord.toUpperCase() );
}
);
for ( var normalizedPackedWord of normaliezdPackedWords ) {
if (
normalizedPackedWord.includes( normalizedWord ) ||
normalizedWord.includes( normalizedPackedWord )
) {
return( true );
}
}
return( false );
}
}
I tried to leave a lot of comments in the code explaining the approach; so, I won't go into any more detail. The approach is "brute force" but, seems to work decently well. I wish that I could have created more "overlapping" in the words so as to pack the words more tightly into the letter grid. But, I suspect that would have exploded the degree of complexity.
I found an example of Jamis Buck implementing a word search generator in Ruby; and, I tried to read through his logic; but, the Ruby syntax is surprisingly confusing for me. I will say, though, that his Ruby code is significantly shorter than my JavaScript code. I guess that speaks to the expressiveness of the Ruby language (which I think is a big part of why people love it).
Anyway, this was a fun mental exercise in Angular 9.1.4. And, now that I have a way to generate a word search puzzle, I may try to follow this up with a demo that actually implements the puzzle interactions (ie, highlighting words).
Want to use code from this post? Check out the license.
Reader Comments
It looks cool, so I am not alone who is using JavaScript to generate Word Search Puzzle )))
@Alex,
They are fun :) I only wish that my algorithm worked a bit more elegantly. Or rather, that it was able to fit more words. In the end, I feel like there should be more opportunity to get overlapping words into the mix. But, I suppose a more thorough algorithm may become inefficient in terms of processing times.