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
import uuid
from datetime import datetime as time
from collections import deque
from itertools import islice
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User():

    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = deque([], 50)
        self.posts_count = 0

    def get_uuid(self):
        return self.uuid

    def get_post(self):
        counter = 0
        while counter < len(self.posts):
            post = self.posts.pop()
            self.posts.appendleft(post)
            yield post
            counter += 1

    def add_post(self, post_content):
        new_post = Post(self.uuid, post_content)
        self.posts_count += 1
        self.posts.appendleft(new_post)


class Post():

    def __init__(self, author_uuid, content):
        self.author = author_uuid
        self.published_at = time.now()
        self.content = content

    def __lt__(self, other):
        return self.published_at < other.published_at

    def __gt__(self, other):
        return self.published_at > other.published_at


class SocialGraph():

    def __init__(self):
        self.graph = {}
        self.users = {}

    def add_user(self, user):
        user_uuid = user.get_uuid()
        if user_uuid not in self.users:
            self.users[user_uuid] = user
            self.graph[user_uuid] = set()
        else:
            raise UserAlreadyExistsError

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

    def delete_user(self, user_uuid):
        if user_uuid in self.users.keys():
            del self.graph[user_uuid]
            del self.users[user_uuid]
        else:
            raise UserDoesNotExistError
        for follows in self.graph.values():
            if user_uuid in follows:
                follows.remove(user_uuid)

    def check_uuid(self, user_uuids):
        for user_uuid in user_uuids:
            if user_uuid not in self.users:
                raise UserDoesNotExistError

    def follow(self, follower, followee):
        self.check_uuid([follower, followee])
        self.graph[follower].add(followee)

    def unfollow(self, follower, followee):
        self.check_uuid([follower, followee])
        self.graph[follower].remove(followee)

    def is_following(self, follower, followee):
        self.check_uuid([follower, followee])
        return followee in self.graph[follower]

    def following(self, user_uuid):
        self.check_uuid([user_uuid])
        return self.graph[user_uuid]

    def followers(self, user_uuid):
        self.check_uuid([user_uuid])
        return {user for user, following in self.graph.items()
                if user_uuid in following}

    def friends(self, user_uuid):
        self.check_uuid([user_uuid])
        return self.followers(user_uuid) & self.graph[user_uuid]

    def max_distance(self, user_uuid):
        self.check_uuid([user_uuid])
        distances = [dist for dist in self.bfs(user_uuid).values()
                     if dist != math.inf]
        return sorted(distances)[-1]

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.check_uuid([from_user_uuid, to_user_uuid])
        dist_from = self.bfs(from_user_uuid)[to_user_uuid]
        dist_to = self.bfs(to_user_uuid)[from_user_uuid]
        if dist_to == math.inf and dist_from == math.inf:
            raise UsersNotConnectedError
        if dist_from < dist_to:
            return dist_from
        else:
            return dist_to

    def nth_layer_followings(self, user_uuid, n):
        self.check_uuid([user_uuid])
        return [user_uuid for user_uuid, dist in self.bfs(user_uuid).items()
                if dist == n]

    def get_feed(self, user_uuid, limit):
        feed = []
        for followed in self.graph[user_uuid]:
            user_posts = list(islice(self.users[followed].posts, 0, limit))
            feed.extend(user_posts)
        return feed

    def bfs(self, user_uuid):
        dist = dict((user_uuid, math.inf) for user_uuid in self.graph.keys())
        queue = deque([user_uuid])
        dist[user_uuid] = 0
        while queue:
            grey = queue.pop()
            for white in self.graph[grey]:
                queue.append(white)
                if dist[grey] + 1 < dist[white]:
                    dist[white] = dist[grey] + 1
        return dist

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.check_uuid([user_uuid])
        feed = self.get_feed(user_uuid, limit)
        return sorted(feed, reverse=True)[offset:offset+limit]

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.082s

OK

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

