Nikolaj-K · October 28, 2023 10:40 · dclancy13 · Sep 21, 2023 · SquigglyWorm · Sep 29, 2023
diff --git a/make_voting_assignment.py b/make_voting_assignment.py
 """
 Scirpt discussed in video here:

 https://youtu.be/2b9fOpX0zKY?si=hjztP-RAwIgq_Yed

 HV-MTL Voting assignment based on users with different voting capactities per day.

 More formally: Generation of a balanced simple digraph* (and corresponding plot)
               based on a vertex set and their number of outgoing edges,
               with a high number of opposing edges (reciprocated votes percentage is a config).
 *i.e. such that there's no self-edges (no self-votes) and without parallel arrows in one direction (no double-vote),
 and such that the in- and out-degree is equal, for each vertex.

 If you're interested expanding the algo, I have some open questions about the problem here:
 https://math.stackexchange.com/questions/4729172/deranged-generous-gift-giving-in-the-limit

 Author: Nikolaj-K
 Discord: Nikolaj-K (nikolajk)

 TODO for you if you want to hop on:
    1. Copy the last USERS_ list at the bottom of the comment section
    2. Add your field (name, id, capacities of votes per day) and post it as a comment far below.
 You can use 3 dashes (the  ` symbol) to get code style on github (also on Discord).
 The new entry in the USERS's list should look like so:
 User("Nikolaj-K", 11015, 6),
 """

 import datetime
 import random
 import numpy as np
 import networkx as nx
 import matplotlib.pyplot as plt

 print("IMPORTS DONE.")


 class Config:
    RECIPROCATED_VOTES_RATIO: float = 10 / 100


 class User:
    def __init__(self, name: str, id: int, voting_capacity: int):
        self.name = name
        self.id = id
        self.voting_capacity = voting_capacity

    def __has_same_name(self, other_user) -> bool:
        return other_user.name == self.name

    def equals(self, other_user) -> bool:
        if self.__has_same_name(other_user):
            assert (
                other_user.id == self.id
                and other_user.voting_capacity == self.voting_capacity
            ), f"Inconsistency in the list for {self.name}"
        return self.__has_same_name(other_user)


 USERS = [
    # Your Discord name, your id, your commited voting capacity (for the next day/round)
    # The most up to date version of this list is at the bottom of the github comment section, edit there!
    # Copy and edit the list.
    User("Anti-Hiro", 3664, 12),
    User("Orephelious", 1757, 12),
    User("Ulysseus", 23419, 11),
    User("Ulysseus (hv#2)", 19934, 11),
    User("Ulysseus (hv#3)", 20639, 11),
    User("TommyLeigh", 5851, 10),
    User("Vesa", 12745, 10),
    User("Panigalist", 12015, 9),
    User("MrTax", 1364, 9),
    User("Nikolaj-K", 11015, 9),
    User("THE_SquigglyWorm", 6448, 6),
    User("PeterKiu.sol", 12433, 8),
    User("PeterKiu.sol (hv#2)", 11687, 8),
    User("PeterKiu.sol (hv#3)", 4197, 8),
    User("HubbaBubba", 1927, 8),
    User("HubbaBubba (hv#2)", 13653, 8),
    User("Clemfandango", 10463, 8),
    User("BLKstut", 14419, 8),
    User("TommyLeigh (hv#2)", 4695, 2),
    User("dave_eco", 12402, 8),
    # Removed:
    User("Medhi0", 2879, 0),
    User("Medhi0 (hv#2)", 1052, 0),
    User("DylanDaVillain", 18437, 0),
    User("Fripon", 4025, 0),
    User("Billybagz", 10384, 0),
    User("Snuggster", 6307, 0),
    User("NateMercs", 1235, 0),
    User("Lucast88 Knight", 5013, 0),
 ]
 DONT_MATCH_WITH = {  # Avoid voting for your own other HV
    "Ulysseus": ["Ulysseus (hv#2)", "Ulysseus (hv#3)",],
    "Ulysseus (hv#2)": ["Ulysseus (hv#3)",],
    "HubbaBubba (hv#2)": ["Ulysseus", "Ulysseus (hv#2)", "Ulysseus (hv#3)",],
    "HubbaBubba": [
        "HubbaBubba (hv#2)",
        "Ulysseus",
        "Ulysseus (hv#2)",
        "Ulysseus (hv#3)",
    ],
    "PeterKiu.sol": ["PeterKiu.sol (hv#2)", "PeterKiu.sol (hv#3)",],
    "PeterKiu.sol (hv#2)": ["PeterKiu.sol (hv#3)",],
    "TommyLeigh": ["TommyLeigh (hv#2)",],
    "THE_SquigglyWorm": ["Orephelious",],
    # Removed:
    # "Medhi0": ["Medhi0 (hv#2)",],
 }

 # Auxiliary cleanup
 USERS_ = [
    u for u in USERS if u.voting_capacity
 ]  # Remove entries with voting_capacity set to zero
 USERS_.sort(key=lambda user: user.voting_capacity)
 USERS_ = USERS_[::-1]

 # Sanity check
 for k, ns in DONT_MATCH_WITH.items():
    names = [u.name for u in USERS_]
    assert k in names, k
    assert all([n in names for n in ns]), ns


 def make_random_pairings(adjacency_in: dict) -> list:
    adjacency = {k: v for k, v in adjacency_in.items()}  # Copy

    sources = []  # Ordered multiset of vertices, interleaved
    while sum(list(adjacency.values())):
        for v_src, capacity in adjacency.items():
            if capacity > 0:
                sources.append(v_src)
                adjacency[v_src] += -1

    assert len(sources) == sum(list(adjacency_in.values()))

    targets = []
    i = 0
    while len(targets) < len(sources):
        i += 1
        excluded = {v: [v] for v in adjacency.keys()}  # No self-vote
        leftovers = list(sources)
        targets = []
        for s in sources:
            include = lambda t: not (
                t in excluded[s]
                or t.name in DONT_MATCH_WITH.get(s.name, [])
                or s.name in DONT_MATCH_WITH.get(t.name, [])
            )
            candidates = list(filter(include, leftovers))
            if not candidates:
                break
            t = random.choice(candidates)
            leftovers.remove(t)
            targets.append(t)
            excluded[s].append(t)  # no double vote
        if (i % 100) == 0:
            print(f"attempt {i}, matched ", len(targets), " of ", len(sources))

    assert (
        len(targets) == len(sources)
        and len(leftovers) == 0
        and all([len(excluded[s]) == s.voting_capacity + 1 for s in sources])
    )

    pairings = list(zip(sources, targets))

    assert not any([l.equals(r) for l, r in pairings])

    return pairings


 def to_adjancency(pairings: list) -> dict:
    adj = {src: [] for src, _target in pairings}
    for src, target in pairings:
        adj[src].append(target)
    return adj


 def num_reciprocal_votes(pairings: list) -> int:
    return sum(pair[::-1] in pairings for pair in pairings)


 def log_adjacency(adjacency) -> None:
    print("" " ".join([f"@{u.name}" for u in USERS_]))
    print()
    print(f"Today's lineup ({datetime.date.today()})")
    print()
    for u_src, u_targets in adjacency.items():
        u_src_voting_capacity: int = len(u_targets)
        assert u_src_voting_capacity == u_src.voting_capacity and all(
            [u.name != u_src.name for u in u_targets]
        )
        print(
            f"{u_src.name} ({u_src.id}, with capacity set to {u_src.voting_capacity}), please energy-vote for:"
        )
        for idx, u in enumerate(u_targets):
            # is_not_reciprocal: str = "*" if u_src not in adjacency[u] else ""
            id = str(u.id) + (5 - len(str(u.id))) * " "
            print(f"  {idx + 1}. {id} a.k.a. {u.name}, ", end="\n")
    print()
    # Short version
    num_votes_all = sum([len(u_t) for u_t in adjacency.values()])
    for u_src, u_targets in adjacency.items():
        id = str(u_src.id) + (6 - len(str(u_src.id))) * " "
        s_ = f"{len(u_targets)}/{num_votes_all} #{id} {u_src.name}"
        s = s_ + (33 - len(s_)) * " "
        print(
            s
            + f" => "
            + ", ".join(
                [
                    str(u.id)
                    + ("*" if (False and u_src not in adjacency[u]) else "")
                    + (
                        5
                        - len(
                            str(u.id)
                            + (
                                "*"
                                if (False and u_src not in u_src not in adjacency[u])
                                else ""
                            )
                        )
                    )
                    * " "
                    for u in sorted(u_targets, key=lambda u: u.id)
                ]
            )
        )
    print()
    print(
        "You got 24 hours to cast your votes. Best ping the the people once you voted for them."
    )
    print("For the follow-up day, anybody can append themselves at the very bottom of")
    print(
        "<https://gist.github.com/Nikolaj-K/cdea02d39de125c6dab28fa13e559583?permalink_comment_id=4616662#gistcomment-4616662>"
    )


 def draw_graph(pairings) -> None:
    make_label = lambda user: f"{user.name}\n{user.id}"
    edgelist_ = [(make_label(u1), make_label(u2)) for u1, u2 in pairings]
    edgelist = []

    print()
    not_rec = []
    for e in edgelist_:
        if e[::-1] not in edgelist_:
            not_rec.append(e)
            # print(f"* " + " ".join("    ->    ".join(list(e)).split("\n")) + "    is not reciprocal"     )
    for e in edgelist_:
        rev_e = e[::-1]
        if e not in not_rec and rev_e not in (edgelist + not_rec):
            edgelist.append(e)

    G = nx.DiGraph(directed=True)
    G.add_edges_from(edgelist_)
    pos = nx.shell_layout(G)
    nx.draw_networkx_edges(
        G,
        pos,
        edgelist=edgelist,
        edge_color="g",
        arrows=False,
        arrowsize=5,
        connectionstyle="arc3,rad=0.0",
    )
    nx.draw_networkx_edges(
        G,
        pos,
        edgelist=not_rec,
        edge_color="black",
        arrows=True,
        arrowsize=15,
        connectionstyle="arc3,rad=0.0",
    )
    nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap("jet"), node_size=0)
    nx.draw_networkx_labels(G, pos, font_size=10)
    plt.axis("off")
    plt.show()


 def run_main():
    print("RUN MAIN.")
    adjacency_ = {u: u.voting_capacity for u in USERS_}

    rel_rv = 0
    sim = 0
    print("make_random_pairings ...")
    pairings = make_random_pairings(adjacency_)

    print("Run while-loop ...")
    while num_reciprocal_votes(pairings) < Config.RECIPROCATED_VOTES_RATIO * len(
        pairings
    ):
        print(f"#{sim}")
        pairings = make_random_pairings(adjacency_)  # re-sample

        if sim % 5 == 0:
            print(f"#{sim}")
        sim += 1
        num_rv: int = num_reciprocal_votes(pairings)
        num_pairings: int = len(pairings)
        rel_rv_ = round(100 * num_rv / len(pairings), 2)
        if rel_rv_ > rel_rv:
            rel_rv = rel_rv_
            print(
                f"#{sim} num_pairings = {num_pairings}, num_reciprocal_votes = {num_rv} ({rel_rv} %)"
            )

    adjacency = to_adjancency(pairings)
    has_duplicates = lambda xs: len(set(xs)) < len(xs)
    assert not any([has_duplicates(ts) for ts in adjacency.values()])

    log_adjacency(adjacency)
    draw_graph(pairings)


 if __name__ == "__main__":
    run_main()
	"""
	Scirpt discussed in video here:

	https://youtu.be/2b9fOpX0zKY?si=hjztP-RAwIgq_Yed

	HV-MTL Voting assignment based on users with different voting capactities per day.

	More formally: Generation of a balanced simple digraph* (and corresponding plot)
	based on a vertex set and their number of outgoing edges,
	with a high number of opposing edges (reciprocated votes percentage is a config).
	*i.e. such that there's no self-edges (no self-votes) and without parallel arrows in one direction (no double-vote),
	and such that the in- and out-degree is equal, for each vertex.

	If you're interested expanding the algo, I have some open questions about the problem here:
	https://math.stackexchange.com/questions/4729172/deranged-generous-gift-giving-in-the-limit

	Author: Nikolaj-K
	Discord: Nikolaj-K (nikolajk)

	TODO for you if you want to hop on:
	1. Copy the last USERS_ list at the bottom of the comment section
	2. Add your field (name, id, capacities of votes per day) and post it as a comment far below.
	You can use 3 dashes (the ` symbol) to get code style on github (also on Discord).
	The new entry in the USERS's list should look like so:
	User("Nikolaj-K", 11015, 6),
	"""

	import datetime
	import random
	import numpy as np
	import networkx as nx
	import matplotlib.pyplot as plt

	print("IMPORTS DONE.")


	class Config:
	RECIPROCATED_VOTES_RATIO: float = 10 / 100


	class User:
	def __init__(self, name: str, id: int, voting_capacity: int):
	self.name = name
	self.id = id
	self.voting_capacity = voting_capacity

	def __has_same_name(self, other_user) -> bool:
	return other_user.name == self.name

	def equals(self, other_user) -> bool:
	if self.__has_same_name(other_user):
	assert (
	other_user.id == self.id
	and other_user.voting_capacity == self.voting_capacity
	), f"Inconsistency in the list for {self.name}"
	return self.__has_same_name(other_user)


	USERS = [
	# Your Discord name, your id, your commited voting capacity (for the next day/round)
	# The most up to date version of this list is at the bottom of the github comment section, edit there!
	# Copy and edit the list.
	User("Anti-Hiro", 3664, 12),
	User("Orephelious", 1757, 12),
	User("Ulysseus", 23419, 11),
	User("Ulysseus (hv#2)", 19934, 11),
	User("Ulysseus (hv#3)", 20639, 11),
	User("TommyLeigh", 5851, 10),
	User("Vesa", 12745, 10),
	User("Panigalist", 12015, 9),
	User("MrTax", 1364, 9),
	User("Nikolaj-K", 11015, 9),
	User("THE_SquigglyWorm", 6448, 6),
	User("PeterKiu.sol", 12433, 8),
	User("PeterKiu.sol (hv#2)", 11687, 8),
	User("PeterKiu.sol (hv#3)", 4197, 8),
	User("HubbaBubba", 1927, 8),
	User("HubbaBubba (hv#2)", 13653, 8),
	User("Clemfandango", 10463, 8),
	User("BLKstut", 14419, 8),
	User("TommyLeigh (hv#2)", 4695, 2),
	User("dave_eco", 12402, 8),
	# Removed:
	User("Medhi0", 2879, 0),
	User("Medhi0 (hv#2)", 1052, 0),
	User("DylanDaVillain", 18437, 0),
	User("Fripon", 4025, 0),
	User("Billybagz", 10384, 0),
	User("Snuggster", 6307, 0),
	User("NateMercs", 1235, 0),
	User("Lucast88 Knight", 5013, 0),
	]
	DONT_MATCH_WITH = { # Avoid voting for your own other HV
	"Ulysseus": ["Ulysseus (hv#2)", "Ulysseus (hv#3)",],
	"Ulysseus (hv#2)": ["Ulysseus (hv#3)",],
	"HubbaBubba (hv#2)": ["Ulysseus", "Ulysseus (hv#2)", "Ulysseus (hv#3)",],
	"HubbaBubba": [
	"HubbaBubba (hv#2)",
	"Ulysseus",
	"Ulysseus (hv#2)",
	"Ulysseus (hv#3)",
	],
	"PeterKiu.sol": ["PeterKiu.sol (hv#2)", "PeterKiu.sol (hv#3)",],
	"PeterKiu.sol (hv#2)": ["PeterKiu.sol (hv#3)",],
	"TommyLeigh": ["TommyLeigh (hv#2)",],
	"THE_SquigglyWorm": ["Orephelious",],
	# Removed:
	# "Medhi0": ["Medhi0 (hv#2)",],
	}

	# Auxiliary cleanup
	USERS_ = [
	u for u in USERS if u.voting_capacity
	] # Remove entries with voting_capacity set to zero
	USERS_.sort(key=lambda user: user.voting_capacity)
	USERS_ = USERS_[::-1]

	# Sanity check
	for k, ns in DONT_MATCH_WITH.items():
	names = [u.name for u in USERS_]
	assert k in names, k
	assert all([n in names for n in ns]), ns


	def make_random_pairings(adjacency_in: dict) -> list:
	adjacency = {k: v for k, v in adjacency_in.items()} # Copy

	sources = [] # Ordered multiset of vertices, interleaved
	while sum(list(adjacency.values())):
	for v_src, capacity in adjacency.items():
	if capacity > 0:
	sources.append(v_src)
	adjacency[v_src] += -1

	assert len(sources) == sum(list(adjacency_in.values()))

	targets = []
	i = 0
	while len(targets) < len(sources):
	i += 1
	excluded = {v: [v] for v in adjacency.keys()} # No self-vote
	leftovers = list(sources)
	targets = []
	for s in sources:
	include = lambda t: not (
	t in excluded[s]
	or t.name in DONT_MATCH_WITH.get(s.name, [])
	or s.name in DONT_MATCH_WITH.get(t.name, [])
	)
	candidates = list(filter(include, leftovers))
	if not candidates:
	break
	t = random.choice(candidates)
	leftovers.remove(t)
	targets.append(t)
	excluded[s].append(t) # no double vote
	if (i % 100) == 0:
	print(f"attempt {i}, matched ", len(targets), " of ", len(sources))

	assert (
	len(targets) == len(sources)
	and len(leftovers) == 0
	and all([len(excluded[s]) == s.voting_capacity + 1 for s in sources])
	)

	pairings = list(zip(sources, targets))

	assert not any([l.equals(r) for l, r in pairings])

	return pairings


	def to_adjancency(pairings: list) -> dict:
	adj = {src: [] for src, _target in pairings}
	for src, target in pairings:
	adj[src].append(target)
	return adj


	def num_reciprocal_votes(pairings: list) -> int:
	return sum(pair[::-1] in pairings for pair in pairings)


	def log_adjacency(adjacency) -> None:
	print("" " ".join([f"@{u.name}" for u in USERS_]))
	print()
	print(f"Today's lineup ({datetime.date.today()})")
	print()
	for u_src, u_targets in adjacency.items():
	u_src_voting_capacity: int = len(u_targets)
	assert u_src_voting_capacity == u_src.voting_capacity and all(
	[u.name != u_src.name for u in u_targets]
	)
	print(
	f"{u_src.name} ({u_src.id}, with capacity set to {u_src.voting_capacity}), please energy-vote for:"
	)
	for idx, u in enumerate(u_targets):
	# is_not_reciprocal: str = "*" if u_src not in adjacency[u] else ""
	id = str(u.id) + (5 - len(str(u.id))) * " "
	print(f" {idx + 1}. {id} a.k.a. {u.name}, ", end="\n")
	print()
	# Short version
	num_votes_all = sum([len(u_t) for u_t in adjacency.values()])
	for u_src, u_targets in adjacency.items():
	id = str(u_src.id) + (6 - len(str(u_src.id))) * " "
	s_ = f"{len(u_targets)}/{num_votes_all} #{id} {u_src.name}"
	s = s_ + (33 - len(s_)) * " "
	print(
	s
	+ f" => "
	+ ", ".join(
	[
	str(u.id)
	+ ("*" if (False and u_src not in adjacency[u]) else "")
	+ (
	5
	- len(
	str(u.id)
	+ (
	"*"
	if (False and u_src not in u_src not in adjacency[u])
	else ""
	)
	)
	)
	* " "
	for u in sorted(u_targets, key=lambda u: u.id)
	]
	)
	)
	print()
	print(
	"You got 24 hours to cast your votes. Best ping the the people once you voted for them."
	)
	print("For the follow-up day, anybody can append themselves at the very bottom of")
	print(
	"<https://gist.github.com/Nikolaj-K/cdea02d39de125c6dab28fa13e559583?permalink_comment_id=4616662#gistcomment-4616662>"
	)


	def draw_graph(pairings) -> None:
	make_label = lambda user: f"{user.name}\n{user.id}"
	edgelist_ = [(make_label(u1), make_label(u2)) for u1, u2 in pairings]
	edgelist = []

	print()
	not_rec = []
	for e in edgelist_:
	if e[::-1] not in edgelist_:
	not_rec.append(e)
	# print(f"* " + " ".join(" -> ".join(list(e)).split("\n")) + " is not reciprocal" )
	for e in edgelist_:
	rev_e = e[::-1]
	if e not in not_rec and rev_e not in (edgelist + not_rec):
	edgelist.append(e)

	G = nx.DiGraph(directed=True)
	G.add_edges_from(edgelist_)
	pos = nx.shell_layout(G)
	nx.draw_networkx_edges(
	G,
	pos,
	edgelist=edgelist,
	edge_color="g",
	arrows=False,
	arrowsize=5,
	connectionstyle="arc3,rad=0.0",
	)
	nx.draw_networkx_edges(
	G,
	pos,
	edgelist=not_rec,
	edge_color="black",
	arrows=True,
	arrowsize=15,
	connectionstyle="arc3,rad=0.0",
	)
	nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap("jet"), node_size=0)
	nx.draw_networkx_labels(G, pos, font_size=10)
	plt.axis("off")
	plt.show()


	def run_main():
	print("RUN MAIN.")
	adjacency_ = {u: u.voting_capacity for u in USERS_}

	rel_rv = 0
	sim = 0
	print("make_random_pairings ...")
	pairings = make_random_pairings(adjacency_)

	print("Run while-loop ...")
	while num_reciprocal_votes(pairings) < Config.RECIPROCATED_VOTES_RATIO * len(
	pairings
	):
	print(f"#{sim}")
	pairings = make_random_pairings(adjacency_) # re-sample

	if sim % 5 == 0:
	print(f"#{sim}")
	sim += 1
	num_rv: int = num_reciprocal_votes(pairings)
	num_pairings: int = len(pairings)
	rel_rv_ = round(100 * num_rv / len(pairings), 2)
	if rel_rv_ > rel_rv:
	rel_rv = rel_rv_
	print(
	f"#{sim} num_pairings = {num_pairings}, num_reciprocal_votes = {num_rv} ({rel_rv} %)"
	)

	adjacency = to_adjancency(pairings)
	has_duplicates = lambda xs: len(set(xs)) < len(xs)
	assert not any([has_duplicates(ts) for ts in adjacency.values()])

	log_adjacency(adjacency)
	draw_graph(pairings)


	if __name__ == "__main__":
	run_main()