@OzrenTkalcec/

Dividing of K people into N groups

Python

No description

fork
loading
Files
  • main.py

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.33167406908854935","path":"main.py","file":{"path":"main.py","content":{"asEncoding":{"base64":"I0V4YW1wbGVzOgojcGVyc29ucyA9IFtbMSwzXSwgWzAsM10sIFswLDFdLCBbMSwyXV0KI3BlcnNvbnMgPSBbWzEsMiwzXSwgWzAsMiwzXSwgWzAsMSwzXSwgWzAsMSwyXV0KI3BlcnNvbnMgPSBbWzEsMl0sIFswLDJdLCBbMCwzXSwgWzAsMl1dCgpwZXJzb25zID0gW1sxLDJdLCBbMCwyXSwgWzAsM10sIFswLDJdXQpwcmludCgiUGVyc29ucyBhcnJheSIsIHBlcnNvbnMpCgpwZXJzb25zX3Blcl9ncm91cCA9IDIKcHJpbnQoIlBlcnNvbnMgcGVyIGdyb3VwIiwgcGVyc29uc19wZXJfZ3JvdXApCgptaW5fd2lzaGVzX3Blcl9wZXJzb24gPSAyCnByaW50KCJNaW4gd2lzaGVzIHBlciBwZXJzb24iLCBtaW5fd2lzaGVzX3Blcl9wZXJzb24pCgpncm91cF9jb3VudCA9IGxlbihwZXJzb25zKSAvLyBwZXJzb25zX3Blcl9ncm91cApwcmludCgiVHJ5aW5nIHRvIGdyb3VwIHBlcnNvbnMgaW4iLCBncm91cF9jb3VudCwgImdyb3Vwcy4uLiIpIAoKZGVmIGdyb3VwX2lubmVyKHBlcnNvbnNfaW5kZXgsIGdyb3VwcywgZGVwdGgpOgogICAgcHJpbnQocGVyc29uc19pbmRleCwgZ3JvdXBzKQogICAgIyBFbnRlcmluZyBvbmUgZGVjaXNpb24gdHJlZSBsZXZlbCBvZiBkZXB0aAogICAgZm9yIGkgaW4gcGVyc29uc19pbmRleDoKICAgICAgICAjcHJpbnQoInRoaXNfcGVyc29uIGlzIiwgaSkgICAgIAogICAgICAgIGZvciBqIGluIHJhbmdlKGxlbihwZXJzb25zW2ldKSk6CiAgICAgICAgICAgICNwcmludCgid2lzaGVkIHBlcnNvbiBpcyIsIHBlcnNvbnNbaV1bal0pCiAgICAgICAgICAgIG5ld19wZXJzb25zX2luZGV4ID0gW3AgZm9yIHAgaW4gcGVyc29uc19pbmRleCBpZiAocCBpcyBub3QgaSkgYW5kIChwIGlzIG5vdCBwZXJzb25zW2ldW2pdKV0KICAgICAgICAgICAgbmV3X2dyb3VwcyA9IE5vbmUKICAgICAgICAgICAgd2lzaF9ncm91cGVkX2ludG8gPSBbZ3JvdXAgZm9yIGdyb3VwIGluIGdyb3VwcyBpZiBwZXJzb25zW2ldW2pdIGluIGdyb3VwXSBvciBOb25lCiAgICAgICAgICAgIGlmIHdpc2hfZ3JvdXBlZF9pbnRvIGlzIG5vdCBOb25lOgogICAgICAgICAgICAgICAgaWYgKGxlbih3aXNoX2dyb3VwZWRfaW50b1swXSkgKyAxKSA8PSBwZXJzb25zX3Blcl9ncm91cDoKICAgICAgICAgICAgICAgICAgICAjcHJpbnQoImFkZGluZyBpbnRvIGdyb3VwIiwgd2lzaF9ncm91cGVkX2ludG9bMF0pCiAgICAgICAgICAgICAgICAgICAgbmV3X2dyb3VwcyA9IFtncm91cCBmb3IgZ3JvdXAgaW4gZ3JvdXBzIGlmIGdyb3VwICE9IHdpc2hfZ3JvdXBlZF9pbnRvWzBdXSArICh3aXNoX2dyb3VwZWRfaW50b1swXSArIFtpXSkKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgI3ByaW50KCJjb3VsZCBub3QgYWRkIGFueSBtb3JlIHBlcnNvbnMgaW50byBncm91cCIsIHdpc2hfZ3JvdXBlZF9pbnRvWzBdKQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBpZiAobGVuKGdyb3VwcykgKyAxKSA8PSBncm91cF9jb3VudDoKICAgICAgICAgICAgICAgICAgICAjcHJpbnQoImFkZGluZyBncm91cCIpCiAgICAgICAgICAgICAgICAgICAgbmV3X2dyb3VwcyA9IGdyb3VwcyArIFtbaSwgcGVyc29uc1tpXVtqXV1dCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgICNwcmludCgiY291bGQgbm90IGFkZCBhbnkgbmV3IGdyb3VwcyIpCiAgICAgICAgICAgICAgICAgICAgY29udGludWUKCiAgICAgICAgICAgICNwcmludCgibmV3X2dyb3VwcyIsIG5ld19ncm91cHMpCiAgICAgICAgICAgICNwcmludCgibmV3X3BlcnNvbnNfaW5kZXgiLCBuZXdfcGVyc29uc19pbmRleCkKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmIGxlbihuZXdfcGVyc29uc19pbmRleCkgPiAwOgogICAgICAgICAgICAgICAgc29sdXRpb25fZ3JvdXBzID0gZ3JvdXBfaW5uZXIobmV3X3BlcnNvbnNfaW5kZXgsIG5ld19ncm91cHMsIGRlcHRoICsgMSkKICAgICAgICAgICAgICAgIGlmIHNvbHV0aW9uX2dyb3VwczoKICAgICAgICAgICAgICAgICAgICByZXR1cm4gc29sdXRpb25fZ3JvdXBzCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB3aXNoZXNfZ3JhbnRlZCA9IFswXSAqIGxlbihwZXJzb25zKQogICAgICAgICAgICAgICAgZm9yIGsgaW4gcmFuZ2UobGVuKHBlcnNvbnMpKToKICAgICAgICAgICAgICAgICAgICAjcHJpbnQoImNoZWNraW5nIHBlcnNvbiIsIGspCiAgICAgICAgICAgICAgICAgICAgcGVyc29uX2dyb3VwID0gW2dyb3VwIGZvciBncm91cCBpbiBncm91cHMgaWYgayBpbiBncm91cF0KICAgICAgICAgICAgICAgICAgICAjcHJpbnQoInBlcnNvbl9ncm91cCIsIHBlcnNvbl9ncm91cCkKCiAgICAgICAgICAgICAgICAgICAgd2lzaGVzX2dyYW50ZWRba10gPSAwCiAgICAgICAgICAgICAgICAgICAgZm9yIHcgaW4gcGVyc29uc1trXToKICAgICAgICAgICAgICAgICAgICAgICAgI3ByaW50KCJjaGVja2luZyB3aXNoIiwgdykKICAgICAgICAgICAgICAgICAgICAgICAgd2lzaF9ncm91cCA9IFtncm91cCBmb3IgZ3JvdXAgaW4gZ3JvdXBzIGlmIHcgaW4gZ3JvdXBdCiAgICAgICAgICAgICAgICAgICAgICAgICNwcmludCgid2lzaF9ncm91cCIsIHdpc2hfZ3JvdXApCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIHBlcnNvbl9ncm91cCA9PSB3aXNoX2dyb3VwOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgd2lzaGVzX2dyYW50ZWRba10gPSB3aXNoZXNfZ3JhbnRlZFtrXSArIDEKCiAgICAgICAgICAgICAgICAjcHJpbnQoIndpc2hlc19ncmFudGVkIiwgd2lzaGVzX2dyYW50ZWQpCiAgICAgICAgICAgICAgICBpZiBhbGwod2cgPj0gbWluX3dpc2hlc19wZXJfcGVyc29uIGZvciB3ZyBpbiB3aXNoZXNfZ3JhbnRlZCk6CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ld19ncm91cHMKICAgICAgICAgICAgICAgICNlbHNlOgogICAgICAgICAgICAgICAgIyAgICBwcmludCgiY2FuJ3QgZ3JhbnQgZW5vdWdoIHdpc2hlcyB0byBldmVyeW9uZSIpCiAgICAKICAgIHJldHVybiBOb25lCgpkZWYgZ3JvdXAoKToKICAgIHBlcnNvbnNfaW5kZXggPSBbaSBmb3IgaSBpbiByYW5nZShsZW4ocGVyc29ucykpXQogICAgI3ByaW50KCJwZXJzb25zX2luZGV4IGlzIiwgcGVyc29uc19pbmRleCkKICAgIGdyb3VwcyA9IFtdCiAgICByZXR1cm4gZ3JvdXBfaW5uZXIocGVyc29uc19pbmRleCwgZ3JvdXBzLCAwKQoKZ3JvdXBzID0gZ3JvdXAoKQppZiBncm91cHMgaXMgTm9uZToKICAgIHByaW50KCJObyBzb2x1dGlvbiBmb3VuZCIpCmVsc2U6CiAgICBwcmludCgiU29sdXRpb24gZm91bmQiKQogICAgcHJpbnQoIkdyb3VwczoiLCBncm91cHMp"},"asBuffer":null},"loaded":true}}
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
#Examples:
#persons = [[1,3], [0,3], [0,1], [1,2]]
#persons = [[1,2,3], [0,2,3], [0,1,3], [0,1,2]]
#persons = [[1,2], [0,2], [0,3], [0,2]]

