timeit

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

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

Решение на Социална мрежа от Светомир Стоименов

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

Към профила на Светомир Стоименов

Резултати

  • 9 точки от тестове
  • 0 бонус точки
  • 9 точки общо
  • 7 успешни тест(а)
  • 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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = 'No user with the given uuid!'


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = 'User with the given uuid already exists!'


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


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

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

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

    def add_follower(self, user):
        self.followers.add(user)

    def remove_follower(self, user):
        self.followers.discard(user)

    def follow(self, user):
        self.following.add(user)

    def unfollow(self, user):
        self.following.discard(user)

    def has_follower(self, user):
        return user in self.followers

    def is_following(self, user):
        return user in self.following

    def get_friends(self):
        return self.followers & self.following


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 get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        deleted_user = self.get_user(user_uuid)
        for uid, user in self.users.items():
            user.remove_follower(deleted_user)
            user.unfollow(deleted_user)
        del self.users[user_uuid]

    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("A user cannot follow himself")
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        followed_user.add_follower(following_user)
        following_user.follow(followed_user)

    def unfollow(self, follower, followee):
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        followed_user.remove_follower(following_user)
        following_user.unfollow(followed_user)

    def is_following(self, follower, followee):
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        return following_user.is_following(followed_user)

    def followers(self, user_uuid):
        user = self.get_user(user_uuid)
        return {follower.uuid for follower in user.followers}

    def following(self, user_uuid):
        user = self.get_user(user_uuid)
        return {followed.uuid for followed in user.following}

    def friends(self, user_uuid):
        user = self.get_user(user_uuid)
        return {friend.uuid for friend in user.get_friends()}

    def max_distance(self, user_uuid):
        user = self.get_user(user_uuid)
        queue = [user, '#']
        waiting = {user}
        distance = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                distance += 1
                queue.append('#')
                continue
            for followed in currUser.following:
                waiting.add(followed)
                queue.append(followed)
        return distance if distance != 0 else math.inf

    def min_distance(self, from_user_uuid, to_user_uuid):
        start_user = self.get_user(from_user_uuid)
        end_user = self.get_user(to_user_uuid)
        queue = [start_user, '#']
        waiting = {start_user}
        distance = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                distance += 1
                queue.append('#')
                continue
            for followed in currUser.following:
                if followed is end_user:
                    return distance + 1
                if followed not in waiting:
                    waiting.add(followed)
                    queue.append(followed)
        return math.inf

    def nth_layer_followings(self, user_uuid, n):
        start_user = self.get_user(user_uuid)
        queue = [start_user, '#']
        waiting = {start_user}
        layer = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                layer += 1
                if layer == n:
                    return [user.uuid for user in queue]
                queue.append('#')
                continue
            for followed in currUser.following:
                waiting.add(followed)
                queue.append(followed)
        return []

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feeded = self.get_user(user_uuid)
        feed = [post for user in feeded.following for post in user.get_post()]
        feed.sort(key=lambda post: post.published_at, reverse=True)
        return feed[offset: offset + limit]

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

.F......
======================================================================
FAIL: test_distnaces (test.TestSocialGraph)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
AssertionError: 3 != 2

----------------------------------------------------------------------
Ran 8 tests in 0.064s

FAILED (failures=1)

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

Светомир обнови решението на 18.04.2016 13: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
import uuid
import datetime
import math


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = 'No user with the given uuid!'


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = 'User with the given uuid already exists!'


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


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

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

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

    def add_follower(self, user):
        self.followers.add(user)

    def remove_follower(self, user):
        self.followers.discard(user)

    def follow(self, user):
        self.following.add(user)

    def unfollow(self, user):
        self.following.discard(user)

    def has_follower(self, user):
        return user in self.followers

    def is_following(self, user):
        return user in self.following

    def get_friends(self):
        return self.followers & self.following


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 get_user(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
        return self.users[user_uuid]

    def delete_user(self, user_uuid):
        deleted_user = self.get_user(user_uuid)
        for uid, user in self.users.items():
            user.remove_follower(deleted_user)
            user.unfollow(deleted_user)
        del self.users[user_uuid]

    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("A user cannot follow himself")
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        followed_user.add_follower(following_user)
        following_user.follow(followed_user)

    def unfollow(self, follower, followee):
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        followed_user.remove_follower(following_user)
        following_user.unfollow(followed_user)

    def is_following(self, follower, followee):
        following_user = self.get_user(follower)
        followed_user = self.get_user(followee)
        return following_user.is_following(followed_user)

    def followers(self, user_uuid):
        user = self.get_user(user_uuid)
        return {follower.uuid for follower in user.followers}

    def following(self, user_uuid):
        user = self.get_user(user_uuid)
        return {followed.uuid for followed in user.following}

    def friends(self, user_uuid):
        user = self.get_user(user_uuid)
        return {friend.uuid for friend in user.get_friends()}

    def max_distance(self, user_uuid):
        user = self.get_user(user_uuid)
        queue = [user, '#']
        waiting = {user}
        distance = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                distance += 1
                queue.append('#')
                continue
            for followed in currUser.following:
                waiting.add(followed)
                queue.append(followed)
        return distance if distance != 0 else math.inf

    def min_distance(self, from_user_uuid, to_user_uuid):
        start_user = self.get_user(from_user_uuid)
        end_user = self.get_user(to_user_uuid)
        queue = [start_user, '#']
        waiting = {start_user}
        distance = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                distance += 1
                queue.append('#')
                continue
            for followed in currUser.following:
                if followed is end_user:
                    return distance + 1
                if followed not in waiting:
                    waiting.add(followed)
                    queue.append(followed)
        return math.inf

    def nth_layer_followings(self, user_uuid, n):
        start_user = self.get_user(user_uuid)
        queue = [start_user, '#']
        waiting = {start_user}
        layer = 0
        while len(queue) > 1:
            currUser = queue.pop(0)
            if currUser == '#':
                layer += 1
                if layer == n:
                    return [user.uuid for user in queue]
                queue.append('#')
                continue
            for followed in currUser.following:
                waiting.add(followed)
                queue.append(followed)
        return []

    def generate_feed(self, user_uuid, offset=0, limit=10):
        feeded = self.get_user(user_uuid)
        feed = [post for user in feeded.following for post in user.get_post()]
        feed.sort(key=lambda post: post.published_at, reverse=True)
        return feed[offset: offset + limit]