README

Introduction

Lecturer: Steve Yan โ€‹
โ€‹
โ€‹
Location: Macao Polytechnic Institute
Time Schedule: From 26 Oct. Each Tuesday, 18:00 - 19:30
Semester: 1

Useful URLs

Typora: typora.io
โ€‹
Google Colab: google/colab
โ€‹
LeetCode: leetcode/problemset
โ€‹
POJ: poj/problemlist
โ€‹

How to use this repository?

Clone via HTTPS using following command or Click Code then Download ZIP.
1
git clone https://github.com/Ex10si0n/Algorithms.git
Copied!
You can open README.md (Markdown File: open via Typora or notepad.exe) locally or on this page.

Assessments

  • Attandance
  • Assignments

Outline

This lecture will specifically focus on the Algorithms implementation. My example code will be demostrated in Python, but you can adopt any kind of programming language if you prefer.
No slides are distributed (cuz. I do not regard slides as effecient format to display codes) but all of the codes and explanations are showed on this README.md.
Following topics will be covered in the Interest Group

Before We Start (for MPI Algorithms lecture)

Here are some useful tools for coding. I will briefly introduce them as follows:

vim (neovim)

Vim is a high efficient code editor in command line. I will use vim to implement the Algorithms code in this lecture. You can try to use it with ease because I will specifically introduce some shortcuts and modes of vim. But you are free to adopt any IDEs or text editor you like. You can install it by command:

Installation

1
# Linux
2
sudo <package-manager> install neovim
3
โ€‹
4
# macOS
5
brew install neovim
6
โ€‹
7
# Windows
8
choco install vim
Copied!

Package manager installation on macOS and Windows

1
# macOS (in Terminal.app)
2
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"
3
โ€‹
4
# Windows (in powershell.exe with Administrator)
5
Set-ExecutionPolicy Bypass -Scope Process -Force; [System.Net.ServicePointManager]::SecurityProtocol = [System.Net.ServicePointManager]::SecurityProtocol -bor 3072; iex ((New-Object System.Net.WebClient).DownloadString('https://community.chocolatey.org/install.ps1'))
Copied!

Or install vim in IDEs (better experience)

LeetCode

LeetCode in ็ŸฅไนŽ. It is a good platform for elementary algorithms learning. It is appropriate for preparing for a job as well as learning algorithms.
I you do not have a LeetCode account, please visit Leetcode.com or Leetcode-cn.com (ไธญๆ–‡้ข˜็›ฎ) to create an account.
โ€‹

Chapter 1. Fundamental Algorithms

Greedy

Greedy Algorithms can be adopted when a specific problem can be proofed that when locally optimal choice in each stages can produce a globally optimal choice. But in many problems, all stages is optimized does not means that it will be globally optimized.

โ€‹LC11 Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai)and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Example 1:
img
1
Input: height = [1,8,6,2,5,4,8,3,7]
2
Output: 49
3
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Copied!
Constraints:
  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104
Sol.
Picture0.png
  • If in Brute Force (ๆšดๅŠ›ๆžšไธพ) way, we can encount n * n possibilities then calculate each area to get the max area.
  • Greedy Approach can optimize the complexity from $O(N^2)$ to $O(N)$
    • Let i be the first line and j be the last line.
    • For each pair of lines selected, the covered area size is A(i, j) = min(height_i, height_j) * (j - i).
    • If we move the longer line inner, min(height_i', height_j') <= min(height_i, height_j)
    • If we move the shorter line inner, min(height_i', height_j') > or <= min(height_i, height_j)
    • If the area will be larger, the contribution of updating lines will be positive.
    • Hence, we can only encount only n - 1 times then we can get the largest area.
    • Ref. https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
    • Status Transferring Tree
1
class Solution:
2
def maxArea(self, height):
3
i = 0
4
j = len(height) - 1
5
ans = 0
6
while i < j:
7
if height[i] < height[j]:
8
ans = max(ans, height[i] * (j - i))
9
i += 1
10
else:
11
ans = max(ans, height[j] * (j - i))
12
j -= 1
13
return ans
Copied!

โ€‹LC122 Best Time to Buy and Sell Stock II (Exercise)

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
1
Input: prices = [7,1,5,3,6,4]
2
Output: 7
3
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
4
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
5
Total profit is 4 + 3 = 7.
Copied!
Example 2:
1
Input: prices = [1,2,3,4,5]
2
Output: 4
3
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
4
Total profit is 4.
Copied!
Example 3:
1
Input: prices = [7,6,4,3,1]
2
Output: 0
3
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Copied!
Constraints:
  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104
Sol.
Profit Graph
Consider two days
  • if the stock price of the next day is higher than today, buy it and sell it at next day.
  • in other circumstances, you can never earn more money.
1
class Solution:
2
def maxProfit(self, prices):
3
max = 0
4
for i in range(1, len(prices)):
5
if prices[i] > prices[i - 1]:
6
max += prices[i] - prices[i - 1]
7
return max
Copied!
Binary Search is an efficient algorithm for finding an item from a sorted set of items. Here is an example for finding -1 from the given list.
Could not load image
As the figure shows, adopting binary search can lower the time complexity from $O(N)$ to $O(\log N)$ [Note: When analysising Algorithms time and space complexity, $\log N$ stands for $log_2 N$]
The code pattern of binary search algorithms are easy to understand, we often use l, r, mid to point with the left and right pointer. mid is always calculated with the formular l + r // 2.
1
# Assume that bigger answer is better
2
l = 0, r = N, mid
3
โ€‹
4
while l < r:
5
mid = (l + r) // 2
6
if can_solve(mid):
7
l = mid
8
else:
9
r = mid
10
โ€‹
11
answer = mid
Copied!
By extension, when solving a problem, we can also adopt binary search for searching the solution from a sorted list of possible solution. Here is an example, make your hands dirty.

[Assignment I]P2678 Stones (NOIP15 Day2 Q1)

For a better understanding, you can read the problem in CN Version.
The annual "stone jumping" competition is about to start again! The competition will be held in a straight river with huge rocks distributed in the river. The committee has selected two rocks as the starting and ending points of the competition. Between the start point and the end point, there are N pieces of rocks (the rocks that do not include the start point and the end point). During the competition, the players will start from the starting point and jump to the adjacent rocks at each step until they reach the finish line.
In order to increase the difficulty of the competition, the committee plans to remove some rocks to make the shortest jumping distance of the contestants as long as possible during the competition. Due to budget constraints, the committee can remove at most M rocks between the start and end points (the start and end rocks cannot be removed).
You should write a program to read L, N, M that represent the distance between starting point and ending point(L), the number of rocks between starting point and ending point(N), number of rocks the committe can remove at most(M). The data constraint is L >= 1, N >= M >= 0
For the following N lines, the i-th line has $D_i$, which represents the distance between the i-th rock and the starting point. The data constraint is (i < j) Di < Dj, Di != Dj
And your program should print an integer which is the maximum distance of minimum jumpping interval.
Sample I/O
Input Data:
1
25 5 2
2
2
3
11
4
14
5
17
6
21
Copied!
Output Data:
1
4
Copied!
Explanation:
After removing the rocks that distance from starting point are 2 and 14, the rest rocks are 11, 17, 21. The solution is optimal. You can try other methods to see the result.
1
[Start]--- 11 ---[Rock(11)]-- 6 --[Rock(17)]- 4 -[End(21)]
Copied!
Data Scaling
Portion
M
N
L
20%
0 โ‰ค M โ‰ค 10
0 โ‰ค M โ‰ค 10
1 โ‰ค L โ‰ค 1,000,000,000
30%
10 โ‰ค M โ‰ค 100
10 โ‰ค M โ‰ค 100
1 โ‰ค L โ‰ค 1,000,000,000
50%
100 โ‰ค M โ‰ค 50,000
100 โ‰ค M โ‰ค 50,000
1 โ‰ค L โ‰ค 1,000,000,000
Test your code
Mention: You will see this Test your code Section when the problem is not available to test online, you may insert your codes on the template source code to implement algorithms in order to make the tester run dependablely.
How to test:
  1. 1.
    set RUN_TEST = True
  2. 2.
    copy the code file into directory testing/
  3. 3.
    run the code with command python <file_name>.py
  4. 4.
    Then the testing code will automatically start and result will be given