Стилиян обнови решението на 18.04.2016 16:26 (преди над 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
import uuid
from datetime import datetime as time
from collections import deque
from itertools import islice
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User():

    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = deque([], 50)
        self.posts_count = 0

    def get_uuid(self):
        return self.uuid

    def get_post(self):
        counter = 0
        while counter < len(self.posts):
            post = self.posts.pop()
            self.posts.appendleft(post)
            yield post
            counter += 1

    def add_post(self, post_content):
        new_post = Post(self.uuid, post_content)
        self.posts_count += 1
        self.posts.appendleft(new_post)


class Post():

    def __init__(self, author_uuid, content):
        self.author = author_uuid
        self.published_at = time.now()
        self.content = content

    def __lt__(self, other):
        return self.published_at < other.published_at

    def __gt__(self, other):
        return self.published_at > other.published_at


class SocialGraph():

    def __init__(self):
        self.graph = {}
        self.users = {}

    def add_user(self, user):
        user_uuid = user.get_uuid()
        if user_uuid not in self.users:
            self.users[user_uuid] = user
            self.graph[user_uuid] = set()
        else:
            raise UserAlreadyExistsError

    def get_user(self, user_uuid):
        if user_uuid not in self.users.keys():
            raise UserDoesNotExistError
        else:
            return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid in self.users.keys():
            del self.graph[user_uuid]
            del self.users[user_uuid]
        else:
            raise UserDoesNotExistError
        for follows in self.graph.values():
            if user_uuid in follows:
                follows.remove(user_uuid)

    def follow(self, follower, followee):
        self.graph[follower].add(followee)

    def unfollow(self, follower, followee):
        self.graph[follower].remove(followee)

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

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

    def followers(self, user_uuid):
        return {user for user, following in self.graph.items()
                if user_uuid in following}

    def friends(self, user_uuid):
        return self.followers(user_uuid) & self.graph[user_uuid]

    def max_distance(self, user_uuid):
        distances = [dist for dist in self.bfs(user_uuid).values()
                     if dist != math.inf]
        return sorted(distances)[-1]

    def min_distance(self, from_user_uuid, to_user_uuid):
        dist_from = self.bfs(from_user_uuid)[to_user_uuid]
        dist_to = self.bfs(to_user_uuid)[from_user_uuid]
        if dist_from < dist_to:
            return dist_from
        else:
            return dist_to

    def nth_layer_followings(self, user_uuid, n):
        return [user_uuid for user_uuid, dist in self.bfs(user_uuid).items()
                if dist == n]

    def get_feed(self, user_uuid, limit):
        feed = []
        for followed in self.graph[user_uuid]:
            user_posts = list(islice(self.users[followed].posts, 0, limit))
            feed.extend(user_posts)
        return feed

    def bfs(self, user_uuid):
        dist = dict((user_uuid, math.inf) for user_uuid in self.graph.keys())
        queue = deque([user_uuid])
        dist[user_uuid] = 0
        while queue:
            grey = queue.pop()
            for white in self.graph[grey]:
                queue.append(white)
                if dist[grey] + 1 < dist[white]:
                    dist[white] = dist[grey] + 1
        return dist

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feed = self.get_feed(user_uuid, limit)
        return sorted(feed, reverse=True)[offset:offset+limit]

Стилиян обнови решението на 18.04.2016 16:42 (преди над 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
import uuid
from datetime import datetime as time
from collections import deque
from itertools import islice
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User():

    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = deque([], 50)
        self.posts_count = 0

    def get_uuid(self):
        return self.uuid

    def get_post(self):
        counter = 0
        while counter < len(self.posts):
            post = self.posts.pop()
            self.posts.appendleft(post)
            yield post
            counter += 1

    def add_post(self, post_content):
        new_post = Post(self.uuid, post_content)
        self.posts_count += 1
        self.posts.appendleft(new_post)


class Post():

    def __init__(self, author_uuid, content):
        self.author = author_uuid
        self.published_at = time.now()
        self.content = content

    def __lt__(self, other):
        return self.published_at < other.published_at

    def __gt__(self, other):
        return self.published_at > other.published_at


class SocialGraph():

    def __init__(self):
        self.graph = {}
        self.users = {}

    def add_user(self, user):
        user_uuid = user.get_uuid()
        if user_uuid not in self.users:
            self.users[user_uuid] = user
            self.graph[user_uuid] = set()
        else:
            raise UserAlreadyExistsError

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

    def delete_user(self, user_uuid):
        if user_uuid in self.users.keys():
            del self.graph[user_uuid]
            del self.users[user_uuid]
        else:
            raise UserDoesNotExistError
        for follows in self.graph.values():
            if user_uuid in follows:
                follows.remove(user_uuid)

    def check_uuid(self, user_uuids):
        for user_uuid in user_uuids:
            if user_uuid not in self.users:
                raise UserDoesNotExistError

    def follow(self, follower, followee):
        self.check_uuid([follower, followee])
        self.graph[follower].add(followee)

    def unfollow(self, follower, followee):
        self.check_uuid([follower, followee])
        self.graph[follower].remove(followee)

    def is_following(self, follower, followee):
        self.check_uuid([follower, followee])
        return followee in self.graph[follower]

    def following(self, user_uuid):
        self.check_uuid([user_uuid])
        return self.graph[user_uuid]

    def followers(self, user_uuid):
        self.check_uuid([user_uuid])
        return {user for user, following in self.graph.items()
                if user_uuid in following}

    def friends(self, user_uuid):
        self.check_uuid([user_uuid])
        return self.followers(user_uuid) & self.graph[user_uuid]

    def max_distance(self, user_uuid):
        self.check_uuid([user_uuid])
        distances = [dist for dist in self.bfs(user_uuid).values()
                     if dist != math.inf]
        return sorted(distances)[-1]

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.check_uuid([from_user_uuid, to_user_uuid])
        dist_from = self.bfs(from_user_uuid)[to_user_uuid]
        dist_to = self.bfs(to_user_uuid)[from_user_uuid]
        if dist_to == math.inf and dist_from == math.inf:
            raise UsersNotConnectedError
        if dist_from < dist_to:
            return dist_from
        else:
            return dist_to

    def nth_layer_followings(self, user_uuid, n):
        self.check_uuid([user_uuid])
        return [user_uuid for user_uuid, dist in self.bfs(user_uuid).items()
                if dist == n]

    def get_feed(self, user_uuid, limit):
        feed = []
        for followed in self.graph[user_uuid]:
            user_posts = list(islice(self.users[followed].posts, 0, limit))
            feed.extend(user_posts)
        return feed

    def bfs(self, user_uuid):
        dist = dict((user_uuid, math.inf) for user_uuid in self.graph.keys())
        queue = deque([user_uuid])
        dist[user_uuid] = 0
        while queue:
            grey = queue.pop()
            for white in self.graph[grey]:
                queue.append(white)
                if dist[grey] + 1 < dist[white]:
                    dist[white] = dist[grey] + 1
        return dist

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.check_uuid([user_uuid])
        feed = self.get_feed(user_uuid, limit)
        return sorted(feed, reverse=True)[offset:offset+limit]