#!/usr/local/cpython-3.9/bin/python3

"""Find the order of an alien alphabet, using a list of words sorted in that alien order."""

from __future__ import print_function, unicode_literals, division

import sys
import pprint
import collections

import toposort


def common_prefix(word1, word2):
    """
    Return a common prefix of word1 and word2.

    If there is no common prefix, return the null string
    """
    min_len = min(len(word1), len(word2))

    for index in range(min_len):
        if word1[index] == word2[index]:
            continue
        break

    return word1[:index]


def main():
    """Find the "alphabetical order" from a list of "sorted" words given on the commandline."""
    if sys.argv[1:]:
        ordered_words = sys.argv[1:]
    else:
        raise SystemExit('Give me whitespace-separated words on the command line')

    partial_order_dict = collections.defaultdict(set)

    for word1, word2 in zip(ordered_words, ordered_words[1:]):
        if word1 == word2:
            # It's possible, in an ordered (nondecreasing) list, to have adjacent words that are the same.
            continue

        cp = common_prefix(word1, word2)

        len_cp = len(cp)

        lower = word1[len_cp]
        higher = word2[len_cp]

        # This was lower to higher, but that was coming up in
        # reverse order.  Doing higher to lower appears to work nicely.
        partial_order_dict[higher].add(lower)

    # final_order should become a list of sets
    try:
        final_order = list(toposort.toposort(partial_order_dict))
    except toposort.CircularDependencyError:
        raise SystemExit('Circular dependency error')

    # Instead of using a final_order.reverse(), we invert partial_order above.
    # final_order.reverse()

    pprint.pprint(final_order)


main()