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
179
180
181
182
183
184
185
186
from uuid import uuid4
from datetime import datetime
from collections import UserDict
from collections import defaultdict


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

    def __eq__(self, other):
        return self.uuid == other.uuid

    def __repr__(self):
        return str(self)

    def __str__(self):
        return str(self.full_name)

    def __hash__(self):
        return hash(self.uuid)

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts.pop(0)

        self.posts.append(Post(self.uuid, post_content))

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


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

    def __str__(self):
        return self.content

    def __repr__(self):
        return str(self)


class UserDatabase(UserDict):
    def __getitem__(self, key):
        try:
            val = UserDict.__getitem__(self, key)
        except KeyError:
            raise UserDoesNotExistError(key)

        return val

    def __setitem__(self, key, value):
        if key in self:
            raise UserAlreadyExistsError(key)

        UserDict.__setitem__(self, key, value)

    def __delitem__(self, key):
        if key not in self:
            raise UserDoesNotExistError(key)

        UserDict.__delitem__(self, key)


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

    def __str__(self):
        return str(self.users)

    def add_user(self, user):
        self.users[user.uuid] = user

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

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

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

    def unfollow(self, follower, followee):
        try:
            self.graph[self.get_user(follower)].remove(followee)
        except KeyError:
            pass

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

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

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

    def friends(self, user_uuid):
        return {followee
                for followee in self.following(user_uuid)
                if user_uuid in self.following(followee)}

    def max_distance(self, user_uuid):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        max_dist = 0
        while queue:
            user, dist = queue.pop(0)
            if dist > max_dist:
                max_dist = dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return max_dist

    def min_distance(self, from_user_uuid, to_user_uuid):
        queue = [(from_user_uuid, 0)]
        visited = set([from_user_uuid])
        while queue:
            user_uuid, dist = queue.pop(0)
            if user_uuid is to_user_uuid:
                return dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user_uuid)
                 if uuid not in visited])
            visited.update(self.following(from_user_uuid))

        raise UsersNotConnectedError()

    def nth_layer_followings(self, user_uuid, n):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        nth_layer = set()
        while queue:
            user, dist = queue.pop(0)
            if dist is n:
                nth_layer.add(user)
                continue
            if dist > n:
                break

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return nth_layer

    def generate_feed(self, user_uuid, offset=0, limit=10):
        result = []
        for uuid in self.following(user_uuid):
            for post in self.users[uuid].get_post():
                result.append(post)
        result.sort(key=lambda post: post.published_at, reverse=True)
        return result[offset:limit + offset]


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        super(UserDoesNotExistError, self).__init__(
            "User with uuid {} does not exist!".format(uuid))


class UserAlreadyExistsError(Exception):
    def __init__(self, uuid):
        super(UserAlreadyExistsError, self).__init__(
            "User with uuid {} already exists!".format(uuid))


class UsersNotConnectedError(Exception):
    def __init__(self):
        super(UsersNotConnectedError, self).__init__(
            "Users are not connected!")

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

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

OK

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

Виктор обнови решението на 12.04.2016 21:13 (преди над 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
from uuid import uuid4
from datetime import datetime


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

    def __eq__(self, other):
        return self.uuid == other.uuid

    def __repr__(self):
        return str(self)

    def __str__(self):
        return str(self.full_name)

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts.pop(0)

        self.posts.append(Post(self.uuid, post_content))

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

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

    def unfollow(self, user_uuid):
        self.following.remove(user_uuid)


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

    def __str__(self):
        return self.content

    def __repr__(self):
        return str(self)


class UserDatabase(dict):
    def __init__(self, *args):
        dict.__init__(self, args)

    def __getitem__(self, key):
        try:
            val = dict.__getitem__(self, key)
        except KeyError:
            raise UserDoesNotExistError(key)

        return val

    def __setitem__(self, key, value):
        if key in self:
            raise UserAlreadyExistsError(key)

        dict.__setitem__(self, key, value)

    def __delitem__(self, key):
        if key not in self:
            raise UserDoesNotExistError(key)

        dict.__delitem__(self, key)


class SocialGraph:
    def __init__(self):
        self.users = UserDatabase()

    def __str__(self):
        return str(self.users)

    def add_user(self, user):
        self.users[user.uuid] = user

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

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

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

    def unfollow(self, follower, followee):
        try:
            self.users[follower].unfollow(followee)
        except KeyError:
            pass

    def is_following(self, follower, followee):
        return followee in self.following(follower)

    def followers(self, user_uuid):
        return {uuid for uuid in self.users
                if user_uuid in self.following(uuid)}

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

    def friends(self, user_uuid):
        return {followee
                for followee in self.following(user_uuid)
                if user_uuid in self.following(followee)}

    def max_distance(self, user_uuid):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        max_dist = 0
        while queue:
            user, dist = queue.pop(0)
            if dist > max_dist:
                max_dist = dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return max_dist

    def min_distance(self, from_user_uuid, to_user_uuid):
        queue = [(from_user_uuid, 0)]
        visited = set([from_user_uuid])
        while queue:
            user_uuid, dist = queue.pop(0)
            if user_uuid is to_user_uuid:
                return dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user_uuid)
                 if uuid not in visited])
            visited.update(self.following(from_user_uuid))

        raise UsersNotConnectedError()

    def nth_layer_followings(self, user_uuid, n):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        nth_layer = set()
        while queue:
            user, dist = queue.pop(0)
            if dist is n:
                nth_layer.add(user)
                continue
            if dist > n:
                break

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return nth_layer

    def generate_feed(self, user_uuid, offset=0, limit=10):
        result = []
        for uuid in self.following(user_uuid):
            for post in self.users[uuid].get_post():
                result.append(post)
        result.sort(key=lambda post: post.published_at, reverse=True)
        return result[offset:limit + offset]


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        super(UserDoesNotExistError, self).__init__(
            "User with uuid {} does not exist!".format(uuid))


class UserAlreadyExistsError(Exception):
    def __init__(self, uuid):
        super(UserAlreadyExistsError, self).__init__(
            "User with uuid {} already exists!".format(uuid))


class UsersNotConnectedError(Exception):
    def __init__(self):
        super(UsersNotConnectedError, self).__init__(
            "Users are not connected!")
  • Идеята да си направиш свой наследник на dict за пазене на потребители е добра, но наследи от collections.UserDict, вместо от dict
  • Не мисля, че е добра идея да пазиш следените в инстанцията на потребителя. Представи си, че всеки потребител може да е част от 5 социални графа :)

Виктор обнови решението на 18.04.2016 11:39 (преди над 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
from uuid import uuid4
from datetime import datetime
from collections import UserDict
from collections import defaultdict


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

    def __eq__(self, other):
        return self.uuid == other.uuid

    def __repr__(self):
        return str(self)

    def __str__(self):
        return str(self.full_name)

    def __hash__(self):
        return hash(self.uuid)

    def add_post(self, post_content):
        if len(self.posts) == 50:
            self.posts.pop(0)

        self.posts.append(Post(self.uuid, post_content))

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


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

    def __str__(self):
        return self.content

    def __repr__(self):
        return str(self)


class UserDatabase(UserDict):
    def __getitem__(self, key):
        try:
            val = UserDict.__getitem__(self, key)
        except KeyError:
            raise UserDoesNotExistError(key)

        return val

    def __setitem__(self, key, value):
        if key in self:
            raise UserAlreadyExistsError(key)

        UserDict.__setitem__(self, key, value)

    def __delitem__(self, key):
        if key not in self:
            raise UserDoesNotExistError(key)

        UserDict.__delitem__(self, key)


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

    def __str__(self):
        return str(self.users)

    def add_user(self, user):
        self.users[user.uuid] = user

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

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

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

    def unfollow(self, follower, followee):
        try:
            self.graph[self.get_user(follower)].remove(followee)
        except KeyError:
            pass

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

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

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

    def friends(self, user_uuid):
        return {followee
                for followee in self.following(user_uuid)
                if user_uuid in self.following(followee)}

    def max_distance(self, user_uuid):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        max_dist = 0
        while queue:
            user, dist = queue.pop(0)
            if dist > max_dist:
                max_dist = dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return max_dist

    def min_distance(self, from_user_uuid, to_user_uuid):
        queue = [(from_user_uuid, 0)]
        visited = set([from_user_uuid])
        while queue:
            user_uuid, dist = queue.pop(0)
            if user_uuid is to_user_uuid:
                return dist

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user_uuid)
                 if uuid not in visited])
            visited.update(self.following(from_user_uuid))

        raise UsersNotConnectedError()

    def nth_layer_followings(self, user_uuid, n):
        queue = [(user_uuid, 0)]
        visited = set([user_uuid])
        nth_layer = set()
        while queue:
            user, dist = queue.pop(0)
            if dist is n:
                nth_layer.add(user)
                continue
            if dist > n:
                break

            queue.extend(
                [(uuid, dist + 1) for uuid in self.following(user)
                 if uuid not in visited])
            visited.update(self.following(user_uuid))

        return nth_layer

    def generate_feed(self, user_uuid, offset=0, limit=10):
        result = []
        for uuid in self.following(user_uuid):
            for post in self.users[uuid].get_post():
                result.append(post)
        result.sort(key=lambda post: post.published_at, reverse=True)
        return result[offset:limit + offset]


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        super(UserDoesNotExistError, self).__init__(
            "User with uuid {} does not exist!".format(uuid))


class UserAlreadyExistsError(Exception):
    def __init__(self, uuid):
        super(UserAlreadyExistsError, self).__init__(
            "User with uuid {} already exists!".format(uuid))


class UsersNotConnectedError(Exception):
    def __init__(self):
        super(UsersNotConnectedError, self).__init__(
            "Users are not connected!")