All about technology
Just write this snippet for my practice of 0-1 Knapsack Problem:
values = [1, 2, 3, 4, 5]
weights = [3, 2, 1, 9, 6]
max_weight = 12
def knappack():
n = len(values)
dp = [[0] * (max_weight+1) for _ in range(n)]
print(dp)
for i in range(n):
for j in range(1, max_weight+1):
if weights[i] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
print(dp[-1][-1])
knappack()My first idea is depth-first-search: iterate all people, try to give them different hats. The solution got TLE (Time Limit Exceeded). Then as a hint from discussion forum, I started to iterate hat (instead of people), try to give them different people. The solution also got TLE (even I used lru_cache for function):
from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, path) -> int:
if len(path) == len(hats):
return 1
if start == len(hp):
return 0
total = 0
for person in (hp[start] - set(path)):
total += dfs(start + 1, tuple(list(path) + [person]))
total += dfs(start + 1, path)
return total % (10**9 + 7)
return dfs(0, tuple())Using list as data structure to record visited node is not efficient enough in this case. Since there will be no more than 10 people, the most efficient data structure to record visited people is bits.
My final solution is still using dfs (by using lru_cache, it is also a dynamic-programming):
from collections import defaultdict
class Solution:
def numberWays(self, hats: List[List[int]]) -> int:
hp = defaultdict(set)
for index, hat in enumerate(hats):
for _id in hat:
hp[_id].add(index)
hp = [people for people in hp.values()]
@functools.lru_cache(None)
def dfs(start, mask) -> int:
if bin(mask).count('1') == len(hats):
return 1
if start == len(hp):
return 0
total = 0
for person in hp[start]:
if (1 << person) & mask > 0:
continue
mask |= 1 << person
total += dfs(start + 1, mask)
mask ^= 1 << person
total += dfs(start + 1, mask)
return total % (10**9 + 7)
return dfs(0, 0)To solve Leetcode #1675, I wrote the below code with the help of hints:
import sys
import heapq
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
n = len(nums)
heapq.heapify(nums)
_max = max(nums)
ans = max(nums) - min(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 1:
heapq.heappush(nums, item * 2)
_max = max(_max, item * 2)
ans = min(ans, _max - heapq.nsmallest(1, nums)[0])
else:
heapq.heappush(nums, item)
break
print("stage1:", nums)
nums = [-item for item in nums]
heapq.heapify(nums)
_max = max(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 0:
heapq.heappush(nums, item // 2)
_max = max(_max, item // 2)
ans = min(ans, _max - heapq.nsmallest(1, nums)[0])
else:
break
return ans I know, the code looks quite messy. But the more annoying problem is: it exceeded the time limit.
After learning the solutions from these smart guys, I realized how stupid I am — I can just use nums[0] instead of heapq.nsmallest(1, nums)[0] to get the smallest element in a heap, just as the official document said.
Then I just change two lines of my code and it passed all the test cases in time:
import sys
import heapq
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
n = len(nums)
heapq.heapify(nums)
_max = max(nums)
ans = max(nums) - min(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 1:
heapq.heappush(nums, item * 2)
_max = max(_max, item * 2)
ans = min(ans, _max - nums[0])
else:
heapq.heappush(nums, item)
break
print("stage1:", nums)
nums = [-item for item in nums]
heapq.heapify(nums)
_max = max(nums)
while True:
item = heapq.heappop(nums)
if item % 2 == 0:
heapq.heappush(nums, item // 2)
_max = max(_max, item // 2)
ans = min(ans, _max - nums[0])
else:
break
return ansThe first intuitive idea that jumps out of my mind after taking a look at LeetCode #127 is using the graph algorithm. But for building the graph first, I need to traverse the wordList by O(n2) times.
Here comes the time complexity analysis: the length of the wordList is about 5000, O(n2) means 5000*5000=25*106. For a python script in LeetCode, it will cost about 1 second for every 106 operations. Thus 25*106 will cost about 25 seconds, which is too long for a LeetCode question.
Therefore the best method to build a graph is not to traverse the wordList multiple times, but to just iterate all lower-case alphabets (be aware of the constraints beginWord, endWord, and wordList[i] consist of lowercase English letters.). By just iterating lower-case alphabets, I can reduce time to 260*5000=1.3*106 (the max length of words in wordList is 10).
The code below also uses my old trick of visited nodes.
from collections import defaultdict
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words_set = set(wordList)
conns = defaultdict(set)
for word in wordList + [beginWord]:
for index in range(len(word)):
conns[word] |= {word[:index] + cand + word[index+1:] for cand in "abcdefghijklmnopqrstuvwxyz" if cand != word[index] and word[:index] + cand + word[index+1:] in words_set}
# bfs
queue = {beginWord}
already = set()
ans = 1
while queue:
new_queue = set()
for node in queue:
for _next in conns[node]:
if _next == endWord:
return ans + 1
new_queue.add(_next)
already |= queue
queue = new_queue - already
ans += 1
return 0The popular solution for LeetCode #494 is dynamic programming. But my first idea is Divide and Conquer. Although it’s not very fast, it’s another idea:
from collections import Counter
class Solution:
def get_results(self, nums: List[int]) -> Counter:
layer = [nums[0], -nums[0]]
for num in nums[1:]:
new_layer = []
for item in layer:
for val in [-num, num]:
new_layer.append(item + val)
layer = new_layer
return Counter(layer)
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
if n == 1:
return [0, 1][nums[0] == target or -nums[0] == target]
half = n // 2
left = self.get_results(nums[:half])
right = self.get_results(nums[half:])
ans = 0
for lkey, lcnt in left.items():
rcnt = right[target - lkey]
ans += rcnt * lcnt
return ans |
 |
 |
It does not mean I just read three books in the whole year of 2022 when I just showed three books above. Although reading some short history stories and books about financial knowledge, I still think those are not vital to my life experience.
As a software developer, why did I read a book about the semiconductor material: Silicon Carbide? Frankly speaking, just because of curiosity. In recent years, a lot of news and articles said SiC (Silicon Carbide) will be the future material of EVs (Electric Vehicles), and all the companies that produced SiC will become extremely popular and rich. But after skimming this book (or maybe a long paper), I realized that SiC has been found and produced for many years and at an early age, scientists only thought of it as a material for lighting and sensing. If even the most intelligent people consider SiC as “not very popular” about 10 years ago, why should I believe it will become “the future of EV” in the next 10 years only because some financial guys said this? Inflating a financial bubble is easy, but science is all about hard work and frequent failures.
“A Song of Ice and Fire” is a great novel. The only drawback after reading it (I mean, the first 5 volumes) is I couldn’t be interested in other novels for a long time. Even the “A Knight of the Seven Kingdoms”, written by George RR Martin himself, can’t match it. The first story for Dunk the Hedge Knight is wonderful, but the left two are normal.
The reason I put the algorithm book here (also in 2021) is that I am still trying to revisit and learn algorithms in 2022. After graduating from school, I spend quite a lot of time learning technology about machine learning, compilers, operating systems, and even semiconductors. But not the algorithms. Since learning new algorithms are terribly tedious, I avoid touching them for such a long time. How could a software engineer try to learn everything but algorithms? I felt a little regret. So, I will do it now.
 |
 |
 |
 |
 |
|
I know it looks too late that I wrote this article in the middle of the year. But, late is much better than none. Right?
I bought the seven books series of “A song of ice and fire” on 23rd November 2019 and finish reading them on 3rd August 2021. It is definitely the best fantasy novel I have read so far (sorry Salvatore, I just told you my true thought). The whole world and the whole story in it are cold and cruel, but unimaginably fascinating and attractive.
The first book of the series is published early in 1996 when I was just a stupid middle school student. I feel really regret I hadn’t started to learn English more intensive and started to read “A song of ice and fire” since then.
The currently last book of the series is published in 2011, a total of eleven years ago. Oh, George, please write the last two volumes as quickly as possible. Your fans had been waiting for 11 years. I don’t want to wait another 11 years more…
Fortunately, I also got some time to look into some area that I am really interesting in but couldn’t benifit my work, such as Semiconductor. The book “Introduction to Semiconductor Technology” really helps me a lot. It starts the introduction from basic phisicals and chemistry knowledge to how to make silicon wafer, to how to paste photoresist, to how to etch, to how lithography, to how to etch, to how to make backend wires. Although forgot almost all my chemistry knowledge before, I still could understand all the process in this industry. And it looks really cool! I can’t hold to show a image for a beautiful DRAM:
In computer science, the algorithm is one of the most important, and also the most difficult part. As a career routine, I found this “The Algorithm Design Manual” and study the algorithms again, mainly focus on the dynamic-programming and just skim through the graph algorithm (they are far away from my daily work, and also far difficult…). I couldn’t say I understood this book very well but at least I take my share of it. And, hope I can revisit it again in the near future.
About two weeks ago I met the “number of islands” problem in LeetCode. The first idea that jumped out of my brain is ‘dynamic programming’: I can create a new matrix (let’s name it ‘number matrix’) with the same size as the problem matrix, and set every position a value. The value is the number of islands from (0, 0) to this position.
For example, as the below problem matrix:
| 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 |
We can create the ‘number matrix’:
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 3 |
| 2 | 2 | 3 | 3 |
Why the (4, 0) position in ‘number matrix’ is 2? Because the (0, 0) to (4, 0) area in ‘problem matrix’ has two islands:
| 1 |
| 0 |
| 1 |
| 0 |
Then, every time we want to calculate the value of a position in the ‘number matrix’ we can first calculate the values of its ‘left’, ‘top’ and ‘left-top’ position.
For example, since the (3, 3), (4, 3) and (3, 4) positions in the ‘number matrix’ are all ‘3’, and the (4, 4) position in ‘problem matrix’ is ‘0’, the (4, 4) position of ‘number matrix’ should be ‘3’ also.
But unfortunately, after two weeks of struggling on thinking, I finally found out that the value of a position in the ‘number matrix’ can’t be decided by its nearest three positions: left, top and left-top. The counterexample is below:
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Let’s just build the number matrix for the (6, 6) to (7, 7) area of problem matrix A:
| 2 | 2 |
| 2 |
Don’t rush. Let’s look at another problem matrix:
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
This time, we also build the number matrix for the (4, 4) to (5, 5) area of problem matrix B:
| 2 | 2 |
| 2 |
See? They have the same values for left, top and left-top, but different final results (problem matrix A has just 1 island but problem matrix B has 2).
Two weeks of hard thinking just got the wrong idea. But this is the charming of algorithm 🙂
Imagine we have an array of numbers [9, 8, 7, 1, 2, 3, 4, 5, 6]. What’s the best solution to split it into 3 partitions with the most “average sum”, which means they have minimum differences for their sums. (Remember that we can’t change the order of this array)
For example, we can split this array into three partitions like this [9, 8, 7] [1, 2, 3, 4] [5, 6]. Then the sums of the three partitions are 24, 10, 11. This solution is not the best since the sums have big differences.
The algorithm and source code for this problem is in the book “The Algorithm Design Manual“. And below is the python code of my implementation:
# Find the most average way for partitions
import numpy as np
def maximum_partition(sequence, M, nr_partitions, sum_array):
for n in range(2, len(sequence) + 1):
for k in range(2, nr_partitions + 1):
array = []
for i in range(1, n + 1):
select = max(M[i][k - 1], sum_array[n - 1] - sum_array[i - 1])
array.append(select)
M[n][k] = min(array)
return M[len(sequence)][nr_partitions]
def init_matrix(sequence, nr_partitions, M, sum_array):
for index in range(len(sequence)):
sum_array.append(sum(sequence[: index + 1]))
for k in range(1, nr_partitions + 1):
M[1][k] = sequence[0]
for n in range(1, len(sequence) + 1):
M[n][1] = sum(sequence[:n])
if __name__ == "__main__":
# The sequence and the number of partitions
sequence = [9, 8, 7, 1, 2, 3, 4, 5, 6]
partitions = 3
# init
M = np.zeros((len(sequence) + 1, partitions + 1), dtype=int)
sum_array = []
init_matrix(sequence, partitions, M, sum_array)
# call the main function
range_sum_max = maximum_partition(sequence, M, partitions, sum_array)
print("Sum of the maximum range:", range_sum_max)
# split the sequence by using maximum sum of one range
current_sum = 0
for index in range(len(sequence)):
if (current_sum + sequence[index]) > range_sum_max:
print("| ", end="")
current_sum = 0
current_sum += sequence[index]
print(sequence[index], end=" ")
print("\r")The code is unbelievable simple (just less than 50 lines). And this is the power and charm of dynamic programming.
I am reading the second edition of “The Algorithm Design Manual” recently. Reaching the chapter about backtracking, I realized that this method could solve many problems, even complicated problems, quickly and efficiently. Therefore I plan to write a solution to the n-queens problem by using backtracking.
Here is my Python code (Github):
# Using backtracking to resolve n-queues problem
import numpy as np
max_columns = 8
max_rows = max_columns
def print_chess(problem):
head = "_" * (len(problem) + 2)
tail = "-" * (len(problem) + 2)
print(head)
for row in problem:
row_str = "|"
for item in row:
row_str += str(item)
row_str += "|"
print(row_str)
print(tail + "\n")
def remove_diagonal(problem, occupied_coordinate, max_cols, candidates):
row, col = occupied_coordinate
step = max_cols - col - 1
# remove right-down
if (row + step) < len(problem) and (row + step) in candidates:
candidates.remove(row + step)
# remove right-up
if (row - step) >= 0 and (row - step) in candidates:
candidates.remove(row - step)
def construct_candidates(problem, k) -> int:
if k <= 0: # for first column
return [0] # return 'first row' if it is a 1x1 chess
else:
# find empty rows
candidates = set(range(len(problem)))
for col in range(k):
for row in range(max_rows):
if problem[row][col] > 0:
# remove queens in the same row or same column
if row in candidates:
candidates.remove(row)
# remove queens in the same diagonal
remove_diagonal(problem, (row, col), k, candidates)
return list(candidates)
# check all rows to make sure they all have queues ('1')
def is_solution(problem, k):
result = True
for index in range(min(k, len(problem))):
if sum(problem[index]) <= 0:
result = False
return result
def construct_solution(problem, candidate, k):
new_problem = problem.copy()
new_problem[candidate][k - 1] = 1
return new_problem
def solve(problem, k):
if is_solution(problem, k):
print_chess(problem)
return 1
else:
count = 0
candidates = construct_candidates(problem, k)
for candidate in candidates:
new_problem = construct_solution(problem, candidate, k)
count += solve(new_problem, k + 1)
return count
if __name__ == "__main__":
# try to resolve a max_rows x max_columns chess matrix
initial_problem = np.zeros((max_rows, max_columns), dtype=int)
count = solve(initial_problem, 1)
print("Number of solutions: ", count)I use NumPy for operations of the “chessboard” (matrix) as it’s extremely efficient.
The previous time I wrote code for the n-queens problem was in 2001, which was 20 years ago. The data centre of my school just gave us some old Intel 486 machines for practice, since we were not students of the computer science department (they keep the newest machines for their own students). The eight-queues problem cost about a half-hour to run at that time. But now it will only cost half a second on my laptop:
See how Moore’s law works in the recent 20 years.