Forem: Abdelrahman AbouDeghedy

Pattern Matching Using Knuth–Morris–Pratt (KMP) Algorithm

Abdelrahman AbouDeghedy — Mon, 21 Aug 2023 19:09:25 +0000

Introduction

Hi everyone! Today we're going to discuss a very interesting algorithm that is very handy in the string matching problems.

Consider the following problem: Given the string text = "cvabcg", and the string pattern = "abc". Find whether the pattern exists inside of the text, and return the index of the first matching character.

In the previous example, the answer should be $2$ , as we can find the pattern "abc" starting from index 2 inside the text string.

The Naïve Way

The simplest way to solve this is to loop through each character of the text string, then check if the pattern starts from that character index or not.

int patternMatching(string text, string pattern) {
    int n = text.size(), m = pattern.size();

    for (int i = 0; i < n; i++) {
        bool flag = true;
        int idx = i;
        for (int j = 0; j < m; j++) {
            if (pattern[j] != text[idx]) {
                flag = false;
                break;
            } else {
                idx++;
            }
        }

        if (flag) {
            return i;
        }
    }

    return -1;
}

Unfortunately, the time complexity of this approach is $O (n * m)$ , where $n$ is the length of the text string, and $m$ is the length of the pattern string.

The Efficient Way (Using KMP Algorithm)

The KMP algorithm helps solving this problem in just $O (n + m)$ . It consists of two stages:

Constructing the LPS (AKA: PI) table.
Pattern matching.

1. Constructing the LPS/PI table.

LPS stands for longest proper prefix that is also a suffix.
This is the preprocessing step in our algorithm.
$lps[i]\text{lps}[i]$ = the longest proper prefix of the substring $pattern[0,…i]\text{pattern}[0,\dots i]$ which is also a suffix of the substring $pattern[0,…i]\text{pattern}[0,\dots i]$ .

Note: The prefix and suffix we mentioned can overlap.

Proper prefix of a string means that the prefix is not equal to the string itself. Which indicates that $lps[0]=0\text{lps}[0] = 0$ always (substring of length 1 can't have a proper prefix).

Examples

1. Consider string "ababcd"

a	b	a	b	c	d
0	0	1	2	0	0

Explanation: Examine the following substrings:
a      > Not a proper prefix, hence lps[i] = 0
ab     > prefix != suffix, hence lps[i] = 0
aba    > prefix 'a' == suffix 'a', hence lps[i] = 1
abab   > prefix 'ab' == suffix 'ab', hence lps[i] = 2
ababc  > prefix != suffix, hence lps[i] = 0
ababcd > prefix != suffix, hence lps[i] = 0

2. Consider string "abcabcabc"

a	b	c	a	b	c	a	b	c
0	0	0	1	2	3	4	5	6

Explanation: Examine the following substrings:
a         > Not a proper prefix, hence lps[i] = 0
ab        > prefix != suffix, hence lps[i] = 0
abc       > prefix != suffix, hence lps[i] = 0
abca      > prefix 'a' == suffix 'a', hence lps[i] = 1
abcab     > prefix 'ab' == suffix 'ab', hence lps[i] = 2
abcabc    > prefix 'abc' == suffix 'abc', hence lps[i] = 3
abcabca   > prefix 'abca' == suffix 'abca', hence lps[i] = 4 > Overlapping
abcabcab  > prefix 'abcab' == suffix 'abcab', hence lps[i] = 5 > Overlapping
abcabcabc > prefix 'abcabc' == suffix 'abcabc', hence lps[i] = 6 > Overlapping

Algorithm

Let's define prefixMatchedEndIdx which marks the end index of the current prefix that matches the current suffix.

If the new string character (new suffix character) matches the character at prefixMatchedEndIdx, then we extend the current prefix length by one.
If the new suffix character doesn't match the character at prefixMatchedEndIdx, and the prefixMatchedEndIdx is actually the first character of the string, then there is no way this suffix matches any prefix.
If the new suffix character doesn't match the character at prefixMatchedEndIdx, but prefixMatchedEndIdx is NOT the first character of the string, then there is a chance we can find a smaller prefix that can match the current suffix.

How much reduction we need to the prefix length?

We reduce it to be the lps (longest prefix that is also a suffix) of the previous prefix length.
- In other words, we reduce it to the previous prefix length that matched some suffix, so that there is a chance of the new smaller prefix matching some suffix.

Consider the follwoing string: "aabaaac"
i = 4: "aabaa  | ac"  > lps[i] = 2, prefixMatchedEndIdx = 2
i = 5: "aabaaa | c"   > pattern[prefixMatchedEndIdx] != pattern[i]
        > prefixMatchedEndIdx = lps[prefixMatchedEndIdx - 1] = 1

vector<int> computeLps(string pattern){
    int m = pattern.size();
    vector<int> lps (pattern.size(), 0);
    int prefixMatchedEndIdx = 0, i = 1;

    while(i < m) {
        if (pattern[i] == pattern[prefixMatchedEndIdx]) {
            prefixMatchedEndIdx ++;
            lps[i] = prefixMatchedEndIdx;
            i++;
        } else if (prefixMatchedEndIdx == 0) {
            lps[i] = prefixMatchedEndIdx;
            i++;
        } else {
            prefixMatchedEndIdx = lps[prefixMatchedEndIdx - 1];
        }
    }

    return lps;
}

Time Complexity: $O (m)$ , where $m$ is the length of the string we are preprocessing.

2. Pattern matching

After knowing how to construct the lps array, we want to check whether a pattern exists inside of text.

Concatenate both the pattern and the text (starting with the pattern), and use a separator between them that is not a character of the two strings (such as $).
Compute the lps array for the new string.
If we find an element with an lps value == length of the pattern, it means that there is a suffix (substring from text) that is equal to the prefix (pattern), and since the lps value is equal to the length of the pattern, it means that we found the entire pattern inside the text.
- In this case we want to return the index of the first matching character of the pattern inside the text; which in this case: i - (m + 1) - (m - 1).
  - $i$ : current index in the concatenated string.
  - $m$ : length of the pattern string.
  - $m + 1$ : length of the pattern string + the separator.
  - $m - 1$ : to get to the first character of the matched string.

int patternMatching(string text, string pattern) {
    int n = text.size(), m = pattern.size();

    string concat = pattern + "$" + text;
    vector<int> lps = computeLps(concat);

    for (int i = m + 1; i <= n + m; i++) { /* m + 1 is where the text starts */
        if (lps[i] == m) {
            // m + 1, to skip the concatenated pattern with the separator $
            // m - 1, to get the index at the start of the string
            return i - (m + 1) - (m - 1);
        }
    }

    return -1;
}

Time Complexity: $O (n)$ , where $n$ is the length of the text string.

That's it, now you just added a new interesting algorithm to your toolbox. I hope this was helpful, and let me know your thoughts in the comments.

Start Contributing On Open Source Projects

Abdelrahman AbouDeghedy — Sun, 28 Mar 2021 04:22:25 +0000

Recently, I tried to enter the open-source world, and contribute on GitHub. After doing some search and experimenting with one of my friends, I figured it out, and I will try to demonstrate it as easily as possible.

First of all, I will go with the installation guide for Git Bash, and explaining some common git terms.

Git Bash Installation.
Forking.
Issues.
Pull Requests.
Adding & Committing.
Steps To Make a Successful Contribution.

Git Bash Installation

Git Bash is essentially a terminal, where you can implement git commands on.

You can download git bash from here, and choose the appropriate operating system that works for you.

Issues

According to GitHub Guides, “Issues are a great way to keep track of tasks, enhancements, and bugs for your projects.”

On any open-source project, navigate to the issues tab, and choose an open issue that you can solve.

Before working on any issue, you should add a comment to request solving it, then solving, after the owner of the project assigns it to you.

Forking

According to GitHub Docs, “A fork is a copy of a repository. Forking a repository allows you to freely experiment with changes without affecting the original project.”

Pull Request

This is the core feature of collaborating.

After fixing the issue, you make a pull request, that suggests adding your fix to the project, and the project owner will review it, and respond to you.

If he accepted it, he will merge your fix with the project.

Commit Message

It’s a message that describes the changes that you did.

When you work on solving an issue, your commit message should include the number and the name of the issue.

Adding

After making any changes to your project, you should add it first to what’s known as “Staging Area” before committing it. The details of the staging area are not important to complete this process.

Pushing

This is the operation in which we push our changes from our local repo, to the remote one.
It’s used to make the remote repo in sync with our local one.

Steps To Make a Successful Contribution.

Configuring your info.

This is a mandatory step, so that the commit message that you will make, will have an author.

git config --global user.name "Your name"
git config --global user.email "Your Email"

Fork the Repository.

On GitHub, on the top right corner, press the fork button.

Clone the Forked Repo.

On GitHub, press the green button, and copy the cloning link.

git clone [the url copied from the remote repo]

Making a New Branch.

Make a new branch to your local repo, so we can make changes to the project inside this branch, and later we will ask the project owner to merge our branch with the main branch of the project.

The best practice is to make the branch name the same as the issue name.

git checkout -b [Your branch name]

Setting an Upstream.

We set up an upstream so that when we push our changes later, the default destination to push into will be our new branch.

git push -u origin [Your Branch Name]

Making Changes to the Files Locally.

Make the required changes to the project, that solve the issue.

Checking the State of Your Files.

This is an optional step, that shows the modified files (locally).

git status

Adding the Changes, then Commit them and Writing a Commit Message.

To add the changes, we do the following:

git add *

The * means add all the changed files, you can replace it with any file name that you changed before.

To commit a change, we do the following:

git commit -m "Your Commit Message"

Pushing our Changes to Our Forked Remote Repo.

git push

Making a Pull Request.

When you open your GitHub forked repo, you will find this message pops up.

Click on Compare & pull request to make a pull request, then add your comment, and press create a pull request.

That's it. Congratulations on your first pull request! I hope this post was helpful for you, and helped on your open source journey. Good Luck!

Centering Elements in CSS3

Abdelrahman AbouDeghedy — Mon, 22 Feb 2021 20:13:32 +0000

Introduction

Hello! Today I will cover different cases for centering elements in CSS3.

What we mean by centering?

Centering an element inside a parent element.

Note: The width of the centered element must be less than the width of the container (parent) element, so we can center it.

The cases that we will discuss:

1- Centering Block Elements.
2- Centering Non-block Elements.

Centering Block Elements.

Block elements are the element in which the display property is set to block.

A. Horizontal Center.

For block elements, we can use the margin: 0 auto trick.

Basically, it sets the margin of the top and bottom to zero, and when the left and the right margins have the same value: auto, it means that the margins are distributed equally on both sides of the elements. That makes the element centered.

The width by default is set to auto, and auto for block elements is 100%, so we should change it.

Example:

B. Vertical Center.

This method can be used for both vertical and horizontal centering.

We will use the absolute positioning.

First, we set a reference point, which is the top-left point of the parent element, by setting the parent element’s positioning to relative.

Second, Shift the current element 50% right, and 50% down.

Shifting works with respect to the top-left point of the element, but we wanted to shift the element from its center.

To fix the previous problem, we shift the element 50% (of its total width) to the left, and 50% (of its total height) to the top by using the transform property.

Example:

Centering Non-block Elements.

By non-block elements, we mean text inside an element, inline element, or inline-block element.

A. Center Horizontally.

We treat inline, and inline-block elements as text with respect to the parent element.

For a horizontal center, we will use text-align: center in the parent element.

Example:

B. Center Vertically.

Change the line-height of the parent to be equal to the height of the parent.

Then, change the vertical-align of the child to be middle, and the line-height of the child to be normal.

Example:

That's it for today! I really hope that you learned from it. Tell me about your thoughts in the comments.

Fix Collapsing in CSS3

Abdelrahman AbouDeghedy — Sat, 20 Feb 2021 12:48:48 +0000

Hi! Today I will discuss different types of collapsing in CSS, and how to fix them.

What is the definition of collapsing?

Collapsed element is an element with a zero height.

Types of collapses that we will discuss:

1- Floating Elements Collapse.
2- Margin Collapse.
3- Absolute Positioning Collapse.
4- Empty Div Collapse.

Floating Elements Collapse.

This is a common problem with floated elements.

If we have an element, that contains nothing but floated elements, then this parent element will collapse.

Fixing it

We will apply the famous “clear-fix” to fix this problem.

It’s a fix applied to the after pseudo-element of the parent element.

Margin Collapse.

Margin collapse happens when you set margin-top for an element, and margin-bottom for the element above it, then the total margin between the two elements is the max-margin between both of them, not the sum of the two margins.

Fixing it

To eliminate that effect, set one of the two elements' display to be inline-block.

Absolute Positioning Collapse.

This type of collapsing happens if the parent container that holds the absolute elements doesn't have an explicit height or width, it will collapse.

Fixing it

The solution is to give the parent container an explicit height or width.

Note: When you gave it a height, don't use percentages, as the parent of this parent (body) is not specified explicitly.

Empty Div Collapse.

If we have an empty div, with no content, then it will collapse.

Fixing it

We could insert some content in the div, by writing the HTML special entity &nbsp that corresponds to space.

Another solution is to set a min-height, or a height (with no percentages) for the div.

That's it for today! I hope you learned from it. Good luck!

Sorting in Python 3 for Competitive Programming

Abdelrahman AbouDeghedy — Fri, 19 Feb 2021 15:14:29 +0000

Introduction

Today, we will discuss many cases for sorting in Python 3. It’s a must-have skill in competitive programming.

Explaining the Sort Function, and its Different Arguments.

By default, the sorting function, sorts in ascending order.

The sort function can take two optional arguments:

A- The reverse attribute: It takes a boolean value. True if the sorting is descending, false if ascending.

L = [3, 5, 1, 8, 5, 9]
L = sorted (L, reverse = True)
print (L)   # [9, 8, 5, 5, 3, 1]

B- The key attribute: It takes a comparison function (I will call it: key function throughout this article) for custom sorting.

The key function is applied to each element of the list, to create a pseudo list of the new values returned from that function. Then, the sorting is done based on the values of this pseudo list.

Note: We assign a function to the key attribute, not the return of a function.

Example:

L = ['g', 'a', 'n', 'A', 'B', 'r', 'Y']
L = sorted (L, key = str.lower)
print (L) # ['a', 'A', 'B', 'g', 'n', 'r', 'Y']

# sorts the characters after converting them to lowercase (dynamically on the fly)

Writing Our Own Comparison Function.

We can also write our user-defined key function.

How to write a sorting key function?

The function takes one argument that represents an element of the iterable.

Note: That element could be a single variable, a tuple, or even a list (in a list of lists for example).

The function will compute a value of each element, that we will sort upon.

Example:

'sorts based on the value of the (modulus by 10) of each element'
def keyFunc (element) :
    return element % 10

L = [1, 3, 6, 7, 9, 11]
L = sorted (L, key = keyFunc)
for i in L :
    print (i, end = " ")
''' 1 11 3 6 7 9 '''

Sorting Based on the i-th Element in a List of Tuples.

Suppose that we have a list of tuples, and we want to sort it based on the second element of each tuple.

Based on what we learned in the last section, we will write our own key function to handle that.

The argument of the key function corresponds to a tuple, that represents a single element of the list.

We will return the second element from that tuple, to sort based on it.

Example:

listOfTuples = [(1, 'c', 1), (0, 'a', 9), (5, 'h', 5)]
listOfTuples = sorted (listOfTuples, key = lambda iter : iter[1])
for i in listOfTuples :
    print (i)
'''
(0, 'a', 9)
(1, 'c', 1)
(5, 'h', 5)
'''

Secondary Sorting.

Consider the following scenario:

If we have a dictionary, and the keys are strings, values are integers, and we want to sort it based on the integers, but if two integers were equal, then sort based on their corresponding string values.

To do so, the key function will return an extra value, to define our second criteria.

Example:

def keyFunc (element) :
    return element[1], element[0]   # sorting based on values, then the keys

d = {'f' : 9, 'd' : 8, 'b': 8}
d = sorted (d.items (), key = keyFunc)
print (d)   # [('b', 8), ('d', 8), ('f', 9)]

More Complex Examples

What if we want to sort a dictionary based on ascending values, then by descending keys.

If the reverse attribute took the value of True, it will perform both the first and the second sorting in descending order.

If we added a negative sign in front of one of the return values of the key function, then it will have the opposite sorting effect that was set for it.

Example:

d = {'b': 9, 'd' : 8, 'f' : 8}
d = sorted (d.items (), key = lambda x : (-x[1], x[0]), reverse = True)    # sorting based on ascending values, then by descending keys
print (d)   # [('f', 8), ('d', 8), ('b', 9)]

Note: the negative sign can be added before an integer element only.

Example:

d = {'f' : 8, 'd' : 8, 'b': 9}
# we want to sort based on ascending values, then by descending keys
d = sorted (d.items (), key = lambda x : (x[1], -x[0])) # TypeError: bad operand type for unary -: 'str'

That's it for today! I hope you learned from it. Good Luck!

OOP in JavaScript. #1. Constructor and Prototypes

Abdelrahman AbouDeghedy — Mon, 15 Feb 2021 18:33:16 +0000

Introduction

Hi! Today I will start a series, in which I will talk about OOP in Javascript. I will start by explaining constructor functions and prototypes.

OOP in JavaScript

OOP is a programming paradigm (style of code) based on the concept of objects.

OOP in JS is different from the classical OOP.

In classical OOP we have objects that are instantiated from classes.
In JS OOP, we create objects, then we link them to a prototype object (that got all the methods), then the objects inherit all the methods of the prototype (It can be also said that: the prototype delegates the methods to the objects).

How can we create objects, their Prototype, and Linking Them Together?

We have three ways in JS to achieve that:
1- Constructor Functions.
2- ES6 Classes.
3- Object.create ().

Today we will discuss the first one, which is: Constructor Functions.

Constructor Functions

When we create a constructor function, the convention is to start its name with a capital letter.

Arrow function won't work as a constructor function, because it doesn't have its own this keyword.

This constructor function can be used to make any number of objects as we want.

The Difference Between Calling a Constructor Function and Calling a Normal Function:

When we call a constructor function, we use the new keyword.

Example:

const Person = function (firstName, birthYear) {
    this.firstName = firstName;
    this.birthYear = birthYear;
}

// Making an instance of the constructor function
const Abdelrahman = new Person ('Abdelrahman', 2001);
const Abdelrahman = new Person ('Habiba', 2003);

When we invoke a constructor function, the following do happen:

An empty object is created (empty object means that it has neither properties nor methods).

We can add some properties for that empty object in the constructor function’s body using the this keyword (just like we did in the previous example).

The this keyword is set to point to the newly created empty object.
The newly created object is linked to a prototype, which means:

A- Creating a new __proto__ property for the object.

B- Set it to the prototype property of the constructor function.

This empty object is returned from the constructor function.

If that seems overwhelming to you, don't worry! Just stick with me, and you will understand everything when I start talking about prototypes.

The need for Prototypes

Suppose that we want to add some methods to the object.

It’s a bad practice to add them inside the constructor function body, as those methods will be shared with all instances, while we don’t always need the methods to be shared. That will affect performance!

Example:

const Person = function (firstName, birthYear) {
    this.firstName = firstName;
    this.birthYear = birthYear;

    // Bad Practice (methods inside constructor function)
    this.calcAge = function () {
        console.log(2037 - this.birthYear);
    }
}

The solution to the previous problem is using prototypes.

Prototypes

Each and every function (including the constructor function) in JS has a property called: prototype.

When we add methods (or properties) to the prototype property of our constructor function, only one copy of this method is made, to be used later by all of the instances.

All the objects (instances) will inherit all the methods defined in the prototype property. This is called prototypal inheritance.

When we call a property or a method on an object, if it’s not found in the object itself, JS will search on its prototype.

The following example shows, how can we add a method to the prototype property of the function constructor:

Person.prototype.calcAge = function () {
    console.log(2037 - this.birthYear);
}

Abdelrahman.calcAge ();

Any object always has access to the methods and properties from its prototype. To do that, we use the special property __proto__ that is available for all JS objects.

Remember: __proto__ used to access the prototype for any object. The prototype property is for the constructor function.

Constructor function’s prototype property is not used to yield the prototype for the constructor function itself, but to yield the prototype for all the objects created from this constructor.

Note: prototype is a property, but constructorFunction.prototype is an object.

Example to illustrate the previous statements:

console.log(Abdelrahman.__proto__ === Person.prototype);  // true
console.log(Person.prototype.isPrototypeOf (Abdelrahman)); // true
console.log(Person.prototype.isPrototypeOf (Person));   // false

Note: We used the isPrototypeOf method (for the prototype property) to check whether the constructor function’s prototype is the prototype of the object passed or not.

Adding properties to the Prototype of the Constructor function

This is not practical in many cases, as all of the instances will share the same value for this property.

Person.prototype.species = "Homo Species";
console.log(Abdelrahman.species, habiba.species);  // Homo Species Homo Species

We can use the hasOwnProerty method for any object and pass an object property (as a string) to it. It will return true if the passed property is not a prototypal property.

console.log(Abdelrahman.hasOwnProperty ('species'));   // false

Prototype Chain

It's a series of links between objects linked using prototypes.

Each created object in JS is just an instance of the Object constructor function.

When we use the curlies {} to write an object literal, it’s equivalent to writing new Object constructor.

The prototype of any object is the constructor function that this object was created from. When we reach Object, it’s on the top of the prototype chain, and it has no parent, so its prototype will be null.

console.log(Abdelrahman.__proto__.__proto__);  // Object.prototype
console.log(Abdelrahman.__proto__.__proto__.__proto__);    // null

Applying what we learned

We can apply what we learned in the Array constructor.

Creating an array using the brackets [], is equivalent to creating it using the new Array constructor.

const arr = [1, 3, 1, 3, 6, 6, 5, 6, 1];
console.log(arr.__proto__ === Array.prototype); // true

We can add a method to the Array constructor function prototype (and all array objects will inherit it).

const arr = [1, 3, 1, 3, 6, 6, 5, 6, 1];
Array.prototype.unique = function () {
    return [...new Set (this)];
};
console.log(arr.unique ()); // Array(4) [ 1, 3, 6, 5 ]

That's it for today! I hope you learned from it. See you soon!

Manipulating Lists in Python 3 for Competitive Programming

Abdelrahman AbouDeghedy — Mon, 30 Nov 2020 08:02:52 +0000

Introduction

A couple of months ago, I was preparing for the ECPC Qualifications and I knew that we can't use any external libraries like Numpy in the competition, so I tried to figure out some alternative methods to manipulate lists, and today, I want to share it with you!

We will discuss four techniques:

Performing Multiple Swaps on Rows and columns Efficiently
Initializing a 2D Matrix
Deleting an Element from a List That You’re Iterating Upon
Getting the Transpose of a Matrix

Performing Multiple Swaps on Rows and columns Efficiently

Steps:

Store the matrix in a list of lists
Create two dictionaries, one for the rows (that has size equal to the number of rows), and another for the columns (has size equal to the number of columns)
Both keys and values are initialized to the initial indexing of the matrix
The keys for those dictionaries are the original value for the indices of the matrix, the values are the indices after all swap operations
We will access matrix elements using those dictionaries only

Sample Code:

matrix = [[1, 2, 3], [4, 5, 6]]

col = {i : i for i in range (3)} # creating columns map
row = {i : i for i in range (2)} # creating rows map

# I will perform three swaps, but you could extend to way more than that!
col[0], col[1] = col[1], col[0] # first swap
row[0], row[1] = row[1], row[0] # second swap
col[2], col[0] = col[0], col[2] # third swap

for i in matrix : # printing the original matrix before the swaps
    print (i)
'''
output:
[1, 2, 3]
[4, 5, 6]
'''

# printing the matrix after the swaps
for i in range (2) : # iterate through the whole matrix
    for j in range (3) :
        print (matrix [row[i]][col[j]], end = ' ') # accessing the matrix using the two maps
    print ()
'''
output:
6 4 5 
3 1 2 
'''

Initializing a 2D Matrix

It seems like an easy topic, but there is a trick that a lot of people don’t get at the first glance

I will show you the wrong way that many got mistaken over, then I will show you the correct method of doing it

The Wrong Method

This method will create four references, all to the same 1-D list
If you changed any element in the first 1-D list, it will affect the rest of the lists (will affect all elements with the same index as in the first list)
This is because the reference of the first list is the same reference to the rest of the list

Sample Code:

# The WRONG way
# DO NOT DO THIS!
matrix = [[0] * 3] * 4 # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
'''

The Right Method

We will use a for loop, It's equivalent to writing multiple statements
This will create multiple references, one for each row (1-D list)

Sample Code:

matrix = [[0] * 3 for _ in range (4)] # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
'''

Deleting an Element from a List That You’re Iterating Upon

If we deleted some elements from a list while iterating over it, we will get the following error:

IndexError: list index out of range

Steps of deleting elements from a list while iterating over it correctly:

Let's call the array that we want to delete elements from (arr)
Make a new boolean array, and we called it (isDeleted)
If the current element should be deleted, then make the corresponding element in the boolean array = 1

Note that: In the boolean array, the value of one means that the elements should be deleted, value of zero means otherwise

Make a third array, we called it (LAfterDeletion), that will take the elements from arr that correspond to elements in the boolean array with a value of 0

Sample Code:

L = [1, 2, 3, 5, 66, 7, 8, 4, 23, 12] # making a list

isDeleted = [0] * len (L) # creating the boolean array
LAfterDeletion = [] # create the final array, that will take values after deletion

# Delete the elements that are larger than 5!
for i in range (len (L)) :
    if L[i] > 5 :
        isDeleted[i] = 1
for i in range (len (isDeleted)) :
    if isDeleted[i] == 0:
        LAfterDeletion.append(L[i])
print (LAfterDeletion) # [1, 2, 3, 5, 4]

Getting the Transpose of a Matrix

The main idea is based on using the zip function
Zip () function takes multiple iterables and returns a generator that contains a series of tuples, where each tuple contains a series of elements, one from each iterable
We could cast this generator to a list

Sample Code:

lis = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # declaring the original list
for i in lis :
    print (i)
'''
output:

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
'''
lis = list (zip (*lis)) # first rotation (replacing rows with columns)
# *lis is used to unpack the list of lists to multiple lists, equivalent to: lis[0], lis[1], lis[2]
for i in lis :
    print (i)
'''
output:
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)
'''

That's it! I hope you learned from it. Happy coding!