Strings—Python

Python has native support for Strings (which is basically text). Many computer programs need to process text data and Python’s string type has powerful features to make the lives of developers easy!

String Literals

Here are a few examples of how to create strings in Python using literals.

sq = 'String made with Single Quotes'
dq = "String made with double quotes"
tq = """String with triple quotes"""

Double quote strings let you embed an apostrope character without escaping it. So you can write “I’m a cat” as a string literal in Python. Triple quote strings allow white space and line breaks in the string.

Individual Characters

Python strings support the index operator, so you can access characters in a string using [n] where n is the position of the character you wish to access. Here are a few ways to process strings by individual characters.

kitties = 'I like kitties'

# Access by index
for i in range(0, len(kitties)):
    print(kitties[i])

# Access with iteration
for c in kitties:
    print (c)

Useful Methods

The Python string class has many useful methods. You can view them all at Python documentation. Here are some of the ones I use the most.

islower()

This checks if a string is all lower case characters.

kitties = 'i like kitties'
if kitties.islower():
    print(kitties, ' is lower case')
else:
    print(kitties, ' is not lower case')

lower()

Python Strings are immutable, but you can use lower to convert a string to all lower case.

kitties = 'I like kitties'

if not kitties.islower():
    kittens = kitties.lower()
    print(kittens) 

isupper()

This method tests if a string is all upper case.

kitties = 'I LIKE KITTIES'

if kitties.isupper():
    print(kitties, ' is upper case')
else:
    print(kitties, ' is not upper case')

upper()

This method converts the string to upper case.

kitties = 'i like kitties'

if not kitties.isupper():
    cat = kitties.upper()
    print(cat)

isnumeric()

Checks if the strings is a numbers. This is useful if you want to convert a string to an int.

number_str = '3'

if number_str.isnumeric():
    number = int(number_str)

format()

This is useful for using a generic string that allows you to replace {} with values.

