<jupyter_start><jupyter_text>Problem:  You and some friends are deciding teams for a game. Some people don't like each other, and don't want to be on the same team. There are also people who need to be on the same team because they are such good friends. There are also people who don't mind if someone is on their team or not.  Edge types:  * Friend: Must be on the same team* Enemy: Must be on different teams* Neutral: Doesn't matter if on same or different team<jupyter_code>from my_libraries.graph_theory.MyGraph import *
import random,math
def randind(arr):
    return math.floor(random.random()*len(arr))
def getRelNeighbors(G,node,rel):
    ans = set([])
    for n in G.get_neighbors(node):
        if G[node]['to'][n]['rel'] is rel:
            ans.add(n)
    return ans<jupyter_output><empty_output><jupyter_text>prepare graph<jupyter_code>players = [
    'mike',
    'bobby',
    'eubihn',
    'feit',
    'austin',
    'kibby',
    'jonah',
    'sean'
]
numTeams = 2
G = Graph()
G.add_node(*players)
G
G.set_edge('mike','feit',{'rel':'enemy'})
G.set_edge('mike','bobby',{'rel':'friend'})
G.set_edge('austin','jonah',{'rel':'friend'})
G.set_edge('eubihn','jonah',{'rel':'enemy'})
G.set_edge('feit','kibby',{'rel':'enemy'})
G
for a in G.get_nodes():
    for b in G.get_nodes():
        if b not in G.get_neighbors(a) and a is not b:
            G.set_edge(a,b,{'rel':'neutral'})
G['mike']<jupyter_output><empty_output><jupyter_text>random guess and check methodproblems:* indefinite performance time* if a correct arrangement does not exist, the program will infinitely loop<jupyter_code>def guess():
    teams = []
    players = list(G.get_nodes())
    while len(players) > 0:
        team = []
        while len(team)< math.floor(len(G.get_nodes())/numTeams) and len(players)>0:
            team.append(players.pop(randind(players)))
        teams.append(team)
    return teams
guess()
def check(guess):
    #check enemies
    for team in guess:
        for a in team:
            for b in team:
                if a is b:
                    continue
                else:
                    if G[a]['to'][b]['rel'] is 'enemy':
                        return False
    #check friends
    for team in guess:
        for a in team:
            friends = getRelNeighbors(G,a,'friend')
            if not friends <= set(team):
                return False
    return True
g = guess()
while not check(g):
    g = guess()
g<jupyter_output><empty_output><jupyter_text>lexicographic guess and check method<jupyter_code>from my_libraries.lexicographicOrder import *
def guess(perm):
    teams = []
    players = perm[:]
    while len(players) > 0:
        team = []
        while len(team)< math.floor(len(G.get_nodes())/numTeams) and len(players)>0:
            team.append(players.pop(0))
        teams.append(team)
    return teams
guess(list(G.get_nodes())),list(G.get_nodes())
# uses the same check function as random guess and check method
players = list(G.get_nodes())
for perm in allPerms(players):
    perm = list(perm)
#     print(guess(perm))
    if check(guess(perm)):
        print(perm,guess(perm))
        break<jupyter_output>['kibby', 'bobby', 'mike', 'eubihn', 'jonah', 'feit', 'austin', 'sean'] [['kibby', 'bobby', 'mike', 'eubihn'], ['jonah', 'feit', 'austin', 'sean']]<jupyter_text>direct method<jupyter_code>def dft(G,a,rel):
    visited = set([a])
    def f(a):
        visited.add(a)
        for b in getRelNeighbors(G,a,rel):
            if b not in visited:
                f(b)
    f(a)
    return visited
dft(G,'eubihn','enemy')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1442495126705653, 'fraction_numerical': 0.001670843776106934, 'mean_word_length': 3.1382488479262673, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '624236', 'license': 'MIT', 'n_tokens_mistral': 1283, 'n_tokens_neox': 1248, 'n_words': 325, 'path': 'python/friend and enemy teams.ipynb', 'repo_name': 'quasarbright/quasarbright.github.io', 'size': '3591'}