Author avatar

Recnac

Python Tricks - Black Magic - Part 1

Recnac

  • Nov 23, 2019
  • 10 Min read
  • 20 Views
  • Nov 23, 2019
  • 10 Min read
  • 20 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.

In this guide, we will begin learning some uncommon, advanced tricks in Python. These include amazing tricks related to what I like to call "black magic." Each Python trick is explained in two steps:

  1. A brief description of the concept and an interactive code example
  2. Some inspiring examples to enlighten you

Explanation of Black Magic

This guide covers some uncommon tricks, and many of them may have side effects. But these tricks are really cool and play a magical role in specific scenarios—so I call them "black magic" in the Python world. Due to the limitations of scenarios and the side effects, their main role is to open up your mind, light up your inspiration, and level up your Pythonic ability.

Once you weigh the pros and cons and know how to use them properly, some of them could become part of your code.

EAFP

This article, Idiomatic Python: EAFP versus LBYL, makes a good point about EAFP vs. LBYL:

EAFP (easier to ask for forgiveness than permission) means that you should just do what you expect to work and if an exception might be thrown from the operation then catch it and deal with that fact.

LBYL (look before you leap) is when you first check whether something will succeed and only proceed if you know it will work.

1
2
3
4
5
6
7
8
9
10
"""LBYL"""
if "key" in dict_:
    value += dict_["key"]
    
"""EAFP"""
# downplays the importance of the key
try:
    value += dict_["key"]
except KeyError:
    pass
python

This obeys the Python's design philosophy: "Explicit is better than implicit."

The performance of EAFP is also acceptable in Python:

But since exceptions are used for control flow like in EAFP, Python implementations work hard to make exceptions a cheap operation, and so you should not worry about the cost of exceptions when writing your code.

Unlike other black magic tricks, this is a recommended coding style in Python.

EAFP is a legitimate coding style in Python and you should feel free to use it when it makes sense.

Let's write a Fibonacci example in a Pythonic style. We will provide the result with generator and iterate in EAFP style.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""pythonic fibonacci"""
# generator function
def fibonacci(n):
    a, b, counter = 0, 1, 0
    while counter <= n:
        yield a
        a, b = b, a + b	# multiple assignment
        counter += 1
        
f = fibonacci(5)
# EAFP
while True:
    try:
        print (next(f), end=" ")
    except StopIteration:
        break
# output: 0 1 1 2 3 5 
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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""used in detect cycle in linked list"""
# L141: determine there is a cycle in a linked list
def has_cycle_in_linked_list(head: ListNode) -> bool:
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

"""used in binary search and insert"""
# L334: given an unsorted array return whether an increasing subsequence (incontinuous) of length k exists or not in the array.
def increasing_triplet(nums: List[int], k: int) -> bool:
    try:
        inc = [float('inf')] * (k - 1)
        for x in nums:
            inc[bisect.bisect_left(inc, x)] = x
        return k == 0
    except:
        return True

"""used in eval"""
# L301: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
def remove_invalid_parentheses(s: str) -> List[str]:
    def isvalid(s):
        try:
            eval('0,' + ''.join(filter('()'.count, s)).replace(')', '),'))
            return True
        except:
            pass
    level = {s}
    while True:
        valid = list(filter(isvalid, level))
        if valid:
            return valid
        level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
python

self assist

This is a trick of dynamic property. The cost is a little intrusive, as it pollutes the original structure.

Inspiring Example

Use self as the dummy node in a linked list.

1
2
3
4
5
6
"""reuse self to save the cost of dummy node"""
def traverse_linked_list(self, head: TreeNode) -> TreeNode:
    pre, pre.next = self, head
    while pre.next:
        self.process_logic(pre.next)
    return self.next  # return head node
python

eval

eval() executes arbitrary strings as Python code. But note that eval may become a potential security risk.

Inspiring Example

Build a tree constructor and use eval to execute.

1
2
3
4
5
6
# L536: construct binary tree from string
def str2tree(s: str) -> TreeNode:
    def t(val, left=None, right=None):
        node, node.left, node.right = TreeNode(val), left, right
        return node
    return eval('t(' + s.replace('(', ',t(') + ')') if s else None
python

str.find

This is a clever use of str.find. Although this usage is not very generalizable, the idea can be used for reference.

Inspiring Example

We use find to construct a mechanism: if val is '#' return 1, if not return -1.

1
2
3
4
5
6
7
8
# L331: verify preorder serialization of a binary tree, if it is a null node, we record using a sentinel value #
def is_valid_serialization(preorder: str) -> bool:
    need = 1
    for val in preorder.split(','):
        if not need:
            return False
        need -= ' #'.find(val)
    return not need
python

str.replace

Use str.replace to implement a string version's union-find (disjoint-set).

Inspiring Example

Compared with ordinary union-find, this string version is concise, elegant, and efficient.

1
2
3
4
"""convert int to unicode char, and use str.replace to merge the connected nodes by reduce"""
# L323: given n nodes from 0 to n - 1 and a list of undirected edges, find the number of connected components in an undirected graph.
def count_connected_components(n: int, edges: List[List[int]]) -> int:
    return len(set(reduce(lambda s, edge: s.replace(s[edge[1]], s[edge[0]]), edges, ''.join(map(chr, range(n))))))
python

^ (xor)

^ is usually used for removing even exactly same numbers and save the odd, or save the distinct bits and remove the same.

Inspiring Examples

These examples illustrate some amazing usages of ^.

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
"""Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same."""
"""bit manipulate: a^b^b = a"""
# L268: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
def missing_number(nums: List[int]) -> int:
    res = 0
    for i, e in enumerate(nums):
        res = res ^ i ^ e
    return res ^ len(nums)

"""simply find the first index whose "partner index" (the index xor 1) holds a different value."""
# L540: find the single element, in a sorted array where every element appears twice except for one. 
def single_non_duplicate(nums: List[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == nums[mid ^ 1]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

"""parity in triple comparisons"""
# L81: search a target in a rotated sorted array
def search_in_rotated_sorted_arr(nums: List[int], target: int) -> int:
    """I have three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know
    whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to
    distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them"""
    self.__getitem__ = lambda i: (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
    i = bisect.bisect_left(self, True, 0, len(nums))
    return i if target in nums[i:i+1] else -1
python

Conclusion

In this guide, we have learned some black magic Python tricks, such as EAFP, eval, xor, and advanced skills for some built-in functions. I hope some of them will be useful for you.

In PArt 2, we will continue to learn about other black magic Python tricks. 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