CoDEVIANT #20 (10/7/20)-Strings and Things (Soup is good food)
Problem# 1: Now this one is a pretty classic and simple one, but I’m looking at it today because I am getting better at utilizing pointers and while-loops instead of using a boatload of for-loops.
So we are writing a function that takes a non-empty string and returns a boolean representing whether that string is a palindrome. In this problem, single character strings are considered palindromes.
Palindrome: a word or phrase that reads the same backward as forward
So here’s how I solved it:
function isPalindrome(string) {
if(string.length === 1) {
return true
}
string.split('')
let left = 0
let right = string.length - 1
while(left < string.length && left !== right) {
if(string[left] == string[right]) {
left++
right--
} else {
return false
}
}
return true
}First off, I say that if the length of our string is 1, there’s no way it could not be a palindrome, so I return true if that’s the case in an if-statement.
if(string.length === 1) {
return true
}Pretty painless.
Then I turn the string into an array with the split method. I pass in an empty pair of adjacent apostrophes to make each character in the string be an individual element in the array.
string.split('')I then create two variables, left and right to serve as pointers for the array which we are going to use later in a while-loop. left will start at the beginning of the array, so it will be 0. right will be the length of the array minus one (to point at the index that corresponds to the last element of the array since in JavaScript arrays are zero-indexed [meaning you count 0 as 1, 1 as 2, 2 as 3 etc…]
let left = 0
let right = string.length - 1Then we create a while-loop to be active as long as left is less than the array’s length AND left does not equal right.
- We want left to not be longer than the array itself, otherwise that would be silly and we’d go on to infinity and your computer would crash.
- We want left not equaling right because if it does, then they are pointing at the same element in the array which would mean they are at the one unique value in the potential palindrome
while(left < string.length && left !== right) {
...
}Inside the while-loop, I create an if-statement to say that if string[left] is equal to string[right] then we increment left by one and decrement right by 1. This facilitates the purpose of the pointers, left and right, to point at each progressively inward (from both sides) array element to compare them and see if we are dealing with a palindrome.
If string[left] and string[right] at any point DO NOT equal each other, we return false.
while(left < string.length && left !== right) {
if(string[left] == string[right]){
left++
right--
} else {
return false
}
}Then, if after all of that, we still haven’t returned false, and left and right equal each other (thus ending the active status of the while-loop) we must be dealing with a palindrome, so we return true.
return truethe full solution again:
function isPalindrome(string) {
if(string.length === 1) {
return true
}
string.split('')
let left = 0
let right = string.length - 1
while(left < string.length && left !== right) {
if(string[left] == string[right]) {
left++
right--
} else {
return false
}
}
return true
}Now, how did the masters do it?
function isPalindrome(string) {
let reversedString = ''
for(let i = string.length - 1; i >=0; i--){
reversedString += string[i]
}
return string === reversedString
}This is clever…really clever. I like it! I have a habit of making things more involved than they have to be. This solution gets surgical with the problem, it’s really cool.
First we create a variable called reversedString equaling an empty set of apostrophes (indicating that it is a string).
let reversedString = ''Then we create a for-loop which:
- makes the iterator (i) equal the length of the string minus one
- iterates over the length of the string
- stays active as long as the iterator (i) is more than or equal to 0
- in each loop decrements the iterator (i)
for(let i = string.length - 1; i >= 0; i--) {
...
}Inside the for-loop we add string[i] to whatever value reversedString has at that moment. Over time, this continually adds onto reversedString to spell out the reverse of whatever string is.
for(let i = string.length - 1; i >= 0; i--) {
reversedString += string[i]
}Then we return a boolean based on whether string equals reversedString.
return string === reversedStringI got so hung up on pointers and while-loops from other recent problems that I didn’t consider inverting the common take on a for-loop.
Problem #2: Oh yeah, it’s a twofer.
So in this problem, we receive a non-empty string of lowercase letters and a non-negative integer representing a ‘key’. We want to create a function that returns a new string obtained by shifting every letter in the input string by key number of positions in the alphabet. We need to make sure that we ‘wrap’ around the alphabet (i.e. if we get something that is initially ‘z’ it doesn’t just become nothing but will start from the beginning of the alphabet onwards)
Ex: If we get xyz and our key is one, we shold expect to get yza.
Here is how I solved the problem:
function caesarCipherEncryptor(string, key) {
let alphabet = ['a','b','c','d','e','f','g',
'h','i','j','k','l','m','n',
'o','p','q','r','s','t','u',
'v','w','x','y','z']
let arr = []
string = string.split('')
string.forEach(el => {
alphabet.forEach((letter, index) => {
if(el === letter) {
let num = index + key
while(num > 25 ) {
num = Math.abs(alphabet.length - num)
}
arr.push(num)
}
})
}) return arr.map(el => {
return alphabet[el]
}).join('')
}
First things first, I need an alphabet. Lucky for you, I know a thing or two. One of those things is the alphabet.
So lets make an array, appropriate called alphabet and make each element a lowercase member of the alphabet.
let alphabet = ['a','b','c','d','e','f','g',
'h','i','j','k','l','m','n',
'o','p','q','r','s','t','u',
'v','w','x','y','z']Next, I create an empty array called arr. This will come in handy later.
let arr = []We are given a string as an argument, creatively called string. What I’m going to do is convert this string to an array where each of its letters becomes an individual element in said array. I achieve this by using the split method on the string and pass in a pair of apostrophes as arguments to the method.
string = string.split('')Then I use the forEach method on our array ‘string’. I use el to refer to the element being focused on in a given loop via this method.
string.forEach(el => {
...
})Inside this block, I use the forEach method on the alphabet array. I use the word letter to refer to the element being used in each loop and index to refer to the array-address of letter in alphabet
string.forEach(el => {
alphabet.forEach((letter, index) => {
...
})
})Inside of this inner block, I create an if-statement where if el is equal to the letter at a given moment, a new variable called num is created which equals the sum of index and key.
string.forEach(el => {
alphabet.forEach((letter, index) => {
if(el === letter) {
let num = index + key
}
})
})Under the declaration of num, I create a while-loop. In it, as long as num is over 25 (the length — 1 of alphabet) num will be recalculated to be the absolute difference of the length of the alphabet array minus num. Once the while-loop is deactivated because num would be 25 or below, we push whatever num is into our empty array: arr.
string.forEach(el => {
alphabet.forEach((letter, index) => {
if(el === letter) {
let num = index + key
}
while(num > 25) {
num = Math.abs(alphabet.length - num)
}
arr.push(num)
})
})Okay. Stay frosty, I’mma break it down. So with our if-statement, things get seemingly a little nutty. It’s actually pretty cool. So if we had ‘zcr’ as our input string and we had 56 as our key, we’re going to be in for some odd stuff because there are only 26 letters in the alphabet and we’re already counting up to 25 since our alphabet array is zero-indexed. So let’s pretend we’re inside the if-statement and for ‘z’, num is going to equal the sum of 25 + 56. That gives us 81. There is no 81’st address in our alphabet array and num is larger than 25. So now we recalculate num to equal the absolute-value of alphabet’s length minus num. Alphabet’s length minus num equals negative 55. Taking the absolute of a number means that we basically make whatever we have a positive integer. So that leaves us with num equalling 55…still, num is larger than 25 so we go through the process again. 26–55 = -29. Take the absolute value of that and we’re at 29. AGAIN! (because 29 is larger than 25). 26–29 = -3. Take the absolute value of that and we have 3. Now 3 is not larger than 25. We take that value and push it into arr.
Next, we write the final chunk of code outside of all the forEach methods. We return the result of using the map method on arr. In the use of this method, we have the value being iterated over, represented by el, return the value of alphabet[el]. Then we use the join method with empty quotes to return the newly constructed string we sought to us.
return arr.map(el => {
return alphabet[el]
}).join('')And that’s how we would get something ‘zcr’ with a key of 56 turned into ‘dgv’.
So how did the super-nerds do it?
function caesarCipherEncryptor(string, key) {
let newLetters = []
let newKey = key % 26
for(const letter of string) {
newLetters.push(getNewLetter(letter, newKey))
}
return newLetters.join('')
function getNewLetter(letter, key) {
const newLetterCode = letter.charCodeAt() + key
return newLetterCode <= 122
? String.fromCharCode(newLetterCode)
: String.fromCharCode(96 + (newLetterCode % 122))
}
}Okay…this is pretty snazzy coding.
We first create a variable that’s an empty array called newLetters.
let newLetters = []We create a variable called newKey which will equal the key modulo’d by 26. When we modulo something, it returns the remainder of the division. So if I modulo’d 13 and 4, we know that 4x3 is 12 and we have one left over. So our result would be 1. That sort of thing. So if you get a key that’s smaller than 26 (the length of our alphabet) like 13 you’re getting 13 back because 13/26…is..yeah, you don’t get anything but remainders from that division. If we were passed a massive key like 56, then 56 % 26 -> 4.
let newKey = key % 26Next we say that for every letter of string, we’re going to push into newLetters the result of a method we’ll create soon named getNewLetter which will accept letter and newKey.
- *This is a way of iterating over each character in a string without first turning it into an array. I wouldn’t have thought of it and it’s not something I’ve seen alot, but it’s cool to know about**
for(const letter of string) {
newLetters.push(getNewLetter(letter, newKey))}
Next let’s create our method getNewLetter. In it, we create a variable called newLetterCode. It equals the result of using the charCodeAt string method on letter + the key.
So in a variety of programming languages, there is a system you can make use of called Unicode. It’s a standardized practice of assigning a number to each letter, number, punctuation mark, etc. We are learning right now that convert symbols to their unicode-value by using the charCodeAt method on them. Conversely, we can create a string from the unicode-value by running String.fromCharCode(enter_your_unicode_value_here).
- a in unicode is 97
- z in unicode is 122
So back to the getNewLetter method, we have created a unicode translatable number in our variable, newLetterCode.
function getNewLetter(letter, key) {
const newLetterCode = letter.charCodeAt() + key
}Next, we return something different depending on whether newLetterCode is less than or equal to 122 (z in unicode speak).
- If newLetterCode is 122 or under, we return the result of String.fromCharCode(newLetterCode)
- If newLetterCode is over 122, we return the result of String.fromCharCode(96 + (newLetterCode % 122))
The first option is pretty understandable. We get a unicode that lies within the a to z range and we return it. Cool. Simple. If newLetterCode is over 122, is when things start to get interesting, however. We first get the result of moduloing newLetterCode by 122 (similarly to how we did at the start of the problem with 26, we do this to ensure we get a value that will lie within our a-z parameters). Then we add the result of that to 96. Why 96? Recall that 97 in unicode is ‘a’. If we started adding the modulo result to 97, we’d be one letter too far forward all the time, so we start at 96 to get an accurate result.
function getNewLetter(letter, key) {
const newLetterCode = letter.charCodeAt() + key
return newLetterCode <= 122
? String.fromCharCode(newLetterCode)
: String.fromCharCode(96 + (newLetterCode & 122))
}Going back to our main function, recall that we called this method we just wrote passing in letter and newKey as arguments. The result of that gets pushed into the empty array we created at the start of this: newLetters.
Once all that is done, we return the result of using the join method with an empty pair of quotes on newLetters.
return newLetters.join('')Here’s the answer again now that we’ve broken it down:
function caesarCipherEncryptor(string, key) {
let newLetters = []
let newKey = key % 26
for(const letter of string) {
newLetters.push(getNewLetter(letter, newKey))
}
return newLetters.join('')
function getNewLetter(letter, key) {
const newLetterCode = letter.charCodeAt() + key
return newLetterCode <= 122
? String.fromCharCode(newLetterCode)
: String.fromCharCode(96 + (newLetterCode % 122))
}
}Pretty sweet huh? I didn’t think it was possible to solve these alphabet problems without spelling out a whole array by hand.
Peace!