Author avatar

Recnac

Python Tricks - Black Magic - Part 1

Recnac

  • Nov 23, 2019
  • 10 Min read
  • 4,330 Views
  • Nov 23, 2019
  • 10 Min read
  • 4,330 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"""LBYL"""
2if "key" in dict_:
3    value += dict_["key"]
4    
5"""EAFP"""
6# downplays the importance of the key
7try:
8    value += dict_["key"]
9except KeyError:
10    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"""pythonic fibonacci"""
2# generator function
3def fibonacci(n):
4    a, b, counter = 0, 1, 0
5    while counter <= n:
6        yield a
7        a, b = b, a + b	# multiple assignment
8        counter += 1
9        
10f = fibonacci(5)
11# EAFP
12while True:
13    try:
14        print (next(f), end=" ")
15    except StopIteration:
16        break
17# output: 0 1 1 2 3 5 
python

Inspiring Examples

1"""used in detect cycle in linked list"""
2# L141: determine there is a cycle in a linked list
3def has_cycle_in_linked_list(head: ListNode) -> bool:
4    try:
5        slow = head
6        fast = head.next
7        while slow is not fast:
8            slow = slow.next
9            fast = fast.next.next
10        return True
11    except:
12        return False
13
14"""used in binary search and insert"""
15# L334: given an unsorted array return whether an increasing subsequence (incontinuous) of length k exists or not in the array.
16def increasing_triplet(nums: List[int], k: int) -> bool:
17    try:
18        inc = [float('inf')] * (k - 1)
19        for x in nums:
20            inc[bisect.bisect_left(inc, x)] = x
21        return k == 0
22    except:
23        return True
24
25"""used in eval"""
26# L301: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
27def remove_invalid_parentheses(s: str) -> List[str]:
28    def isvalid(s):
29        try:
30            eval('0,' + ''.join(filter('()'.count, s)).replace(')', '),'))
31            return True
32        except:
33            pass
34    level = {s}
35    while True:
36        valid = list(filter(isvalid, level))
37        if valid:
38            return valid
39        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"""reuse self to save the cost of dummy node"""
2def traverse_linked_list(self, head: TreeNode) -> TreeNode:
3    pre, pre.next = self, head
4    while pre.next:
5        self.process_logic(pre.next)
6    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# L536: construct binary tree from string
2def str2tree(s: str) -> TreeNode:
3    def t(val, left=None, right=None):
4        node, node.left, node.right = TreeNode(val), left, right
5        return node
6    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# L331: verify preorder serialization of a binary tree, if it is a null node, we record using a sentinel value #
2def is_valid_serialization(preorder: str) -> bool:
3    need = 1
4    for val in preorder.split(','):
5        if not need:
6            return False
7        need -= ' #'.find(val)
8    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"""convert int to unicode char, and use str.replace to merge the connected nodes by reduce"""
2# 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.
3def count_connected_components(n: int, edges: List[List[int]]) -> int:
4    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"""Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same."""
2"""bit manipulate: a^b^b = a"""
3# L268: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
4def missing_number(nums: List[int]) -> int:
5    res = 0
6    for i, e in enumerate(nums):
7        res = res ^ i ^ e
8    return res ^ len(nums)
9
10"""simply find the first index whose "partner index" (the index xor 1) holds a different value."""
11# L540: find the single element, in a sorted array where every element appears twice except for one. 
12def single_non_duplicate(nums: List[int]) -> int:
13    lo, hi = 0, len(nums) - 1
14    while lo < hi:
15        mid = (lo + hi) // 2
16        if nums[mid] == nums[mid ^ 1]:
17            lo = mid + 1
18        else:
19            hi = mid
20    return nums[lo]
21
22"""parity in triple comparisons"""
23# L81: search a target in a rotated sorted array
24def search_in_rotated_sorted_arr(nums: List[int], target: int) -> int:
25    """I have three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know
26    whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to
27    distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them"""
28    self.__getitem__ = lambda i: (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
29    i = bisect.bisect_left(self, True, 0, len(nums))
30    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]