timeit

Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Решение на Социална мрежа от Десислава Цветкова

Обратно към всички решения

Към профила на Десислава Цветкова

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 8 успешни тест(а)
  • 0 неуспешни тест(а)

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
from uuid import uuid4
from collections import defaultdict
import datetime
from math import inf


class UsersNotConnectedError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class PostList:
    def __init__(self, limit):
        self.limit = limit
        self.posts = []

    def append(self, post):
        if len(self.posts) == self.limit:
            self.posts.pop(0)
        self.posts.append(post)

    def __iter__(self):
        return iter(self.posts)


class Post:
    def __init__(self, content, author):
        self.content = content
        self.author = author
        self.published_at = datetime.datetime.now()

    def __repr__(self):
        return self.content


class User:
    LIMIT = 50

    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = PostList(type(self).LIMIT)

    def add_post(self, post_content):
        self.posts.append(Post(post_content, self.uuid))

    def get_post(self):
        return iter(self.posts)

    def __repr__(self):
        return self.full_name


class SocialGraph:
    def __init__(self):
        self.users = {}
        self.__following = defaultdict(set)
        self.__followers = defaultdict(set)

    def __initialize_user(self, user):
        self.users[user.uuid] = user
        self.__followers[user.uuid] = set()
        self.__following[user.uuid] = set()

    def __check(self, *args):
        for user_uuid in args:
            if user_uuid not in self.users.keys():
                raise UserDoesNotExistError

    def add_user(self, user):
        if user.uuid in self.users.keys():
            raise UserAlreadyExistsError
        self.__initialize_user(user)

    def get_user(self, user_uuid):
        self.__check(user_uuid)
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        self.__check(user_uuid)
        del self.users[user_uuid]

        for user in self.__following[user_uuid]:
            self.__followers[user].remove(user_uuid)
        for user in self.__followers[user_uuid]:
            self.__following[user].remove(user_uuid)

        del self.__following[user_uuid]
        del self.__followers[user_uuid]

    def follow(self, follower, followee):
        self.__check(follower, followee)

        self.__following[follower].add(followee)
        self.__followers[followee].add(follower)

    def unfollow(self, follower, followee):
        self.__check(follower, followee)
        try:
            self.__following[follower].remove(followee)
            self.__followers[followee].remove(follower)
        except KeyError:
            pass

    def is_following(self, follower, followee):
        self.__check(follower, followee)
        return followee in self.__following[follower]

    def followers(self, user_uuid):
        self.__check(user_uuid)
        return self.__followers[user_uuid]

    def following(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid]

    def friends(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid] & self.__followers[user_uuid]

    def max_distance(self, user_uuid):
        self.__check(user_uuid)
        farthest = 0
        visited = []
        to_be_visited = [(user_uuid, 0)]
        while to_be_visited:
            current, level = to_be_visited.pop(0)
            farthest = max(level, farthest)
            visited.append(current)
            for next_user in self.__following[current]:
                if next_user not in visited:
                    to_be_visited.append((next_user, level + 1))
        if farthest == 0:
            return inf
        return farthest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check(to_user_uuid, to_user_uuid)

        min_dist = self.__djiikstra(from_user_uuid)[to_user_uuid]
        if min_dist == inf:
            raise UsersNotConnectedError
        return min_dist

    def __djiikstra(self, from_user_uuid):
        distances = {user: inf for user in self.users.keys()}
        to_be_visited = list(self.users.keys())
        distances[from_user_uuid] = 0
        while to_be_visited:
            closest = min(to_be_visited, key=distances.get)
            to_be_visited.remove(closest)
            for user in self.__following[closest]:
                if distances[closest] + 1 < distances[user]:
                    distances[user] = distances[closest] + 1
        return distances

    def nth_layer_followings(self, user_uuid, n):
        self.__check(user_uuid)
        visited = [user_uuid]
        level = 0
        to_be_visited = [(user_uuid, level)]
        nthlevel = []

        while to_be_visited:
            current, level = to_be_visited.pop(0)
            if level == n and current not in visited:
                nthlevel.append(current)
            else:
                visited.append(current)
                for next_user in self.__following[current]:
                    if next_user not in visited:
                        to_be_visited.append((next_user, level + 1))
        return nthlevel

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check(user_uuid)
        all_posts = list(map(lambda x: self.users[x].posts.posts,
                             self.__following[user_uuid]))
        all_posts = [post for posts in all_posts for post in posts]
        all_posts.sort(key=lambda post: post.published_at, reverse=True)
        return all_posts[offset:offset + limit]

