9021_TUT_2

Exercise 1:

This exercise focuses on input validation and formatting floating-point numbers. The goal is to prompt the user to enter a floating-point number between -1 and 1 (exclusive). If the input is valid, the program rounds the number to two decimal places and prints it. Otherwise, it keeps prompting the user until a valid input is provided.
Key Points:

• The program uses a try-except block to catch invalid inputs (e.g., strings that cannot be converted to floats).
• The input() function is wrapped in an infinite while loop to continuously ask for input until the correct condition is met.

In the updated version of Exercise 1, we use the formatting :.2f instead of round(). Here’s the key difference between the two:

• round(): This is a Python built-in function that rounds a number to a specified number of decimal places. For example, round(1.236, 2) will return 1.24. However, the output of round() is still a float, but it does not guarantee a fixed number of decimal places when printed. For instance, round(1.0001, 2) would return 1.0 and only display one decimal place, not two.
• :.2f: This is part of Python’s string formatting and ensures the number is displayed with exactly two decimal places, no matter what the number is. It also rounds the number appropriately. For instance, number = 1.0 formatted as f”{number:.2f}” will print 1.00. This makes :.2f particularly useful for consistent display of decimal places, which is important for formatting output for users.

while True:
    try:
        i = input('Enter a floating point number between -1 and 1 excluded: ')
        number = float(i)
        if '.' not in i:
            raise ValueError
        if -1 < number < 1:
            # not using round() here because it rounds to the nearest even number
            print(f'\nUp to +/-0.005, you input {number:.2f}')
        else:
            raise ValueError
        break
    except ValueError:
        print("You got that wrong, try again!\n")

Exercise 2:

This exercise involves processing a block of text and formatting it into sentences. Each sentence should have its first word capitalized, and the remaining words should be in lowercase. The task is to handle spaces and punctuation properly.

Key Points:

• A regular expression (re.sub) is used to replace multiple spaces with a single space.
• Another regular expression (re.split) is used to split the text into sentences while preserving punctuation marks.
• After splitting, the sentences are processed: the first word is capitalized, and all other words are made lowercase.
• Finally, the processed sentences are recombined into a single formatted text.

Why use re in Exercise 2, and what is re?

In Exercise 2, we use re (Python’s regular expression module) to process and format the text input. Let’s break down why re is used and what it is:

What is re?

re stands for regular expressions, which are powerful tools for matching patterns in strings. The re module in Python allows you to work with regular expressions to search, split, and manipulate text based on specific patterns. Regular expressions are highly flexible and efficient for handling complex string operations.

Why use re in Exercise 2?

In this exercise, we need to handle several complex text manipulations:

1. Replace multiple spaces with a single space: Sentences in the text may have irregular spaces between words, so we need to normalize these spaces. Instead of writing loops or conditions to handle each case, we use re.sub() with a pattern r’\s+’ to easily match all occurrences of one or more spaces and replace them with a single space.
2. Split sentences while preserving punctuation: We need to split the text into individual sentences, where each sentence is followed by punctuation (e.g., ‘.’, ‘!’, or ‘?’). The function re.split(r’([.!?])’, text) allows us to split the text based on punctuation while keeping the punctuation marks, which is crucial for proper sentence reconstruction.

Regular expressions allow us to:

• Efficiently match patterns like spaces or punctuation.
• Perform complex text transformations with minimal code.
• Handle edge cases that would otherwise require more manual handling.

# Assume that the argument text is a string that denotes a text,
# defined as one or more sentences, two successive
# sentences being separated by at least one space,
# the first sentence being possibly preceded with spaces,
# the last sentence being possibly followed by spaces,
# a sentence being defined as at least two words,
# two successive words in a sentence being separated by
# at least one space, a word being defined as a sequence
# of (uppercase or lowercase) letters,
# - possibly followed by a comma for a word that is
#   not the last one in its sentence,
# - definitely followed by a full stop, an exclamation mark
#   or a question mark for a word that is the last one
#   in its sentence.
import re


def f2(text):
    # Use regular expression to replace multiple spaces with a single space
    text = re.sub(r'\s+', ' ', text.strip())

    # Correct way to split sentences while preserving delimiters
    sentences = re.split(r'([.!?])', text)

    # Process sentences and punctuation separately
    new_text = []
    i = 0
    while i < len(sentences)-1:
        sentence = sentences[i].strip()
        if sentence:
            sentence =' '.join(sentence.capitalize().split())
            # Rebuild the sentence and add back the punctuation
            new_text.append(sentence +sentences[i +1])
        i += 2
    return ' '.join(new_text)

Exercise 3:

This exercise works with lists of integers and aims to repeatedly remove the first and last elements of the list as long as they are equal. The list is treated as a double-ended queue (deque) for efficient removal of elements from both ends.

Key Points:

• The deque data structure is used because it provides O(1) operations for popping elements from both ends, which is more efficient than using lists.
• The program checks if the first and last elements of the deque are equal and removes them until this condition is no longer met.
• The deque is converted back to a list before being returned.

Why is deque more efficient than list in Exercise 3?

In Exercise 3, we are frequently removing elements from both the front (left) and the back (right) of the list. This is where using a deque (double-ended queue) from Python’s collections module becomes more efficient compared to using a standard list.

Here’s why:

• List Behavior: When you use a standard list and call list.pop(0) to remove the first (leftmost) element, it requires shifting all the remaining elements one position to the left. This shift operation takes linear time—O(n), where n is the number of elements in the list. This means that for every removal from the front, the larger the list, the slower the operation becomes.

  • Removing from the right side of a list using list.pop() is an O(1) operation (constant time) because no elements need to be shifted, making it efficient only when working from the end of the list.

• Deque Behavior: A deque (double-ended queue) is specifically designed to support efficient append and pop operations from both ends. In a deque, both popleft() and pop() operations take constant time—O(1)—because the deque is implemented as a doubly linked list. This means no elements need to be shifted when popping from the left or right.

  • In Exercise 3, where we need to frequently remove elements from both ends of the list, using a deque ensures that both the removal from the left (popleft()) and the right (pop()) are performed in constant time. This makes the entire process much more efficient, especially for large lists where repeated operations would slow down if we used a standard list.

What is a deque?

A deque (short for “double-ended queue”) is a data structure that allows for fast appending and popping of elements from both ends. It is part of the collections module in Python and is optimized for scenarios where you need to efficiently add or remove elements from both ends of the sequence.

Key Features of deque:

• O(1) time complexity for operations on both ends (append, pop, appendleft, popleft).
• It is implemented as a doubly linked list, meaning each element contains a reference to both the previous and next elements, allowing efficient traversal in both directions.
• deque is ideal for scenarios where you need frequent and efficient insertions and removals from both the front and back of a sequence, unlike a standard list where such operations are costly at the front.

# Assume that the argument L is a list of integers.
#
# For as long as the list has at least two elements
# and the first and last elements of the list are equal,
# pop out those elements.

# def f3(L):
# # Remove the list as long as it has at least two elements and the first and last elements are equal
#     while len(L) > 1 and L[0] == L[-1]:
#         L.pop(0) # Remove the first element
#         L.pop(-1) # Remove the last element
#     return L


from collections import deque

def f3(L):
    L = deque(L)  # Convert the list to a deque for efficient popping from both ends
    # Continue removing elements while there are at least two elements and the first and last are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.popleft()  # Efficiently remove the first element (O(1) operation)
        L.pop()      # Efficiently remove the last element (O(1) operation)
    return list(L)   # Convert the deque back to a list and return it

Exercise 4:

This exercise deals with lists of integers that are in increasing order. The goal is to remove any element whose value is equal to its index in the list. The program iterates over the list and removes such elements, ensuring the index is correctly adjusted after each removal.

Key Points:

• The program uses a while loop and checks if the element at index i is equal to i. If true, it removes the element and does not increment i, so that the next element at the same position is checked.
• The remove() function is used to delete the element, which is appropriate for this task.
• Care is taken to ensure that index adjustments are handled correctly.

The reason we use remove() instead of pop(0) or popleft() in a deque is that we need to specifically remove the value that matches the number we reached. pop() and popleft() remove elements by position, without considering the value, which isn’t suitable for our case.

# Assume that the argument L is a list of integers
# that forms an increasing sequence.
#
# For as long as some member of the list is equal to its index
# in the list, pop out the leftmost such member of the list.

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.remove(L[i])  # Using remove() here since popleft() removes from the left only
        else:
            i += 1  # Only increment i if no element was removed
    return L

Exercise 5:

This exercise works with a circular list of integers. The task is to identify elements that are both larger than one of their adjacent elements and smaller than the other. The result is returned as a dictionary where each key is such an element, and its value is a pair of the adjacent elements (one smaller and one larger).

Key Points:

• The list is treated as circular, meaning the first element is considered adjacent to the last element.
• The program iterates through the list, compares each element with its neighbors, and stores those that meet the criteria.
• For each valid element, the adjacent smaller and larger elements are stored in a dictionary.

To solve this problem, we need to create a dictionary D where each key is an element in the list L that satisfies a certain condition, and the value is a tuple of two elements. The first element of this tuple is the adjacent element that is smaller than the current key, and the second element is the adjacent element that is larger than the current key.

Steps:

1. Loop structure: Check each element.
2. Processing of adjacent elements: Since the list is cyclic, the previous element of the first element is the last element, and the next element of the last element is the first element.
3. Condition check: Find the adjacent elements that are smaller and larger than the current element, and add them to the result dictionary.

# Assume that the argument L is a list of at least 3 distinct integers.
#
# Returns a dictionary D whose keys are those of the members e of L,
# if any, that are
# - smaller than the element right before or right after, and
# - larger than the element right before or right after.
# It is considered that
# - the first member of L is right after the last member of L, and
# - the last member of L is right before the first member of L
# (as if making a ring out of the list).
# For a key e in D, the associated value is the pair whose
# first element is the member of L that is right before or right after
# e and smaller than e, and whose second element is the member of L
# that is right before or right after e and greater than e.

def f5(L):
    D = {}
    for i in range(len(L)):
        m = L[i - 1]
        n = L[(i + 1) % len(L)]
        if n < m:
            m, n = n, m
        if m < L[i] < n:
            D[L[i]] = m, n
    return D

Exercise 6:

This exercise deals with factorizing an integer n into the form 2^k * m, where m is an odd number. If n is negative, the program adds a negative sign to the output. If n is zero, it prints a special message.

Key Points:

• The program uses a loop to divide n by 2 until n is no longer divisible by 2, counting the number of divisions (k).
• The absolute value of n is used to ensure correct handling of negative numbers, and a sign is added to the final result if the original number was negative.
• The program handles the special case where n = 0 by printing a unique message.

More Details:

1. You need to express the given integer n as n = 2^k * m.
   • k represents the number of times n can be divided by 2. In other words, it is the power of 2 in the factorization of n.
   • m is the remaining odd part after dividing out all factors of 2.
2. If n is negative, the output should include a negative sign.
3. Special case: If n = 0, a specific message should be printed.
4. The result is printed directly, not returned.

# Assume that the argument n is an integer.
#
# The output is printed out, not returned.
#
# You might find the abs() function useful.
def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
    else:
        k = 0
        ori = n
        if n < 0:
            sign = '-'
            n = -n
        else:
            sign = ''
        while n % 2 == 0:
            n //= 2
            k += 1
        print(f"{ori} = {sign}2^{k} * {n}")
    return

FOR VERY VERY VERY VERY VERY BIG NUMBER:

When dealing with very large integers, the method of continuously dividing the number by 2 to factor out powers of 2 (2^k) can become inefficient. This is because each division can be costly in terms of computational time, especially for very large numbers with millions or billions of digits. Each division involves recalculating the entire integer, which is slow for large integers.
Using Bit Manipulation:

A much more efficient approach is to use bit manipulation to determine how many times a number can be divided by 2 (i.e., how many factors of 2 it has). This method avoids division altogether and instead directly analyzes the binary representation of the number to count the number of trailing zeros, which correspond to the powers of 2 in the factorization.

Why?

1. Bitwise operations are much faster than arithmetic operations like division, especially for large integers. Counting the trailing zeros in a number’s binary representation can be done in constant time.

2. Extracting the lowest set bit of a number allows us to quickly find how many times a number can be divided by 2 without having to repeatedly divide the number. This provides the power of 2 (k) directly.

def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
        return
    
    # Handle negative sign
    sign = '-' if n < 0 else ''
    n = abs(n)
    
    # Using bit manipulation to count how many trailing zeros (powers of 2)
    k = (n & -n).bit_length() - 1  # Count trailing zeros by isolating the lowest set bit
    
    # Remove 2^k factor from n
    m = n >> k  # Equivalent to n // 2^k, shifting right by k bits
    
    # Print the result
    print(f"{sign}{n} = {sign}2^{k} * {m}")