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


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

    def add_post(self, post_content):
        published_at = datetime.datetime.now()
        post = Post(self.uuid, published_at, post_content)
        if len(self.posts) >= 50:
            del(self.posts[0])
        self.posts.append(post)
        return published_at

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

    def __str__(self):
        return "{0}, {1} ".format(self.full_name, self.uuid)

    def __repr__(self):
        return "{0} ".format(self.full_name)


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

    def __str__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)

    def __repr__(self):
        return self.__str__()


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User with this UUID Does Not Exist!"


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "These two users are not connected!"


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = "User already existis Exception!"


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

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

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

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

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

    def unfollow(self, follower, followee):
        self.graph[self.get_user(follower)].remove(self.get_user(followee))

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

    def followers(self, user_uuid):
        return [user.uuid for user in self.graph
                if self.get_user(user_uuid) in self.graph[user]]

    def following(self, user_uuid):
        return [user.uuid for user in self.graph[self.get_user(user_uuid)]]

    def friends(self, user_uuid):
        return list(set(self.following(user_uuid)) &
                    set(self.followers(user_uuid)))

    def max_distance(self, user_uuid):
        count = 1
        while self.nth_layer_followings(user_uuid, count) != []:
            count += 1
        if count == 1:
            return math.inf
        return count - 1

    def min_path(self, from_user_uuid, to_user_uuid, path=[]):
        start = self.get_user(from_user_uuid)
        end = self.get_user(to_user_uuid)
        path = path + [start]
        if start == end:
            return path
        if start not in self.graph:
            return None
        shortest = None
        for node in self.graph[start]:
            if node not in path:
                newpath = self.min_path(node.uuid, end.uuid, 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, path=[]):
        return len(self.min_path(from_user_uuid, to_user_uuid, path=[])) - 1

    def nth_layer_followings(self, user_uuid, n):
        start = self.get_user(user_uuid)
        visited = [start]
        result = []
        last_level = [start]

        def helper(l, count, num):
            if count == num:
                for elem in l:
                    result.extend(self.graph[elem])
            if count < num:
                newlist = []
                for elem in l:
                    visited.extend(self.graph[elem])
                    newlist.extend(self.graph[elem])
                helper(newlist, count + 1, n)
            return [person.uuid for person in (set(result) - set(visited))]
        return helper(last_level, 1, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        all_posts = []
        for followee in self.graph[self.get_user(user_uuid)]:
            all_posts.extend(followee.posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

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

...F....
======================================================================
FAIL: test_following (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: False is not true

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

FAILED (failures=1)

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

Симеон обнови решението на 13.04.2016 13:11 (преди над 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
import uuid
import datetime


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

    def add_post(self, post_content):
        published_at = datetime.datetime.now()
        post = Post(self.uuid, published_at, post_content)
        if len(self.posts) >= 50:
            del(self.posts[0])
        self.posts.append(post)
        return published_at

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

    def __str__(self):
        return "{0}, {1} ".format(self.full_name, self.uuid)

    def __repr__(self):
        return "{0} ".format(self.full_name)


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

    def __str__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)

    def __repr__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User with this UUID Does Not Exist!"


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "These two users are not connected!"


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = "User already existis Exception!"


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

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

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

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

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

    def unfollow(self, follower, followee):
        self.graph[self.get_user(follower)].remove(self.get_user(followee))

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

    def followers(self, user_uuid):
        return [user.uuid for user in self.graph
                if self.get_user(user_uuid) in self.graph[user]]

    def following(self, user_uuid):
        return [user.uuid for user in self.graph[self.get_user(user_uuid)]]

    def friends(self, user_uuid):
        return list(set(self.following(user_uuid)) &
                    set(self.followers(user_uuid)))

    def max_distance(self, user_uuid):
        count = 1
        while self.nth_layer_followings(user_uuid, count) != []:
            count += 1
        return count - 1

    def min_path(s, from_user_uuid, to_user_uuid, path=[]):
        start = s.get_user(from_user_uuid)
        end = s.get_user(to_user_uuid)
        path = path + [start]
        if start == end:
            return path
        if start not in s.graph:
            return None
        shortest = None
        for node in s.graph[start]:
            if node not in path:
                newpath = s.min_path(node.uuid, end.uuid, 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, path=[]):
        return len(self.min_path(from_user_uuid, to_user_uuid, path=[])) - 1

    def nth_layer_followings(self, user_uuid, n):
        start = self.get_user(user_uuid)
        visited = [start]
        result = []
        lst = [start]

        def helper(l, count, num):
            if count == num:
                for elem in l:
                    result.extend(self.graph[elem])
            if count < num:
                newlist = []
                for elem in l:
                    visited.extend(self.graph[elem])
                    newlist.extend(self.graph[elem])
                helper(newlist, count + 1, n)
            return [person.uuid for person in (set(result) - set(visited))]
        return helper(lst, 1, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        all_posts = []
        for followee in self.graph[self.get_user(user_uuid)]:
            all_posts.extend(followee.posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

Симеон обнови решението на 16.04.2016 21:01 (преди над 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
import uuid
import datetime
import math


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

    def add_post(self, post_content):
        published_at = datetime.datetime.now()
        post = Post(self.uuid, published_at, post_content)
        if len(self.posts) >= 50:
            del(self.posts[0])
        self.posts.append(post)
        return published_at

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

    def __str__(self):
        return "{0}, {1} ".format(self.full_name, self.uuid)

    def __repr__(self):
        return "{0} ".format(self.full_name)


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

    def __str__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)

    def __repr__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User with this UUID Does Not Exist!"


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "These two users are not connected!"


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = "User already existis Exception!"


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

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

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

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

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

    def unfollow(self, follower, followee):
        self.graph[self.get_user(follower)].remove(self.get_user(followee))

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

    def followers(self, user_uuid):
        return [user.uuid for user in self.graph
                if self.get_user(user_uuid) in self.graph[user]]

    def following(self, user_uuid):
        return [user.uuid for user in self.graph[self.get_user(user_uuid)]]

    def friends(self, user_uuid):
        return list(set(self.following(user_uuid)) &
                    set(self.followers(user_uuid)))

    def max_distance(self, user_uuid):
        count = 1
        while self.nth_layer_followings(user_uuid, count) != []:
            count += 1
        if count == 1:
            return math.inf
        return count - 1

    def min_path(s, from_user_uuid, to_user_uuid, path=[]):
        start = s.get_user(from_user_uuid)
        end = s.get_user(to_user_uuid)
        path = path + [start]
        if start == end:
            return path
        if start not in s.graph:
            return None
        shortest = None
        for node in s.graph[start]:
            if node not in path:
                newpath = s.min_path(node.uuid, end.uuid, 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, path=[]):
        return len(self.min_path(from_user_uuid, to_user_uuid, path=[])) - 1

    def nth_layer_followings(self, user_uuid, n):
        start = self.get_user(user_uuid)
        visited = [start]
        result = []
        lst = [start]

        def helper(l, count, num):
            if count == num:
                for elem in l:
                    result.extend(self.graph[elem])
            if count < num:
                newlist = []
                for elem in l:
                    visited.extend(self.graph[elem])
                    newlist.extend(self.graph[elem])
                helper(newlist, count + 1, n)
            return [person.uuid for person in (set(result) - set(visited))]
        return helper(lst, 1, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        all_posts = []
        for followee in self.graph[self.get_user(user_uuid)]:
            all_posts.extend(followee.posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

Симеон обнови решението на 17.04.2016 19:23 (преди над 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
import uuid
import datetime
import math


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

    def add_post(self, post_content):
        published_at = datetime.datetime.now()
        post = Post(self.uuid, published_at, post_content)
        if len(self.posts) >= 50:
            del(self.posts[0])
        self.posts.append(post)
        return published_at

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

    def __str__(self):
        return "{0}, {1} ".format(self.full_name, self.uuid)

    def __repr__(self):
        return "{0} ".format(self.full_name)


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

    def __str__(self):
        return "Author: {} , Published at: {}, Content: {}"\
            .format(self.author, self.published_at, self.content)

    def __repr__(self):
        return self.__str__()


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User with this UUID Does Not Exist!"


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "These two users are not connected!"


class UserAlreadyExistsError(Exception):
    def __init__(self):
        self.message = "User already existis Exception!"


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

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

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

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

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

    def unfollow(self, follower, followee):
        self.graph[self.get_user(follower)].remove(self.get_user(followee))

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

    def followers(self, user_uuid):
        return [user.uuid for user in self.graph
                if self.get_user(user_uuid) in self.graph[user]]

    def following(self, user_uuid):
        return [user.uuid for user in self.graph[self.get_user(user_uuid)]]

    def friends(self, user_uuid):
        return list(set(self.following(user_uuid)) &
                    set(self.followers(user_uuid)))

    def max_distance(self, user_uuid):
        count = 1
        while self.nth_layer_followings(user_uuid, count) != []:
            count += 1
        if count == 1:
            return math.inf
        return count - 1

    def min_path(self, from_user_uuid, to_user_uuid, path=[]):
        start = self.get_user(from_user_uuid)
        end = self.get_user(to_user_uuid)
        path = path + [start]
        if start == end:
            return path
        if start not in self.graph:
            return None
        shortest = None
        for node in self.graph[start]:
            if node not in path:
                newpath = self.min_path(node.uuid, end.uuid, 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, path=[]):
        return len(self.min_path(from_user_uuid, to_user_uuid, path=[])) - 1

    def nth_layer_followings(self, user_uuid, n):
        start = self.get_user(user_uuid)
        visited = [start]
        result = []
        last_level = [start]

        def helper(l, count, num):
            if count == num:
                for elem in l:
                    result.extend(self.graph[elem])
            if count < num:
                newlist = []
                for elem in l:
                    visited.extend(self.graph[elem])
                    newlist.extend(self.graph[elem])
                helper(newlist, count + 1, n)
            return [person.uuid for person in (set(result) - set(visited))]
        return helper(last_level, 1, n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
        all_posts = []
        for followee in self.graph[self.get_user(user_uuid)]:
            all_posts.extend(followee.posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]