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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
from uuid import uuid4
from functools import reduce
from datetime import datetime
from time import sleep
import math


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

    def __str__(self):
        return ('User:    ' + str(self.author) +
                '\n' + 'Date:    ' + str(self.published_at) +
                '\n' + 'Content: ' + self.content + '\n')


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

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

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

    def manage_posts(self):
        if len(self.posts) >= 50:
            del self.posts[0]


class SocialGraph:
    def __init__(self):
        self.nodes = {}  # върхове {user_uuid: user, ...}
        self.edges = {}  # ръбове -{follower_uuid: {followee1_uuid, ...}...}

    def uuid_in_graph(self, user_uuid):
        if self.nodes.get(user_uuid) is not None:
            return True
        else:
            raise UserDoesNotExistError
            return False

    def add_user(self, user):
        if self.nodes.get(user.uuid) is not None:
            raise UserAlreadyExistsError
        else:
            self.nodes[user.uuid] = user
            self.edges[user.uuid] = set()

    def get_user(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return self.nodes[user_uuid]

    def delete_user(self, user_uuid):
        for followee in self.following(user_uuid):
            self.unfollow(user_uuid, followee)
        for follower in self.followers(user_uuid):
            self.unfollow(follower, user_uuid)
        del self.nodes[user_uuid]

    def follow(self, follower, followee):
        if follower is followee:
            raise UserFollowingSelf
        elif self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            self.edges[follower].add(followee)

    def unfollow(self, follower, followee):
        if self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            self.edges[follower] = self.edges[follower] - {followee}

    def is_following(self, follower, followee):
        if self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            return followee in self.edges[follower]

    def followers(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return {x for x in self.edges if user_uuid in self.edges[x]}

    def following(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return self.edges[user_uuid]

    def friends(self, user_uuid):
        return {x for x in self.following(user_uuid) &
                self.followers(user_uuid)}

    def traverse_graph(self, from_user_uuid, counter=-1,
                       to_user_uuid=None, n=None):
        if to_user_uuid is not None:
            self.uuid_in_graph(to_user_uuid)
        visited = set()
        not_visited = {from_user_uuid}
        while not_visited != set():
            nth_layer_visited = set()
            for x in not_visited:
                xs_neighbours = self.following(x) - visited
                nth_layer_visited = nth_layer_visited | xs_neighbours
                visited.add(x)
            nth_layer_visited = nth_layer_visited - visited
            counter = counter + 1
            if counter == n:  # nth_layer_followings
                return nth_layer_visited
            if to_user_uuid in visited:  # min_distance
                return counter
            not_visited = nth_layer_visited - not_visited
        if to_user_uuid is not None:  # we're in min_distance
            raise UsersNotConnectedError
        if counter is 0:  # we're in max_distance
            return math.inf
        if n is not None:  # we're in nth_layer_followings
            return set()
        return counter  # returned only in max_distance

    def max_distance(self, user_uuid):
        return self.traverse_graph(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return (self.traverse_graph(from_user_uuid,
                                    to_user_uuid=to_user_uuid))

    def nth_layer_followings(self, user_uuid, n):
        return self.traverse_graph(user_uuid, counter=0, n=n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
            return (sorted(reduce((lambda x, y: x + y),
                                  [list(self.get_user(x).get_post())
                                   for x in self.following(user_uuid)],
                                  []),
                           key=lambda post: post.published_at)
                    [-offset - 1: -offset - limit - 1: -1])


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User does not exist!"


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


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "Users aren't connected! :("


class UserFollowingSelf(Exception):
    def __init__(self):
        self.message = "User is trying to follow himself!"

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.099s

OK

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

Мартин обнови решението на 10.04.2016 18: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
from uuid import uuid4
from queue import Queue
from functools import reduce
from datetime import datetime


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

    def __str__(self):
        return ('User:    ' + str(self.author) +
                '\n' + 'Date:    ' + str(self.published_at) +
                '\n' + 'Content: ' + self.content + '\n')


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

    def add_post(self, post_content):
        self.manage_posts()
        newPost = Post(self.uuid, post_content)
        self.posts.put(newPost)
        self.iterable_posts.append(newPost)

    def get_post(self):
        return (x for x in self.iterable_posts)

    def manage_posts(self):
        if self.posts.full():
            self.posts.get()
            del self.iterable_posts[0]


class SocialGraph:
    def __init__(self):
        self.edges = []  # ръбове -[(follower,followee)...]
        self.nodes = []  # върхове

    def uuid_in_graph(self, user_uuid):
        if user_uuid in [x.uuid for x in self.nodes]:
            return True
        else:
            raise UserDoesNotExistError
            return False

    def add_user(self, user):
        if user in self.nodes:
            raise UserAlreadyExistsError
        else:
            self.nodes.append(user)

    def get_user(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return [x for x in self.nodes if x.uuid == user_uuid][0]

    def delete_user(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            for followee in self.following(user_uuid):
                unfollow(user_uuid, followee)
            for follower in self.followers(user_uuid):
                unfollow(follower, user_uuid)
            self.nodes.remove(self.get_user(user_uuid))

    def follow(self, follower, followee):
        self.edges.append((self.get_user(follower), self.get_user(followee)))

    def unfollow(self, follower, followee):
        self.edges.remove((self.get_user(follower), self.get_user(followee)))

    def is_following(self, follower, followee):
        return ((self.get_user(follower),
                self.get_user(followee)) in self.edges)

    def followers(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return {x[0].uuid for x in self.edges if x[1].uuid == user_uuid}

    def following(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return {x[1].uuid for x in self.edges if x[0].uuid == user_uuid}

    def friends(self, user_uuid):
        return {x for x in self.following(user_uuid) &
                self.followers(user_uuid)}

    def traverse_graph(self, from_user_uuid, counter=-1,
                       to_user_uuid=None, n=None):
        if to_user_uuid is not None:
            self.uuid_in_graph(to_user_uuid)
        visited = set()
        not_visited = {from_user_uuid}
        while not_visited != set():
            temp = set()
            for x in not_visited:
                temp1 = {y for y in self.following(x) if y not in visited}
                temp = temp | temp1
                visited.add(x)
            temp = {x for x in temp if x not in visited}
            counter = counter + 1
            if counter == n:
                return temp
            if to_user_uuid in visited:
                return counter
            not_visited = temp - not_visited
        if to_user_uuid is not None:
            raise UsersNotConnectedError
        return counter

    def max_distance(self, user_uuid):
        return self.traverse_graph(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return (self.traverse_graph(from_user_uuid,
                                    to_user_uuid=to_user_uuid))

    def nth_layer_followings(self, user_uuid, n):
        return self.traverse_graph(user_uuid, counter=0, n=n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
            return (sorted(reduce((lambda x, y: x + y),
                                  [list(self.get_user(x).get_post())
                                   for x in self.following(user_uuid)],
                                  []),
                           key=lambda post: post.published_at)
                    [-offset - 1: -offset - limit - 1: -1])


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User does not exist!"


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


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "Users aren't connected! :("
  • Имаш camelCase променливи
  • Не мисля, че queue.Queue е подходящата колекция за целите на публикации. Искаме да можем да обхождаме по няколко пъти публикациите. Разгледай типовете дефинирани в collections
  • edges и nodes са ти списъци, в които често ти се налага да търсиш елементи, което води до линейна сложност на търсенето. Докарай го до константна :)
  • temp и temp1 са лоши имена

Мартин обнови решението на 18.04.2016 11:17 (преди над 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
from uuid import uuid4
from functools import reduce
from datetime import datetime
from time import sleep
import math


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

    def __str__(self):
        return ('User:    ' + str(self.author) +
                '\n' + 'Date:    ' + str(self.published_at) +
                '\n' + 'Content: ' + self.content + '\n')


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

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

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

    def manage_posts(self):
        if len(self.posts) >= 50:
            del self.posts[0]


class SocialGraph:
    def __init__(self):
        self.nodes = {}  # върхове {user_uuid: user, ...}
        self.edges = {}  # ръбове -{follower_uuid: {followee1_uuid, ...}...}

    def uuid_in_graph(self, user_uuid):
        if self.nodes.get(user_uuid) is not None:
            return True
        else:
            raise UserDoesNotExistError
            return False

    def add_user(self, user):
        if self.nodes.get(user.uuid) is not None:
            raise UserAlreadyExistsError
        else:
            self.nodes[user.uuid] = user
            self.edges[user.uuid] = set()

    def get_user(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return self.nodes[user_uuid]

    def delete_user(self, user_uuid):
        for followee in self.following(user_uuid):
            self.unfollow(user_uuid, followee)
        for follower in self.followers(user_uuid):
            self.unfollow(follower, user_uuid)
        del self.nodes[user_uuid]

    def follow(self, follower, followee):
        if follower is followee:
            raise UserFollowingSelf
        elif self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            self.edges[follower].add(followee)

    def unfollow(self, follower, followee):
        if self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            self.edges[follower] = self.edges[follower] - {followee}

    def is_following(self, follower, followee):
        if self.uuid_in_graph(follower) and self.uuid_in_graph(followee):
            return followee in self.edges[follower]

    def followers(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return {x for x in self.edges if user_uuid in self.edges[x]}

    def following(self, user_uuid):
        if self.uuid_in_graph(user_uuid):
            return self.edges[user_uuid]

    def friends(self, user_uuid):
        return {x for x in self.following(user_uuid) &
                self.followers(user_uuid)}

    def traverse_graph(self, from_user_uuid, counter=-1,
                       to_user_uuid=None, n=None):
        if to_user_uuid is not None:
            self.uuid_in_graph(to_user_uuid)
        visited = set()
        not_visited = {from_user_uuid}
        while not_visited != set():
            nth_layer_visited = set()
            for x in not_visited:
                xs_neighbours = self.following(x) - visited
                nth_layer_visited = nth_layer_visited | xs_neighbours
                visited.add(x)
            nth_layer_visited = nth_layer_visited - visited
            counter = counter + 1
            if counter == n:  # nth_layer_followings
                return nth_layer_visited
            if to_user_uuid in visited:  # min_distance
                return counter
            not_visited = nth_layer_visited - not_visited
        if to_user_uuid is not None:  # we're in min_distance
            raise UsersNotConnectedError
        if counter is 0:  # we're in max_distance
            return math.inf
        if n is not None:  # we're in nth_layer_followings
            return set()
        return counter  # returned only in max_distance

    def max_distance(self, user_uuid):
        return self.traverse_graph(user_uuid)

    def min_distance(self, from_user_uuid, to_user_uuid):
        return (self.traverse_graph(from_user_uuid,
                                    to_user_uuid=to_user_uuid))

    def nth_layer_followings(self, user_uuid, n):
        return self.traverse_graph(user_uuid, counter=0, n=n)

    def generate_feed(self, user_uuid, offset=0, limit=10):
            return (sorted(reduce((lambda x, y: x + y),
                                  [list(self.get_user(x).get_post())
                                   for x in self.following(user_uuid)],
                                  []),
                           key=lambda post: post.published_at)
                    [-offset - 1: -offset - limit - 1: -1])


class UserDoesNotExistError(Exception):
    def __init__(self):
        self.message = "User does not exist!"


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


class UsersNotConnectedError(Exception):
    def __init__(self):
        self.message = "Users aren't connected! :("


class UserFollowingSelf(Exception):
    def __init__(self):
        self.message = "User is trying to follow himself!"