GitHub - kclapper/Koggle: Boggle the boardgame, now as a website and React component!

Boggle the boardgame, now as a website and React component! - kclapper/Koggle

GitHubkclapper

A while back, me and my girlfriend were playing a lot of Boggle. Around that time, I was reading Clean Architecture by Robert C. Martin. It ended up being very influential to how I see system architecture and I had a few major takeaways:

• Your dependencies should always point from lower level to higher level concepts. The things that are most likely to change should be the easiest to change.
• The structure of your code should scream what kind of application you're building. When you look at your repo, your first takeaway shouldn't be, "this is a Spring app", it should be, "this is a healthcare system." (I'm paraphrasing Martin here).
• A good architecture defers as decisions to as late as possible. For example, the exact database you use should be a detail of your application, one that the core of your application doesn't care about. Only the outer layer of your architecture should care about the database implementation.

With these ideas in mind, I wanted to build an online version of Boggle so my girlfriend and I could play together, even when we were out of the house or didn't have the board with us.

The 'Business Logic'

The core logic of the application (or the 'business logic' if you prefer) is the game board (the data) and how to play the game (business rules). With the principles outline above in mind, I wanted these concepts to be high level components of the system that had as few dependencies as possible.

Critically, I wanted them to be separate from the presentation of the game. I was using React as my front-end framework but I didn't want my core logic to care about this decision. To facilitate this, I went with an event driven design. The game is represented by classes that implement the Controller interface. This interface specifies what key functions a game of boggle performs such as:

• Starting and stopping the game.
• Notifying event listeners when the game starts, finishes, or is stopped.
• And getting details about the board like it's size and the letters on it.

Here I'm using the Observer design pattern to make this an event driven design. Using events, the game controllers don't have to know about other components in the system and can focus exclusively on it's logic. Notably, there is no React code in any of the classes that implement this interface. It's not necessary, because they are decoupled from the UI.

This Controller interface is implemented by an AbstractBoggle class. There is a lot of internal logic that is shared by different boggle boards, so it's useful to put it all in one place to reduce repetition. The RegularBoggle and BigBoggle classes both inherit from AbstractBoggle , and their implementations are essentially just variations on setting up the board they contain. The bodies of RegularBoggle and BigBoggle are small as a result (~50 loc).

The UI

Like I mentioned, I used React for the UI. React has a handy feature to help synchronize with outside components and APIs called useEffect. It essentially lets you "break out" of React and I used it throughout the UI code to interact with the Controller classes.

Here is a good example. This code snippet comes from the main UI component and it's purpose is to update the UI when the game starts. There is a state variable called inProgress that controls how the UI looks when the game is in progress. With useEffect, I add a 'gameStart' event listener that sets this value to true.

Solver

In that code snippet you'll also see that I use a class called Solver to find all of the words on the board so they can be displayed at the end of the game. There isn't anything special about this class from an architecture standpoint, but I had fun making it because I got to demonstrate some algorithms knowledge.

To find all of the words on a Boggle board is tricky. The naive solution would be to start from each block on the board and draw out all of the possible paths that don't contain repetitions. I recognized that this is essentially a graph traversal problem and the naive solution is essentially a more computationally expensive version of depth-first search.

Knowing the naive solution would be slow, I built it anyway and used it as a jumping off point. I represented the board as a graph, then found each string that can be made. I cross referenced these strings with the Official Scrabble Dictionary to see if they were words and saved the ones that were. This solution took a long time to finish, on the order of 30 seconds to a minute or more (depending on the size of the board).

Seeing as how a user could click start then immediately click stop, I needed to be able to solve the boards faster than 30 seconds.

I ended up using a trie to speed up the algorithm. There are free versions of the Official Scrabble Dictionary in json form on project Gutenberg. From those files, I took the entire English dictionary and built one large trie. When building the trie, nodes that represented the end of a valid word were flagged.

When solving the board, you start at each block and you keep trying to find new words, but the important optimization is that you follow along in the trie as well. If no more words can be found by going from one block to another, then you stop following that path and move on to the next one. In this way, the traversal doesn't explore any path on the board that can't lead to a valid word.

With this algorithm the Boggle boards can be solved almost instantly. After clicking start, you can immediately click stop and the solution will show up right away.

Tools

When it comes to "your code should scream out what kind of application it is," I think I missed the mark a bit. I think, in practical terms, the tools we use will necessarily influence structure of your code to some degree reflect. When you look at the source code for Koggle, it's clear it's a Node app. The npm package structure is all there. It's written in Typescript and uses React as a front-end framework. It also uses Bootstrap for styling.

CI/CD

Koggle is written in Typescript and distributed as an npm package. When users install Koggle, they can add the Boggle React component to their projects. I use GitHub Actions for CI/CD. When a new commit is added to the main branch, the code is linted, type checked, and tested. When a semantic version tag is created, an Action first lints, type checks, and tests the code. Assuming those all pass, it then publishes the package to npm. It also builds and deploys the demo site.