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


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = [0] * 50
        self.__post_idx = 0
        self.__posts_overflow = False
        self.follows = {}

    def add_post(self, post_content):
        time = datetime.now()
        self.posts[self.__post_idx] = Post(self.uuid, time, post_content)
        self.__post_idx += 1
        if self.__post_idx == 50:
            self.__post_idx = 0
            self.__posts_overflow = True

    def get_post(self):
        if self.__posts_overflow:
            for post_idx in range(self.__post_idx, 50):
                yield self.posts[post_idx]
        for post_idx in range(0, self.__post_idx):
            yield self.posts[post_idx]

    def get_newest_posts(self, n):
        if not self.__posts_overflow and n > len(self.posts):
            return [self.posts[idx] for idx in
                    range(self.__post_idx - 1, -1, -1)]
        if n > 50:
            n = 50
        return [self.posts[idx] for idx
                in range(self.__post_idx - 1, self.__post_idx - n - 1, -1)]


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


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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

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

    def __check_if_exists(self, *args):
        for user in args:
            if user not in self.users:
                raise UserDoesNotExistError

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

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

    def follow(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if follower == followee:
            raise ValueError
        self.users[follower].follows[followee] = self.users[followee]

    def unfollow(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if followee in self.users[follower].follows:
            del self.users[follower].follows[followee]

    def is_following(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if followee in self.users[follower].follows:
            return True
        return False

    def followers(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users if user_uuid in
                    self.users[uuid].follows])

    def following(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users[user_uuid].follows])

    def friends(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users[user_uuid].follows
                    if user_uuid in self.users[uuid].follows])

    def max_distance(self, user_uuid):
        self.__check_if_exists(user_uuid)
        if not self.users[user_uuid].follows:
            return inf
        dist = 0
        visited = set()
        queue = deque()
        queue.append(user_uuid)
        while queue:
            curr = queue.pop()
            visited.add(curr)
            if not self.users[curr].follows \
                    or set(self.users[curr].follows) <= visited \
                    or set(self.users[curr].follows) <= set(queue):
                continue
            queue.extendleft(set(self.users[curr].follows))
            dist += 1
        return dist

    def find_min_dist(self, from_user_uuid, to_user_uuid, visited):
        dist = 0
        min_dist = inf
        if from_user_uuid == to_user_uuid:
            return dist
        visited.add(from_user_uuid)
        for user in (set(self.users[from_user_uuid].follows) - visited):
            dist = (self.find_min_dist(user, to_user_uuid, visited) + 1)
            if dist < min_dist:
                min_dist = dist
        visited.remove(from_user_uuid)
        return min_dist

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check_if_exists(from_user_uuid, to_user_uuid)
        dist = self.find_min_dist(from_user_uuid, to_user_uuid, set())
        if dist == inf:
            raise UsersNotConnectedError
        return dist

    def nth_layer_followings(self, user_uuid, n):
        self.__check_if_exists(user_uuid)
        level = 1
        DELIMETER = 'delimeter'
        visited = set()
        queue = deque()
        queue.append(user_uuid)
        while queue and level < n:
            curr = queue.pop()
            if curr == DELIMETER:
                level += 1
                continue
            visited.add(curr)
            queue.extendleft(set(self.users[curr].follows) -
                             visited - set(queue))
            queue.appendleft(DELIMETER)
        return set(queue) - set([DELIMETER])

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check_if_exists(user_uuid)
        feed = []
        for user in self.users[user_uuid].follows:
            feed.extend(self.users[user].get_newest_posts(limit))
        sorted_feed = sorted(feed, key=lambda a: a.published_at, reverse=True)
        if offset + limit > len(sorted_feed):
            return sorted_feed[offset:]
        return sorted_feed[offset:offset + limit]

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

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

OK

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

