DEV Community

loading...
Cover image for Manipulating Lists in Python 3 for Competitive Programming

Manipulating Lists in Python 3 for Competitive Programming

Abdelrahman Deghedy
Communication and Electronics Student at Alexandria University
Originally published at thetuteur.com ・4 min read

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 
'''
Enter fullscreen mode Exit fullscreen mode

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]
'''
Enter fullscreen mode Exit fullscreen mode

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]
'''
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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)
'''
Enter fullscreen mode Exit fullscreen mode

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

Discussion (8)

Collapse
joaomcteixeira profile image
João M.C. Teixeira

Hi,

Very curious post. Is this an abstraction of a greater implementation, or is the actual implementation? If it is the actual implementation, I ask why not numpy?

If it is an abstraction of a greater implementation, can you give some examples? Do you use the lists with multiple types, rather than just integers?

Cheers,

Collapse
abdelrahmandeghedy profile image
Abdelrahman Deghedy Author

Hi João,

It was some ideas from my experience solving problems in preparation for the ACM

About Numpy, we can't install an external library in the ACM, so I tried to figure out some alternative methods, So I used them in small programs written for competitive programming problems

I used lists with different types before

Thanks!

Collapse
joaomcteixeira profile image
João M.C. Teixeira

That is a very nice explanation. Maybe you can add that as an intro in the post, to contextualize your implementation.

Sorry, I am not from a computer science background, ACM stands for?

Cheers,

Thread Thread
abdelrahmandeghedy profile image
Abdelrahman Deghedy Author

Great idea!

The full name is: ACM ICPC
It stands for: Association for Computing Machinery - International Collegiate Programming Contest

You can read more at:
en.wikipedia.org/wiki/Internationa...

I only participated in the local one, I didn't qualify to the international

Thanks!

Thread Thread
joaomcteixeira profile image
João M.C. Teixeira

Thanks so much for explaining me.

I found your implementation very curious. At fist, it looks like: "why would I want to do this?", but then...

I work a lot with Numpy, but somehow within I feel there will be a place for an implementation like this in my projects.

How large are the lists you have worked with? Do you have any experience in performance? More than 2 dimensions? :-) as you can see, I am a very curious person.

I am having quite busy days, but asap I have some spare time I will have a close look also.

Cheers,

Thread Thread
abdelrahmandeghedy profile image
Abdelrahman Deghedy Author

Unfortunately, I don't quite remember, but most of the problems I solve have the following properties:

1) Running time = 2 seconds
2) Size of the list = 10e5 or 10e6

Those numbers are approximations, not exact!

I usually use lists with no more than two dimensions

Hope that helps!

Thread Thread
joaomcteixeira profile image
João M.C. Teixeira

That helps a lot.

I will let you know if I explore this concept further. I certainly will.
Cheers,

Thread Thread
abdelrahmandeghedy profile image
Abdelrahman Deghedy Author

Glad to hear that

Good luck!

Forem Open with the Forem app