Hugs and Kisses algorithm - the only way to find true love
- Raf Y
- Feb 14, 2024
- 2 min read
In honor of Valentine's day, I've been hard at work figuring out an algorithm for finding true love. My inspiration came from watching my son play with a board of X's and O's. Here is a picture of the board:
I figured, if you want to find true love, then it's important that you validate someone's valentine/love letter is signed with a valid pattern of X's and O's! If it's not valid, then it's obvious that the person you received a valentine from is not invested in your love - they're being sloppy!
So, I've come up with an algorithm to validate this. The rules are, given an arbitrary matrix (we are going with a matrix to stay true to the board my son was playing with) where each element can either have an "X" or and "O", the matrix is valid if and only if for every instance of "X", an "O" follows. A few examples:
[["X", "O"]] is valid!
[["X"]] is not valid!
[["X", "O", "X", "O", "X"]] is not valid since the last "X" is not followed by an "O"!
[["X", "O"], ["X", "O"]] is valid! The first row is valid, and so is the 2nd.
I now present to you my "Hugs and Kisses" algorithm:
The key thing to look at here is line 11 - we want to ensure that "X" is not the last character and is followed by an "0" - otherwise it's an invalid pattern. There are ways to make the algorithm more efficient too - such as ensure there are at least 2 elements for each row - for example!
Time Complexity is O(n * m), where n is the number of rows and m is the length of a row, because we still need to check each element in the matrix at least once.
Space Complexity is O(1), the algorithm uses a fixed amount of memory regardless of the input size to check for a valid XO pattern.
Happy Valentine's day!