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
from uuid import uuid4, UUID
from datetime import datetime
from collections import deque
from itertools import islice


MAX_POSTS = 50


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = deque(maxlen=MAX_POSTS)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))

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


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


def decorator_check_uuid(func):
    def user_existance_checker(*args):
        graph = args[0]
        for uid in args:
            # is it user
            if type(uid) == UUID and uid not in graph.users:
                raise UserDoesNotExistError
        return func(*args)
    return user_existance_checker


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, set()]

    @decorator_check_uuid
    def get_user(self, user_uuid):
        return self.users[user_uuid][0]

    @decorator_check_uuid
    def delete_user(self, user_uuid):
        self.users.pop(user_uuid)
        # remove user from all users
        for uid in list(self.users.keys()):
            followees = self.following(uid)
            if user_uuid in followees:
                followees.remove(user_uuid)

    @decorator_check_uuid
    def follow(self, follower, followee):
        self.following(follower).add(followee)

    @decorator_check_uuid
    def unfollow(self, follower, followee):
        self.following(follower).remove(followee)

    @decorator_check_uuid
    def is_following(self, follower, followee):
        return followee in self.following(follower)

    @decorator_check_uuid
    def followers(self, user_uuid):
        followers = set()
        for uid, user_data in self.users.items():
            if uid == user_uuid:
                continue
            if self.is_following(uid, user_uuid):
                followers.add(uid)
        return followers

    @decorator_check_uuid
    def following(self, user_uuid):
        return self.users[user_uuid][1]

    @decorator_check_uuid
    def friends(self, user_uuid):
        friends = []
        followees = self.following(user_uuid)
        for followee in followees:
            if self.is_following(followee, user_uuid):
                friends.append(followee)
        return friends

    @decorator_check_uuid
    def max_distance(self, user_uuid):
        last_level = []
        passed = set()
        level = 1
        while True:
            cur_level = self.nth_layer_followings(user_uuid, level)
            if not cur_level:
                return level-1
            passed = passed.union(last_level)
            level += 1
        return 0

    @decorator_check_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        level_followees = self.following(from_user_uuid)
        level = 1
        while True:
            if not level_followees:
                level = 0
                break
            if to_user_uuid in level_followees:
                break
            level += 1
            level_followees = self.nth_layer_followings(from_user_uuid, level)
        if level == 0:
            raise UsersNotConnectedError
        return level

    @decorator_check_uuid
    def nth_layer_followings(self, user_uuid, n):
        def get_sub_followees(uuid):
            followees = self.following(uuid)
            return [uid for uid in followees if uid not in passed]
        if n == 0:
            return []
        layer_followees = self.following(user_uuid)
        passed = set()
        while n > 1 and layer_followees:
            n -= 1
            passed = passed.union(layer_followees)
            sub_followees = map(get_sub_followees, layer_followees)
            layer_followees = set().union(*sub_followees)
        return layer_followees

    def generate_feed(self, user_uuid, offset=0, limit=10):
        for followee in self.following(user_uuid):
            posts = islice(self.get_user(followee).posts, offset, offset+limit)
            for post in posts:
                yield post


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass

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

..F.....
======================================================================
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: ['10', '11', '12', '13', '14', '15', '16', [182 chars]'29'] != ['39', '29', '19', '9', '38', '28', '18', '8', '37', '27']

First differing element 0:
10
39

First list contains 30 additional elements.
First extra element 10:
30

+ ['39', '29', '19', '9', '38', '28', '18', '8', '37', '27']
- ['10',
-  '11',
-  '12',
-  '13',
-  '14',
-  '15',
-  '16',
-  '17',
-  '18',
-  '19',
-  '30',
-  '31',
-  '32',
-  '33',
-  '34',
-  '35',
-  '36',
-  '37',
-  '38',
-  '39',
-  '0',
-  '1',
-  '2',
-  '3',
-  '4',
-  '5',
-  '6',
-  '7',
-  '8',
-  '9',
-  '20',
-  '21',
-  '22',
-  '23',
-  '24',
-  '25',
-  '26',
-  '27',
-  '28',
-  '29']

----------------------------------------------------------------------
Ran 8 tests in 0.065s

FAILED (failures=1)

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

Данаил обнови решението на 18.04.2016 10: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
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
from uuid import uuid4, UUID
from datetime import datetime
from collections import deque
from itertools import islice


MAX_POSTS = 50


class User:
    def __init__(self, full_name):
        self.full_name = full_name
        self.uuid = uuid4()
        self.posts = deque(maxlen=MAX_POSTS)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))

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


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


def decorator_check_uuid(func):
    def user_existance_checker(*args):
        graph = args[0]
        for uid in args:
            # is it user
            if type(uid) == UUID and uid not in graph.users:
                raise UserDoesNotExistError
        return func(*args)
    return user_existance_checker


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, set()]

    @decorator_check_uuid
    def get_user(self, user_uuid):
        return self.users[user_uuid][0]

    @decorator_check_uuid
    def delete_user(self, user_uuid):
        self.users.pop(user_uuid)
        # remove user from all users
        for uid in list(self.users.keys()):
            followees = self.following(uid)
            if user_uuid in followees:
                followees.remove(user_uuid)

    @decorator_check_uuid
    def follow(self, follower, followee):
        self.following(follower).add(followee)

    @decorator_check_uuid
    def unfollow(self, follower, followee):
        self.following(follower).remove(followee)

    @decorator_check_uuid
    def is_following(self, follower, followee):
        return followee in self.following(follower)

    @decorator_check_uuid
    def followers(self, user_uuid):
        followers = set()
        for uid, user_data in self.users.items():
            if uid == user_uuid:
                continue
            if self.is_following(uid, user_uuid):
                followers.add(uid)
        return followers

    @decorator_check_uuid
    def following(self, user_uuid):
        return self.users[user_uuid][1]

    @decorator_check_uuid
    def friends(self, user_uuid):
        friends = []
        followees = self.following(user_uuid)
        for followee in followees:
            if self.is_following(followee, user_uuid):
                friends.append(followee)
        return friends

    @decorator_check_uuid
    def max_distance(self, user_uuid):
        last_level = []
        passed = set()
        level = 1
        while True:
            cur_level = self.nth_layer_followings(user_uuid, level)
            if not cur_level:
                return level-1
            passed = passed.union(last_level)
            level += 1
        return 0

    @decorator_check_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        level_followees = self.following(from_user_uuid)
        level = 1
        while True:
            if not level_followees:
                level = 0
                break
            if to_user_uuid in level_followees:
                break
            level += 1
            level_followees = self.nth_layer_followings(from_user_uuid, level)
        if level == 0:
            raise UsersNotConnectedError
        return level

    @decorator_check_uuid
    def nth_layer_followings(self, user_uuid, n):
        def get_sub_followees(uuid):
            followees = self.following(uuid)
            return [uid for uid in followees if uid not in passed]
        if n == 0:
            return []
        layer_followees = self.following(user_uuid)
        passed = set()
        while n > 1 and layer_followees:
            n -= 1
            passed = passed.union(layer_followees)
            sub_followees = map(get_sub_followees, layer_followees)
            layer_followees = set().union(*sub_followees)
        return layer_followees

    def generate_feed(self, user_uuid, offset=0, limit=10):
        for followee in self.following(user_uuid):
            posts = islice(self.get_user(followee).posts, offset, offset+limit)
            for post in posts:
                yield post


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass