Author avatar

Recnac

Python Tricks - Black Magic - Part 2

Recnac

  • Nov 23, 2019
  • 10 Min read
  • 13 Views
  • Nov 23, 2019
  • 10 Min read
  • 13 Views
Data
Python

Introduction

Editor's note: This guide is part of a series on useful Python tricks. Read more about the series and find links the other guides here.

This is the second of two guides on some uncommon, advanced tricks in Python—what I like to refer to as "black magic." In the first, we learned many useful black magic Python tricks. Check it out if you missed it.

In this guide, we will continue to add more black magic Python tricks to our arsenal.

Sentinel

Sentinel can make a program simpler: it's a mechanism to distinguish useful data from placeholders, which indicate data is absent.

For example, we can put the key we search after the end of the array. This ensures that we will eventually find the element. When we find it, we only have to check whether we found a real element or just the sentinel.

Here we compare two similar built-in functions: str.index without sentinel and str.find with sentinel.

1
2
3
4
5
6
7
8
9
10
11
"""find vs index"""    
"""index without sentinel"""
try:
    i = a.index(b)
except:
    return

"""find with sentinel"""
i = a.find(b)
if i == -1:
    return
python

As a design philosophy, the idea of sentinel is widely used in Python. We will further discuss the sentinel mechanism in a separate guide, including default value, loop terminator, sentinel object, and functional sentinel.

Inspiring Examples

These examples show the sentinel idea used in both build-in functions and application scenarios.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""sentinel in iter"""
blocks = ''.join(iter(partial(f.read, 32), ''))

"""sentinel in dict.get"""
sentinel = object()
value = my_dict.get(key, sentinel)
if value is not sentinel:
    # Do something with value

"""add a sentinel n at the end (which is the appropriate last insertion index then)"""
# L47: given a collection of numbers that might contain duplicates, return all possible unique permutations.
def permute_unique(nums: List[int]) -> List[List[int]]:
    perms = [[]]
    for n in nums:
        perms = [p[:i] + [n] + p[i:]
                 for p in perms
                 for i in range((p + [n]).index(n) + 1)]
    return perms

"""sentinel in matrix"""    
def traverse_neighbors(matrix: List[List[int]]):
    m, n = len(matrix), len(matrix[0])
    """augment matrix to void length check by sentinel"""
    matrix += [0] * n,
    for row in matrix:
        row.append(0)

    for i in range(m):
        for j in range(n):
            # construct neighbor iterator
            for I, J in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                """no need to check boundary"""
                process_neighbor_logic(matrix[I][J])

"""functional sentinel"""
def get_element(matrix: List[List[int]], i: int, j: int) -> int:
    return matrix[i][j] if 0 <= i < m and 0 <= j < n else -1
python

+= ,

1
some_list += element,	# actually "element," is a tuple
python

is equivalent to

1
some_list.append(element)
python

+= , is shorter to type and more clear, even faster, @Recnac: Shorter and clearer than what? according to the test @Recnac: what test?. But if your teammates or readers are not familiar with it, It may cause confusion.

1
2
3
4
arr = [1, 2, 3]
arr += 4,
arr
# [1, 2, 3, 4]
python

List Comprehension with Break

We know we cannot use branch logic (conditional execution) like if/else in list comprehension, so how to simulate break in list comprehension?

Note: This is just a study and exploration of list comprehension. Since this trick is too hackish, with poor readability and performance, it should not be used in production code. But the techniques and ideas can be used for reference and may provide some inspiration.

Let's take this Stack Overflow question as an example:

How can I stop the iteration of list comprehension when a particular element is found?

1
2
# pseudo code
new_list=[a for a in origin_list break if a==break_elment]
python

Here is the hackish solution:

1
2
3
4
5
6
7
# https://stackoverflow.com/a/56054962/11263560
origin_list = [1, 2, 3, 3, 4, 3, 5]
break_elment = 3

new_list = [a for end in [[]] for a in origin_list
         if not end and not (a == break_elment and end.append(42))]
# output: [1, 2, 3]
python

There are many techniques used in this trick:

  1. The key point is building an end condition in list comprehension. Skip the rest of the elements when end is not empty (actually not break out, but indeed in logic).
  2. How to initialize a variable (end) in a list comprehension? Here is a trick to wrap it in a for list: for end in [[]].
  3. How to implement branch logic in a list comprehension? Use the lazy evaluation technique in and/or to divide branch logics.

Inspiring Examples

Here are more similar examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# https://stackoverflow.com/a/55671533/11263560
# How can I break a list comprehension based on a condition, for instance when the number 412 is found?
# requirement in pseudo code
even = [n for n in numbers if 0 == n % 2 and break if n == 412]

"""use end condition"""
even = [n for end in [[]] for n in numbers
        if (False if end or n != 412 else end.append(42))
        or not end and not n % 2]

# https://stackoverflow.com/q/55646039/11263560
"""use push & pop to record last pair"""
res = [last.pop() and last.append(b) or b for last in [[desired_list[0]]] for a, b in 
       zip([desired_list[0]] + desired_list, desired_list) if abs(a[1] - b[1]) <= 5 and a == last[0]]

"""use end condition"""
res = [b for end in [[]] for a, b in zip([desired_list[0]] + desired_list, desired_list) 
       if (False if end or abs(a[1] - b[1]) <= 5 else end.append(42)) or not end and abs(a[1] - b[1]) <= 5]
python

Integrated by Fractions

Integrate several dimensions into one dictionary using an index with fractions.

Inspiring Example

1
2
3
4
5
6
7
8
9
10
11
# L562: given a 01 matrix, find the longest line of consecutive one. the line could be horizontal, vertical, diagonal or anti-diagonal.
def longest_line_of_consecutive_one_in_matrix(matrix: List[List[int]]) -> int:
    max_len = 0
    cur_len = defaultdict(int)
    for i, row in enumerate(matrix):
        for j, v in enumerate(row):
            """merge row, col, analog, anti-analog into one dict by index with fractions"""
            for key in i, j + .1, i + j + .2, i - j + .3:    # analog: i+j, anti-analog: i-j
                cur_len[key] = (cur_len[key] + 1) * v   # accumulate util v turn to zero
                max_len = max(max_len, cur_len[key])
    return max_len
python

Complex Number in Matrix

Use complex number for two-dimensional representation or visit four directions with imaginary unit calculation.

A property of imaginary number j:

1
2
3
a = 1j
a, a * a, a ** 3, a ** 4
# values: j, -1, -j, 1
python

Inspiring Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""simplify two-dimension index into one-dimension by complex number"""
# traverse neighbors in matrix
def traverse_neighbor_by_complex(matrix: List[List[int]]) -> None:
    matrix = {i + 1j * j: v for i, row in enumerate(matrix) for j, v in enumerate(row)}
    for z in matrix:
        """visit 4-directional neighbor by complex calculation"""
        for k in range(4):
            process_neighbor_logic(matrix.get(z + 1j ** k))

# L657: given a sequence of robot 4-directional moves "LRUD", judge if this robot ends up at (0, 0) after it completes its moves.
def judge_circle(moves: str) -> bool:
    """D: 1j**-1=-1j, R: 1j**0=1+0j, U: 1j**1=1j, L: 1j**2=-1+0j, result in D+U=0 and L+R=0"""
    return not sum(1j**'RUL'.find(m) for m in moves)

"""use complex number to represent island(simplify 2d -> 1d and turn into a sparse representation)"""
# L695: an island is a group of 1's connected 4-directionally, find the maximum area of an island in the given 2D array.
def max_area_of_island(grid: List[List[int]]) -> int:
    grid = {i + j * 1j: val for i, row in enumerate(grid) for j, val in enumerate(row)}
    """calculate the area of paricular island by visit neigher complex calculation"""
    def area(z):
        return grid.pop(z, 0) and 1 + sum(area(z + 1j ** k) for k in range(4))
    return max(map(area, set(grid)))
python

Conclusion

In this guide, we have learned more black magic Python tricks, such as sentinel, list comprehension with break, and advanced usages for fractions and complex number. I hope some of them will be useful for you.

There are other advanced techniques not mentioned here. This guide simply offers a good starting point to travel in the Python world. You can also download an example notebook, black_magics.ipynb, from Github.

This guide is one of a series of Python tricks guides:

I hope you enjoyed it. If you have any questions, you're welcome to contact me at [email protected]

0