String Replacement Game

* The screenshot above is from my web-based game called the Replacement Game.

Mathematics

When I was an undergraduate student, I studied mathematics.

Mathematics isn’t just restricted to the study of numbers. It also includes the study of many different kinds of structures such as sets, functions, relations, graphs, etc.

But, my favorite structures are finite strings.

Strings

A finite string is a finite sequence of characters. Each character comes from a predefined alphabet.

For example, consider the alphabet {‘a’, ‘b’, ‘c’}. Then, “bcbbbaac” is an example of a finite string.

Just like how there are basic operations on numbers such as addition, subtraction, multiplication, and division, there are basic operations on finite strings such as concatenation, duplication, reversal, and replacement.

Replacement

We will focus on the string operation called replacement (also known as string substitution).

For the replacement operation, you are given strings x, y, and z such that:

• x is the original string
• y is the old substring
• z is the new substring

The operation replaces each occurrence of y within x by z.

Let’s look at an example:

• x = “acbabaac”
• y = “ba”
• z = “cb”

If we perform replacement, then the resulting string is “accbcbac”.

Replacement Game

In an effort to educate others about strings and string operations, I decided to create a web-based game called the Replacement Game.

In this game, the user is given:

• an initial string
• a final string
• three string replacement rules

The Goal

Apply a sequence of replacement rules to get from the initial string to the final string.

How It Works

To apply a replacement rule, the user clicks one of the three options. This updates the current string and expands another list of three options.

By clicking options, the user can expand and collapse possible paths to a solution. As a result, the user can explore many possible paths at once in an effort to reach the final string.

Tracking Progress

Over 1,000 challenges (of varying difficulty) are available in the Replacement Game.

Users can Login to track their progress through the challenges. The login page only requires a short nickname that will be published publicly on the Leaderboard.

As the game is currently in beta, we do not require passwords.

Final Thoughts

The replacement game is meant to be a fun and educational project. So far, two amazing users (dan & john) have already completed all of the challenges.

Although there is a focus in society on learning how to perform numeric calculations, I suggest that learning how to perform string calculations is also important.

Thank you for reading and I hope that you have a nice day!

* Originally published in 2019.