timeit

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

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

Решение на Социална мрежа от Даниел Шушков

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

Към профила на Даниел Шушков

Резултати

  • 8 точки от тестове
  • 0 бонус точки
  • 8 точки общо
  • 6 успешни тест(а)
  • 2 неуспешни тест(а)

Код

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


class User:

    def __init__(self, name):
        self.name = name
        self.uuid = uuid.uuid4()
        self.posts = []

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

    def get_post(self):
        num = 0
        while num < len(self.posts):
            yield self.posts[num]
            num += 1


class Post:

    def __init__(self, author_, content_):
        self.author = author_
        self.content = content_
        self.published_at = datetime.datetime.now()


class SocialGraph:

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

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

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

    def delete_user(self, user_uuid):
        self.chech_exsist(user_uuid)
        del self.graph[user_uuid]
        for key in self.graph:
            if user_uuid in self.graph[key][1]:
                self.graph[key][1].remove(user_uuid)

    def follow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee not in self.graph[follower][1]:
            self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee in self.graph[follower][1]:
            self.graph[follower][1].remove(followee)

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

    def followers(self, user_uuid):
        self.chech_exsist(user_uuid)
        followers = set()
        for key in self.graph:
            if key is user_uuid:
                continue
            else:
                if user_uuid in self.graph[key][1]:
                    followers.add(key)
        return followers

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

    def friends(self, user_uuid):
        self.chech_exsist(user_uuid)
        friends = set()
        for neighbour in self.graph[user_uuid][1]:
            if user_uuid in self.graph[neighbour][1]:
                friends.add(neighbour)
        return friends

    def check_user(self, user_uuid):
        return user_uuid in self.graph.keys()

    def chech_exsist(self, user_uuid):
        if not self.check_user(user_uuid):
            raise UserDoesNotExistError
        return None

    def max_distance(self, user_uuid):
        self.chech_exsist(user_uuid)
        for i in range(len(self.graph.keys()), 0, -1):
            if len(self.nth_layer_followings(user_uuid, i)) is not 0:
                return i
        return 0

    def find_shortest_path(self, start, end, path):
        path_ = path + [start]
        if start == end:
            return path_

        shortest = []
        for node in self.graph[start][1]:
            if node not in path_:
                newpath = self.find_shortest_path(node, end, path_)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.chech_exsist(from_user_uuid)
        self.chech_exsist(to_user_uuid)
        path = []
        result = self.find_shortest_path(from_user_uuid, to_user_uuid, path)
        if len(result) - 1 < 0:
            raise UsersNotConnectedError
        return len(result) - 1

    def dfs(self, start, result, visited, curr_level, n):
        if curr_level is n:
            result.add(start)
            return
        visited.add(start)
        for next in self.graph[start][1] - visited:
            curr_level_ = curr_level + 1
            self.dfs(next, result, visited, curr_level_, n)
        visited.remove(start)

    def nth_layer_followings(self, user_uuid, n):
        self.chech_exsist(user_uuid)
        result = set()
        visited = set()
        self.dfs(user_uuid, result, visited, 0, n)
        return result

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.chech_exsist(user_uuid)
        result = []
        for neighbour in self.graph[user_uuid][1]:
            result.extend(self.graph[neighbour][0].posts)
        result2 = sorted(result, key=lambda post: post.published_at)
        return result2[offset:offset + limit]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

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

.FF.....
======================================================================
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

======================================================================
FAIL: test_feed (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: Lists differ: ['0', '10', '20', '30', '1', '11', '21', '31', '2', '12'] != ['39', '29', '19', '9', '38', '28', '18', '8', '37', '27']

First differing element 0:
0
39

- ['0', '10', '20', '30', '1', '11', '21', '31', '2', '12']
+ ['39', '29', '19', '9', '38', '28', '18', '8', '37', '27']

----------------------------------------------------------------------
Ran 8 tests in 0.068s

FAILED (failures=2)

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

Даниел обнови решението на 18.04.2016 11:09 (преди над 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
import uuid
import datetime


class User:

    def __init__(self, name):
        self.name = name
        self.uuid = uuid.uuid4()
        self.posts = []

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

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


class Post:

    def __init__(self, author_, content_):
        self.author = author_
        self.content = content_
        self.published_at = datetime.datetime.now()


class SocialGraph:

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

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

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

    def delete_user(self, user_uuid):
        self.chech_exsist(user_uuid)
        del self.graph[user_uuid]
        for key in self.graph:
            if user_uuid in self.graph[key][1]:
                self.graph[key][1].remove(user_uuid)

    def follow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee not in self.graph[follower][1]:
            self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee in self.graph[follower][1]:
            self.graph[follower][1].remove(followee)

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

    def followers(self, user_uuid):
        self.chech_exsist(user_uuid)
        followers = set()
        for key in self.graph:
            if key is user_uuid:
                continue
            else:
                if user_uuid in self.graph[key][1]:
                    followers.add(key)
        return followers

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

    def friends(self, user_uuid):
        self.chech_exsist(user_uuid)
        friends = set()
        for neighbour in self.graph[user_uuid][1]:
            if user_uuid in self.graph[neighbour][1]:
                friends.add(neighbour)
        return friends
    # ok

    def check_user(self, user_uuid):
        return user_uuid in self.graph.keys()

    def chech_exsist(self, user_uuid):
        if not self.check_user(user_uuid):
            raise UserDoesNotExistError
        return None

    def max_distance(self, user_uuid):
        self.chech_exsist(user_uuid)
        for i in range(len(self.graph.keys()), 0, -1):
            print(str(i) + "::::")
            print(len(self.nth_layer_followings(user_uuid, i)))
            if len(self.nth_layer_followings(user_uuid, i)) is not 0:
                return i
        return 0

    def find_shortest_path(self, start, end, path):
        path_ = path + [start]
        if start == end:
            return path_

        shortest = None
        for node in self.graph[start][1]:
            if node not in path_:
                newpath = self.find_shortest_path(node, end, path_)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.chech_exsist(from_user_uuid)
        self.chech_exsist(to_user_uuid)
        path = []
        result = self.find_shortest_path(from_user_uuid, to_user_uuid, path)
        return len(result) - 1

    def dfs(self, start, result, visited, curr_level, n):
        if curr_level is n:
            result.add(start)
            return
        visited.add(start)
        for next in self.graph[start][1] - visited:
            curr_level_ = curr_level + 1
            self.dfs(next, result, visited, curr_level_, n)
        visited.remove(start)

    def nth_layer_followings(self, user_uuid, n):
        self.chech_exsist(user_uuid)
        result = set()
        visited = set()
        self.dfs(user_uuid, result, visited, 0, n)
        return result

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.chech_exsist(user_uuid)
        result = []
        for neighbour in self.graph[user_uuid][1]:
            result.extend(self.graph[neighbour][0].posts)
        sorted(result, key=lambda post: str(post.published_at))
        return result[offset:offset + limit]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

Даниел обнови решението на 18.04.2016 14:44 (преди над 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


class User:

    def __init__(self, name):
        self.name = name
        self.uuid = uuid.uuid4()
        self.posts = []

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

    def get_post(self):
        num = 0
        while num < len(self.posts):
            yield self.posts[num]
            num += 1


class Post:

    def __init__(self, author_, content_):
        self.author = author_
        self.content = content_
        self.published_at = datetime.datetime.now()


class SocialGraph:

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

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

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

    def delete_user(self, user_uuid):
        self.chech_exsist(user_uuid)
        del self.graph[user_uuid]
        for key in self.graph:
            if user_uuid in self.graph[key][1]:
                self.graph[key][1].remove(user_uuid)

    def follow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee not in self.graph[follower][1]:
            self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.chech_exsist(follower)
        self.chech_exsist(followee)
        if followee in self.graph[follower][1]:
            self.graph[follower][1].remove(followee)

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

    def followers(self, user_uuid):
        self.chech_exsist(user_uuid)
        followers = set()
        for key in self.graph:
            if key is user_uuid:
                continue
            else:
                if user_uuid in self.graph[key][1]:
                    followers.add(key)
        return followers

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

    def friends(self, user_uuid):
        self.chech_exsist(user_uuid)
        friends = set()
        for neighbour in self.graph[user_uuid][1]:
            if user_uuid in self.graph[neighbour][1]:
                friends.add(neighbour)
        return friends

    def check_user(self, user_uuid):
        return user_uuid in self.graph.keys()

    def chech_exsist(self, user_uuid):
        if not self.check_user(user_uuid):
            raise UserDoesNotExistError
        return None

    def max_distance(self, user_uuid):
        self.chech_exsist(user_uuid)
        for i in range(len(self.graph.keys()), 0, -1):
            if len(self.nth_layer_followings(user_uuid, i)) is not 0:
                return i
        return 0

    def find_shortest_path(self, start, end, path):
        path_ = path + [start]
        if start == end:
            return path_

        shortest = []
        for node in self.graph[start][1]:
            if node not in path_:
                newpath = self.find_shortest_path(node, end, path_)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.chech_exsist(from_user_uuid)
        self.chech_exsist(to_user_uuid)
        path = []
        result = self.find_shortest_path(from_user_uuid, to_user_uuid, path)
        if len(result) - 1 < 0:
            raise UsersNotConnectedError
        return len(result) - 1

    def dfs(self, start, result, visited, curr_level, n):
        if curr_level is n:
            result.add(start)
            return
        visited.add(start)
        for next in self.graph[start][1] - visited:
            curr_level_ = curr_level + 1
            self.dfs(next, result, visited, curr_level_, n)
        visited.remove(start)

    def nth_layer_followings(self, user_uuid, n):
        self.chech_exsist(user_uuid)
        result = set()
        visited = set()
        self.dfs(user_uuid, result, visited, 0, n)
        return result

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.chech_exsist(user_uuid)
        result = []
        for neighbour in self.graph[user_uuid][1]:
            result.extend(self.graph[neighbour][0].posts)
        result2 = sorted(result, key=lambda post: post.published_at)
        return result2[offset:offset + limit]


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass