Conditional & Repetitive Statements, continued...¶

Let's see several examples of using conditional and repetitive statements for implementing useful algorithms:

Python allows us to check if a value is inside of a container with the membership operator:

In [1]:
5 in [100, 4, 48, 7]
Out[1]:
False

Let's code this ourselves. The code below can be used for finding out if a number is in a list of numbers:

In [2]:
# Number to check
num = 9

# Container to search
lst = [100, 4, 48, 5]

num_in_list = False

for el in lst:
    if el == num:
        num_in_list = True
        break

print(num_in_list)

False

The code, by default, assumes that the searched number is not in the list. We then iterate over the list, and search for the number using equality. If the number does exist in the list, then we know that we don't have to search any more, so we can immediately get out of the loop (with break).

By changing the code very slightly, we can also find out if a list contains a number bigger than the given number:

In [2]:
num = 9

lst = [100, 4, 48, 5]

bigger_than_num = False

for el in lst:
    if el > num:
        print(el, '>', num)
        bigger_than_num = True
        break

print(bigger_than_num)

100 > 9
True

Here's an example of doing decimal to binary conversion. You can try it with any positive value:

In [3]:
# Input number
num_decimal = 19

# Let's keep the value of num_decimal, by using a temporary variable
temp = num_decimal
remainders = []

while temp > 0:
    dividend = temp
    quotient = temp // 2
    remainder = temp % 2
    
    remainders.append(remainder)
    temp = quotient
    print(dividend, '/ 2 = ', quotient, 'Remainder:', remainder)

# Convert the result to a string
# First, invert the list of bits
remainders = remainders[::-1]
num_binary = ''
for bit in remainders:
    num_binary = num_binary + str(bit)
print(f"{num_decimal} = '{num_binary}'")

19 / 2 =  9 Remainder: 1
9 / 2 =  4 Remainder: 1
4 / 2 =  2 Remainder: 0
2 / 2 =  1 Remainder: 0
1 / 2 =  0 Remainder: 1
19 = '10011'

The following example computes the AND operation between two bitstrings, bit-per-bit:

In [4]:
str1 = '1010'
str2 = '1100'

n = len(str1)

i = 0
answer = []
while i < n:
    # Get the boolean value of the first argument
    bool1 = bool(int(str1[i]))
    bool2 = bool(int(str2[i]))
    
    result = bool1 and bool2
    
    if result == True:  # Note: You could also just write 'if result:' here
        answer.append('1')
    else:
        answer.append('0')
    i += 1

# Print out the result
answer_str = ''
for bit in answer:
    answer_str = answer_str + bit
print(f'{str1} AND {str2} = {answer_str}')
# A faster way to accomplish this is by using the code in the comment below
# ''.join(answer)

1010 AND 1100 = 1000

As you recall, we wrote some code to convert decimal numbers to binary.

Similarly, we can write an algorithm to convert a binary string to a decimal number, as follows:

In [5]:
input_str = '10011'

# Makes the code more reasonable
input_inverted = input_str[::-1]
n = len(input_inverted)

total = 0

power = 0
for i in range(n):
    bit = input_inverted[i]
    total += int(bit) * (2 ** power)
    power += 1 

print(f'{input_str} = {total}')

10011 = 19

Averaging a list of numbers:

In [6]:
lst = [1, 2, 4123, 1, 231]

i = 0
n = len(lst)
total = 0
while i < n:
    total += lst[i]
    i += 1
total / n
Out[6]:
871.6
In [7]:
lst = [[1,3], [4,5,6], 7, [10,20]]

new_lst = []

for el in lst:
    if type(el) != list:
        new_lst.append(el)
    else:
        # Compute the average of the list
        i = 0
        n = len(el)
        total = 0
        while i < n:
            total += el[i]
            i += 1
        average = total / n
        new_lst.append(average)
print(new_lst)

[2.0, 5.0, 7, 15.0]

The following algorithm takes an input list, and replaces each nested list of numbers with the average of the list:

In [8]:
lst = [20, 30, [4, 8], [10, 20, 0]]

new_lst = []
for el in lst:
    # If the element is not a list, just copy it to the new list
    if type(el) != list:
        new_lst.append(el)
    else:
        # Compute the average of the list (using the previous code)
        i = 0
        n = len(el)
        total = 0
        while i < n:
            total += el[i]
            i += 1
        average = total / n
        # Instead of the list, add the average of the list to the new list
        new_lst.append(average)
print(new_lst)

[20, 30, 6.0, 10.0]

Here's an example implementation of bubble sort, which is a method for sorting a list of numbers so that they are ordered from smallest to largest:

In [9]:
import random

num_elements = 10

# Generate a list of random numbers between 0 and 100
lst = [random.randint(0, 100) for i in range(num_elements)]
print('Input: ', lst)
n = len(lst)

# Loop until we make no swaps
while True:
    swapped = False
    for i in range(n-1):
        # Check side-by-side elements
        if lst[i] > lst[i+1]:
            lst[i], lst[i+1] = lst[i+1], lst[i]
            swapped = True
    if not swapped:
        break

# If we're here, then we the list is ordered:
print('Sorted:', lst)

Input:  [18, 77, 56, 92, 43, 47, 99, 89, 6, 100]
Sorted: [6, 18, 43, 47, 56, 77, 89, 92, 99, 100]

Finally, here is our implementation for run-length encoding, from the workbook:

In [10]:
str1 = 'AAAABBCCCDDDDDDE'

new_string = ''


current_character = '@' # @ is a placeholder token, it won't actually be printed.
current_repetition = 0 # Holds the count of repetitions of the current character

for el in str1:
    if current_character == el:
        current_repetition += 1
    else:
        if current_repetition > 0:
            new_string = new_string + str(current_repetition) + current_character
        current_character = el
        current_repetition = 1
if current_repetition > 0:
    new_string = new_string + str(current_repetition) + current_character
new_string
Out[10]:
'4A2B3C6D1E'
In [16]:
ord('A')
Out[16]:
65
In [17]:
chr(65)
Out[17]:
'A'
In [21]:
import math
In [22]:
math.cos(math.pi)
Out[22]:
-1.0
In [20]:
import random

len_string = 20
input_str = ''
for _ in range(len_string):
    input_str  = input_str + chr(random.randint(ord('A'), ord('Z')))
print(input_str)



d = {}

for character in input_str:
    if character in d:
        d[character] += 1
    else:
        d[character] = 1

d

LGFZYVAINWRLZCCLBDNR
Out[20]:
{'L': 3,
 'G': 1,
 'F': 1,
 'Z': 2,
 'Y': 1,
 'V': 1,
 'A': 1,
 'I': 1,
 'N': 2,
 'W': 1,
 'R': 2,
 'C': 2,
 'B': 1,
 'D': 1}
In [ ]: