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
173
174
175
176
177
import uuid
import operator
from datetime import datetime
from collections import deque


class UserDoesNotExistError(Exception):
    def __init__(self):
        pass


class UserAlreadyExistsError(Exception):
    def __init__(self):
        pass


class UsersNotConnectedError(Exception):
    def __init__(self):
        pass


class User:

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

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

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


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


class SocialGraph:
    def __init__(self):
        self._soc_graph = {}
        self.users = {}

    def add_user(self, user):
        if user in self._soc_graph.keys():
            raise UserAlreadyExistsError
        else:
            self._soc_graph.update({user: set()})
            self.users.update({user.uuid: user})

    def get_user(self, user_uuid):
        if user_uuid not in [x.uuid for x in self._soc_graph.keys()]:
            raise UserDoesNotExistError
        else:
            return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users.keys():
            raise UserDoesNotExistError
        else:
            self._soc_graph.pop(self.users.pop(user_uuid))

    def follow(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            self._soc_graph[self.users[follower]].add(followee)

    def unfollow(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            self._soc_graph[self.users[follower]].discard(followee)

    def is_following(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            return followee in self._soc_graph[self.users[follower]]

    def followers(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return {user.uuid for user in self._soc_graph if user_uuid in self._soc_graph[user]}

    def following(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return self._soc_graph[self.users[user_uuid]]

    def friends(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return {uid for uid in self._soc_graph[self.users[user_uuid]] if user_uuid in self._soc_graph[self.users[uid]]}

    def max_distance(self, user_uuid):
        visited = set()
        queue = deque()
        visited.add(self.users[user_uuid])
        queue.append((0, self.users[user_uuid]))
        counter = 0

        while queue:
            node_with_level = queue.popleft()
            level, node = node_with_level

            for follower in self._soc_graph[node]:
                if follower not in visited:
                    visited.add(follower)
                    counter = level + 1
                    queue.append((level + 1, self.users[follower]))
        return counter

    def min_distance(self, from_user_uuid, to_user_uuid):
        visited = set()
        queue = deque()
        try:
            visited.add(self.users[from_user_uuid])
            queue.append((0, self.users[from_user_uuid]))

            while queue:
                node_with_level = queue.popleft()
                level, node = node_with_level

                if node.uuid == to_user_uuid:
                    return level

                for follower in self._soc_graph[node]:
                    if follower not in visited:
                        visited.add(follower)
                        queue.append((level + 1, self.users[follower]))
        except UsersNotConnectedError:
            raise

    def nth_layer_followings(self, user_uuid, n):
        visited = set()
        queue = deque()
        counter = 0
        nth = []

        visited.add((0, self.users[user_uuid]))
        queue.append((0, self.users[user_uuid]))

        while queue and n != counter:
            node_with_level = queue.popleft()
            node = node_with_level[1]
            counter = node_with_level[0]
            for follower in self._soc_graph[node]:
                if follower not in visited:
                    visited.add((counter + 1, self.users[follower]))
                    queue.append((counter + 1, self.users[follower]))
        nth = [user[1].uuid for user in visited if user[0] == counter]
        if n > self.max_distance(user_uuid):
            return []
        return nth

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

..E.....
======================================================================
ERROR: 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
AttributeError: 'SocialGraph' object has no attribute 'generate_feed'

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

FAILED (errors=1)

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

Александра обнови решението на 14.04.2016 00:38 (преди над 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
import uuid
import operator
from datetime import datetime
from collections import deque


class UserDoesNotExistError(Exception):
    def __init__(self):
        pass


class UserAlreadyExistsError(Exception):
    def __init__(self):
        pass


class UsersNotConnectedError(Exception):
    def __init__(self):
        pass


class User:

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

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

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


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


class SocialGraph:
    def __init__(self):
        self._soc_graph = {}
        self.users = {}

    def add_user(self, user):
        if user in self._soc_graph.keys():
            raise UserAlreadyExistsError
        else:
            self._soc_graph.update({user: set()})
            self.users.update({user.uuid: user})

    def get_user(self, user_uuid):
        if user_uuid not in [x.uuid for x in self._soc_graph.keys()]:
            raise UserDoesNotExistError
        else:
            return self.users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.users.keys():
            raise UserDoesNotExistError
        else:
            self._soc_graph.pop(self.users.pop(user_uuid))

    def follow(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            self._soc_graph[self.users[follower]].add(followee)

    def unfollow(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            self._soc_graph[self.users[follower]].discard(followee)

    def is_following(self, follower, followee):
        try:
            self.get_user(follower)
        except UserDoesNotExistError:
            raise
        else:
            return followee in self._soc_graph[self.users[follower]]

    def followers(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return {user.uuid for user in self._soc_graph if user_uuid in self._soc_graph[user]}

    def following(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return self._soc_graph[self.users[user_uuid]]

    def friends(self, user_uuid):
        try:
            self.get_user(user_uuid)
        except UserDoesNotExistError:
            raise
        else:
            return {uid for uid in self._soc_graph[self.users[user_uuid]] if user_uuid in self._soc_graph[self.users[uid]]}

    def max_distance(self, user_uuid):
        visited = set()
        queue = deque()
        visited.add(self.users[user_uuid])
        queue.append((0, self.users[user_uuid]))
        counter = 0

        while queue:
            node_with_level = queue.popleft()
            level, node = node_with_level

            for follower in self._soc_graph[node]:
                if follower not in visited:
                    visited.add(follower)
                    counter = level + 1
                    queue.append((level + 1, self.users[follower]))
        return counter

    def min_distance(self, from_user_uuid, to_user_uuid):
        visited = set()
        queue = deque()
        try:
            visited.add(self.users[from_user_uuid])
            queue.append((0, self.users[from_user_uuid]))

            while queue:
                node_with_level = queue.popleft()
                level, node = node_with_level

                if node.uuid == to_user_uuid:
                    return level

                for follower in self._soc_graph[node]:
                    if follower not in visited:
                        visited.add(follower)
                        queue.append((level + 1, self.users[follower]))
        except UsersNotConnectedError:
            raise

    def nth_layer_followings(self, user_uuid, n):
        visited = set()
        queue = deque()
        counter = 0
        nth = []

        visited.add((0, self.users[user_uuid]))
        queue.append((0, self.users[user_uuid]))

        while queue and n != counter:
            node_with_level = queue.popleft()
            node = node_with_level[1]
            counter = node_with_level[0]
            for follower in self._soc_graph[node]:
                if follower not in visited:
                    visited.add((counter + 1, self.users[follower]))
                    queue.append((counter + 1, self.users[follower]))
        nth = [user[1].uuid for user in visited if user[0] == counter]
        if n > self.max_distance(user_uuid):
            return []
        return nth