This repository contains the codes required for the FLAMES algorithm which is a quiet famous game. This code is a naive approach of solving FLAMES but is very good for explaining the use of different data structures in a fun way which one might be keen to learn. The basic task of this was to understand data structures and how to use them in a fun way so that anyone could understand why one may need to study it.
I don't think this had to be explained beacuse almost everybody has once in their lifetime played the famous game which lets you know what to expect from your crush or someone you just vibe with.
There might be few who need a recap of what FLAMES is. For them it is a game mwhere you need two name; for an example I wil be going with:
David Sally and
Keneth Morrison
The rules of the game is pretty simple; cut out the common letters from both the names and then count the remaining letters.
Here as you can see the remaining number of elements is 20
So now the last part of the game is repeatedly couting over the letters "FLAMES" until you reach the flame number and then you remove that particular letter from "FLAMES" and start counting again from the next element and repeat the process.
If you reach the end then start from the start and do this untill one letter remains which will determine the result.
Now for the result; different elements represent something different.
- F - Friend
- L - Love
- A - Attraction
- M - Marriage
- E - Enemy
- S - Sibling
Now, result for the example I have chosen here turns out to be and I used this code to run it is
David Sally
Keneth Morrison
Ouch! Something is wrong. Too much negativity.
David Sally and Keneth Morrison are ENEMIES!
Try to solve your problems or kill the other one to live a peaceful life.
Funny isn't it?
As discussed above one has to rule out common letters in both the names and to accomplish that I used the hash function.
The hash function counts the frequency of letters in string boy and substracts the elements if there in string girl so that now all the common letters are decremented by number of times they are repeated in both the strings.
Now int flame_number is declared and both the hash functions are check and if mp_girl[girl[i]]!=0 then flame_number is incremented by 1. This is done for both boy and girl. This way I calculated the flame_number
This project of mine is not very recent rather I thought of writing the code for FLAMES in first second semester of first year of my B.Tech but at that time I didn't know Data Structures and Algorithms so I couldn't figure out how to solve the repeatitive deletion of letters in FLAMES.
Now, I know various method by which this could be solved and there are more efficient solution to this problem but I wanted to combine my college level DSA skills with competitive DSA skills which I gained through leetcode.com and through contests.
What I want to express is that through this approach one can understand how linked lists can be utilised to make a fun project which one can show off to their friends whilst gaining the knowledge of DSA and their further use in technology.
But why Circular Linked Lists?
If you know the rules then you must be wondering how one can approach a problem of deleting one letter from a set of letters using a particular number which also loops over the remaining letters in the set?
Don't worry. I thought about that too and after kicking myself in the head I thought, "Loop, hmm. Circles, hmm. Circular linked list!" and like that I had an intuition which once I went forward with got me the solution I was searching for since 5 months.
In Circular linked list the tail pointer points to the head so that even if the pointer one is using to traverse the list comes to the end of the list it would again go to the head of the list. And this was the Eurekha! moment for me. I created a simple circular linked list with insert function and a size counter. I didn't use the normal delete funciton one might write rather wrote the flames(int pos) function which deleted the letter at pos making sure to update the previous pointer points to the next of that position.
Here the only special case that I had to look at was when the pos iteration pointed at the head of the list. In this case I have to delete that head and update the head pointer. The tail anyway points to head so that takes cares of everything else.
The deletion coninued till the size of the list == 1. At that point the algorithm is over and the head->data is returned as the result. This result is then used to determine the final result of FLAMES.
If the strings had any uppercases then the hash function would count them separately leading to bugs in the code so to avoid that a new function was written remove_spaces_and_uppercase_to_lowercase. This function also removes the spaces which doesn't affect the algorithm but it's safe to be cautious anyways.