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
import uuid
import datetime
from collections import defaultdict
from math import inf


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        yield from self.posts


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(function):
        def check_and_execution(*args):
            arg_count = len(args) == 2 or not isinstance(args[2], uuid.UUID)
            if arg_count or args[1] == args[2]:
                if not any([user.uuid == args[1] for user in args[0].users]):
                    raise UserDoesNotExistError
            elif not [user.uuid == args[1] or user.uuid == args[2]
                      for user in args[0].users].count(True) == 2:
                raise UserDoesNotExistError
            return function(*args)
        return check_and_execution

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    @users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise UserCannotFollowHimselfError
        self.followings[follower].add(followee)

    @users_exist
    def unfollow(self, follower, followee):
        self.followings[follower].discard(followee)

    @users_exist
    def is_following(self, follower, followee):
        return followee in self.followings[follower]

    @users_exist
    def followers(self, user_uuid):
        return {user for user, followees in self.followings.items()
                if user_uuid in followees}

    @users_exist
    def following(self, user_uuid):
        return self.followings[user_uuid]

    @users_exist
    def friends(self, user_uuid):
        return {user for user in self.followers(user_uuid)
                if user in self.followings[user_uuid]}

    @users_exist
    def max_distance(self, user_uuid):
        if self.followings[user_uuid] == set():
            return inf
        distance = 0
        nodes = {user_uuid}
        visited = {user_uuid}
        next_layer = set()
        while len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            nodes = next_layer.copy()
            next_layer.clear()
        return distance - 1

    @users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        distance = 0
        nodes = {from_user_uuid}
        visited = {from_user_uuid}
        next_layer = set()
        while len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            if to_user_uuid in next_layer:
                return distance
            nodes = next_layer.copy()
            next_layer.clear()
        raise UsersNotConnectedError

    @users_exist
    def nth_layer_followings(self, user_uuid, n):
        distance = 0
        nodes = {user_uuid}
        visited = {user_uuid}
        next_layer = set()
        while distance < n and len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            nodes = next_layer.copy()
            next_layer.clear()
        return nodes

    @users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        posts = []
        for user in self.following(user_uuid):
            posts.extend(self.get_user(user).posts)
        posts.sort(key=lambda post: post.published_at)
        return posts[-(offset + 1):-(limit + offset + 1):-1]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCannotFollowHimselfError(Exception):
    pass

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.065s

OK

История (6 версии и 4 коментара)

Тодор обнови решението на 09.04.2016 22:28 (преди над 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
import uuid
import datetime
from collections import defaultdict


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        for post in self.posts:
            yield post


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(self, *args):
        if len(args) in {1, 3}:
            return any([user.uuid == args[0] for user in self.users])
        return [user.uuid == args[0] or user.uuid == args[1]
                for user in self.users].count(True) == 2

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    def follow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].add(followee)
        else:
            raise UserDoesNotExistError

    def unfollow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].discard(followee)
        else:
            raise UserDoesNotExistError

    def is_following(self, follower, followee):
        if self.users_exist(follower, followee):
            return followee in self.followings[follower]
        else:
            raise UserDoesNotExistError

    def followers(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followings
                    if user_uuid in self.followings[user]}
            # return {user for user, followees in self.followings.items()
            #         if user_uuid in followees}
        else:
            raise UserDoesNotExistError

    def following(self, user_uuid):
        if self.users_exist(user_uuid):
            return self.followings[user_uuid]
        else:
            raise UserDoesNotExistError

    def friends(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followers(user_uuid)
                    if user in self.followings[user_uuid]}
        else:
            raise UserDoesNotExistError

    def distances(self, *args):
        if self.users_exist(*args):
            distance = 0
            nodes = {args[0]}
            visited = {args[0]}
            new_nodes = set()
            while len(nodes):
                if len(args) == 3 and distance == args[1]:
                    break
                for node in nodes:
                    new_nodes.update(self.followings[node].difference(visited))
                    visited.update(new_nodes)
                distance += 1
                if len(args) == 2 and args[1] in new_nodes:
                    return distance
                nodes = new_nodes.copy()
                new_nodes.clear()
            if len(args) == 2:
                raise UsersNotConnectedError
            elif len(args) == 3:
                return list(nodes)
            return distance - 1
        else:
            raise UserDoesNotExistError

    def max_distance(self, user_uuid):
        return self.distances(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return self.distances(from_user_uuid, to_user_uuid)

    def nth_layer_followings(self, user_uuid, n):
        return self.distances(user_uuid, n, None)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if self.users_exist(user_uuid):
            posts = []
            for user in self.following(user_uuid):
                posts.extend(self.get_user(user).posts)
                print([post.content for post in self.get_user(user).posts])
            posts.sort(key=lambda post: post.published_at)
            print([post.content for post in posts])
            return posts[-(offset+1):-(limit+1):-1]
        else:
            raise UserDoesNotExistError


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

Тодор обнови решението на 09.04.2016 23:04 (преди над 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
import uuid
import datetime
from collections import defaultdict


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        for post in self.posts:
            yield post


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(self, *args):
        if len(args) in {1, 3}:
            return any([user.uuid == args[0] for user in self.users])
        return [user.uuid == args[0] or user.uuid == args[1]
                for user in self.users].count(True) == 2

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    def follow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].add(followee)
        else:
            raise UserDoesNotExistError

    def unfollow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].discard(followee)
        else:
            raise UserDoesNotExistError

    def is_following(self, follower, followee):
        if self.users_exist(follower, followee):
            return followee in self.followings[follower]
        else:
            raise UserDoesNotExistError

    def followers(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followings
                    if user_uuid in self.followings[user]}
            # return {user for user, followees in self.followings.items()
            #         if user_uuid in followees}
        else:
            raise UserDoesNotExistError

    def following(self, user_uuid):
        if self.users_exist(user_uuid):
            return self.followings[user_uuid]
        else:
            raise UserDoesNotExistError

    def friends(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followers(user_uuid)
                    if user in self.followings[user_uuid]}
        else:
            raise UserDoesNotExistError

    def distances(self, *args):
        if self.users_exist(*args):
            distance = 0
            nodes = {args[0]}
            visited = {args[0]}
            new_nodes = set()
            while len(nodes):
                if len(args) == 3 and distance == args[1]:
                    break
                for node in nodes:
                    new_nodes.update(self.followings[node].difference(visited))
                    visited.update(new_nodes)
                distance += 1
                if len(args) == 2 and args[1] in new_nodes:
                    return distance
                nodes = new_nodes.copy()
                new_nodes.clear()
            if len(args) == 2:
                raise UsersNotConnectedError
            elif len(args) == 3:
                return nodes
            return distance - 1
        else:
            raise UserDoesNotExistError

    def max_distance(self, user_uuid):
        return self.distances(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return self.distances(from_user_uuid, to_user_uuid)

    def nth_layer_followings(self, user_uuid, n):
        return self.distances(user_uuid, n, None)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if self.users_exist(user_uuid):
            posts = []
            for user in self.following(user_uuid):
                posts.extend(self.get_user(user).posts)
            posts.sort(key=lambda post: post.published_at)
            return posts[-(offset+1):-(limit+1):-1]
        else:
            raise UserDoesNotExistError


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

Тодор обнови решението на 09.04.2016 23:34 (преди над 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
import uuid
import datetime
from collections import defaultdict


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        for post in self.posts:
            yield post


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(self, *args):
        if len(args) in {1, 3}:
            return any([user.uuid == args[0] for user in self.users])
        return [user.uuid == args[0] or user.uuid == args[1]
                for user in self.users].count(True) == 2

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    def follow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].add(followee)
        else:
            raise UserDoesNotExistError

    def unfollow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].discard(followee)
        else:
            raise UserDoesNotExistError

    def is_following(self, follower, followee):
        if self.users_exist(follower, followee):
            return followee in self.followings[follower]
        else:
            raise UserDoesNotExistError

    def followers(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followings
                    if user_uuid in self.followings[user]}
            # return {user for user, followees in self.followings.items()
            #         if user_uuid in followees}
        else:
            raise UserDoesNotExistError

    def following(self, user_uuid):
        if self.users_exist(user_uuid):
            return self.followings[user_uuid]
        else:
            raise UserDoesNotExistError

    def friends(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followers(user_uuid)
                    if user in self.followings[user_uuid]}
        else:
            raise UserDoesNotExistError

    def distances(self, *args):
        if self.users_exist(*args):
            distance = 0
            nodes = {args[0]}
            visited = {args[0]}
            new_nodes = set()
            while len(nodes):
                if len(args) == 3 and distance == args[1]:
                    break
                for node in nodes:
                    new_nodes.update(self.followings[node].difference(visited))
                    visited.update(new_nodes)
                distance += 1
                if len(args) == 2 and args[1] in new_nodes:
                    return distance
                nodes = new_nodes.copy()
                new_nodes.clear()
            if len(args) == 2:
                raise UsersNotConnectedError
            elif len(args) == 3:
                return nodes
            return distance - 1
        else:
            raise UserDoesNotExistError

    def max_distance(self, user_uuid):
        return self.distances(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return self.distances(from_user_uuid, to_user_uuid)

    def nth_layer_followings(self, user_uuid, n):
        return self.distances(user_uuid, n, None)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if self.users_exist(user_uuid):
            posts = []
            for user in self.following(user_uuid):
                posts.extend(self.get_user(user).posts)
            posts.sort(key=lambda post: post.published_at)
            return posts[-(offset + 1):-(limit + offset + 1):-1]
        else:
            raise UserDoesNotExistError


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass
  • Виж какво прави yield from, може да му намериш приложение тук :)

  • При положение, че имаме уникален идентификатор за потребителя, дали няма да ти спести малко работа използването на друга колекция за self.users

  • За въпроса ти: МИсля, че и двете са еднакво разбираеми, но аз лично харесвам повече закоментирания вариант

  • Той малко си прекалил в желанието си да нямаш повтарящ се код и си допуснал да се слагаш един излишен None като аргумент само за да можеш да ги различаваш, а и имаш много if-ове за отделните случаи. В случая повече натоварваш алгоритмите с проверки, отколкото премахваш повтарящ се код. Може би не е нужно да обединяваш и трите функции, като идея са доста различни :)

Тодор обнови решението на 14.04.2016 00:23 (преди над 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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
import uuid
import datetime
from collections import defaultdict
from math import inf


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        yield from self.posts


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(self, *args):               # TODO decorator
        if len(args) == 1 or args[0] == args[1]:
            return any([user.uuid == args[0] for user in self.users])
        return [user.uuid == args[0] or user.uuid == args[1]
                for user in self.users].count(True) == 2

    def add_user(self, user):
        if user in self.users:
            raise UserAlreadyExistsError
        self.users.add(user)
        self.followings[user.uuid]
        print(self.followings[user.uuid])

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    def follow(self, follower, followee):
        if self.users_exist(follower, followee):
            if follower == followee:
                raise UserCannotFollowHimselfError
            self.followings[follower].add(followee)
        else:
            raise UserDoesNotExistError

    def unfollow(self, follower, followee):
        if self.users_exist(follower, followee):
            self.followings[follower].discard(followee)
        else:
            raise UserDoesNotExistError

    def is_following(self, follower, followee):
        if self.users_exist(follower, followee):
            return followee in self.followings[follower]
        else:
            raise UserDoesNotExistError

    def followers(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user, followees in self.followings.items()
                    if user_uuid in followees}
        else:
            raise UserDoesNotExistError

    def following(self, user_uuid):
        if self.users_exist(user_uuid):
            return self.followings[user_uuid]
        else:
            raise UserDoesNotExistError

    def friends(self, user_uuid):
        if self.users_exist(user_uuid):
            return {user for user in self.followers(user_uuid)
                    if user in self.followings[user_uuid]}
        else:
            raise UserDoesNotExistError

    def distances(self, *args):
        if self.users_exist(*args):
            distance = 0
            nodes = {args[0]}
            visited = {args[0]}
            new_nodes = set()
            while len(nodes):
                if len(args) == 3 and distance == args[1]:
                    break
                for node in nodes:
                    new_nodes.update(self.followings[node].difference(visited))
                    visited.update(new_nodes)
                distance += 1
                if len(args) == 2 and args[1] in new_nodes:
                    return distance
                nodes = new_nodes.copy()
                new_nodes.clear()
            if len(args) == 2:
                raise UsersNotConnectedError
            elif len(args) == 3:
                return nodes
            return distance - 1
        else:
            raise UserDoesNotExistError

    def max_distance(self, user_uuid):
        if self.users_exist(user_uuid):
            if self.followings[user_uuid] == set():
                return inf
            # distance = 0
            # nodes = {user_uuid}
            # visited = {user_uuid}
            # next = set()
            distance, nodes, visited, next = 0, {user_uuid}, {user_uuid}, set()
            while len(nodes):
                for node in nodes:
                    next.update(self.followings[node].difference(visited))
                    visited.update(next)
                distance += 1
                nodes = next.copy()
                next.clear()
            return distance - 1
        else:
            raise UserDoesNotExistError

    def min_distance(self, from_user_uuid, to_user_uuid):
        if self.users_exist(from_user_uuid, to_user_uuid):
            if from_user_uuid == to_user_uuid:
                return 0
            # distance = 0
            # nodes = {from_user_uuid}
            # visited = {from_user_uuid}
            # new_nodes = set()
            distance, nodes = 0, {from_user_uuid}
            visited, new_nodes = {from_user_uuid}, set()
            while len(nodes):
                for node in nodes:
                    new_nodes.update(self.followings[node].difference(visited))
                    visited.update(new_nodes)
                distance += 1
                if to_user_uuid in new_nodes:
                    return distance
                nodes = new_nodes.copy()
                new_nodes.clear()
            raise UsersNotConnectedError
        else:
            raise UserDoesNotExistError

    def nth_layer_followings(self, user_uuid, n):               # TODO recheck
        if self.users_exist(user_uuid):
            # distance = 0
            # nodes = {user_uuid}
            # history = defaultdict(set)
            # next = set()
            distance, nodes = 0, {user_uuid}
            history, next = defaultdict(set), set()
            while len(nodes) and distance < n:
                for node in nodes:
                    children = self.followings[node].difference(history[node])
                    for child in children:
                        history[child].update(history[node].union({node}))
                    next.update(children)
                distance += 1
                nodes = next.copy()
                next.clear()
            return nodes.difference({user_uuid})
        else:
            raise UserDoesNotExistError

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if self.users_exist(user_uuid):
            posts = []
            for user in self.following(user_uuid):
                posts.extend(self.get_user(user).posts)
            posts.sort(key=lambda post: post.published_at)
            return posts[-(offset + 1):-(limit + offset + 1):-1]
        else:
            raise UserDoesNotExistError


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCannotFollowHimselfError(Exception):
    pass
  • Само в get_post успях да му намеря приложение.
  • Ами множеството не ми е отворило много работа. Може да го заменя със списък или речник, като така ще избегна викането на get_user.
  • Във вече разделените функции кое е по-добре, коментираното, или разопаковането?
  • За методи на клас може ли да се направи декоратор и как?

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


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        yield from self.posts


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(function):
        def check_and_execution(*args):
            arg_count = len(args) == 2 or not isinstance(args[2], uuid.UUID)
            if arg_count or args[1] == args[2]:
                if not any([user.uuid == args[1] for user in args[0].users]):
                    raise UserDoesNotExistError
            elif not [user.uuid == args[1] or user.uuid == args[2]
                      for user in args[0].users].count(True) == 2:
                raise UserDoesNotExistError
            return function(*args)
        return check_and_execution

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    @users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise UserCannotFollowHimselfError
        self.followings[follower].add(followee)

    @users_exist
    def unfollow(self, follower, followee):
        self.followings[follower].discard(followee)

    @users_exist
    def is_following(self, follower, followee):
        return followee in self.followings[follower]

    @users_exist
    def followers(self, user_uuid):
        return {user for user, followees in self.followings.items()
                if user_uuid in followees}

    @users_exist
    def following(self, user_uuid):
        return self.followings[user_uuid]

    @users_exist
    def friends(self, user_uuid):
        return {user for user in self.followers(user_uuid)
                if user in self.followings[user_uuid]}

    @users_exist
    def max_distance(self, user_uuid):
        if self.followings[user_uuid] == set():
            return inf
        distance = 0
        nodes = {user_uuid}
        visited = {user_uuid}
        next = set()
        while len(nodes):
            for node in nodes:
                next.update(self.followings[node].difference(visited))
                visited.update(next)
            distance += 1
            nodes = next.copy()
            next.clear()
        return distance - 1

    @users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        distance = 0
        nodes = {from_user_uuid}
        visited = {from_user_uuid}
        new_nodes = set()
        while len(nodes):
            for node in nodes:
                new_nodes.update(self.followings[node].difference(visited))
                visited.update(new_nodes)
            distance += 1
            if to_user_uuid in new_nodes:
                return distance
            nodes = new_nodes.copy()
            new_nodes.clear()
        raise UsersNotConnectedError

    @users_exist
    def nth_layer_followings(self, user_uuid, n):               # TODO rework
        distance = 0
        nodes = {user_uuid}
        history = defaultdict(set)
        next = set()
        while len(nodes) and distance < n:
            for node in nodes:
                children = self.followings[node].difference(history[node])
                for child in children:
                    history[child].update(history[node].union({node}))
                next.update(children)
            distance += 1
            nodes = next.copy()
            next.clear()
        return nodes.difference({user_uuid})

    @users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        posts = []
        for user in self.following(user_uuid):
            posts.extend(self.get_user(user).posts)
        posts.sort(key=lambda post: post.published_at)
        return posts[-(offset + 1):-(limit + offset + 1):-1]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCannotFollowHimselfError(Exception):
    pass

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


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


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

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts = self.posts[1:]
        self.posts.append(Post(self.uuid, post_content))

    def get_post(self):
        yield from self.posts


class SocialGraph:
    def __init__(self):
        self.users = set()
        self.followings = defaultdict(set)

    def users_exist(function):
        def check_and_execution(*args):
            arg_count = len(args) == 2 or not isinstance(args[2], uuid.UUID)
            if arg_count or args[1] == args[2]:
                if not any([user.uuid == args[1] for user in args[0].users]):
                    raise UserDoesNotExistError
            elif not [user.uuid == args[1] or user.uuid == args[2]
                      for user in args[0].users].count(True) == 2:
                raise UserDoesNotExistError
            return function(*args)
        return check_and_execution

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

    def get_user(self, user_uuid):
        for user in self.users:
            if user.uuid == user_uuid:
                return user
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        try:
            self.followings.pop(user_uuid)
        except KeyError:
            pass
        for user in self.users:
            if user.uuid != user_uuid:
                self.unfollow(user.uuid, user_uuid)
        self.users.discard(self.get_user(user_uuid))

    @users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise UserCannotFollowHimselfError
        self.followings[follower].add(followee)

    @users_exist
    def unfollow(self, follower, followee):
        self.followings[follower].discard(followee)

    @users_exist
    def is_following(self, follower, followee):
        return followee in self.followings[follower]

    @users_exist
    def followers(self, user_uuid):
        return {user for user, followees in self.followings.items()
                if user_uuid in followees}

    @users_exist
    def following(self, user_uuid):
        return self.followings[user_uuid]

    @users_exist
    def friends(self, user_uuid):
        return {user for user in self.followers(user_uuid)
                if user in self.followings[user_uuid]}

    @users_exist
    def max_distance(self, user_uuid):
        if self.followings[user_uuid] == set():
            return inf
        distance = 0
        nodes = {user_uuid}
        visited = {user_uuid}
        next_layer = set()
        while len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            nodes = next_layer.copy()
            next_layer.clear()
        return distance - 1

    @users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        distance = 0
        nodes = {from_user_uuid}
        visited = {from_user_uuid}
        next_layer = set()
        while len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            if to_user_uuid in next_layer:
                return distance
            nodes = next_layer.copy()
            next_layer.clear()
        raise UsersNotConnectedError

    @users_exist
    def nth_layer_followings(self, user_uuid, n):
        distance = 0
        nodes = {user_uuid}
        visited = {user_uuid}
        next_layer = set()
        while distance < n and len(nodes):
            for node in nodes:
                next_layer.update(self.followings[node].difference(visited))
                visited.update(next_layer)
            distance += 1
            nodes = next_layer.copy()
            next_layer.clear()
        return nodes

    @users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        posts = []
        for user in self.following(user_uuid):
            posts.extend(self.get_user(user).posts)
        posts.sort(key=lambda post: post.published_at)
        return posts[-(offset + 1):-(limit + offset + 1):-1]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCannotFollowHimselfError(Exception):
    pass