Данислав обнови решението на 18.04.2016 13:24 (преди над 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
from uuid import uuid4
from datetime import datetime
from collections import deque
from math import inf


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = [0] * 50
        self.__post_idx = 0
        self.__posts_overflow = False
        self.follows = {}

    def add_post(self, post_content):
        time = datetime.now()
        self.posts[self.__post_idx] = Post(self.uuid, time, post_content)
        self.__post_idx += 1
        if self.__post_idx == 50:
            self.__post_idx = 0
            self.__posts_overflow = True

    def get_post(self):
        if self.__posts_overflow:
            for post_idx in range(self.__post_idx, 50):
                yield self.posts[post_idx]
        for post_idx in range(0, self.__post_idx):
            yield self.posts[post_idx]

    def get_newest_posts(self, n):
        if not self.__posts_overflow and n > len(self.posts):
            return [self.posts[idx] for idx in
                    range(self.__post_idx - 1, -1, -1)]
        if n > 50:
            n = 50
        return [self.posts[idx] for idx
                in range(self.__post_idx - 1, self.__post_idx - n - 1, -1)]


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


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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

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

    def __check_if_exists(self, *args):
        for user in args:
            if user not in self.users:
                raise UserDoesNotExistError

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

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

    def follow(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if follower == followee:
            raise ValueError
        self.users[follower].follows[followee] = self.users[followee]

    def unfollow(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if followee in self.users[follower].follows:
            del self.users[follower].follows[followee]

    def is_following(self, follower, followee):
        self.__check_if_exists(follower, followee)
        if followee in self.users[follower].follows:
            return True
        return False

    def followers(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users if user_uuid in
                    self.users[uuid].follows])

    def following(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users[user_uuid].follows])

    def friends(self, user_uuid):
        self.__check_if_exists(user_uuid)
        return set([uuid for uuid in self.users[user_uuid].follows
                    if user_uuid in self.users[uuid].follows])

    def max_distance(self, user_uuid):
        self.__check_if_exists(user_uuid)
        if not self.users[user_uuid].follows:
            return inf
        dist = 0
        visited = set()
        queue = deque()
        queue.append(user_uuid)
        while queue:
            curr = queue.pop()
            visited.add(curr)
            if not self.users[curr].follows \
                    or set(self.users[curr].follows) <= visited \
                    or set(self.users[curr].follows) <= set(queue):
                continue
            queue.extendleft(set(self.users[curr].follows))
            dist += 1
        return dist

    def find_min_dist(self, from_user_uuid, to_user_uuid, visited):
        dist = 0
        min_dist = inf
        if from_user_uuid == to_user_uuid:
            return dist
        visited.add(from_user_uuid)
        for user in (set(self.users[from_user_uuid].follows) - visited):
            dist = (self.find_min_dist(user, to_user_uuid, visited) + 1)
            if dist < min_dist:
                min_dist = dist
        visited.remove(from_user_uuid)
        return min_dist

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.__check_if_exists(from_user_uuid, to_user_uuid)
        dist = self.find_min_dist(from_user_uuid, to_user_uuid, set())
        if dist == inf:
            raise UsersNotConnectedError
        return dist

    def nth_layer_followings(self, user_uuid, n):
        self.__check_if_exists(user_uuid)
        level = 1
        DELIMETER = 'delimeter'
        visited = set()
        queue = deque()
        queue.append(user_uuid)
        while queue and level < n:
            curr = queue.pop()
            if curr == DELIMETER:
                level += 1
                continue
            visited.add(curr)
            queue.extendleft(set(self.users[curr].follows) -
                             visited - set(queue))
            queue.appendleft(DELIMETER)
        return set(queue) - set([DELIMETER])

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.__check_if_exists(user_uuid)
        feed = []
        for user in self.users[user_uuid].follows:
            feed.extend(self.users[user].get_newest_posts(limit))
        sorted_feed = sorted(feed, key=lambda a: a.published_at, reverse=True)
        if offset + limit > len(sorted_feed):
            return sorted_feed[offset:]
        return sorted_feed[offset:offset + limit]