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


class UserError(Exception):
    pass


class UserDoesNotExistError(UserError):
    pass


class UserAlreadyExistsError(UserError):
    pass


class UsersNotConnectedError(UserError):
    pass


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


class User:
    max_publications = 50

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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if(len(self.posts) > self.max_publications):
            self.posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self.users = []
        self.pairs = []

    # Validate user uuid
    def validate_uuid(method):
        def decorator(self, *args, **kwargs):
            ids = [user.uuid for user in self.users]
            if not all(id in ids for id in args if isinstance(id, uuid.UUID)):
                raise UserDoesNotExistError()
            return method(self, *args, **kwargs)
        return decorator

    @validate_uuid
    def get_user_list_id(self, user_uuid):
        return [id for id, user in enumerate(self.users)
                if user.uuid == user_uuid][0]

    def add_user(self, user):
        try:
            self.get_user(user.uuid)
            raise UserAlreadyExistsError()
        except UserDoesNotExistError:
            self.users.append(user)

    def get_user(self, user_uuid):
        return self.users[self.get_user_list_id(user_uuid)]

    def delete_user(self, user_uuid):
        del self.users[self.get_user_list_id(user_uuid)]

    @validate_uuid
    def follow(self, follower, followee):
        self.pairs.append((follower, followee))

    @validate_uuid
    def unfollow(self, follower, followee):
        self.pairs = [(fer, fee) for fer, fee in self.pairs
                      if not(fer == follower and fee == followee)]

    @validate_uuid
    def is_following(self, follower, followee):
        return any(fer == follower and fee == followee
                   for fer, fee in self.pairs)

    @validate_uuid
    def followers(self, user_uuid):
        return {fer for fer, fee in self.pairs if fee == user_uuid}

    @validate_uuid
    def following(self, user_uuid):
        return {fee for fer, fee in self.pairs if fer == user_uuid}

    @validate_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        result = 0
        while to_user_uuid not in self.nth_layer_followings(
              from_user_uuid, result) and result < len(self.users):
            result += 1
        if to_user_uuid not in self.nth_layer_followings(
              from_user_uuid, result):
            raise UsersNotConnectedError()
        return result

    @validate_uuid
    def max_distance(self, user_uuid):
        result = 0
        while self.nth_layer_followings(user_uuid, result):
            result += 1
        return result - 1

    @validate_uuid
    def nth_layer_followings(self, user_uuid, n):
        last_layer = [user_uuid]
        visited = set(last_layer)
        for _ in range(n):
            last_layer = [uuid for fee in last_layer for uuid
                          in self.following(fee) if uuid not in visited]
            visited = visited.union(last_layer)
        return last_layer

    @validate_uuid
    def friends(self, user_uuid):
        return self.followers(user_uuid).intersection(
            self.following(user_uuid))

    def generate_feed(self, user_uuid, offset=0, limit=10):
        return sorted([post for uuid in self.following(user_uuid)
                      for post in self.get_user(uuid).posts],
                      key=lambda post: post.published_at,
                      reverse=True)[offset:][:limit]

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.066s

OK

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

Илия обнови решението на 16.04.2016 13:39 (преди над 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
import uuid
import datetime


class UserError(Exception):
    pass


class UserDoesNotExistError(UserError):
    pass


class UserAlreadyExistsError(UserError):
    pass


class UsersNotConnectedError(UserError):
    pass


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


class User:
    max_publications = 50

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

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if(len(self.posts) > self.max_publications):
            self.posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self.users = []
        self.pairs = []

    # Validate user uuid
    def validate_uuid(method):
        def decorator(self, *args, **kwargs):
            ids = [user.uuid for user in self.users]
            if not all(id in ids for id in args if isinstance(id, uuid.UUID)):
                raise UserDoesNotExistError()
            return method(self, *args, **kwargs)
        return decorator

    @validate_uuid
    def get_user_list_id(self, user_uuid):
        return [id for id, user in enumerate(self.users)
                if user.uuid == user_uuid][0]

    def add_user(self, user):
        try:
            self.get_user(user.uuid)
            raise UserAlreadyExistsError()
        except UserDoesNotExistError:
            self.users.append(user)

    def get_user(self, user_uuid):
        return self.users[self.get_user_list_id(user_uuid)]

    def delete_user(self, user_uuid):
        del self.users[self.get_user_list_id(user_uuid)]

    @validate_uuid
    def follow(self, follower, followee):
        self.pairs.append((follower, followee))

    @validate_uuid
    def unfollow(self, follower, followee):
        self.pairs = [(fer, fee) for fer, fee in self.pairs
                      if not(fer == follower and fee == followee)]

    @validate_uuid
    def is_following(self, follower, followee):
        return any(fer == follower and fee == followee
                   for fer, fee in self.pairs)

    @validate_uuid
    def followers(self, user_uuid):
        return {fer for fer, fee in self.pairs if fee == user_uuid}

    @validate_uuid
    def following(self, user_uuid):
        return {fee for fer, fee in self.pairs if fer == user_uuid}

    @validate_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        result = 0
        while to_user_uuid not in self.nth_layer_followings(
              from_user_uuid, result) and result < len(self.users):
            result += 1
        if to_user_uuid not in self.nth_layer_followings(
              from_user_uuid, result):
            raise UsersNotConnectedError()
        return result

    @validate_uuid
    def max_distance(self, user_uuid):
        result = 0
        while self.nth_layer_followings(user_uuid, result):
            result += 1
        return result - 1

    @validate_uuid
    def nth_layer_followings(self, user_uuid, n):
        last_layer = [user_uuid]
        visited = set(last_layer)
        for _ in range(n):
            last_layer = [uuid for fee in last_layer for uuid
                          in self.following(fee) if uuid not in visited]
            visited = visited.union(last_layer)
        return last_layer

    @validate_uuid
    def friends(self, user_uuid):
        return self.followers(user_uuid).intersection(
            self.following(user_uuid))

    def generate_feed(self, user_uuid, offset=0, limit=10):
        return sorted([post for uuid in self.following(user_uuid)
                      for post in self.get_user(uuid).posts],
                      key=lambda post: post.published_at,
                      reverse=True)[offset:][:limit]
  • Идеята да валидираш uuid-та с декоратор е яка, обаче:
    • Името decorator е кофти, това е крайния резултат от декорирането, т.е. по-скоро искаш да го кръстиш decorated.
    • По-важното: всеки път валидираш всички uuid-та, въпреки, че повечет от тях вече са били валидирани.
    • Това те води до там да хващаш UserDoesNotExistError в метода за добавяне на потребител, което е малко грозно.
  • Можеш да си спестиш изцяло get_user_list_id ако избереш по-подходяща структура от данни за users атрибута на SocialGraph.
  • Понеже пазиш информацията за връзките в графа като двойки, всяка операция по премахване или проверка за следване е линейна по броя следвания, а извикването на follow няколко пъти с еднакви аргументи кара pairs да расте ненужно. Можеш да си подредиш данните доста по-оптимално, примерно със set или dict.