google_hash_code_2019/vertical_merger.py at master · dezounet/google_hash_code_2019 · GitHub

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
import random
from copy import copy

from slide import Slide

FACTOR = 10000000


def merge_id(id_1, id_2):
    return id_1 + id_2 * FACTOR


def unmerge_id(merged_id):
    id_1 = merged_id % FACTOR
    id_2 = (merged_id - id_1) / FACTOR

    return int(id_1), int(id_2)


def merge(vertical_pics):
    slides = {}

    # Do not update input struct
    vertical_pics_copy = copy(vertical_pics)

    unmatched_pics = {}

    # for every pic, found a non overlapping pic
    print('find perfect vertical matching (%s)...' % len(vertical_pics_copy))
    keep_going = True
    while keep_going:
        if len(vertical_pics_copy) < 2:
            keep_going = False
        else:
            first_pic = vertical_pics_copy.pop(random.choice(list(vertical_pics_copy.keys())))
            second_pic = None

            for i, pic in vertical_pics_copy.items():
                if not set(first_pic.tags) & set(pic.tags):
                    second_pic = pic
                    break

            if second_pic is not None:
                del vertical_pics_copy[second_pic.id]
                slides[merge_id(first_pic.id, second_pic.id)] = Slide(first_pic, second_pic)
            else:
                unmatched_pics[first_pic.id] = first_pic

    # for the remaining pics, match it with the less overlapping
    print('find remaining vertical matching (%s)...' % len(unmatched_pics))
    keep_going = True
    while keep_going:
        if len(unmatched_pics) < 2:
            keep_going = False
        else:
            first_pic = unmatched_pics.pop(random.choice(list(unmatched_pics.keys())))
            second_pic = None

            tag_count = 0
            for i, pic in unmatched_pics.items():
                current_tag_count = len(set(first_pic.tags) | set(pic.tags))
                if current_tag_count > tag_count:
                    second_pic = pic
                    tag_count = current_tag_count

            del unmatched_pics[second_pic.id]

            slides[merge_id(first_pic.id, second_pic.id)] = Slide(first_pic, second_pic)

    return slides


if __name__ == '__main__':
    merged_id = merge_id(1, 80000)
    print(unmerge_id(merged_id))