Algorithms

Search…

README

Introduction

Location: Macao Polytechnic Institute

Time Schedule: From 26 Oct. Each Tuesday, 18:00 - 19:30

Semester: 1

Useful URLs

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!

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`

.**Fundamental Methodologies**- Linear Structure
- Generic Tree
- Linear Structure (maintained by Tree) (由树维护的线性结构)

- Generic Graph

**Graph Theory (图论)**- Multiple Source Shortest Path - I (多源最短路径)
- Network Flow (网络流)
- Bipartite Graph (二分图)

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.

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.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!

`n == height.length`

`2 <= n <= 105`

`0 <= height[i] <= 104`

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!

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*.

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!

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!

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!

`1 <= prices.length <= 3 * 104`

`0 <= prices[i] <= 104`

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

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.

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.

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!

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

Mention: You will see thisTest your codeSection 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.set`RUN_TEST = True`

2.copy the code file into directory`testing/`

3.run the code with command`python <file_name>.py`

4.Then the testing code will automatically start and result will be given

`#`

, 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!

**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.

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.

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`

Umm, when you understand recursion, it could.

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

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

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 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++

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.

Terms:

TREES - Learn with Data Structures

1

class Node:

2

def __init__(self, val, children=None):

3

self.val = val

4

self.children = children

Copied!

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 - emre.me

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!

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!

Let us consider the following problem to understand Binary Indexed Tree. We have an array

`arr[0 ... n-1]`

. We would like to- 1.Compute the sum of the first i elements.
- 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.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.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.- 1.Leaf Nodes are the elements of the input array.
- 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.

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 **cost** of travelling through each edges). If it is a directed graph,

`adj[A][B] = adj[B][A] = edge_value`

(Where `edge_value (边权值)`

is the `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

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!

`A --- B`

form.1

# Insert your code below

Copied!

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!

An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an **It is not hard to change the adjacency matrix to list form if you really understand how it works.**

`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. 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

Given an undirected and connected graph $G=(V,E)$ (This notation is graph representation in Discrete Mathematics: means graph **G** has a set of **V**ertices and a set of **E**dges), 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)

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.Cluster Analysis
- 2.Handwriting recognition
- 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.

- 1.Initialize the minimum spanning tree with a vertex chosen at random.
- 2.Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
- 3.Keep repeating step 2 until we get a minimum spanning tree

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

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

`*`

.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?

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 *the number of islands*.

`m x n`

2D binary grid `grid`

which represents a map of `'1'`

s (land) and `'0'`

s (water), return 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.

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!

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!

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 300`

`grid[i][j]`

is`'0'`

or`'1'`

.

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.

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!