fm = 'I have {} kitties'
print(fm.format(3')
# Prints: I have 3 kitties

Circular Linked List—Python

The circular linked list a variant of the singly linked list where the last Node links to the head rather than None. Since the list contains a circular reference to the Head, we can navigate a circular linked list starting at any index rather than starting at the head node.

Here is the code for a circular linked list implementation with unit tests. We won’t dicuss the unit tests in this post, but we will go over the linked list implementation.

from enum import Enum


class NodeConstants(Enum):
    FRONT_NODE = 1


class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()


class CircularLinkedList:
    def __init__(self):
        self.head = Node(element=NodeConstants.FRONT_NODE)

        self.head.next_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current != self.head:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node)
        self.head.next_node = node

    def insert_last(self, data):
        current_node = self.head.next_node

        while current_node.next_node != self.head:
            current_node = current_node.next_node

        node = Node(element=data, next_node=current_node.next_node)
        current_node.next_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_pos += 1
                    current_node = current_node.next_node

                node = Node(data, current_node.next_node)
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head.next_node = self.head.next_node.next_node

    def remove_last(self):
        current_node = self.head.next_node

        while current_node.next_node.next_node != self.head:
            current_node = current_node.next_node

        current_node.next_node = self.head

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_node = current_node.next_node
                    current_pos += 1

                current_node.next_node = current_node.next_node.next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError


import unittest
from random import randint


class TestCircularLinkedList(unittest.TestCase):
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    def test_init(self):
        dll = CircularLinkedList()
        self.assertIsNotNone(dll.head)
        self.assertEqual(dll.size(), 0)

    def test_insert_front(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_front(name)

        self.assertEqual(dll.fetch(0), TestCircularLinkedList.names[4])
        self.assertEqual(dll.fetch(1), TestCircularLinkedList.names[3])
        self.assertEqual(dll.fetch(2), TestCircularLinkedList.names[2])
        self.assertEqual(dll.fetch(3), TestCircularLinkedList.names[1])
        self.assertEqual(dll.fetch(4), TestCircularLinkedList.names[0])

    def test_insert_last(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(len(TestCircularLinkedList.names) - 1):
            self.assertEqual(dll.fetch(i), TestCircularLinkedList.names[i])

    def test_insert(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        pos = randint(0, len(TestCircularLinkedList.names) - 1)

        dll.insert('Teddy', pos)
        self.assertEqual(dll.fetch(pos), 'Teddy')

    def test_remove_first(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_first()

    def test_remove_last(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        for i in range(dll.size(), 0, -1):
            self.assertEqual(dll.size(), i)
            dll.remove_last()

    def test_remove(self):
        dll = CircularLinkedList()
        for name in TestCircularLinkedList.names:
            dll.insert_last(name)

        dll.remove(1)

        self.assertEqual(dll.fetch(0), 'Bob Belcher')
        self.assertEqual(dll.fetch(1), 'Tina Belcher')
        self.assertEqual(dll.fetch(2), 'Gene Belcher')
        self.assertEqual(dll.fetch(3), 'Louise Belcher')


if __name__ == '__main__':
    unittest.main()

NodeContants

NodeConstants is an example of Python’s enumeration. A circular linked list requires a distinct head node that the client code can easily identify. Without a distinct head node, we could easily introduce an infinate loop when traversing the linked list. We are going to use NodeContants to help identify the head node.

from enum import Enum


class NodeConstants(Enum):
    FRONT_NODE = 1

There are other ways to indentify the head node, so using enumerations isn’t required. It does give us a way to show off how to do enumerations in Python for those readers who are interested.

Node

We can use the same Node class that we used in singular linked list. Like all linked lists, the Node class holds the data stored in the list and a reference to the next Node in the list.

class Node:
    def __init__(self, element=None, next_node=None):
        self.element = element
        self.next_node = next_node

    def __str__(self):
        if self.element:
            return self.element.__str__()
        else:
            return 'Empty Node'

    def __repr__(self):
        return self.__str__()

CircularLinkedList

This class is the work house of this module and provides us with the linked list implementation. It’s not very different than the singular linked list implementation.

class CircularLinkedList:
    def __init__(self):
        self.head = Node(element=NodeConstants.FRONT_NODE)
        self.head.next_node = self.head

    def size(self):
        count = 0
        current = self.head.next_node

        while current != self.head:
            count += 1
            current = current.next_node

        return count

    def insert_front(self, data):
        node = Node(element=data, next_node=self.head.next_node)
        self.head.next_node = node

    def insert_last(self, data):
        current_node = self.head.next_node

        while current_node.next_node != self.head:
            current_node = current_node.next_node

        node = Node(element=data, next_node=current_node.next_node)
        current_node.next_node = node

    def insert(self, data, position):
        if position == 0:
            self.insert_front(data)
        elif position == self.size():
            self.insert_last(data)
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_pos += 1
                    current_node = current_node.next_node

                node = Node(data, current_node.next_node)
                current_node.next_node = node
            else:
                raise IndexError

    def remove_first(self):
        self.head.next_node = self.head.next_node.next_node

    def remove_last(self):
        current_node = self.head.next_node

        while current_node.next_node.next_node != self.head:
            current_node = current_node.next_node

        current_node.next_node = self.head

    def remove(self, position):
        if position == 0:
            self.remove_first()
        elif position == self.size():
            self.remove_last()
        else:
            if 0 < position < self.size():
                current_node = self.head.next_node
                current_pos = 0

                while current_pos < position - 1:
                    current_node = current_node.next_node
                    current_pos += 1

                current_node.next_node = current_node.next_node.next_node
            else:
                raise IndexError

    def fetch(self, position):
        if 0 <= position < self.size():
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position:
                current_node = current_node.next_node
                current_pos += 1

            return current_node.element
        else:
            raise IndexError

__init__

We initialize the linked list by creating a head Node and then pointing it’s next_node at itself.

def __init__(self):
    self.head = Node(element=NodeConstants.FRONT_NODE)
    self.head.next_node = self.head

In this case, we will use our NodeConstants.FRONT_NODE to help us indentify the head of the list in the debugger. We don’t actually need this but it does help make the code more clear.

size

This method returns the number of elements contained in the linked list.

def size(self):
    count = 0
    current = self.head.next_node

    while current != self.head:
        count += 1
        current = current.next_node

    return count

We begin by making a count variable and a current variable. Current points at self.head.next_node because we aren’t counting self.head. Now we are going to loop until current == self.head. We don’t need to check for None in this case because we don’t have any such Nodes in this implementation.

As we loop, we increment count by one and then advance current to the next node in the list. Eventually, current points at self.head and we terminate the loop at this point. We then return the count.

insert_front

There isn’t much work to do to insert a Node at the beginning of the list.

def insert_front(self, data):
    node = Node(element=data, next_node=self.head.next_node)
    self.head.next_node = node

We create a new Node and point it’s next node at self.head.next_node. Then we just need to point self.head.next_node at the new Node.

insert_last

To insert a Node at the end of the list, we need to tranverse the list to right before self.head.

def insert_last(self, data):
    current_node = self.head.next_node

    while current_node.next_node != self.head:
        current_node = current_node.next_node

    node = Node(element=data, next_node=current_node.next_node)
    current_node.next_node = node

Once again, we have a current_node that requires us to start at self.head.next_node. We then enter a loop that terminates when current_node.next_node == self.head to avoid an infinate loop.

Once we find our insertion point, we create a new Node and point it’s next_node to current_node.next_node (which happens to be self.head). Then current_node.next_node is updated to point at Node.

insert

The insert method let’s us support insertions in the middle of the list. It works by traversing the list to right before the desired position and performing an insertion.
Keep in mind this method has four possible scenerios it must take into account.

  1. Position is 0 -> insert at the front
  2. Position == size() -> insert the end
  3. Position size() -> throw exception
  4. Position > 0 and Position Perform insertion
def insert(self, data, position):
    if position == 0:
        # Case 1
        self.insert_front(data)
    elif position == self.size():
        # Case 2
        self.insert_last(data)
    else:
        if 0 < position < self.size():
            # Case 4
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position - 1:
                current_pos += 1
                current_node = current_node.next_node

            node = Node(data, current_node.next_node)
            current_node.next_node = node
        else:
            # Case 3
            raise IndexError

The cases have been identified with the comments. In cases one and two, we are simply going to reuse code by calling self.insert_front or self.insert_last respectively. We handle case three by raising IndexError to indicate a programming error.

Case four works similar to other other insertions. We start with current_node at self.head.next_node and current_pos at 0. Then we iterate through the list until we reach the node right before the specified position (position – 1).

After exiting the while loop, we create a new Node and point it's next_node at current_node.next_node. The we update current_node.next_node to point at our new Node which now resides at our position.

remove_first

When removing nodes from the front of the list, we reassign self.head.next_node rather than self.head.

def remove_first(self):
    self.head.next_node = self.head.next_node.next_node

Remember that the last Node in this linked list always points at self.head. If we accidently reassigned self.head rather than self.head.next_node, we would break our linked list. However, when we update self.head.next_node to point at self.head.next_node.next_node, we are removing the Node currently located at self.head.next_node.

The removed Node gets garbage collected by the Python runtime environment and the linked list is shrunk by one element.

remove_last

It’s a fairly painless process to remove elements from the end of a circular linked list. We simply need to advance to the element located two positions before self.head and then point that Node’s next_node at self.head.

def remove_last(self):
    current_node = self.head.next_node

    while current_node.next_node.next_node != self.head:
        current_node = current_node.next_node

    current_node.next_node = self.head

We begin with current_node pointing at self.head.next_node and then enter a while loop. Notice that the condition on the while loop is current_node_next_node.next_node != self.head. We want to advance to the second to last element in this list.

Once we have positioned current_node to the proper index in the list, we remove the last node by pointing current_node.next_node at self.head. The removed Node ends up getting grabage collected by Python’s runtime.

remove

The remove method supports removing items from the middle of the list. It has to account for the same cases as insert.

def remove(self, position):
    if position == 0:
        # Case 1
        self.remove_first()
    elif position == self.size():
        # Case 2
        self.remove_last()
    else:
        if 0 < position < self.size():
            # Case 3
            current_node = self.head.next_node
            current_pos = 0

            while current_pos < position - 1:
                current_node = current_node.next_node
                current_pos += 1

            current_node.next_node = current_node.next_node.next_node
        else:
            # Case 4
            raise IndexError

Once again, we are going to dicuss case 3. We start with current_node pointing at self.head.next_node and current_pos = 0. We traverse the list until we arrive at the Node located before position. Now we nust point current_node.next_node at current_node.next_node.next_node. The removed Node gets garbage collected by the Python runtime.

fetch

This method let’s us get data out of the list.

def fetch(self, position):
    if 0 <= position < self.size():
        current_node = self.head.next_node
        current_pos = 0

        while current_pos < position:
            current_node = current_node.next_node
            current_pos += 1

        return current_node.element
    else:
        raise IndexError

After checking position to make sure it's valid, we traverse the list until we arrive at the position. Then we return current_node.element. If position isn't valid, we raise an exception.

Conclusion

This code shows an example a circular linked list, but it’s a simple implementation that we could optimize. This implementation always starts at self.head and traverse the list to a required position, but it could operate by tracking the most recently accessed Node and starting traversals from that point rather than always starting at the front of the list.

Ordered Linear Search—Python

Ordered Linear Searche’s are a varient of Unordered Linear Search. The main difference is that this algorithm expects the search list to be sorted prior to searching. For this reason, the Ordered Linear Search can be a little more efficient than it’s Unordered varient.

Here’s the code

from random import shuffle


def ordered_linear_search(search_list, data):
    for i in range(len(search_list) - 1):
        if search_list[i] == data:
            # Return the index of the item
            return i
        elif search_list[i] > data:
            # The idea here is to fail at this
            # point because search_list isn't sorted
            return None
    # We didn't find our item, so return None
    return None


if __name__ == '__main__':
    names = ['Bob Belcher',
             'Linda Belcher',
             'Tina Belcher',
             'Gene Belcher',
             'Louise Belcher']

    print('Shuffling names')
    shuffle(names)

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

    teddy_index = ordered_linear_search(names, 'Teddy')
    if teddy_index:
        print('Teddy was found at ', str(teddy_index))
    else:
        print('Teddy was not found')

    print('Now sorting...')
    names.sort()

    linda_index = ordered_linear_search(names, 'Linda Belcher')
    if linda_index:
        print('Linda Belcher found at ', str(linda_index))
    else:
        print('Linda Belcher was not found')

When run, you will notice that first we do not find the name ‘Linda Belcher’ because the list is shuffled. After sorting, the search will identifiy ‘Linda Belcher’ at index 2.

Shuffling names
Linda Belcher was not found
Teddy was not found
Now sorting...
Linda Belcher found at  2

Continue—Python

The continue statement is used in Python to return program execution to the beginning of a loop. For a review of loops see for loops and while loops.

Let’s begin with a code example

names = ['Bob Belcher',
         'Linda Belcher',
         None,
         'Louise Belcher',
         'Tina Belcher',
         None,
         'Gene Belcher']

bob = ''
for name in names:
    if name is None:
        continue    # Go back to the top of the loop since
                    # since we can't do comparisons on None
    if 'Bob' in name:
        bob = name

In this situation, we have a list object that has a combination of Strings and Python’s None object. What we are doing is trying to find ‘Bob’ but to do that, we need a way to skip over the None objects or our program will crash. Lines 11 and 12 in the above code snippet do the job of checking if the elemnt name is None first. If it turns out that the element is None, line 12 uses the continue statement to return the execution to the top of the loop.

The continue keyword is useful when we process a loop of mixed types. Let’s take another example of where the keyword is also useful.

while True:
    fileName = input('Enter a file name => ')
    try:
        lines = open(fileName, 'r').readlines()
    except FileNotFoundError:
        print('Try a different file')
        continue # We can't do the next part because
                 # couldn't open the file
    for line in lines:
        print(line)

This code snippet asks the user for a file and then attempts to open the file for processing. However, if for some reason we can’t open the file, the program won’t be able to process lines 9 and 10. For this reason, we use the continue keyword to return program execution to the top of the loop and give the user an opportunity to open a different file.

Break Statement—Python

I’ve done a few posts now on loops. To review, Python has two kinds of loops: while loops and for loops.

I can think of plenty of times that we want to create an infinate loop. To review, an infintate loop is a loop that never ends. Consider this code.

while True:
    pass

Should you run this code, the program will never terminate because the loop condition is always True. In many cases, infinate loops are the result of programming errors, but let’s consider a menu driven program like this:

while True:
    print('1) New File')
    print('2) Open File')
    print('3) Save File')
    print('4) Exit...')

    choice = input('Enter choice => ')
    if choice == 1:
        pass # do something with a new file
    elif choice == 2:
        pass # do something to open a file
    elif choice == 3:
        pass # do something to save a file
    elif choice == 4:
        break # exit this loop and end the application

In this case, we want the program to program to continue to repeat this main menu until the user enters 4. That’s where the magic break keyword comes into play.

The break keyword liternally means to break out of a loop. This example is a common application of the loop but it doesn’t always have to be used in infinate loops. Let’s try and example with the for loop.

names = ['Bob Belcher',
         'Linda Belcher',
         'Louise Belcher',
         'Tina Belcher',
         'Gene Belcher']

bob = ''
for name in names:
    if 'Bob' in name:
        bob = name
        break   # There's no need to keep looping through
                # the rest of the list because we have found Bob

Nested Loops

In previous posts, we covered while and for loops. Python let’s us nest loops. Let’s start with an example.

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    for cell in row:
        print(str(cell))
    print('\n', end=' ')

When run, we get the following output

1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1

So why does this work? In our example, we have data structure that can be thought of in terms of an x,y grid. Basically, it’s a list that contains two lists: one list for each row.

When we begin our loop with for row in grid: we are starting a for loop with a variable named row. Everytime this loop updates, the row variable is assigned the next list object inside of the grid variable.

Now our next line of code is also a for loop: for cell in row. Remeber that row is a list object that corresponds to a row in the grid list. Each item inside of row is a number, so when this loop runs, the variable cell gets updated with a number inside of the list that is currently assigned to the row variable.

We can mix our loops also

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    index = 0
    while index < len(row):
        print(str(row[index]))
        index += 1

This code delivers the same output as the first example. The differnce is that this time, we have a while loop as our nested loop rather than a for loop. As you can see, this code is a little more complex than the first example, but the point of it was to demonstrate that it's possible to mix and match loops.

Also keep in mind that you can have loops that are infintely nested as long as your hardware can handle it. However, if you find that you are nesting loops deeper than two loops, then consider restructing your code since nesting loops that deep will impact the code's reability and make it difficult to debug.

While Loops—Python

Sometimes we need to repeat code in our programs for a certain number of executions. Let’s consider the classic triangle problem:

=
==
===
====
=====
======
=======
========
=========
==========

This is a typical problem that computer science students use to learn about loops. In this problem, we have to print a triangle to the console where the size is specified by the user. Since we don’t know the size of the triangle ahead of time, we won’t be able to do something like this:

print('=')
print('==')
print('===')
# continued...

Our issue is that right now, this code can only print a triangle that has a base size of three. If the user wants ten, we are out of luck. What we need is a programming construct that will continue to build the triangle until it hits the proper size.

Here is the example code of how to do this

size = int(input('Enter the size of the triangle => '))
counter = 0

while counter < size:  # counter < size is the terminating condition.
    # The next two lines repeat as long as condition < size
  print('=' * counter) # Print the triangle
  counter += 1 # Important! Update the counter variable! 

This code accomplishes what we want it to do. This is the output we get when we run this code.

Enter the size of the triangle => 5

=
==
===
====

Let’s talk about why this works. While loops begin with the while keyword followed by a condition. The loop will repeat code inside of the while block as long as the condition is true.

In our case, the condition is counter < size so as long as our counter is less than the size of the triangle that the user specified, our condition will be true and the loop will continue to repeat. As soon as size >= counter the loop will terminate and the program will return to it’s normal execution flow.

Inside of the triangle, we print our triangle and then update our counter variable by 1. It is critical that we update our counter variable because without it, the loop will run forever.

while counter < size:
    print('=' * counter)
print('Loop is over') # Note! We never get to this statement! How come?

The code above will run forever in what is called an 'infinate loop'. The reason this happens is that we fail to increment the counter variable. Remember that loops always run while the terminating condition is true. Since counter is always less than size, our condtion never becomes false and the loop runs forever.
Sometimes we make infinate loops on purpose

while True:
    print('Infinate loop')

Since we are passing the contant True to our loop here, our loop will run forever. It’s on the developer at this point to kill the loop, which will learn when we cover the break keyword.

Finally, Python let’s us add an else statement to while loops that will run once the loop is over.

size = int(input('Enter the size of the triangle => '))
counter = 0

while counter < size:
    print('=' * counter)
    counter += 1
else:
    print('triangle complete') # This code runs when the loop is over