“Guess the Artist” game — with an Autocomplete implementation using a Prefix Tree in React
What is “Guess the Artist”? 🤔🎙💽
Guessing games are popular because they keep you on your toes. It’s also easy and not as complex compared to other game types. For example, in the game Charades, a single person will act out and the rest of the people will guess what the person is acting. There are two states of the game, either you guessed it right or wrong.
That is why I chose to make a guessing game. The user will be given a snippet of random lyrics and the aim is to guess who the artist of the song is. It has two states, Correct 😀 or Incorrect ☹️.
I used a Spotify dataset that I found from Kaggle that contains the top songs in the world from 2010–2019. From this data, I grabbed a random song and artist. I used the output to grab the lyrics of the song from an API called Musixmatch. I then display the lyrics to the user.
For the user guessing part, I used a Prefix Tree data structure to auto-complete the name of the artist once you start typing the name. I created the tree by first grabbing all of the unique artist names from the Spotify dataset. I then converted the names into an array of strings and inserted it to the Prefix Tree.
So what is a Prefix Tree? 🤔🌲
A Prefix Tree or a Trie is a tree data structure. Each node usually has a maximum of 26 child nodes, i.e 1 child node for each alphabet.
Each node object contains information such as all it’s children node references, whether it’s terminal or not, and the character it represents.
A node is said to be terminal if it terminates a string. For example, for the string “PETER”, node ‘R’ would be a terminal node since it represents the last character of the string.
To fully understand the data structure of a Prefix Tree, I highly recommend this article.
Why use a Prefix Tree (Trie)? 🧩🌲
Using a Trie has two main benefits. It’s a more efficient way to search for strings because, we can find strings in O(L) time, where L is the length of the string. This is because when searching for a string, we traverse down to each character and stop once we find the last character of the string. Each step of traversal filters out characters that are not part of the string. The more we type in our input, the narrower our answer will get. This is because our prefix will be more precise once we go down the prefix tree.
The prefix tree has a complete method, which takes in a prefix string and returns all the words that start with the prefix. This is the method that holds the Autocomplete functionality. To better understand the complete method, let’s take an example from the above tree. The prefix string that’s passed in the method is ‘PE’. This method should then return all the strings that start with the prefix ‘PE’ in an array. For the above tree, it will return [‘PETER’, ‘PECK’, ‘PEPPERS’].
The complete method has 2 helper methods: findNode and traverse.
findNode method returns a pair containing the deepest node in the prefix tree that matches the longest prefix of the given string and the node’s depth. For example, if the string ‘PETER’ is passed to findNode, it will return node ‘R’ and depth of 5. This is because ‘R’ is the deepest node from the given prefix and its depth is 5.
The traverse method traverses down the tree starting from any node in the tree. It first checks if the node we passed is terminal. If it is, it appends the prefix. After that, it recursively calls itself at each of its children nodes.
Why use Autocomplete?
Adding an autocomplete feature provides a better user experience. Many times when typing people names, we might get the first few letters correct but we might misspell their names. Having an autocomplete feature would eliminate that by providing all the available words that start with a particular prefix.
In addition, it will save the user time from typing the full name of an Artist or a Band.
Handling cAsE-insensitive search 🕵🏽♀️
Another feature I wanted to implement was enabling a case-insensitive search. Generally, artists have a weird and funky way of writing their names. For example, SHAED has all caps for their band name. Other examples are Charli XCX and G-Eazy. I wanted my game to be user-friendly so that the user can type the name of the artist in any casing and will get their result correctly regardless. I also wanted to keep the original casing of the artists at the same time.
To achieve this, I started by converting all the incoming strings from the user input to lower case. All the unique artists that I have in my prefix tree are also converted to lower case when they’re inserted to the tree. So the trie contains all unique artists in lowercase. The autocomplete will now work since both the prefix input and the values in the tree are lowercases.
The one thing left was how I could convert all the lowercase autocomplete results back to their original casing. I handled this by creating a JSON object that holds the unique artist names in lowercase as keys and their original casing as values. So now once I obtain the artist names, I can call on the object using the artist name as a key and will then get the original artist value as a result. This will also give me an advantage in runtime since the lookup time of JSON objects using keys is O(1). I can then show the result obtained to the user.
In conclusion, applying the autocomplete feature in your application increases the search results and gives a better user experience since the user is not expected to type every character. Once you find the word you’re looking for from the list of autocompletion, you can click on the name to choose it. I hope after reading this article you’ve gained some knowledge about tries and their functionality.
Guess the Artist 🎮🕹
Link to the game: https://liyasileshi.github.io/lyrics/
Take a look at the completed project on my GitHub profile: https://github.com/liyaSileshi/lyrics
Resources 📚
If you would want to research more on Prefix Tree(Trie), below are some links that could be helpful.
- Algorithms: Tries, Robert Sedgewick and Kevin Wayne
- Tries, Brilliant Learning
- Tries, Daniel Ellard
- Tries, Harvard CS50
- Trying to understand Tries, Vaidehi Joshi
🙏🏽 Thanks for reading and feel free to reach out to me or comment below if you have any questions.