P2678 Template (Do not change lines indicated by #, your code can be inserted into the main() or Solution class)
1
class Solution: #
2
'''
3
Implement your algorithms here.
4
'''
5
pass
6
โ€‹
7
RUN_TEST = False
8
input_data = '''25 5 2
9
2
10
11
11
14
12
17
13
21'''
14
โ€‹
15
def main(input_data):
16
input_data_list = list(map(int, input_data.split())) #
17
L = input_data_list[0] #
18
N = input_data_list[1] #
19
M = input_data_list[2] #
20
D = input_data_list[3:] #
21
sol = Solution() #
22
23
ans = None
24
25
if not RUN_TEST: print(ans) #
26
return ans #
27
โ€‹
28
# Do not Change The following code
29
if __name__ == "__main__":
30
from time import time
31
from math import floor
32
if not RUN_TEST: main(input_data)
33
else:
34
earning = 0
35
testcases = 10
36
for i in range(1, 1 + testcases):
37
start = time()
38
_in = open('./test_data/stone/stone%d.in' % i, 'r')
39
key = open('./test_data/stone/stone%d.ans' % i, 'r')
40
input_data = _in.read()
41
ans = main(input_data)
42
end = time()
43
delta = floor((end - start) * 1000)
44
if delta > 1000: print('Time Exceeded Limit.')
45
elif ans - int(key.read()) == 0:
46
print('Test Point %d Accepted in %d ms.' % (i, delta))
47
earning += 1
48
else: print('Test Point %d Wrong Answer.' % i)
49
_in.close(); key.close()
50
print('Point (%d/%d)' % (earning, testcases))
Copied!
Sol.
  • Brute Force: We can select any groups of M stones to be removed. And record the maximum interval of the minimal jump.
  • Linear Search: For the maximum interval of the minimal jump, actually we can adopt the greedy methodology. To try the answer(ans) from L to 1. If two adjacent rocks has interval shorter than ans, then remove the next rock. If the attemption time less than M. It is just the optimal solution.
  • Binary Search: It is obvious that the answer of the question is allocated between 1 and L. For all possibilities we can use binary search to reduce the complexity from $O(N)$ to $O(\log N)$. Try to write the code to adopt the binary search methodology similar to the given code.
Core Code
1
class Solution:
2
โ€‹
3
def can_solve(self, M, D, mid):
4
remove = 0; _next = 0; now = 0; N = len(D)
5
while _next < N - 1:
6
_next += 1
7
if D[_next] - D[now] < mid: remove += 1
8
else: now = _next
9
if remove > M: return False
10
else: return True
11
โ€‹
12
def binary_search(self, L, M, N, D):
13
l = 0
14
r = L
15
ans = mid = 0
16
while l <= r:
17
mid = (l + r) // 2
18
if self.can_solve(M, D, mid):
19
ans = mid
20
l = mid + 1
21
else:
22
r = mid - 1
23
return ans
Copied!

Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive methodology, certain problems can be solved quite easily.
A Mathematical Interpretation
Let us consider a problem that a programmer have to determine the sum of first n natural numbers, there are several ways of doing that but the simplest approach is simply add the numbers starting from 1 to n. So the function simply looks like, (The markdown render of Github does not support LaTeX, better to read it in Typora)
$f(n) = \sum_{i=1}^n i $ or f(n) = 1 + 2 + ... + n
but there is another mathematical approach of representing this,
$f(n) = 1\qquad(n = 1)$ or f(n) = 1 when n == 1
$f(n) = n + f(n-1)\qquad(n>1)$ or f(n) = n + f(n - 1) when n > 1
Can recursion make code more readable?
Umm, when you understand recursion, it could.
Talk is cheap, show me the code. ref.โ€‹
Here is an example for calculating Fibonacci.
1
# Recursion
2
def fibonacci(n):
3
if n <= 2:
4
return 1
5
else:
6
return fibonacci(n - 1) + fibonacci(n - 2)
Copied!
An experienced programmer should have no problem understanding the logic behind the code. As we can see, in order to compute a Fibonacci number, Fn, the function needs to call Fn-1 and Fn-2. Fn-1 recursively calls Fn-2 and Fn-3, and Fn-2 calls Fn-3 and Fn-4. In a nutshell, each call recursively computes two values needed to get the result until control hits the base case, which happens when n<=2.
You can write a simple main() that accepts an integer n as input and outputs the nโ€™th Fibonacci by calling this recursive function and see for yourself how slowly it computes as n gets bigger. It gets horrendously slow once n gets past 40 on my machine.
Here is a non-recursive version that calculates the Fibonacci number:
1
# Non-Recursion
2
def fibonacci(int n):
3
if n <= 2:
4
return 1
5
last = 1
6
nextToLast = 1
7
result = 1
8
for i in range(3, n+1):
9
result = last + nextToLast
10
nextToLast = last
11
last = result
12
return result
Copied!
The logic here is to keep the values already computed in variables last and nextToLast in every iteration of the for loop so that every Fibonacci number is computed exactly once. In this case, every single value is computed only once no matter how big n is.

Data Structure

Linear Structure

Queue
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Types of Queue in Data structure | Queue Data structure Introduction and Operations
Code to implement [src code]โ€‹
1
class Queue:
2
def __init__(self):
3
self.queue = []
4
5
def push(self, elm):
6
self.queue.append(elm)
7
8
def pop(self):
9
val = self.queue[0]
10
del self.queue[0]
11
return val
Copied!
Stack
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Stack Data Structure and Implementation in Python, Java and C/C++
**Code to implement **[src code]โ€‹
1
class Stack:
2
def __init__(self):
3
self.stack = []
4
5
def push(self, elm):
6
self.stack.append(elm)
7
8
def pop(self):
9
val = self.stack.pop()
10
return val
Copied!

Generic Tree

It is a hierarchical structure as elements in a Tree are arranged in multiple levels. In the Tree data structure, the topmost node is known as a root node. Each node contains some data, and data can be of any type.
Tree
Terms:
TREES - Learn with Data Structures
Code to implement [src code]โ€‹
1
class Node:
2
def __init__(self, val, children=None):
3
self.val = val
4
self.children = children
Copied!
Traversal
1
def preorder(root):
2
if root:
3
print(root.val)
4
for child in root.children:
5
preorder(child)
6
โ€‹
7
def postorder(root):
8
if root:
9
for child in root.children:
10
postorder(child)
11
print(root.val)
Copied!
Binary Tree
Binary Tree - emre.me
Code to implement [src code]โ€‹
1
class Node:
2
def __init__(self, val, lch=None, rch=None):
3
self.val = val
4
self.lch = lch
5
self.rch = rch
Copied!
Traversal
1
def preorder(root):
2
if root:
3
print(root.val)
4
preorder(root.lch)
5
preorder(root.rch)
6
โ€‹
7
def postorder(root):
8
if root:
9
postorder(root.lch)
10
postorder(root.rch)
11
print(root.val)
Copied!
Linear Structure Maintained by Tree
Binary Indexed Tree
Let us consider the following problem to understand Binary Indexed Tree. We have an array arr[0 ... n-1]. We would like to
  1. 1.
    Compute the sum of the first i elements.
  2. 2.
    Modify the value of a specified element of the array arr[i] = x where 0 <= i <= n-1.
A simple solution is to run a loop from 0 to i-1 and calculate the sum of the elements. To update a value, simply do arr[i] = x. The first operation takes $O(n)$ time and the second operation takes $O(1)$ time. Another simple solution is to create an extra array and store the sum of the first i-th elements at the i-th index in this new array. The sum of a given range can now be calculated in $O(1)$ time, but the update operation takes $O(n)$ time now. This works well if there are a large number of query operations but a very few number of update operations.
Could we perform both the query and update operations in $O(\log n)$ time?
Take a look at this example.
Each Orange node maintains an interval sum of numbers. If we rotate it, we can have a better understanding.
For example, to get the interval sum(or any other data of an interval you defined) of [0, 10]. just add 2 values rather than 11 values. Try to find which 2 values are components to sum up.
Segment Tree
Let us consider the previous question in Binary Indexed Treeโ€‹
A simple solution is to run a loop from l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes $O(n)$ time and the second operation takes $O(1)$ time.
Another solution is to create another array and store sum from start to i at the ith index in this array. The sum of a given range can now be calculated in $O(1)$ time, but update operation takes $O(n)$ time now. This works well if the number of query operations is large and very few updates. What if the number of query and updates are equal? Can we perform both the operations in $O(\log N)$ time once given the array? We can use a Segment Tree to do both operations in $O(\log N)$ time.
How it works?
  1. 1.
    Leaf Nodes are the elements of the input array.
  2. 2.
    Each internal node represents some merging of the leaf nodes. The merging may be different for different problems. For this problem, merging is sum of leaves under a node.
An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2 * i + 1, right child at 2 * i + 2 and the parent is at โŒŠ(i โ€“ 1) / 2โŒ‹(Note: โŒŠexpressionโŒ‹notation means flooring).

Generic Graph

In this section, I will only introduce the data structure of generic graph and the implementation. The more complex version of graph is in the following chapter.
Adjacency Matrix
Let's back to this straightforward staff: The adjacency matrix to describing or saving a graph in the memory. If node A and node B is interconnected, then adj[A][B] = adj[B][A] = edge_value(Where edge_value (่พนๆƒๅ€ผ) is the cost of travelling through each edges). If it is a directed graph, A -> B means there is a path from A to B but not from B to A, then adj[A][B] = edge_value. The space complexity is $O(N^2)$. That means if the graph has 1,000,000 nodes, an 1,000,000 x 1,000,000 matrix will take in use. Although the size is horrible, it is the most easy understanding way of describing a graph, here is the example and code implementation.
Could not load image
Code to initialize
1
nodes = ['A', 'B', 'C', 'D', 'E', 'F']
2
n = len(nodes)
3
โ€‹
4
# pure python
5
adj = []
6
for i in range(n):
7
adj.append([0] * n)
8
9
# equivalent form by numpy
10
import numpy
11
adj = numpy.zeros([n, n])
Copied!
Exercise: Build an adjacency matrix of non-directed graph in last figure then print the matrix and list all the edge in A --- B form.
1
# Insert your code below
Copied!
One of the solutions
1
edges = ['A B', 'B E', 'B C', 'E C', 'E D', 'C D', 'E F']
2
_map = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5,\
3
5: 'F', 4: 'E', 3: 'D', 2: 'C', 1: 'B', 0: 'A'}
4
โ€‹
5
adj = []
6
n = len(edges)
7
โ€‹
8
โ€‹
9
for i in range(n):
10
adj.append([0] * n)
11
โ€‹
12
for e in edges:
13
from_node, to_node = e.split(' ')
14
adj[_map[from_node]][_map[to_node]] = adj[_map[to_node]][_map[from_node]] = 1
15
โ€‹
16
for i in range(n):
17
for j in range(i, n):
18
if adj[i][j] == 1:
19
print(_map[i], '---', _map[j])
Copied!
Adjacency List
An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an G[]. An entry G[i] represents the list of vertices adjacent to the i-th vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation. It is not hard to change the adjacency matrix to list form if you really understand how it works.
Code to implement [src code]โ€‹
1
G = {}
2
for i in range(10): # The above graph has 10 edges
3
from_node, to_node = input().split(' ')
4
if from_node in G.keys(): G[from_node].append(to_node)
5
else: G[from_node] = [to_node]
6
if to_node in G.keys(): G[to_node].append(from_node)
7
else: G[to_node] = [from_node]
8
9
print(G)
Copied!
1
G = {'A': ['B', 'E', 'G'],
2
'B': ['A', 'G'],
3
'C': ['D', 'E', 'F'],
4
'D': ['C', 'G'],
5
'E': ['A', 'C', 'F'],
6
'F': ['C', 'E', 'G'],
7
'G': ['A', 'B', 'D', 'F']}
Copied!
Up till now, you have read all of the contents of Chapter 1. I strongly advice you writing the code from the scratch to implement the basic data structure. In the following chapter, it's time to learn some tricky stuffs.

