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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def checked(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        return func(self, *args)
    return checked


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if self.is_following(followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        level = 1
        queue = self.graph[from_user_uuid].following
        next_level = []
        visited = [from_user_uuid]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        queue = []
        next_level = self.graph[user_uuid].following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit + offset)]

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.063s

OK

История (5 версии и 0 коментара)

Тина обнови решението на 17.04.2016 23:07 (преди над 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def check(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        else:
            return func(self, *args)
    return check


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if SocialGraph.is_following(self, followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        user = self.graph[from_user_uuid]
        level = 1
        queue = user.following
        next_level = []
        visited = [user]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
                raise UserDoesNotExistError
        user = self.graph[user_uuid]
        queue = []
        next_level = user.following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit+offset)]

Тина обнови решението на 17.04.2016 23:32 (преди над 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def check(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        return func(self, *args)
    return check


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if SocialGraph.is_following(self, followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        user = self.graph[from_user_uuid]
        level = 1
        queue = user.following
        next_level = []
        visited = [user]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
                raise UserDoesNotExistError
        user = self.graph[user_uuid]
        queue = []
        next_level = user.following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit+offset)]

Тина обнови решението на 18.04.2016 14:09 (преди над 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def checked(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        return func(self, *args)
    return checked


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if SocialGraph.is_following(self, followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        user = self.graph[from_user_uuid]
        level = 1
        queue = user.following
        next_level = []
        visited = [user]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        user = self.graph[user_uuid]
        queue = []
        next_level = user.following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit+offset)]

Тина обнови решението на 18.04.2016 15:17 (преди над 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def checked(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        return func(self, *args)
    return checked


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if SocialGraph.is_following(self, followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        user = self.graph[from_user_uuid]
        level = 1
        queue = user.following
        next_level = []
        visited = [user]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        user = self.graph[user_uuid]
        queue = []
        next_level = user.following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit + offset)]

Тина обнови решението на 18.04.2016 15:56 (преди над 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid.uuid4()
        self.posts = []
        self.following = []

    def add_post(self, post_content):
        new_post = Post(self, post_content)
        self.posts.append(new_post)
        if len(self.posts) > 50:
            del self.posts[0]

    def get_post(self):
        for i in range(len(self.posts)):
            yield self.posts[i]


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


def user_exists(func):
    def checked(self, *args):
        for arg in args:
            if arg not in self.graph.keys():
                raise UserDoesNotExistError
        return func(self, *args)
    return checked


class SocialGraph:
    def __init__(self):
        self.graph = {}

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

    @user_exists
    def get_user(self, user_uuid):
        return self.graph[user_uuid]

    @user_exists
    def delete_user(self, user_uuid):
        self.graph[user_uuid].following = []
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                user.following.remove(user_uuid)
        del self.graph[user_uuid]

    @user_exists
    def follow(self, follower, followee):
        if followee not in self.graph[follower].following:
            self.graph[follower].following.append(followee)

    @user_exists
    def unfollow(self, follower, followee):
        if followee in self.graph[follower].following:
            self.graph[follower].following.remove(followee)

    @user_exists
    def is_following(self, follower, followee):
        return followee in self.graph[follower].following

    @user_exists
    def followers(self, user_uuid):
        followers = set()
        for uuid, user in self.graph.items():
            if user_uuid in user.following:
                followers.add(uuid)

        return followers

    @user_exists
    def following(self, user_uuid):
        return set(self.graph[user_uuid].following)

    @user_exists
    def friends(self, user_uuid):
        friends = set()
        for followee in self.graph[user_uuid].following:
            if self.is_following(followee, user_uuid):
                friends.add(followee)

        return friends

    @user_exists
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        level = 1
        queue = self.graph[from_user_uuid].following
        next_level = []
        visited = [from_user_uuid]
        while queue:
            for followed in queue:
                if followed == to_user_uuid:
                    return level
                else:
                    for next_level_followed in self.graph[followed].following:
                        if next_level_followed not in visited:
                            next_level.append(next_level_followed)
                    visited.append(followed)
            level += 1
            queue = next_level
            next_level = []
        raise UsersNotConnectedError

    @user_exists
    def max_distance(self, user_uuid):
        if not self.graph[user_uuid].following:
            return math.inf
        queue = [user_uuid]
        visited = [user_uuid]
        next_level = []
        max_distance = -1
        while queue:
            for user in queue:
                for followed in self.graph[user].following:
                    if followed not in visited:
                        next_level.append(followed)
                        visited.append(followed)
            max_distance += 1
            queue = next_level
            next_level = []
        return max_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        queue = []
        next_level = self.graph[user_uuid].following
        visited = [user_uuid]
        for i in range(n):
            queue = next_level
            next_level = []
            for followed in queue:
                for next_level_followed in self.graph[followed].following:
                    if next_level_followed not in visited:
                        next_level.append(next_level_followed)
                visited.append(followed)
        return set(queue)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.graph.keys():
            raise UserDoesNotExistError
        feed = []
        for user in self.graph[user_uuid].following:
            feed.extend(self.graph[user].posts)
        feed.sort(key=lambda posts: posts.published_at, reverse=True)
        if len(feed) < (limit - offset):
            return feed[offset::]
        else:
            return feed[offset:(limit + offset)]