[Solved] Implementation a Prefix tree or Trie in Unity C#

Souvik Datta Asks: 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:


enter image description here

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:

Code:
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:

Code:
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

Ten-tools.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your response here to help other visitors like you. Thank you, Ten-tools.