[Challenge] Palindrome Detector

challenge

#13

Hard difficulty (JavaScript): https://repl.it/JGyJ/2

Like some of the previous solutions, I also found the RegExp possibility, but decided not to use it since it may get close to the 'imports that do the heavy lifting' that would take away a large chunk of the challenge.

The premise of this code is to check each character in the testString against a whitelist, permittableChars. Any characters that get passed will be checked against foundChars, a list of characters found earlier in the loop. If no match is found, the character is added to the array. If a matching character is found, its match is removed from foundChars. At the end of the loop through all testString's characters, foundChars contains all characters that occur in testString in an odd amount.
If foundChars.length === 0, testString is an even-number length palindrome
If foundChars.length === 1, testString is an odd-number length palindrome
If foundChars.length > 1, testString is not a palindrome

 isPermPalindrome(".0123456789876543210");      //true
 isPermPalindrome(".01234567898765432100");     //false
 isPermPalindrome("Science Bros.");             //false
 isPermPalindrome("Able was I ere I saw Elba"); //true
 
 function isPermPalindrome(testString) {
     //list of all permittable characters to exclude spaces, punctuations, any other symbols, and Order 66
     var permittableChars = ['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', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
     //array of all characters that have been detected, but not yet matched
     var foundChars = [];
     //currently tested character in the loop
     var testChar = '';
     for (i = 0; i < testString.length; i++) {
         testChar = testString.substr(i,1).toLowerCase();
         //check if character is whitelisted and paired
         if (permittableChars.indexOf(testChar) !== -1 && foundChars.indexOf(testChar) !== -1) {
             foundChars.splice(foundChars.indexOf(testChar), 1);
         //check if character is whitelisted and unpaired
         } else if (permittableChars.indexOf(testChar) !== -1 && foundChars.indexOf(testChar) === -1) {
             foundChars.push(testChar);
         }
     }
     if (foundChars.length > 1) {
         console.log(false);
     } else {
         console.log(true);
     }
 }

PS: was it recently added to the extra information page that it is preferred NOT to use the repl.it preview box, but instead just provide the link?


#14

Intermediate/Hard Difficulty in Python: https://repl.it/JHLS/15

A palindrome needs to have even number of all letters/digits (with possibly one letter as an exception). The function creates a set to store odd-numbered letters/digits and traverses through input string. When a letter/digit appears in string for a second time, it is removed from the set. It is expected that if an input string is a palindrome, the loop will end with an empty set (all letters in even numbers) or a set containing a single letter (a pivot letter in palindrome).

To account for capitalization, the function first transforms the input string into lowercase. To deal with whitespaces and punctuation, each element is checked with concatenated string.whitespace and string.punctiation.

import string

def isPermPalindrome(s):
  rubbish = string.punctuation + string.whitespace
  letters = set()
  s = string.lower(s)
  for a in s:
    if a in rubbish:
      continue
    if a in letters:
      letters.remove(a)
    else:
      letters.add(a)
  if len(letters) > 1:
    return False
  else:
    return True
    

a = 'yakak'
b = 'Science Bros.'
c = 'kayak'
print isPermPalindrome(c)

#15

From what i can see, you only check if the input is a palindrome, not if it is a permutation of a palindrome. Running string like "1188" or "yakak" through the function should return True, because the characters can be rearranged to form a palindrome.


#16

Oy . .you are right! Didnt catch the full scope of the challenge. Oh dear oh dear :grimacing:


#17

Hey Omnishift,

Yep, we asked people to change up the way that they submit – with more of an emphasis on formatted pasted code than the Repl.it preview box – partially because when so many people include their repl.it previews, it dramatically increased the time it takes to load the page. We definitely still want people to include a repl.it link so that we can assess answers, just don't have it so that it embeds.


#18

Hey hiro_protagonist,

How did you embed your interpreter like that? I'm following the docs but I can't seem to make it work.


#19

ok .. so we try again . .

Python3.6: https://repl.it/JH68/1

from collections import defaultdict


def isPermPalindrome(string: str) -> bool:

    # cleaning non alphanumerical characters from the string, and lower caseing.
    string = ''.join(char.lower() for char in string if char.isalnum())

    # counting occurrence of each type of letter
    count_dict = defaultdict(int)
    for char in string:
        count_dict[char] += 1

    # counting occurrence of chars with an odd occurrence
    odd_count = 0
    for value in count_dict.values():

        if value % 2 != 0:
            odd_count += 1

    # if all chars have an even occurrence we know it can form a palindrome
    # if there is a single char with an odd occurrence, we also know we can form a palindrome of the letters
    # if there are more than one odd occurrence letters, it is not possible to form a palindrome

    return odd_count <= 1


print(isPermPalindrome('Hello World'))
print(isPermPalindrome('Able was I ere I saw Elba'))
print(isPermPalindrome('1881'))
print(isPermPalindrome('1818'))
print(isPermPalindrome('1188'))
print(isPermPalindrome('Eva, can I see bees in a cave?'))
print(isPermPalindrome('Eva, can bees I see in a cave?'))
print(isPermPalindrome('What is going on here? ! !'))

#20

The post above you refers to NOT embedding the repl.it preview. Instead enter a space or any number of letters before the link to allow people to check out your code if they choose.


#21

Here is my Python submission for all difficulties:

# accepts one string parameter, 
# consisting of letters, digits,
# spaces and punctuation
#
# returns a Boolean, representing
# whether or not, the letters, digits
# in the string are a valid permutation
# of a palindrome
def isPermPalindrome(sentence):
# the quantity of letters
# and or digits in the string
    total = 0
# dictionary count for each letter/digit
    tally = {}
# have we seen an odd count
    oddly = False
    # make one O(n) pass through
    # calculate total, of letters
    # tabulate counts, of letters
    for char in sentence:
        if char.isalnum():
            total += 1
            index = char.lower()
            tally[index] = tally.get(index, 0) +1
    # we have two different cases
    # to consider, total odds or even
    if total % 2 :
        # total is odd
        # we can have one and only one
        # odd letter count
        for entry in tally:
            if tally[entry] % 2:
            # found an odd letter count
                if oddly:
                # found another
                    return False
            # remember, what was found
                oddly = True
        return oddly
    else:
        # total is even
        # we can't have any
        # odd letter counts
        for entry in tally:
            if tally[entry] % 2:
            # found an odd letter count
                return False
    return True

def test_isPermPalindrome(test_string):
    print("isPermPalindrome(\"%s\") =>" % test_string, isPermPalindrome(test_string) )

test_isPermPalindrome("kayak")
test_isPermPalindrome("yakak")
test_isPermPalindrome("")
test_isPermPalindrome("a")
test_isPermPalindrome("ba")
test_isPermPalindrome("baa")
test_isPermPalindrome("Abba")
test_isPermPalindrome("Science Bros.")
test_isPermPalindrome("Science Bros.; Noir")
test_isPermPalindrome("Abracadabra")
test_isPermPalindrome("Call, Abracadabra!")
test_isPermPalindrome("God's dog")
test_isPermPalindrome("dog's God")
test_isPermPalindrome("no ding into dong")
test_isPermPalindrome("not ding into dong")
test_isPermPalindrome("1188")
test_isPermPalindrome("1234")

No permutations actually need to be generated.
We just need to determine whether a permutation of a palindrome is possible.

One key factor is the quanity of letters in the string.
We can ignore all other characters, such as spaces and punctuation.
If this total is odd, then only one letter can occur an odd number of times.
If this total is even, then all letters must occur an even number of times.
This is the same as, no letter can occur an odd number of times.

Here is the output of my testcases:

isPermPalindrome("kayak") => True
isPermPalindrome("yakak") => True
isPermPalindrome("") => True
isPermPalindrome("a") => True
isPermPalindrome("ba") => False
isPermPalindrome("baa") => True
isPermPalindrome("Abba") => True
isPermPalindrome("Science Bros.") => False
isPermPalindrome("Science Bros.; Noir") => True
isPermPalindrome("Abracadabra") => False
isPermPalindrome("Call, Abracadabra!") => True
isPermPalindrome("God's dog") => True
isPermPalindrome("dog's God") => True
isPermPalindrome("no ding into dong") => False
isPermPalindrome("not ding into dong") => True
isPermPalindrome("1188") => True
isPermPalindrome("1234") => False

EDIT: Wasn't accepting digits, I fixed that now.

https://repl.it/JHXq/34


#22

As @chrinkus pointed out, the (apparently recently updated) rules state that it is now preferred NOT to have your repl.it code previewed here as embedded interpreter. Instead, code in the challenge topics should be formatted with common code tags as described here. So all you need to do to create the 'optimal submission' is to add your code as such in your post so it can be read without having to go to your repl.it page.
If in another topic you still need to embed repl.it code, just copy its url (not the embed link) without other text on its own line.


#23

This is my try at the intermediate (and maybe hard :smile: ) in Java.
Here's the link to the code https://repl.it/JIAN/2

public class Main 
{
  public static void main (String[] args)
  {
    String input = "helllleh1";
    System.out.println(isPermPalindrome(input)); 
  }
  public static boolean isPermPalindrome(String input)
  {
    int[] alphanum = new int[36]; // to know if a letter appeared an even or odd number of times
    for(int i = 0; i < alphanum.length; i++)
      alphanum[i] = 0;
    input = input.toLowerCase(); // take care of case sensitivity
    for(int i = 0; i < input.length(); i++)
    {
      char c = input.charAt(i);
      if(Character.isLetter(c)) //only consider letters
      {
        alphanum[c-'a'] = 1 - alphanum[c-'a'];
      }
      else if(Character.isDigit(c)) //consider digits too
      {
        alphanum[26+(c-'0')] = 1 - alphanum[26+(c-'0')];
      }
    }
    int unique = 0;
    for(int i = 0; i < alphanum.length; i++)
      unique += alphanum[i];
    return (unique == 1 || unique == 0); // at most one character should occur an odd number of times
  }
}

#25

Code on repl.it

Used Javascript for the intermediate difficulty.

I first removed capitalisation from the input and then extracted [a-z0-9], removing spaces and punctuation. The assignment was to inlcude numbers, but it did not say that we should ignore them.

The idea was to count all the characters in the input string and return false when there are more than 1 odd characters.

And return true for all the other cases.

function isPermPalindrome(input) {
	// Format the input
	input = input.toLowerCase();
	input = input.match(/[a-z0-9]/g);


	// Make a variable to store the character count
	var collection = {};

	// Count the characters
	for(var i = 0; i < input.length; i++) {
		var currentChar = input[i];

		if(collection[currentChar]) {
			collection[currentChar] = collection[currentChar] + 1;
		} else {
			collection[currentChar] = 1;
		}
	}

	// Count the amount odd characters
	/*
	 |   ODD   |   EVEN   |
	 |---------|----------|
	 |   0     |   Any    | => True
	 |---------|----------|
	 |   1     |   Any    | => True
	 |---------|----------|
	 |   +1    |   Any    | => False
	 */
	var odd = 0;

	for(var character in collection) {
		if(collection[character] % 2 != 0) {
			odd++;
		}

		if(odd > 1) {
			return false;
		}
	}

	return true;
}

#26

Main idea:
1. Even number of symbols instances can form polindrome string ('ABBA')
2. Only one symbol allowed to have odd number of instances ('ada')

Here we go with Python3: https://repl.it/JIlS/0

def isPermPalindrome(s):
    # built hash table:
    # hash value True - odd instances of a symbol
    s_hash = {}
    for symb in s.lower():
        if symb.isalpha() or symb.isdigit():
            if symb in s_hash:
                del s_hash[symb]
            else:
                s_hash[symb] = True

    # Check no more than 1 value in the hash
    return len(s_hash) <= 1
    
print( isPermPalindrome("Science Bros.") )

#27

Here's my entry for hard challenge in Python. The code counts occurences of all allowed chars, then recognizes a palindrome permutation if:

  • every char has even amount of occurrences (eg. "abba")
    or
  • every char except one has even amount of occurrences, if string length (counting allowed chars only) is odd (eg. "kayak")

def isPermPalindrome(text):
    charcount = [0] * 36                 # [0123456789abcdefghijklmnopqrstuvwxyz]
    for char in (text):
        char = ord(char) | 32              # to lowercase
        if   char >= 48 and char <=  57:   # count numbers
            charcount[char-48] += 1
        elif char >= 97 and char <= 122:   # count letters, ignore other
            charcount[char-87] += 1

    charsum = sum(charcount)            
    if charsum == 0: return False    # no valid chars in the string
    tlodd = charsum % 2              # odd text length flag
    for i in charcount:
        if   i%2 == 0: continue
        elif i%2 and tlodd:          # odd-sized string can have 1 unpaired char
            tlodd = 0                      
        else:                        # another odd count
            return False
    return True

Single iteration, used separate sum(charcount) rather than count inside the loop as it turns out to be faster. Settled on no O(n) string operations at the cost of some speed to keep memory use low.
repl.it


#28

Here is my interesting take on the Basic Challenge in Python 2.7 https://repl.it/JEHj/29

After realizing that most entries determine whether or not a word could even be considered before testing, my code just goes ahead and brute forces generation and testing of permutations. Due to not enough memory, my code only works for up to 10 character strings (not counting whitespace).

# First, I defined how to check if a word is a palindrome by reversing the string and comparing it to the original.
def isPalindrome(text):
    def reverse(text):
        anti_text = ""
        for char in text[::-1]:
            anti_text += char
        return anti_text
    if reverse(text) == text:
        return True
    else:
        return False

# Next, I defined how to generate a list of all possible permutations of a string. I did this using recursion. As a result, the program is very sluggish if the length of the string is longer than seven characters (not counting whitespace) and will actually run out of memory for strings longer than 10 characters (not counting whitespace).
def getPerms(text):
    if len(text) == 1:
        return text
    recursive_perms = []
    for c in text:
        for perm in getPerms(text.replace(c, "", 1)):
            recursive_perms.append(c + perm)
    return recursive_perms

# Next, I went through and checked if each permutation was a palindrome. If one or more permutations are palindromes, it returns true. If no permutations are palindromes, it returns false.
def isPermPalindrome(text):
    text = text.replace(" ", "")
    word = text.lower()
    perms = getPerms(word)
    result = bool
    for perm in perms:
        if isPalindrome(perm) == True:
            result = True
    if result == True:
        return True
    else:
        return False

test = raw_input("Input:")    
print "Output:", isPermPalindrome(test)

#29

Consider this:

def isPalindrome(text):
    return text == text[::-1]

As for memory problems, try converting your recursive function into a generator (read up on yield) so you can iterate on it directly. Also if the objective is to test whether at least 1 palindrome exists, break immediately after finding the first one.


#30

Python 3 All difficulties

# Program to test if a given string is a permutation of a palindrome.

# inp = input
def isPermPalindrome(inp):
    
    # Make input into list of lowercase input
    inp = list(inp.lower())

    # Remove everything that is not alphanumeric
    for char in inp:
        if char.isalnum() == False:
            inp.remove(char)

    # Create variable and loop though to see if there is only 0 or 1 odd char
    num_of_odd_char = 0

    for char in inp:
        if inp.count(char) % 2 == 1:
            num_of_odd_char += 1
            inp.remove(char)

    # If there is more than 1 odd character counted it is not a palindrome
    if num_of_odd_char > 1:
        return False
    else:
        del num_of_odd_char

    return True

isPermPalindrome("Science Bros.")
print(isPermPalindrome("Science Bros."))

#31

Excuse me, while I go hit my head against the wall a couple thousand times...

Anyway, here is my new code, based upon your recommendations... https://repl.it/JEHj/36

# First, I defined how to check if a word is a palindrome by reversing the string and comparing it to the original.
def isPalindrome(text):
    return text == text[::-1]

# Next, I defined how to generate a list of all possible permutations of a string. I did this using recursion. 
# As a result, the program is very sluggish if the length of the string is longer than seven characters (not counting whitespace),
# and will actually run out of memory for strings longer than 10 characters (not counting whitespace). 
def getPerms(text):
    if len(text) == 1:
        return text
    recursive_perms = []
    for c in text:
        for perm in getPerms(text.replace(c, "", 1)):
            recursive_perms.append(c + perm)
    return recursive_perms

# Next, I checked if any permutation was a palindrome. If any permutation is a palindrome, it returns True and breaks. 
# If no permutations are palindromes, it returns False.
def isPermPalindrome(text):
    text = text.replace(" ", "")
    word = text.lower()
    perms = getPerms(word)
    result = False
    for perm in perms:
        if isPalindrome(perm) == True:
            result = True
            break
    return result

# This is just the code to run test instances.
test_1 = raw_input("Input:")    
print "Output:", isPermPalindrome(test_1)
test_2 = raw_input("Input:")
print "Output:", isPermPalindrome(test_2)
test_3 = raw_input("Input:")
print "Output:", isPermPalindrome(test_3)

# Side note, this program works well for some of the most common single-word palindromes and their corresponding permutations.
# Unfortunately, the word tattarrattat (The longest palindromic word in the Oxford English Dictionary) does not return anything.

#32

Basic difficulty. Python.

To determine weather a string could be a palindrome it has to have either even number of each letter or even number of each letter + 1. To test that I reduce the string to set of unique letters and then I search for letters that occur uneven number of times. Any string with more than one letter without pair is not able to produce palindrome = False.

 def isPermPalindrome(s=None):                                                    
     singles = 0                                                                  
     s = s.lower()                                                                
     for l in set(s):                                                             
         if s.count(l) % 2 != 0:                                                  
             singles += 1                                                         
     if singles > 1:                                                              
         return False                                                             
     else:                                                                        
         return True

#33

Sorry for the super late response!

This is a neat little challenge.
As almost everyone realised creating every permutation possible and checking if that is a palindrome would be crazy inefficient.

The best solution is to make sure each letter has a pair, at the end at most one letter can be left,

In my opinion, the two most elegant solutions using this criteria were the first two. So the winners are @betamaster97156 and @tagrockstar79958. Congrats guys!

Don’t forget there is a new challenge published every Wednesday so keep coming back for more!