Курс по алгоритмам на курсере

26 апреля 2020 г.

Начал проходить курс по алгоритмам на курсере, он бесплатный и имеет хороший рейтинг. В этом посте будут делать заметки, ну и буду постить свой вариант кода, который дается преподавателями. Все примеры в курсе на Java, я же их перепишу на Python и добавлю немного GUI для визуализации и лучшего понимания.

Решения домашних заданий выкладывать, конечно, не буду. Только код, который дают авторы курса. Надеюсь я не брошу этот курс, а то уже слишком много раз не доходил до конца курса.

1ая неделя

Quick Find

И первая тема, которая рассматривается в первой неделе - это проблема dynamic-connectivity. Суть в том, что дается массив int значений, где значение каждого элемента означает вхождение в определенную группу.

Например, дан массив [0, 1, 2] из трех элементов. Каждый элемент имеет свое уникальное значение, а значит, и входит в отдельную группу. Для проверки вхождения двух элементов в одну группу задается функция find которая проверяет входят ли два элемента в одну группу, путем сравнения значений, пример:

1 alist = [0, 1, 2]
2 
3 def find(p: int, q: int):
4     """Проверка вхождения в одну группу, p - индекс первого, q - второго элементов."""
5     return alist[p] == alist[q]

Проверим:

In [2]: find(0,1)
Out[2]: False

In [3]: find(0,2)
Out[3]: False

Затем, задается функция union, которая будет объединять два элемента в одну группу. При этом, нам нужно поменять либо значение всех элементов первой группы на значения элементов второй, либо наоборот. Произвольно решается менять значения элементов первой группы. То есть, если есть список [0, 1, 2] и мы вызываем union(p=0, q=1), то нужно поменять значение 0-го элемента на 1. В более общем случае это можно сделать так:

1 alist = [0, 1, 2]
2  
3 def union(p: int, q: int):
4     """Соединение элементов с индексами p и q в одну группу."""
5     p_val = alist[p]
6     q_val = alist[q]
7     for i, x in enumerate(alist):
8         if x == p_val:
9             alist[i] = q_val

Проверяем:

In [5]: find(0,1)
Out[5]: False

In [6]: union(0,1)

In [7]: find(0,1)
Out[7]: True

In [8]: alist
Out[8]: [1, 1, 2]

Можно также, это записать классом:

 1 class QuickFindUF(object):
 2     """QuickFindUF Union Find Class"""
 3 
 4     def __init__(self, num_of_elems: int):
 5         """Created list of elems here."""
 6         self.alist = list(range(num_of_elems))
 7 
 8     def is_connected(self, p: int, q: int):
 9         """Func to test if two elements connected."""
10         return self.alist[p] == self.alist[q]
11 
12     def union(self, p: int, q: int):
13         """Make union of elements."""
14         p_val = self.alist[p]
15         q_val = self.alist[q]
16         for i, x in enumerate(self.alist):
17             if x == p_val:
18                 self.alist[i] = q_val

Мне также хотелось это визуализировать, поэтому я решил написать небольшое GUI приложение для теста функции union:

 1 import tkinter as tk
 2 
 3 
 4 class Application(tk.Frame):
 5     """Simple Tkinter GUI for union-find theme."""
 6 
 7     def __init__(self, master: object, num_of_elems: int):
 8         """Creating widgets and uf object."""
 9         super().__init__(master)
10         self.master = master
11         self.pack()
12         self.num_of_elems = num_of_elems
13         self.uf = QuickFindUF(num_of_elems)
14         self.create_widgets()
15 
16     def create_widgets(self):
17         """Create all widgets."""
18         self.canvas = tk.Canvas(
19             self,
20             width=800,
21             height=600,
22             borderwidth=2,
23             relief='groove',
24         )
25         self.canvas.pack()
26 
27         self.create_circles()
28 
29         self.label = tk.Label(
30             self, text='Two indexes p and q, comma-separated for union',
31         )
32         self.label.pack()
33         self.entry = tk.Entry(self)
34         self.entry.pack()
35         self.btn = tk.Button(
36             self,
37             text='make union',
38             command=lambda: self.make_union(self.entry.get()),
39         )
40         self.btn.pack()
41 
42         self.regen_btn = tk.Button(
43             self,
44             text='clear and regenerate',
45             command=self.clear_and_regen,
46         )
47         self.regen_btn.pack()
48 
49         self.quit = tk.Button(
50             self,
51             text='QUIT',
52             fg='red',
53             command=self.master.destroy,
54         )
55         self.quit.pack()
56 
57     def create_circles(self):
58         """Creating circles with elements inside."""
59         x_off = 50
60         x = 80
61         y = 150
62         r = 20
63         for el in self.uf.alist:
64             x += x_off
65             x0 = x - r
66             y0 = y - r
67             x1 = x + r
68             y1 = y + r
69 
70             self.canvas.create_oval(x0, y0, x1, y1)
71             self.canvas.create_text(
72                 x,
73                 y,
74                 font='Roboto 20',
75                 fill='black',
76                 text=el,
77             )
78 
79     def make_union(self, value_str):
80         """Perform UF union operation and rerender canvas."""
81         val_list = value_str.split(',')
82         p = int(val_list[0])
83         q = int(val_list[1])
84         self.uf.union(p, q)
85         self.canvas.delete('all')
86         self.create_circles()
87 
88     def clear_and_regen(self):
89         """Clear canvas and rerender."""
90         self.canvas.delete('all')
91         self.uf = QuickFindUF(self.num_of_elems)
92         self.create_circles()
93 
94 
95 root = tk.Tk()
96 root.geometry('1024x768')
97 app = Application(root, num_of_elems=10)
98 app.mainloop()

Полностью код можно посмотреть на github. Видео того, как работает GUI приложение для темы Quick Find Union Find:

Метки

Если вам понравился пост, можете поделиться им в соцсетях: