Palindrome Checker : A sleek implementation of the double-ended queue data structure.
Tags: python, beginners, datastructures, algorithms
Published: 2020-04-04 12:15:34

I am indeed fascinated by __data structures__ and __algorithms__. Besides the fact that they form part of the foundations of programming, landing your first job as a data scientist or a developer might depend on your ability to write a code to implement an algorithm. This could be *searching*, *sorting*, *tree-traversal* and a host of other algorithms. It sure takes constant practice to get a hang of the basic types. Checking if a string is a __palindrome__ is a popular interview problem. In this article I will give you two methods to solve this problem using python built-in modules.

The queue is data structure akin to a queue of customers in an ice cream shop. In this scenario, customers join the queue at the rear and exit at the front of the line after been served.
The ordering of the queue is *First In First Out* (FIFO) as opposed to the *Last In First Out* (LIFO) ordering in a stack. A double ended queue is a unique implementation of a queue in which there is the possibility to remove items from the front and the rear.

## Implementing a double ended queue class.
The three methods of the queue are 
- enqueue: used to insert items onto a queue (same as the *push* method of a stack).
- dequeue: used to delete items from the queue (same as the *pop* method of a stack).
- isempty: used to check if the queue still contains items (same as the *size* attribute of a stack)
To understand how the double ended queue works, let us implement a double eneded queue class.

```python
class DeQueue:
    def __init__(self, queue):
        self._queue = list(queue)
    def getqueue(self):
        return self._queue
    def enqueue(self, item):
        return self._queue.append(item)
    def dequeue_left(self):
        return self._queue.pop(0)
    def dequeue_right(self):
        return self._queue.pop(-1)
    def isEmpty(self): #method to tell if the queue is empty
        return(len(self._queue) == 0)
```
Now we instantiate our class to create a __DeQueue__ object and run an example to see if it works.
``` python
dq = DeQueue(range(10))

for i in range(10, 15):
    dq.enqueue(i)
    v = dq.dequeue_left()
    print(dq.getqueue())
# results
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
```
The built-in **collections** module provides a beautiful *deque* class.
``` python
from collections import deque
dq = deque(range(10))
dq
# results
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

```
We repeat the above example to see if we get the same results.

``` python
for i in range(10, 15):
    dq.append(i)
    v = dq.popleft()
    print(dq)
# and for sure we get the same output as our class
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
deque([3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
deque([4, 5, 6, 7, 8, 9, 10, 11, 12, 13])
deque([5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

```
Having describe in brief how the double ended queue works, lets try to implement our palindrome checker using the *deque* class from collections module. We also import the ascii_lowercase to filter out just letters or the alphabet and ignore *punctuations* - this makes our palindrome checker very robust.

## The implementation is as follows:
- First, we load our string, or numbers, and we check the type since numbers can also be palindromic for example *1221*, *1234321*.
- If the character is a letter of the alphabet, we convert to a lower case character
- Then we loop through using a while loop to check the length of the letters. While the loop runs, we pop from both sides and compare the resulting characters.
- Finally we return false if the characters do not match and True otherwise
- The __magic__ function *%%file* enables us to write the code to a .py file.

``` python
%%file palindrome.py
from collections import deque
from string import ascii_lowercase

def palindrome(sentence):
    letters = deque() # we start with an empty
    for char in sentence:
        if isinstance(char, int):
            letters.append(char)
        else:
            char = char.lower()
            if char in ascii_lowercase:
                letters.append(char)
                
    while len(letters) > 1:
        if letters.popleft() != letters.pop():
            return False
    return True
```
To test our palindrome checker, I have gathered a list of palindromes in a text file named 'palindrome.txt'

```python
with open('palindrome_template.txt') as fh:
    print("we have {} palindromes".format(sum(1 for line in fh)))
    for lnum, line in enumerate(fh):
        if lnum > 10:
            break
        print(line[:-1]) 
# result
we have 19 palindromes

with open('palindrome_template.txt') as fh:
    for lnum, line in enumerate(fh):
        if lnum > 10:
            break
        print(line[:-1]) 
# results
Are we not pure? 'No, sir!' Panama's moody Noriega brags. 'It is garbage!' Irony dooms a man-a prisoner up to new era.

Are we not drawn onward, we few, drawn onward to new era?

Never odd or even.

Stressed desserts

racecar

kayak
```
## Writing a unit test for our functions
Our __unit test__ will be carried out using __pytest__. The following code illustrates the unit test implementation. The *setup_class* method is performed once for the whole class while the *teardown* method cleans up the state after our test.

``` python
%%file test_palindrome.py
import pytest, os, shutil
import palindrome

class TestPalindrome(object):
    pal_file_template = 'palindrome_template.txt'
    pal_file_testor = 'pal_test.txt'
    
    def setup_class(self):
        shutil.copy(TestPalindrome.pal_file_template, TestPalindrome.pal_file_testor)
    def teardown_class(self):
        os.remove(TestPalindrome.pal_file_testor)
    def test_words(self):
        new_dromes = [str(line) for line in open(TestPalindrome.pal_file_testor)]
        for new_drome in new_dromes:
            assert palindrome.palindrome(new_drome) == True
```
![output](https://dev-to-uploads.s3.amazonaws.com/i/aa7ingg98y9n9lj718qg.png)

## Bonus implementation - Using the SequenceMatcher from the difflib module.

In this bonus example, I use the *Sequencematcher* from the __difflib__ module to execute the same palindrome checker. However I will not go into details of how this works. Basically, we strip punctuations using the maketrans(). Then we compare a string and its reversed form and return True if both strings have a match of 1 or return False if the match is less than 1.

``` python
import difflib, string
def my_palindrome(str):
    trans = str.maketrans('', '', string.punctuation)
    str = str.lower().translate(trans)
    s1 = str.replace(' ', '')
    s2 = s1[::-1]
    match = difflib.SequenceMatcher(None, s2, s1, False).ratio()
    if match != 1:
        return False
    return True   
```
Let's test our second function:

``` python

long_str = "Are we not pure? 'No, sir!' Panama's moody Noriega brags. 'It is garbage!' Irony dooms a man-a prisoner up to new era."

my_palindrome(long_str)
# result
True
```

I hope you learnt something and I hope this post was not too long. I look forward to receiving your feedback so I could improve future posts.

\#Staysafe.