| ~ |

Months ago I came across an article on the methods of shuffling cards in TCG tournaments. Given limited time in a match, the author, hyakkoTCG@hyakko_tcg sought a way to mix a deck thoroughly by shuffling three times. However, at least to me, it is obvious that the methodology proposed is fundamentally flawed. Later I found out in surprise that the article was widely disseminated: it got 2.3k retweets and 3.1k likes on twitter.

Read more »

| ~ |

本系列起始于 2019 年夏天, 目的是记录自己学习厨艺的过程, 尽量把烹饪流程拆分成原子操作, 并探究其原理. 不过因为实践的次数极少所以进展龟速, 另外原理部分我是外行, 全靠查资料, 这进一步拖慢了进度. 姑且先发出来之后慢慢填坑.

Read more »

| ~ |

LeetCode 847. Shortest Path Visiting All Nodes

2020/7/19

广度优先搜索.

一个 trick 是可以用二进制数表示访问过的节点, 1 表示访问过, 0 表示未访问过. 比如一共 5 个节点 (0-indexed), 则可以用 11001 表示访问过节点 0, 3, 4. 位运算 1<<n 比 2**n 快得多.

from collections import deque

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        '''
        binary representation
        e.g. 11001 for nodes 034 visited and 12 unvisited
        '''
        goal = (1<<len(graph)) - 1
        # (curr_node, visited_nodes, steps)
        queue = deque((node, 1<<node, 0) for node in range(len(graph)))
        seen = set()
        while queue:
            curr_node, visited_nodes, steps = queue.popleft()
            if visited_nodes == goal:
                return steps
            for adj_node in graph[curr_node]:
                state = (adj_node, visited_nodes | 1<<adj_node, steps+1)
                if state not in seen:
                    seen.add(state)
                    queue.append(state) 
        return -1
Read more »

| ~ |

要求 $a^n$, 其中 $a\in\mathbb R$, $n\in\mathbb Z$. 先不妨假设 $n\ge 0$, 基本想法是

\[a^n = \begin{cases} a^{n/2}a^{n/2}, & \text{if $n$ is even,}\\ a^{(n-1)/2}a^{(n-1)/2}a, & \text{if $n$ is odd.} \end{cases}\]

很容易写出时间复杂度 $O(\log n)$ 的递归算法, 而要写迭代算法需要再想一想.

Read more »

| ~ |

第二篇杂录 侧重最佳实践.

最近 (2021/10/28) 发现官方文档有 Programming FAQ — Python 3.10.0 documentation, 很有用.

Misc

一些语法糖

2023/1/10

(1,) + (2, 3)
# (1, 2, 3)

a = {1: 1}
b = {2: 2}
{**a, **b}
# {1: 1, 2: 2}

nonlocal

2022/7/5

忘了看哪个源码的时候读到的

Python の nonlocal と global の違い - Qiita

functools

lru_cache 以及 singledispatch

Read more »

| ~ |

算法分析的那个定理.

Master Theorem

\[T(n) = \begin{cases} \Theta(1), & \text{if } n = 1,\\ aT(n/b) + f(n), & \text{if } n>1. \end{cases}\]

where $a\ge1$, $b>1$ are constants and $f$ is nonnegative. Then

  1. If $f(n) = O(n^{\log_b a-\varepsilon})$ for some constant $\varepsilon >0$, then $T(n) = \Theta(n^{\log_b a})$.
  2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a}\log n)$.
  3. If $f(n) = \Omega(n^{\log_b a+\varepsilon})$ for some constant $\varepsilon >0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
Read more »