persons = [[1,2], [0,2], [0,3], [0,2]]
print("Persons array", persons)

persons_per_group = 2
print("Persons per group", persons_per_group)

min_wishes_per_person = 2
print("Min wishes per person", min_wishes_per_person)

group_count = len(persons) // persons_per_group
print("Trying to group persons in", group_count, "groups...") 

def group_inner(persons_index, groups, depth):
    print(persons_index, groups)
    # Entering one decision tree level of depth
    for i in persons_index:
        #print("this_person is", i)     
        for j in range(len(persons[i])):
            #print("wished person is", persons[i][j])
            new_persons_index = [p for p in persons_index if (p is not i) and (p is not persons[i][j])]
            new_groups = None
            wish_grouped_into = [group for group in groups if persons[i][j] in group] or None
            if wish_grouped_into is not None:
                if (len(wish_grouped_into[0]) + 1) <= persons_per_group:
                    #print("adding into group", wish_grouped_into[0])
                    new_groups = [group for group in groups if group != wish_grouped_into[0]] + (wish_grouped_into[0] + [i])
                else:
                    #print("could not add any more persons into group", wish_grouped_into[0])
                    continue
            else:
                if (len(groups) + 1) <= group_count:
                    #print("adding group")
                    new_groups = groups + [[i, persons[i][j]]]
                else:
                    #print("could not add any new groups")
                    continue

            #print("new_groups", new_groups)
            #print("new_persons_index", new_persons_index)
            
            if len(new_persons_index) > 0:
                solution_groups = group_inner(new_persons_index, new_groups, depth + 1)
                if solution_groups:
                    return solution_groups
            else:
                wishes_granted = [0] * len(persons)
                for k in range(len(persons)):
                    #print("checking person", k)
                    person_group = [group for group in groups if k in group]
                    #print("person_group", person_group)

                    wishes_granted[k] = 0
                    for w in persons[k]:
                        #print("checking wish", w)
                        wish_group = [group for group in groups if w in group]
                        #print("wish_group", wish_group)
                        if person_group == wish_group:
                            wishes_granted[k] = wishes_granted[k] + 1

                #print("wishes_granted", wishes_granted)
                if all(wg >= min_wishes_per_person for wg in wishes_granted):
                    return new_groups
                #else:
                #    print("can't grant enough wishes to everyone")
    
    return None

def group():
    persons_index = [i for i in range(len(persons))]
    #print("persons_index is", persons_index)
    groups = []
    return group_inner(persons_index, groups, 0)

groups = group()
if groups is None:
    print("No solution found")
else:
    print("Solution found")
    print("Groups:", groups)