program for finding ardbo-ardbos

ardbo.py

"""
ardbo.py

inspired by parker higgins "If you take the "c" and "x" off the ends of
"cardboard box", you're left with a perfectly repeating ardbo-ardbo"
<https://bsky.app/profile/xor.blue/post/3lf3xmy7iac2o>
"""

import sys
import collections

def print_ardbo_word_pairs(words):
    """
    Find and print all pairs of words from the given list that, when
    concatenated, form an ardbo-ardbo (a string that, when its first and last
    letters are removed, consists of two copies of the same substring, e.g.
    CARDBOARD BOX).
    """
    partial_ardbos_left = [] # [(left word, required prefix of right word)]
    partial_ardbos_right = [] # [(right word, required suffix of left word)]
    for word in words:
        if len(word) < 4:
            continue
        for i in range((len(word) + 1) // 2, len(word)):
            s1 = word[1:i]
            s2 = word[i:]
            if s1.startswith(s2):
                s3 = word[1 + len(s2):i]
                partial_ardbos_left.append((word, s3))

        for i in range(1, (len(word) - 1) // 2):
            s1 = word[0:i]
            s2 = word[i:-1]
            if s2.endswith(s1):
                s3 = word[i:-1 - len(s1)]
                partial_ardbos_right.append((word, s3))

    dl = collections.defaultdict(list) # suffix -> words with that suffix
    dr = collections.defaultdict(list) # prefix -> words with that prefix
    for word in words:
        dl[word[1:]].append(word)
        dr[word[:-1]].append(word)

    results = []
    for w1, s in partial_ardbos_left:
        for w2 in dr[s]:
            if not w1.endswith(w2): # skip pairs like "REIMAGINE IMAGINE"
                results.append((w1, w2))
    for w2, s in partial_ardbos_right:
        for w1 in dl[s]:
            if not w2.startswith(w1): # skip pairs like "EMBARGO EMBARGOED"
                results.append((w1, w2))
    results.sort(key=lambda p: len(p[0]) + len(p[1]), reverse=True)
    for w1, w2 in results:
        print(w1, w2)


if __name__ == '__main__':
    words = [line.strip() for line in open(sys.argv[1])]
    print_ardbo_word_pairs(words)