Version 1.0 - Final Project For Algorithms - SE2231 - Developed by A. Legayada
This project runs on NextJS and is a browser based game that relies on ShadCN and TailwindCSS. You're facing against an immortal entity that cannot be killed, it has secrets and you need to understand them. Go through color blocks and defend yourself against a foe who can hit YOU, but you CANNOT hit it. A turn based combat that focuses on 'talking' and pattern identification. Can you prove how good you are at the patterns?
May 2025 - untested_release_v.1.0
May 2025 (latest) untested_release_v1.0.1
Vercel - https://long-drome-game.vercel.app/
✅ Clone this repository
bash git clone https://github.com/itsantonle/LongDrome_Game.git
✅ Install dependencies
bash npm install
✅ Run the developement
bash npm run dev
- 🎲 Palindrome Color Selection
- 🖼️ Different Locations
- ❤️🩹 Amiability Bar
- 🖱️ Interactive Action Buttons
- 📱 Responsive Design
- 🌗 Light/Dark Mode
Select colors to defend yourself! Each turn you must choose the longest Palindrome or you will take damage!
Different Locations that feature different backdrop and art. You can choose to fight in the temple or go home and recover!
Improve your relationship with the Guardian by talking and and choosing the correct responses!
Use the buttons to navigate and continue with the game! Talk, fight and use Magic!
Playing on Mobile or on Laptop screens? No problem.
Play in Dark or Light Mode
The Game Mechanics use the famous Manacher Algorithm that finds the longest palindromic strings in linear O(n) time!
this sections handles the process behind the functions
1. setOptimal palindrome gets from determineOptimalPalindrome(client_helper_utils) - calls from main page, validates palindrome
2. findOptimalPalindrome(game_utils) - error handling and returns sequence to determineOptimalPalindrome, validates manacher, otherwise brute force
3. findLongestPalindromeManachger(palindrome_utils) - base case (probably will never fail)
4. findLongestPalindromeBruteForce(palindrome_utils) - (CAUTIONARY FALLBACK)If the array is empty, return { start: 0, length: 0 }.
If the array contains only one element, return { start: 0, length: 1 }.
This step modifies the input by inserting null between each element and at the boundaries.
Example: If the input was
["red", "blue", "red"]it transforms into: Note that in some implementations of Manachers, the '#' is used in the place of 'null
["null", "red", "null", "blue", "null", "red", "null"]This ensures that both odd and even-length palindromes are handled consistently. This due to the fact that Manacher's employes a 'mirroring' technique that operates from a center point and relies on symmetry (Even N means that the center is an x.5 instead of a definite number)
P[i]: Stores the palindrome radius centered at index i. (longest)
Note that radii are used to evaluated the symmetry. Starting at 0 means that the that there is a palindrome of radius 0 (or itsself only) as p[i] is updated as we continue to expand based on symmetry. radius refers to two or n more elements from the center that are symmetrical mirrors of each other
Example:
first transformation with the nulls put in place
[null, "a", null, "b", null, "a", null]
// below is their follow p[i] values from the initialization
P = [0, 0, 0, 0, 0, 0, 0]
// As manacher expands
P = [0, 1, 0, 2, 0, 1, 0] center: The center of the current longest palindrome.
right: The right boundary of the palindrome that extends the farthest.
Example
// initial palindrome
transformed = [null, "a", null, "b", null, "a", null]
// Processing index 3 ("b")
// Expands outward: "a, null, b, null, a"
P[3] = 2 (radius = 2)
// New center = 3, right = 5
// Note: Doesn't count the nulls before the "a" on index 1 and after "a" on index 5P = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] // All radii start at 0
center = 0
right = 0For each position i, check if it’s within the current palindrome (right > i).
If it is, use the mirror value (P[mirror]) to avoid redundant computations.
Otherwise, expand outward from i as long as the transformed elements match.
Updating center and right:
If we find a palindrome that extends beyond right, update center and right.
Example Expansion Process we compare if the left and the right side are symmetrical thus we have these properties: center: 5 radius is 3 let's say we reach green (5) Expand outward (left=4, right=6) → "null" == "null"
Expand again (left=3, right=7) → "blue" == "blue"
Expand again (left=2, right=8) → "null" == "null"
(null) red (null) blue (null) |[green]| (null) blue (null) red (null)Loop through P[i] to find the maximum palindrome length and its center. After iterating through all indices, we find that:
Max palindrome radius: P[6] = 3
Center index: 6
The actual start index in the original array is computed as: Math.floor((centerIndex - maxLen) / 2)
This accounts for the extra null elements.
To convert this back to original indices:
Math.floor((centerIndex - maxLen) / 2)the function returns the starting index and the length of the longest palindrome In 'palidrome-utils'
["blue", "green", "blue"]
this section covers the explaination for the following:
1.genearateNewSequence() (page.tsx) generates new sequence and updates the color sequence state
2.generateRandomSequence (palindrome_utils.ts) the function that is called by generateNewSequencethe difficulty of the generated sequence depends on how far the user is in. The higher the turn count the harder the current set up sets this dynamically.
const newSequence = generateRandomSequence(5, 12, turnCount)
// code that implements this
const difficultyFactor = Math.min(5, Math.floor(turnCount / 3))
// this code adds more noise but does SHOULD NOT DISRUPT THE START OR THE END to preserve integrity
if (difficultyFactor > 2) {
// Add some similar colors to confuse the player
for (let i = 0; i < difficultyFactor; i++) {
const randomIndex = Math.floor(Math.random() * length)
if (
randomIndex !== palindromeStart &&
randomIndex !== palindromeStart + palindromeLength - 1
) {
colors[randomIndex] = colors[Math.floor(Math.random() * length)]
}
}
}identifies the min/ max length of palindrome COLOR[] sequence
The sequence length starts at minLength but grows with difficulty.A safeguard ensures a minimum of 5 elements. maxLength is adjusted to allow larger sequences as difficulty rises.
const min = Math.max(5, minLength + difficultyFactor);
const max = Math.max(min, maxLength + difficultyFactor);const length = Math.floor(Math.random() * (max - min + 1)) + min;
const colors: string[] = [];The actual sequence length is randomly chosen within the min to max range. An empty array colors is initialized to hold the sequence.
for (let i = 0; i < length; i++) {
colors.push(COLORS[Math.floor(Math.random() * COLORS.length)].name);
}A loop fills colors with random names from a predefined COLORS array.
/// this can be modified at anytime
// Define available colors
export const COLORS = [
{ name: 'black', value: '#000000' },
{ name: 'red', value: '#FF0000' },
{ name: 'blue', value: '#0000FF' },
{ name: 'green', value: '#00FF00' },
{ name: 'yellow', value: '#FFFF00' },
{ name: 'purple', value: '#800080' },
{ name: 'orange', value: '#FFA500' },
{ name: 'white', value: '#FFFFFF' },
]4. Creating Hidden Palindrome
The function ensures the sequence includes at least one palindrome. The palindrome’s length is dynamically calculated to be between 5 and 7 characters. A random starting position for the palindrome is selected. These values can be chosen to be dynamic later on.
const palindromeLength = Math.min(7, Math.max(5, Math.floor(length / 2)));
const palindromeStart = Math.floor(Math.random() * (length - palindromeLength));
Contributions to the LongDrome Game is welcome! It's small scale for now but can be more complex! Fork this repository and submit a PR to contribute
This Project is licensed under the MIT LICENSE