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


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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


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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, datetime.now(), post_content))

    def get_post(self):
        return (x for x in self.posts)


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

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

    def get_user(self, user_uuid):
        if user_uuid in self.graph:
            return self.graph[user_uuid]
        raise UserDoesNotExistError()

    def delete_user(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        del self.graph[user_uuid]
        if user_uuid in self.links:
            del self.links[user_uuid]

    def follow(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("One of the user_uuids is not valid")
        if follower in self.links:
            self.links[follower].add(followee)
        else:
            self.links[follower] = {followee}

    def unfollow(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("One of the user_uuids is not valid")
        if follower in self.links:
            if followee in self.links[follower]:
                self.links[follower].remove(followee)

    def is_following(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return follower in self.links and followee in self.links[follower]

    def followers(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        fers = set()
        for user, fings in self.links.items():
            if user_uuid in fings:
                fers.add(user)
        return fers

    def following(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        if user_uuid in self.links:
            return self.links[user_uuid]
        return []

    def friends(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        if user_uuid not in self.links:
            return []
        result = set()
        for fing in self.links[user_uuid]:
            if fing in self.links and user_uuid in self.links[fing]:
                result.add(fing)
        return result

    def max_distance(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return self.bfs_links(user_uuid, None)

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.graph or to_user_uuid not in self.graph:
            raise UserDoesNotExistError("on of the user_uuids is not valid")
        return self.bfs_links(from_user_uuid, to_user_uuid)

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return self.bfs_followings(user_uuid, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        followees = self.following(user_uuid)
        posts = []
        for user in self.graph.values():
            if user.uuid in followees:
                posts.extend(user.posts)
        posts.sort(key=lambda x: x.published_at, reverse=True)
        return posts[offset:(offset + limit)]

    def bfs_links(self, start, end):
        qu = deque([(start, 0)])
        visited = [start]
        max_count = 0
        while qu:
            current, count = qu.popleft()
            max_count = count
            if current == end:
                return count
            visited.append(current)

            for neighbour in self.following(current):
                if neighbour not in visited:
                    qu.append((neighbour, count + 1))
        if end is not None:
            raise UsersNotConnectedError("No path from start to end")
        if max_count == 0:
            return math.inf
        return max_count

    def bfs_followings(self, start, n):
        if n == 0:
            return {}
        qu = deque([(start, 0)])
        visited = [(start, 0)]
        while qu:
            current, count = qu.popleft()
            if count > n:
                break
            for fwing in self.following(current):
                if fwing not in visited:
                    qu.append((fwing, count + 1))
                    visited.append((fwing, count + 1))

        return {element for element, count in visited if count == n}

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

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

OK

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

Мартин обнови решението на 09.04.2016 00:40 (преди над 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
import uuid
from datetime import datetime
from collections import deque
from itertools import chain


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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


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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, datetime.now(), post_content))

    def get_post(self):
        return (x for x in self.posts)


class SocialGraph:
    def __init__(self):
        self.graph = []
        self.links = []

    def add_user(self, user):
        for x in self.graph:
            if x.uuid == user.uuid:
                raise UserAlreadyExistsError()
        self.graph.append(user)

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

    def delete_user(self, user_uuid):
        for x in self.graph:
            if x.uuid == user_uuid:
                self.graph.remove(x)
                return
        raise UserDoesNotExistError()

    def follow(self, follower, followee):
        if (follower, followee) not in self.links:
            self.links.append((follower, followee))

    def unfollow(self, follower, followee):
        if (follower, followee) in self.links:
            self.links.remove((follower, followee))

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

    def followers(self, user_uuid):
        return [fwer for fwer, fwee in self.links if fwee == user_uuid]

    def following(self, user_uuid):
        return [fwer for fwer, fwee in self.links if fwer == user_uuid]

    def friends(self, user_uuid):
        result = [(fwer, fwee) for fwer, fwee in self.links if
                  fwer == user_uuid and (fwee, fwer) in self.links]
        return list(chain.from_iterable(result))

    def max_distance(self, user_uuid):
        return SocialGraph.bfs_links(self.links, user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return SocialGraph.bfs_links(self.links, from_user_uuid, to_user_uuid)

    def nth_layer_friends(self, user_uuid, n):
        return SocialGraph.bfs_friends(self.links, user_uuid, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        followees = self.following(user_uuid)
        posts = []
        for user in self.graph:
            if user.uuid in followees:
                posts.extend(user.posts)
        posts.sort(key=lambda x: x.published_at, reverse=True)
        return posts[offset:limit]

    def bfs_friends(self, start, n):
        qu = deque([(start, 0)])
        visited = [(start, 0)]
        while qu:
            current, count = qu.popleft()
            if count > n:
                break
            for friend in self.friends(current):
                if friend not in visited:
                    qu.append((friend, count + 1))
                    visited.append((friend, count + 1))

        return [element for element, count in visited if count == n]

    def bfs_links(self, start, end):
        qu = deque([(start, 0)])
        visited = [start]
        while qu:
            current, count = qu.popleft()
            if current == end:
                return count
            visited.append(current)

            for neighbour in self.followers(current) + self.following(current):
                if neighbour not in visited:
                    qu.append((neighbour, count + 1))

        return count
  • Всяко търсене, което се прави в add_user, get_user и delete_user е с линейна сложност. Може би списък не е най-добрата колекция за това
  • Изтрит потребител се предполага да не следи и да не бъде следен от никой друг потребител :)
  • След обновеното условие вече се търси nth_layer_followings. Това е по моя вина, но все пак обнови го преди крайния срок :)
  • limit и offset не работят правилно в твоята имплементация на generate_feed. Виж примерите в условието на задачата.

Мартин обнови решението на 12.04.2016 00:47 (преди над 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
from uuid import uuid4
from datetime import datetime
from collections import deque
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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


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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, datetime.now(), post_content))

    def get_post(self):
        return (x for x in self.posts)


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

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

    def get_user(self, user_uuid):
        if user_uuid in self.graph:
            return self.graph[user_uuid]
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError()
        del self.graph[user_uuid]
        if user_uuid in self.links:
            del self.links[user_uuid]

    def follow(self, follower, followee):
        if follower in self.links:
            self.links[follower].add(followee)
        else:
            self.links[follower] = {followee}

    def unfollow(self, follower, followee):
        if follower in self.links:
            if followee in self.links[follower]:
                self.links[follower].remove(followee)

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

    def followers(self, user_uuid):
        followers = set()
        for user, fings in self.links:
            if user_uuid in fings:
                followers.add(user)
        return followers

    def following(self, user_uuid):
        if user_uuid in self.links:
            return self.links[user_uuid]
        return []

    def friends(self, user_uuid):
        if user_uuid not in self.links:
            return []
        result = set()
        for fing in self.links[user_uuid]:
            if fing in self.links and user_uuid in self.links[fing]:
                result.add(fing)
        return result

    def max_distance(self, user_uuid):
        return self.bfs_links(user_uuid, None)

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

    def nth_layer_followings(self, user_uuid, n):
        return self.bfs_followings(user_uuid, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        followees = self.following(user_uuid)
        posts = []
        for user in self.graph.values():
            if user.uuid in followees:
                posts.extend(user.posts)
        posts.sort(key=lambda x: x.published_at, reverse=True)
        return posts[offset:(offset + limit)]

    def bfs_links(self, start, end):
        qu = deque([(start, 0)])
        visited = [start]
        max_count = 0
        while qu:
            current, count = qu.popleft()
            max_count = count
            if current == end:
                return count
            visited.append(current)

            for neighbour in self.following(current):
                if neighbour not in visited:
                    qu.append((neighbour, count + 1))
        if max_count == 0:
            return math.inf
        return max_count

    def bfs_followings(self, start, n):
        qu = deque([(start, 0)])
        visited = [(start, 0)]
        while qu:
            current, count = qu.popleft()
            if count > n:
                break
            for fwing in self.following(current):
                if fwing not in visited:
                    qu.append((fwing, count + 1))
                    visited.append((fwing, count + 1))

        return [element for element, count in visited if count == n]

Мартин обнови решението на 17.04.2016 13: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
from uuid import uuid4
from datetime import datetime
from collections import deque
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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


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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, datetime.now(), post_content))

    def get_post(self):
        return (x for x in self.posts)


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

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

    def get_user(self, user_uuid):
        if user_uuid in self.graph:
            return self.graph[user_uuid]
        raise UserDoesNotExistError

    def delete_user(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError()
        del self.graph[user_uuid]
        if user_uuid in self.links:
            del self.links[user_uuid]

    def follow(self, follower, followee):
        if follower in self.links:
            self.links[follower].add(followee)
        else:
            self.links[follower] = {followee}

    def unfollow(self, follower, followee):
        if follower in self.links:
            if followee in self.links[follower]:
                self.links[follower].remove(followee)

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

    def followers(self, user_uuid):
        fers = set()
        for user, fings in self.links.items():
            if user_uuid in fings:
                fers.add(user)
        return fers

    def following(self, user_uuid):
        if user_uuid in self.links:
            return self.links[user_uuid]
        return []

    def friends(self, user_uuid):
        if user_uuid not in self.links:
            return []
        result = set()
        for fing in self.links[user_uuid]:
            if fing in self.links and user_uuid in self.links[fing]:
                result.add(fing)
        return result

    def max_distance(self, user_uuid):
        return self.bfs_links(user_uuid, None)

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

    def nth_layer_followings(self, user_uuid, n):
        return self.bfs_followings(user_uuid, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        followees = self.following(user_uuid)
        posts = []
        for user in self.graph.values():
            if user.uuid in followees:
                posts.extend(user.posts)
        posts.sort(key=lambda x: x.published_at, reverse=True)
        return posts[offset:(offset + limit)]

    def bfs_links(self, start, end):
        qu = deque([(start, 0)])
        visited = [start]
        max_count = 0
        while qu:
            current, count = qu.popleft()
            max_count = count
            if current == end:
                return count
            visited.append(current)

            for neighbour in self.following(current):
                if neighbour not in visited:
                    qu.append((neighbour, count + 1))
        if max_count == 0:
            return math.inf
        return max_count

    def bfs_followings(self, start, n):
        if n == 0:
            return {}
        qu = deque([(start, 0)])
        visited = [(start, 0)]
        while qu:
            current, count = qu.popleft()
            if count > n:
                break
            for fwing in self.following(current):
                if fwing not in visited:
                    qu.append((fwing, count + 1))
                    visited.append((fwing, count + 1))

        return {element for element, count in visited if count == n}

Мартин обнови решението на 18.04.2016 00:33 (преди над 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
from uuid import uuid4
from datetime import datetime
from collections import deque
import math


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


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


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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, datetime.now(), post_content))

    def get_post(self):
        return (x for x in self.posts)


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

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

    def get_user(self, user_uuid):
        if user_uuid in self.graph:
            return self.graph[user_uuid]
        raise UserDoesNotExistError()

    def delete_user(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        del self.graph[user_uuid]
        if user_uuid in self.links:
            del self.links[user_uuid]

    def follow(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("One of the user_uuids is not valid")
        if follower in self.links:
            self.links[follower].add(followee)
        else:
            self.links[follower] = {followee}

    def unfollow(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("One of the user_uuids is not valid")
        if follower in self.links:
            if followee in self.links[follower]:
                self.links[follower].remove(followee)

    def is_following(self, follower, followee):
        if follower not in self.graph or followee not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return follower in self.links and followee in self.links[follower]

    def followers(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        fers = set()
        for user, fings in self.links.items():
            if user_uuid in fings:
                fers.add(user)
        return fers

    def following(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        if user_uuid in self.links:
            return self.links[user_uuid]
        return []

    def friends(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        if user_uuid not in self.links:
            return []
        result = set()
        for fing in self.links[user_uuid]:
            if fing in self.links and user_uuid in self.links[fing]:
                result.add(fing)
        return result

    def max_distance(self, user_uuid):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return self.bfs_links(user_uuid, None)

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.graph or to_user_uuid not in self.graph:
            raise UserDoesNotExistError("on of the user_uuids is not valid")
        return self.bfs_links(from_user_uuid, to_user_uuid)

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        return self.bfs_followings(user_uuid, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.graph:
            raise UserDoesNotExistError("user_uuid is not valid user id")
        followees = self.following(user_uuid)
        posts = []
        for user in self.graph.values():
            if user.uuid in followees:
                posts.extend(user.posts)
        posts.sort(key=lambda x: x.published_at, reverse=True)
        return posts[offset:(offset + limit)]

    def bfs_links(self, start, end):
        qu = deque([(start, 0)])
        visited = [start]
        max_count = 0
        while qu:
            current, count = qu.popleft()
            max_count = count
            if current == end:
                return count
            visited.append(current)

            for neighbour in self.following(current):
                if neighbour not in visited:
                    qu.append((neighbour, count + 1))
        if end is not None:
            raise UsersNotConnectedError("No path from start to end")
        if max_count == 0:
            return math.inf
        return max_count

    def bfs_followings(self, start, n):
        if n == 0:
            return {}
        qu = deque([(start, 0)])
        visited = [(start, 0)]
        while qu:
            current, count = qu.popleft()
            if count > n:
                break
            for fwing in self.following(current):
                if fwing not in visited:
                    qu.append((fwing, count + 1))
                    visited.append((fwing, count + 1))

        return {element for element, count in visited if count == n}