# Implementation a Prefix tree or Trie in Unity C#

I am trying to make a word game in unity. The game shall be an online game with 4-6 players. The gameplay is somewhat like this:

1. Suppose 4 players are playing the game- p1, p2, p3, and p4.
2. All players start off with a score (let 5).
3. Each player is supposed to give a letter each, such that those letters make some meaningful word.
4. The person who gives the final letter and thus completing the word loses 1 point.
5. Words of length 3 or more are only taken as complete words. Words like 'he', 'hi', 'oh' etc. are ignored for the sake of the fairness of the game.
6. Some other features will also be added for an even fair gameplay. (Like 2 letter or 3 letter cards - where a player will be allowed to give 2 or 3 letters at the same time, or a life card which will sustain the players point even on losing the round etc.)

Let us take an example:

• p1 - H
• p2 - E
• p3 - L
• p4 - L

Now since HELL becomes the complete word, p4 will lose 1 point and the game continues, with p4 starting with a new letter. Taking another example:

• p1 - N
• p2 - O
• p3 - T
• p4 - H .... instead of completing with an 'E' players should try to continue
• p1 - I
• p2 - N
• p3 - G

So p3 will lose a point.

Now if p3 uses any letter, which p4 thinks will not make any word, then p4 can challenge p3. If the word exists with those letters, p4 will lose a point. If the word doesn't exist then, p3 will lose a point.

So, for this kind of a feature, I would need to implement a Trie data structure in my game in Unity C#.

Currently, my game only looks like this:

I can enter any word, in the Input Field and search, if the word is complete and present in the list of words then it shows 1 in the Text above the Input Field. If the word is incomplete and can be completed, then it'll display 2, and if no such word exists, then it'll show 0.

This is my code for Trie/Prefix tree:

using System.Collections;
using System.Collections.Generic;

namespace MyTree {
public class Node {
const int ALPHABET_SIZE = 26;
// declaring 26 child nodes
public Node[] children = new Node[ALPHABET_SIZE];
// variable to check if at that node a word ends or not
public bool isEndOfWord;
// Node constructor
public Node() {
isEndOfWord = false;
// initialsing all child nodes with null value
for (int i = 0; i < ALPHABET_SIZE; i++)
children[i]=(null);
}
}
public class PrefixTree {
public Node root;
public PrefixTree () {
root = getNode();
}

public Node getNode () {
return new Node ();
}

public void Insert (string key) {
int level;
int length = key.Length;
int i;

// making a root
Node pCrawl = root;
// iterating from the first letter to the last letter
for (level = 0; level < length; level++) {
i = 'a' - key[level];
if (pCrawl.children[i] == null)
pCrawl.children[i] = getNode();
pCrawl = pCrawl.children[i];
}
pCrawl.isEndOfWord = true;
}

public int Search(string key) {
int level;
int length = key.Length;
int i;
Node pCrawl = root;

for (level = 0; level < length; level++) {
i = key[level] - 'a';

if (pCrawl.children[i] == null)
return 0;   //Absent
pCrawl = pCrawl.children[i];
}
if (pCrawl != null) {
if (pCrawl.isEndOfWord == true)
return 1;   //Present
return 2;       //Can be completed
}
else
return 0;       //Absent
}
}
}


This is my Word Checking Script:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
using MyTree;

public class CheckDict : MonoBehaviour {

public InputField inpText;
public Text showText;
public TextAsset dictFile;

private string textToString;

private List<string> dictList;
private int dictLen;
private PrefixTree dictionary;

void Start () {
dictList = TextToList (dictFile);
dictList = dictList.GetRange (0, 20);
dictLen = dictList.Count;
dictionary = new PrefixTree ();
//dictionary.root = new Node();

showText.text = dictList[5];
for (int i = 0; i < 20; i++)
dictionary.Insert (dictList [i]);
}

private List<string> TextToList (TextAsset ts) {
return new List<string> (ts.text.Split ('\n'));
}
public void OnSubmit () {
textToString = inpText.text.ToString();
int i = dictionary.Search (textToString);
showText.text = i.ToString();
//      if (dictList.BinarySearch (textToString) < 0)
//          showText.text = "Word missing from dictionary";
//      else
//          showText.text = textToString;
}
}


During runtime, this error is shown:

IndexOutOfRangeException: Array index is out of range. MyTree.PrefixTree.Insert (System.String key) (at Assets/Scripts/PrefixTree.cs:40) CheckDict.Start () (at Assets/Scripts/CheckDict.cs:28)

The program runs, when I enter anything for example: 'aah' which is present in my list of words, I get a 0.

Here is the link to my list of words:

https://github.com/Souvik7cd/Game-dictionary/blob/master/dict.txt

• I notice in the problem method you use i = 'a' - key[level]; while in the other method you use i = key[level] - 'a'; - is it possible key[level] > 'a' leading to i taking on a negative value with the former expression? – DMGregory May 16 '18 at 20:29

I changed the Insert Function of the Prefix-Tree code:

       public void Insert (string key) {
//int level;
int length = key.Length;
int i;

// making a root
Node pCrawl = root;
// iterating from the first letter to the last letter
for (int level = 0; level < length; level++) {
i = key[level] -'a';    // changed
if (i < 0)              // added if
break;

//Debug.Log ("New Node " + level);
//Debug.Log ("Key[level] " + key [level]);
//Debug.Log ("i: " + i);

if (pCrawl.children [i] == null)
pCrawl.children [i] = getNode ();

pCrawl = pCrawl.children[i];
}
pCrawl.isEndOfWord = true;
}

• This answer would be better if you explained why this code change fixed your problem. – DMGregory Aug 9 at 11:47