Skip to content

Instantly share code, notes, and snippets.

@klausbrunner
Created April 5, 2022 14:09
Show Gist options
  • Save klausbrunner/47503d85f0c179fcf25f5876b4f25fc7 to your computer and use it in GitHub Desktop.
Save klausbrunner/47503d85f0c179fcf25f5876b4f25fc7 to your computer and use it in GitHub Desktop.
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