Лог от изпълнението

........
----------------------------------------------------------------------
Ran 8 tests in 0.077s

OK

История (3 версии и 2 коментара)

Десислава обнови решението на 10.04.2016 13:43 (преди над 1 година)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
from uuid import uuid4
from collections import defaultdict
import datetime
from math import inf


class UsersNotConnectedError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class PostList:
    def __init__(self, limit):
        self.limit = limit
        self.posts = []

    def append(self, post):
        if len(self.posts) == self.limit:
            self.posts.pop(0)
        self.posts.append(post)

    def __iter__(self):
        return iter(self.posts)


class Post:
    def __init__(self, content, author):
        self.content = content
        self.author = author
        self.published_at = datetime.datetime.now()

    def __repr__(self):
        return self.content


class User:
    LIMIT = 50

    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = PostList(type(self).LIMIT)

    def add_post(self, post_content):
        self.posts.append(Post(post_content, self.uuid))

    def get_post(self):
        return iter(self.posts)

    def __repr__(self):
        return self.full_name


class SocialGraph:
    def __init__(self):
        self.users = {}
        self.__following = defaultdict(set)
        self.__followers = defaultdict(set)

    def __check(self, user_uuid):
        if user_uuid not in self.users.keys():
            raise UserDoesNotExistError

    def add_user(self, user):
        if user.uuid in self.users.keys():
            raise UserAlreadyExistsError
        self.users[user.uuid] = user

    def get_user(self, user_uuid):
        self.__check(user_uuid)
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        self.__check(user_uuid)
        del self.users[user_uuid]

    def follow(self, follower, followee):
        self.__check(follower)
        self.__check(followee)

        self.__following[follower].add(followee)
        self.__followers[followee].add(follower)

    def unfollow(self, follower, followee):
        self.__check(follower)
        self.__check(followee)
        try:
            self.__following[follower].remove(followee)
            self.__followers[followee].remove(follower)
        except KeyError:
            pass

    def is_following(self, follower, followee):
        self.__check(follower)
        self.__check(followee)
        return followee in self.__following[follower]

    def followers(self, user_uuid):
        self.__check(user_uuid)
        return self.__followers[user_uuid]

    def following(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid]

    def friends(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid] & self.__followers[user_uuid]

    def max_distance(self, user_uuid):
        self.__check(user_uuid)
        farthest = 0
        visited = []
        to_be_visited = [(user_uuid, 0)]
        while to_be_visited:
            current, level = to_be_visited.pop(0)
            farthest = max(level, farthest)
            visited.append(current)
            for next_user in self.__following[current]:
                if next_user not in visited:
                    to_be_visited.append((next_user, level + 1))
        return farthest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check(to_user_uuid)
        self.__check(from_user_uuid)

        min_dist = self.__djiikstra(from_user_uuid)[to_user_uuid]
        if min_dist == inf:
            raise UsersNotConnectedError
        return min_dist

    def __djiikstra(self, from_user_uuid):
        distances = {user: inf for user in self.users.keys()}
        to_be_visited = list(self.users.keys())
        distances[from_user_uuid] = 0
        while to_be_visited:
            closest = min(to_be_visited, key=distances.get)
            to_be_visited.remove(closest)
            for user in self.__following[closest]:
                if distances[closest] + 1 < distances[user]:
                    distances[user] = distances[closest] + 1
        return distances

    def nth_layer_followings(self, user_uuid, n):
        self.__check(user_uuid)
        visited = []
        level = 0
        to_be_visited = [(user_uuid, level)]
        nth_layer_following = []

        while to_be_visited:
            current, level = to_be_visited.pop(0)
            visited.append(current)
            if level == n - 1:
                nth_layer_following.extend(self.__following[current])
            else:
                for next_user in self.__following[current]:
                    if next_user not in visited:
                        to_be_visited.append((next_user, level + 1))
        return nth_layer_following

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check(user_uuid)
        all_posts = list(map(lambda x: self.users[x].posts.posts,
                             self.__following[user_uuid]))
        all_posts = [post for posts in all_posts for post in posts]
        all_posts.sort(key=lambda post: post.published_at, reverse=True)
        return all_posts[offset:offset + limit]