Chapter 2. Graph Theory

Minimum Spanning Tree

What is a Spanning Tree?
Given an undirected and connected graph $G=(V,E)$ (This notation is graph representation in Discrete Mathematics: means graph G has a set of Vertices and a set of Edges), a spanning tree of the graph G is a tree that spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G)
What is a Minimum Spanning Tree?
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are:
  1. 1.
    Cluster Analysis
  2. 2.
    Handwriting recognition
  3. 3.
    Image segmentation

Prim's Algorithms

Primโ€™s Algorithm use Greedy approach to find the minimum spanning tree. We start from one vertex and keep adding edges with the lowest weight until we reach our goal.
The steps for implementing Prim's algorithm:
  1. 1.
    Initialize the minimum spanning tree with a vertex chosen at random.
  2. 2.
    Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
  3. 3.
    Keep repeating step 2 until we get a minimum spanning tree
Code: [src code]โ€‹
1
class Graph:
2
โ€‹
3
def __init__(self, vertices, edges):
4
self.vertices = vertices
5
self.edges = edges
6
โ€‹
7
def adjacency_list(self):
8
G = {}
9
for i in range(len(self.edges)):
10
from_node, to_node, val = self.edges[i].split(' ')
11
if from_node in G.keys(): G[from_node].append((to_node, val))
12
else: G[from_node] = [(to_node, val)]
13
if to_node in G.keys(): G[to_node].append((from_node, val))
14
else: G[to_node] = [(from_node, val)]
15
return G
16
โ€‹
17
18
class Prims:
19
โ€‹
20
def __init__(self, graph):
21
self.visited = []
22
self.mst = []
23
self.graph = graph
24
self.N = len(self.graph.keys())
25
self.visited.append(list(graph.keys())[0])
26
โ€‹
27
def prims(self):
28
while len(self.mst) < self.N - 1:
29
_min = float('inf')
30
from_node = to_node = None;
31
for node in self.visited:
32
for _next in self.graph[node]:
33
next_node = _next[0]
34
edge_val = int(_next[1])
35
if next_node not in self.visited:
36
if _min > edge_val:
37
_min = edge_val
38
from_node = node
39
to_node = next_node
40
โ€‹
41
e = (from_node, to_node, _min)
42
self.visited.append(to_node)
43
self.mst.append(e)
44
return self.mst
45
โ€‹
46
โ€‹
47
if __name__ == "__main__":
48
vertices = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
49
edges = ['a b 4', 'b c 8', 'c d 7', 'd e 9', 'e f 10', 'f g 2', 'g h 1',\
50
'h i 7', 'a h 8', 'g i 6', 'c i 2', 'c f 4', 'd f 14', 'b h 11']
51
graph = Graph(vertices, edges).adjacency_list()
52
mst = Prims(graph).prims()
53
print(mst)
Copied!
Depth First Search (abbr. DFS) (ๆทฑๅบฆไผ˜ๅ…ˆๆœ็ดข) is an algorithm for graph or tree traversal or searching a specific node in a tree. It adopts recursion, so you should understand recursion for a better learning of DFS. For a simple example, there is code snippet of DFS.
Consider the maze is the following:
1
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
2
#. .#. . . . . . . .#. . . . . . . .#. .#.
3
#. .#. .#.#.#.#.#. .#.#.#. .#.#.#. .#. .#.
4
#. . . .#. . . .#. .#. . . .#. .#. . . .#.
5
#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#. .#.
6
#. . . . . . . .#. .#. . . .#. . . . . .#.
7
#. .#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#.
8
#. . . . . . . . . .#. .#. . . .#. . . .#.
9
#. .#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#. .#.
10
#. .#. . . . . . . .#. . . . . .#. .#. .#.
11
#. .#.#.#. .#.#.#. .#. .#.#.#.#.#. .#. .#.
12
#. . . .#. . . .#. . . .#. . . .#. .#. .#.
13
#.#.#. .#.#.#. .#.#.#.#.#. .#. .#. .#. .#.
14
#. .#. . . . . .#. . . . . .#. .#. .#. .#.
15
#. .#.#.#.#.#.#.#.#.#.#.#. .#. .#. .#. .#.
16
#. . . . . .#. . . . . .#. .#. . . .#. .#.
17
#. .#.#.#.#.#. .#. .#. .#. .#. .#.#.#. .#.
18
#. . . . . .#. .#. .#. . . .#. .#. . . .#.
19
#. .#.#.#. .#. .#. .#.#.#.#.#.#.#. .#.#.#.
20
#. . . .#. . . .#. . . . . . . . . . . .#.
21
#.#.#.#.X.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
Copied!
To let computer program walk through the maze, we can adopt DFS in the problem solving program. Here is the pseudo code.
1
def dfs(now_position):
2
visited.append(now_position)
3
if now_position == exit_position:
4
return True
5
# Try to step on adjacent position
6
for dir in "โ†โ†“โ†‘โ†’":
7
next_position = now_position.step(dir)
8
# The case when next position can be stepped on
9
if not next_position is "#" and next_position not in visited:
10
dfs(next_position)
Copied!
Please try to solve the previous maze problem by referencing pseudo code (Or any type of Algorithms you like or you have created). And mark the path using *.
Here is the code to help your program reading and storing the maze. [src code]โ€‹
1
maze = '''#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
2
#.#.#. . . . . . . .#. . . . . . . .#. .#.
3
#. .#. .#.#.#.#.#. .#.#.#. .#.#.#. .#. .#.
4
#. . . .#. . . .#. .#. . . .#. .#. . . .#.
5
#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#. .#.
6
#. . . . . . . .#. .#. . . .#. . . . . .#.
7
#. .#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#.
8
#. . . . . . . . . .#. .#. . . .#. . . .#.
9
#. .#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#. .#.
10
#. .#. . . . . . . .#. . . . . .#. .#. .#.
11
#. .#.#.#. .#.#.#. .#. .#.#.#.#.#. .#. .#.
12
#. . . .#. . . .#. . . .#. . . .#. .#. .#.
13
#.#.#. .#.#.#. .#.#.#.#.#. .#. .#. .#. .#.
14
#. .#. . . . . .#. . . . . .#. .#. .#. .#.
15
#. .#.#.#.#.#.#.#.#.#.#.#. .#. .#. .#. .#.
16
#. . . . . .#. . . . . .#. .#. . . .#. .#.
17
#. .#.#.#.#.#. .#. .#. .#. .#. .#.#.#. .#.
18
#. . . . . .#. .#. .#. . . .#. .#. . . .#.
19
#. .#.#.#. .#. .#. .#.#.#.#.#.#.#. .#.#.#.
20
#. . . .#. . . .#. . . . . . . . . . .#.#.
21
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.'''
22
โ€‹
23
def maze_parser(maze):
24
res = []
25
for line in maze.strip().split('\n'):
26
line = line.strip().split('.')
27
res.append(line)
28
return res
29
โ€‹
30
if __name__ == '__main__':
31
maze = maze_parser(maze)
32
start = [1, 1]
33
end = [19, 19]
Copied!
Using the above parser, the maze can be processed into an 2-D matrix (or array). you can access any (x, y) by invoking maze[x][y].
Please try to understand the psedo code first. Solution changes several codes due to specific problem solving. path list is recorded in each dfs() function's parameter list.
Why the path list should be recorded in the dfs() parameter list but not as instance variable?
Sol. [src code]โ€‹
1
maze = '''#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
2
#.#.#. . . . . . . .#. . . . . . . .#. .#.
3
#. .#. .#.#.#.#.#. .#.#.#. .#.#.#. .#. .#.
4
#. . . .#. . . .#. .#. . . .#. .#. . . .#.
5
#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#. .#.
6
#. . . . . . . .#. .#. . . .#. . . . . .#.
7
#. .#.#.#.#.#.#.#. .#. .#. .#.#.#. .#.#.#.
8
#. . . . . . . . . .#. .#. . . .#. . . .#.
9
#. .#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#. .#.
10
#. .#. . . . . . . .#. . . . . .#. .#. .#.
11
#. .#.#.#. .#.#.#. .#. .#.#.#.#.#. .#. .#.
12
#. . . .#. . . .#. . . .#. . . .#. .#. .#.
13
#.#.#. .#.#.#. .#.#.#.#.#. .#. .#. .#. .#.
14
#. .#. . . . . .#. . . . . .#. .#. .#. .#.
15
#. .#.#.#.#.#.#.#.#.#.#.#. .#. .#. .#. .#.
16
#. . . . . .#. . . . . .#. .#. . . .#. .#.
17
#. .#.#.#.#.#. .#. .#. .#. .#. .#.#.#. .#.
18
#. . . . . .#. .#. .#. . . .#. .#. . . .#.
19
#. .#.#.#. .#. .#. .#.#.#.#.#.#.#. .#.#.#.
20
#. . . .#. . . .#. . . . . . . . . . .#.#.
21
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.'''
22
โ€‹
23
def maze_parser(maze):
24
res = []
25
for line in maze.strip().split('\n'):
26
line = line.strip().split('.')
27
res.append(line)
28
return res
29
โ€‹
30
class Search:
31
def __init__(self, maze, start, end):
32
self.visited = []
33
self.maze = maze
34
self.start = start
35
self.end = end
36
self.size = end[0] + 2
37
self.move_dir = [[-1, 0], [0, -1], [1, 0], [0, 1]]
38
self.path = None
39
self.solve()
40
โ€‹
41
def move(self, _from, towards):
42
return [_from[0]+towards[0], _from[1]+towards[1]]
43
โ€‹
44
def draw_path(self):
45
for step in self.path:
46
self.maze[step[0]][step[1]] = '*'
47
โ€‹
48
def print_maze(self):
49
for i in range(self.size):
50
for j in range(self.size):
51
print(self.maze[i][j], end=' ')
52
print()
53
โ€‹
54
def solve(self):
55
self.dfs(self.start, path=[])
56
self.path = [self.path[i:i+2] for i in range(0, len(self.path), 2)]
57
self.draw_path()
58
self.print_maze()
59
โ€‹
60
def dfs(self, now_position, path):
61
self.visited.append(now_position)
62
if now_position == self.end:
63
self.path = path
64
return True
65
for _dir in self.move_dir:
66
next_position = self.move(_from=now_position, towards=_dir)
67
x = next_position[0]; y = next_position[1]
68
if next_position not in self.visited and maze[x][y] != '#':
69
self.dfs(next_position, path+now_position)
70
return False
71
โ€‹
72
โ€‹
73
if __name__ == '__main__':
74
maze = maze_parser(maze)
75
start = [1, 1]
76
end = [19, 19]
77
search = Search(maze, start, end)
Copied!

LC200 Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
1
Input: grid = [
2
["1","1","1","1","0"],
3
["1","1","0","1","0"],
4
["1","1","0","0","0"],
5
["0","0","0","0","0"]
6
]
7
Output: 1
Copied!
Example 2:
1
Input: grid = [
2
["1","1","0","0","0"],
3
["1","1","0","0","0"],
4
["0","0","1","0","0"],
5
["0","0","0","1","1"]
6
]
7
Output: 3
Copied!
Constraints:
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.
Sol.
1
class Solution:
2
3
def dfs(self, grid, x, y):
4
move_dir = [[-1, 0], [0, 1], [0, -1], [1, 0]]
5
grid[x][y] = '0'
6
for _dir in move_dir:
7
next_x = x + _dir[0]
8
next_y = y + _dir[1]
9
if next_x >= 0 and next_y >= 0 and next_x < len(grid) and next_y < len(grid[0]):
10
if grid[next_x][next_y] == '1':
11
self.dfs(grid, next_x, next_y)
12
13
14
def numIslands(self, grid: List[List[str]]) -> int:
15
res = 0
16
for x in range(len(grid)):
17
for y in range(len(grid[0])):
18
if grid[x][y] == '1':
19
self.dfs(grid, x, y)
20
res += 1
21
return res
Copied!

Shortest Path I

Here is the map of Ex10si0n island. He designed the arrangement of each town (namely A B C D E F G -town) with roads. When the tourist go through a certain path, he or she will pay for a number of coins. The cost of each road is the number inside each diamonds.
You are paying a visit to Ex10si0n island. Can you find the minimum cost for travelling between arbitary two towns?
You may notice that A town is marked in red. The red color have no meanings in current problem.
Graph data
1
_map = {}
2
for i in range(7): _map[i] = chr(i+65); _map[chr(i+65)] = i
3
towns = [chr(i) for i in range(65, 65+7)]
4
edges = ['A B 4', 'A C 1', 'B C 2', 'B D 7', 'B E 6', 'C E 5',\
5
'D G 1', 'E G 6', 'E F 2', 'A F 10', 'F D 9', 'F G 0']
Copied!