My Flatiron School classmate Arielle Sullivan posted her solution to an interesting programming puzzle:
Determine whether the letters in a given string can be arranged to form a palindrome.
Her solutions is below:
1 2 3 4 5 6 7 8 9 10 11
The gist of it is this: Iterate through the string to make sure at most one character is unpaired. So for instance with
lloo, every character is paired up, so we can make the palindrome
lool. The same with
llo making the palindrome
If two or more characters are unpaired, this breaks down. So for instance
lllo has an unpaired
l and therefore can’t form a palindrome.
Looking at line 2 above, my first thought was that this was a good case for the ruby
inject method (or
1 2 3 4 5 6 7 8 9
Looking good! But something was bothering me. We’re essentially doing the following: – If the array of uniques has a character, remove it. – If it doesn’t have a character, add it.
This is essentially the
XOR or exclusive or operator! In ruby the xor operator is the
^ character. In boolean expressions, it returns true if one of two expressions is true but not both.
1 2 3 4
How does this translate to sets and characters? Well, if we have two sets of characters, we can xor them together to get the characters in either but not in both. This is exactly what we want. Unfortunately, you can’t natively xor two arrays in ruby, but you can with the Set class. Let’s give it a try:
1 2 3 4 5 6 7
Even better! If we wanted to do this without the Set class, we can xor two arrays ourselves:
1 2 3 4
Let’s break this down.
(arr1 + arr2) returns an array that combines the two arrays.
(arr1 & arr2) returns an array of items in both. Subtracting the latter from the former results in items that are in either one but not in both.
So our final solution, sans sets would be:
1 2 3 4 5