Десислава обнови решението на 10.04.2016 14:12 (преди над 1 година)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
from uuid import uuid4
from collections import defaultdict
import datetime
from math import inf


class UsersNotConnectedError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class PostList:
    def __init__(self, limit):
        self.limit = limit
        self.posts = []

    def append(self, post):
        if len(self.posts) == self.limit:
            self.posts.pop(0)
        self.posts.append(post)

    def __iter__(self):
        return iter(self.posts)


class Post:
    def __init__(self, content, author):
        self.content = content
        self.author = author
        self.published_at = datetime.datetime.now()

    def __repr__(self):
        return self.content


class User:
    LIMIT = 50

    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = PostList(type(self).LIMIT)

    def add_post(self, post_content):
        self.posts.append(Post(post_content, self.uuid))

    def get_post(self):
        return iter(self.posts)

    def __repr__(self):
        return self.full_name


class SocialGraph:
    def __init__(self):
        self.users = {}
        self.__following = defaultdict(set)
        self.__followers = defaultdict(set)

    def __check(self, *args):
        for user_uuid in args:
            if user_uuid not in self.users.keys():
                raise UserDoesNotExistError

    def add_user(self, user):
        if user.uuid in self.users.keys():
            raise UserAlreadyExistsError
        self.users[user.uuid] = user

    def get_user(self, user_uuid):
        self.__check(user_uuid)
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        self.__check(user_uuid)
        del self.users[user_uuid]

    def follow(self, follower, followee):
        self.__check(follower, followee)

        self.__following[follower].add(followee)
        self.__followers[followee].add(follower)

    def unfollow(self, follower, followee):
        self.__check(follower, followee)
        try:
            self.__following[follower].remove(followee)
            self.__followers[followee].remove(follower)
        except KeyError:
            pass

    def is_following(self, follower, followee):
        self.__check(follower, followee)
        return followee in self.__following[follower]

    def followers(self, user_uuid):
        self.__check(user_uuid)
        return self.__followers[user_uuid]

    def following(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid]

    def friends(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid] & self.__followers[user_uuid]

    def max_distance(self, user_uuid):
        self.__check(user_uuid)
        farthest = 0
        visited = []
        to_be_visited = [(user_uuid, 0)]
        while to_be_visited:
            current, level = to_be_visited.pop(0)
            farthest = max(level, farthest)
            visited.append(current)
            for next_user in self.__following[current]:
                if next_user not in visited:
                    to_be_visited.append((next_user, level + 1))
        return farthest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check(to_user_uuid, to_user_uuid)

        min_dist = self.__djiikstra(from_user_uuid)[to_user_uuid]
        if min_dist == inf:
            raise UsersNotConnectedError
        return min_dist

    def __djiikstra(self, from_user_uuid):
        distances = {user: inf for user in self.users.keys()}
        to_be_visited = list(self.users.keys())
        distances[from_user_uuid] = 0
        while to_be_visited:
            closest = min(to_be_visited, key=distances.get)
            to_be_visited.remove(closest)
            for user in self.__following[closest]:
                if distances[closest] + 1 < distances[user]:
                    distances[user] = distances[closest] + 1
        return distances

    def nth_layer_followings(self, user_uuid, n):
        self.__check(user_uuid)
        visited = []
        level = 0
        to_be_visited = [(user_uuid, level)]
        nth_layer_following = []

        while to_be_visited:
            current, level = to_be_visited.pop(0)
            visited.append(current)
            if level == n - 1:
                nth_layer_following.extend(self.__following[current])
            else:
                for next_user in self.__following[current]:
                    if next_user not in visited:
                        to_be_visited.append((next_user, level + 1))
        return nth_layer_following

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check(user_uuid)
        all_posts = list(map(lambda x: self.users[x].posts.posts,
                             self.__following[user_uuid]))
        all_posts = [post for posts in all_posts for post in posts]
        all_posts.sort(key=lambda post: post.published_at, reverse=True)
        return all_posts[offset:offset + limit]
  • Подсигури се, че триеш всичко свързано с user-а при изтриването му

  • Много ми харесва колко изчистено си имплементирала точно алгоритмите за графи, които ти трябват :)

  • Аз не бих си кръщавала променливата nth_layer_following, тъй като едно погрешно добавено s накрая може да се превърне в ад за дабъгване :smile:

Десислава обнови решението на 17.04.2016 20:31 (преди над 1 година)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
from uuid import uuid4
from collections import defaultdict
import datetime
from math import inf


class UsersNotConnectedError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class PostList:
    def __init__(self, limit):
        self.limit = limit
        self.posts = []

    def append(self, post):
        if len(self.posts) == self.limit:
            self.posts.pop(0)
        self.posts.append(post)

    def __iter__(self):
        return iter(self.posts)


class Post:
    def __init__(self, content, author):
        self.content = content
        self.author = author
        self.published_at = datetime.datetime.now()

    def __repr__(self):
        return self.content


class User:
    LIMIT = 50

    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = PostList(type(self).LIMIT)

    def add_post(self, post_content):
        self.posts.append(Post(post_content, self.uuid))

    def get_post(self):
        return iter(self.posts)

    def __repr__(self):
        return self.full_name


class SocialGraph:
    def __init__(self):
        self.users = {}
        self.__following = defaultdict(set)
        self.__followers = defaultdict(set)

    def __initialize_user(self, user):
        self.users[user.uuid] = user
        self.__followers[user.uuid] = set()
        self.__following[user.uuid] = set()

    def __check(self, *args):
        for user_uuid in args:
            if user_uuid not in self.users.keys():
                raise UserDoesNotExistError

    def add_user(self, user):
        if user.uuid in self.users.keys():
            raise UserAlreadyExistsError
        self.__initialize_user(user)

    def get_user(self, user_uuid):
        self.__check(user_uuid)
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        self.__check(user_uuid)
        del self.users[user_uuid]

        for user in self.__following[user_uuid]:
            self.__followers[user].remove(user_uuid)
        for user in self.__followers[user_uuid]:
            self.__following[user].remove(user_uuid)

        del self.__following[user_uuid]
        del self.__followers[user_uuid]

    def follow(self, follower, followee):
        self.__check(follower, followee)

        self.__following[follower].add(followee)
        self.__followers[followee].add(follower)

    def unfollow(self, follower, followee):
        self.__check(follower, followee)
        try:
            self.__following[follower].remove(followee)
            self.__followers[followee].remove(follower)
        except KeyError:
            pass

    def is_following(self, follower, followee):
        self.__check(follower, followee)
        return followee in self.__following[follower]

    def followers(self, user_uuid):
        self.__check(user_uuid)
        return self.__followers[user_uuid]

    def following(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid]

    def friends(self, user_uuid):
        self.__check(user_uuid)
        return self.__following[user_uuid] & self.__followers[user_uuid]

    def max_distance(self, user_uuid):
        self.__check(user_uuid)
        farthest = 0
        visited = []
        to_be_visited = [(user_uuid, 0)]
        while to_be_visited:
            current, level = to_be_visited.pop(0)
            farthest = max(level, farthest)
            visited.append(current)
            for next_user in self.__following[current]:
                if next_user not in visited:
                    to_be_visited.append((next_user, level + 1))
        if farthest == 0:
            return inf
        return farthest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check(to_user_uuid, to_user_uuid)

        min_dist = self.__djiikstra(from_user_uuid)[to_user_uuid]
        if min_dist == inf:
            raise UsersNotConnectedError
        return min_dist

    def __djiikstra(self, from_user_uuid):
        distances = {user: inf for user in self.users.keys()}
        to_be_visited = list(self.users.keys())
        distances[from_user_uuid] = 0
        while to_be_visited:
            closest = min(to_be_visited, key=distances.get)
            to_be_visited.remove(closest)
            for user in self.__following[closest]:
                if distances[closest] + 1 < distances[user]:
                    distances[user] = distances[closest] + 1
        return distances

    def nth_layer_followings(self, user_uuid, n):
        self.__check(user_uuid)
        visited = [user_uuid]
        level = 0
        to_be_visited = [(user_uuid, level)]
        nthlevel = []

        while to_be_visited:
            current, level = to_be_visited.pop(0)
            if level == n and current not in visited:
                nthlevel.append(current)
            else:
                visited.append(current)
                for next_user in self.__following[current]:
                    if next_user not in visited:
                        to_be_visited.append((next_user, level + 1))
        return nthlevel

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check(user_uuid)
        all_posts = list(map(lambda x: self.users[x].posts.posts,
                             self.__following[user_uuid]))
        all_posts = [post for posts in all_posts for post in posts]
        all_posts.sort(key=lambda post: post.published_at, reverse=True)
        return all_posts[offset:offset + limit]