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
import uuid
import datetime
import math


class Graph:
    @staticmethod
    def find_min(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = Graph.find_min(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    @staticmethod
    def find_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start][1]:
            if node not in path:
                newpaths = Graph.find_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = {}
        self.MAX_POSTS = 50

    def add_post(self, post_content):
        date = datetime.datetime.now()
        if (len(self.posts) >= self.MAX_POSTS):
            del self.posts[min(self.posts.keys())]
        self.posts[date] = Post(self.uuid, date, post_content)

    def get_post(self):
        for date in sorted(self.posts.keys()):
            yield self.posts[date]


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


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][0]

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

    def follow(self, follower, followee):
        if followee in self.users[follower][1]:
            return
        elif followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        else:
            self.users[follower][1].append(followee)

    def unfollow(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        self.users[follower][1].remove(followee)

    def is_following(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        return followee in self.users[follower][1]

    def followers(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set([_ for _ in self.users if user_uuid in self.users[_][1]])

    def following(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set(self.users[user_uuid][1])

    def friends(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return self.followers(user_uuid) & self.following(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.users or to_user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        min_path = Graph.find_min(self.users, from_user_uuid, to_user_uuid)
        return len(min_path) - 1

    def max_distance(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.append(Graph.find_min(self.users, user_uuid, user))
        paths = [path for path in paths if path is not None]
        if max(list(map(lambda _: len(_), paths))) - 1 == 0:
            return math.inf
        return max(list(map(lambda _: len(_), paths))) - 1

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.extend(Graph.find_paths(self.users, user_uuid, user))
        return map(lambda _: _[-1], filter(lambda _: len(_) == n + 1, paths))

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        feed = []
        for user in self.users[user_uuid][1]:
            feed.extend(list(self.get_user(user).get_post()))
        feed = sorted(feed, key=lambda _: _.published_at)
        return list(reversed(feed))[offset:offset+limit]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.067s

OK

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

Любослава обнови решението на 18.04.2016 13:51 (преди над 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
import uuid
import datetime
import math


class Graph:
    @staticmethod
    def find_min(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = Graph.find_min(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    @staticmethod
    def find_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start][1]:
            if node not in path:
                newpaths = Graph.find_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = {}
        self.MAX_POSTS = 50

    def add_post(self, post_content):
        date = datetime.datetime.now()
        if (len(self.posts) < self.MAX_POSTS):
            self.posts[date] = Post(self.uuid, date, post_content)
        else:
            del self.posts[min(self.posts.keys())]
            self.posts[date] = Post(self.uuid, date, post_content)

    def get_post(self):
        for date in sorted(self.posts.keys()):
            yield self.posts[date]


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


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][0]

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

    def follow(self, follower, followee):
        if followee in self.users[follower][1]:
            return
        elif followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        else:
            self.users[follower][1].append(followee)

    def unfollow(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        self.users[follower][1].remove(followee)

    def is_following(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        return followee in self.users[follower][1]

    def followers(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set([_ for _ in self.users if user_uuid in self.users[_][1]])

    def following(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set(self.users[user_uuid][1])

    def friends(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return self.followers(user_uuid) & self.following(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.users or to_user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        min_path = Graph.find_min(self.users, from_user_uuid, to_user_uuid)
        return len(min_path) - 1

    def max_distance(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.append(Graph.find_min(self.users, user_uuid, user))
        paths = [path for path in paths if path is not None]
        if max(list(map(lambda _: len(_), paths))) - 1 == 0:
            return math.inf
        return max(list(map(lambda _: len(_), paths))) - 1

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.extend(Graph.find_paths(self.users, user_uuid, user))
        return map(lambda _: _[-1], filter(lambda _: len(_) == n + 1, paths))


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

Любослава обнови решението на 18.04.2016 14:36 (преди над 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
import uuid
import datetime
import math


class Graph:
    @staticmethod
    def find_min(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = Graph.find_min(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    @staticmethod
    def find_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start][1]:
            if node not in path:
                newpaths = Graph.find_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = {}
        self.MAX_POSTS = 50

    def add_post(self, post_content):
        date = datetime.datetime.now()
        if (len(self.posts) >= self.MAX_POSTS):
            del self.posts[min(self.posts.keys())]
        self.posts[date] = Post(self.uuid, date, post_content)

    def get_post(self):
        for date in sorted(self.posts.keys()):
            yield self.posts[date]


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


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][0]

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

    def follow(self, follower, followee):
        if followee in self.users[follower][1]:
            return
        elif followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        else:
            self.users[follower][1].append(followee)

    def unfollow(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        self.users[follower][1].remove(followee)

    def is_following(self, follower, followee):
        if followee not in self.users or follower not in self.users:
            raise UserDoesNotExistError
        return followee in self.users[follower][1]

    def followers(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set([_ for _ in self.users if user_uuid in self.users[_][1]])

    def following(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return set(self.users[user_uuid][1])

    def friends(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        return self.followers(user_uuid) & self.following(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.users or to_user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        min_path = Graph.find_min(self.users, from_user_uuid, to_user_uuid)
        return len(min_path) - 1

    def max_distance(self, user_uuid):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.append(Graph.find_min(self.users, user_uuid, user))
        paths = [path for path in paths if path is not None]
        if max(list(map(lambda _: len(_), paths))) - 1 == 0:
            return math.inf
        return max(list(map(lambda _: len(_), paths))) - 1

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        paths = []
        for user in self.users:
            paths.extend(Graph.find_paths(self.users, user_uuid, user))
        return map(lambda _: _[-1], filter(lambda _: len(_) == n + 1, paths))

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.users:
            raise UserDoesNotExistError
            return
        feed = []
        for user in self.users[user_uuid][1]:
            feed.extend(list(self.get_user(user).get_post()))
        feed = sorted(feed, key=lambda _: _.published_at)
        return list(reversed(feed))[offset:offset+limit]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass