Skip to content

Instantly share code, notes, and snippets.

@klausbrunner
Created April 5, 2022 14:09
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Given a sequence of pairs (A, B), return a list of 3-tuples (A, B, T) where T is a boolean that marks whether the sequence contains the inverted pair (B, A) as well.
from typing import Sequence
def mark_bidirectionals(pairs: Sequence) -> list:
"""Given a sequence of pairs (A, B), return a list of 3-tuples (A, B, T) where T is a boolean that
marks whether the sequence contains the inverted pair (B, A) as well. Order is preserved, but all
identical and inverted pairs to the right of (i.e. on higher indexes than) the original pair are removed.
Implementation note: pairs must be immutable (usable as dict keys)."""
marks = dict()
for a, b in pairs:
if (b, a) in marks:
marks[(b, a)] = True
elif (a, b) not in marks:
marks[(a, b)] = False
return list((a, b, t) for ((a, b), t) in marks.items())
import pytest
from proc import mark_bidirectionals
def test_mark_bidirectionals_empty():
r = mark_bidirectionals([])
assert r == []
def test_mark_bidirectionals_simple():
r = mark_bidirectionals(
[("A", "B"), ("C", "D"), ("E", "F"), ("B", "A"), ("G", "H"), ("J", "K")])
assert r == [("A", "B", True), ("C", "D", False),
("E", "F", False), ("G", "H", False), ("J", "K", False)]
def test_mark_bidirectionals_multi():
r = mark_bidirectionals([("A", "B"), ("C", "D"), ("E", "F"),
("B", "A"), ("B", "A"), ("G", "H"), ("B", "A"), ("J", "K")])
assert r == [("A", "B", True), ("C", "D", False),
("E", "F", False), ("G", "H", False), ("J", "K", False)]
def test_mark_bidirectionals_identical_dups_removed():
r = mark_bidirectionals(
[("A", "B"), ("C", "D"), ("E", "F"), ("B", "A"), ("A", "B"), ("G", "H"), ("G", "H"), ("J", "K")])
assert r == [("A", "B", True), ("C", "D", False),
("E", "F", False), ("G", "H", False), ("J", "K", False)]
def test_mark_bidirectionals_bi_dups_removed():
r = mark_bidirectionals(
[("A", "B"), ("C", "D"), ("E", "F"), ("B", "A"), ("B", "A"), ("G", "H"), ("B", "A"), ("J", "K")])
assert r == [("A", "B", True), ("C", "D", False),
("E", "F", False), ("G", "H", False), ("J", "K", False)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment