from collections import defaultdict, Counter, deque


def print_string_with_markers(strn, pValue):
    out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]
    return out


def print_array_with_markers(arr, pValue):
    out = "["
    for i in range(len(arr)):
        if i in pValue:
            out += '«'
            out += str(arr[i]) + '»' + ", "
        else:
            out += str(arr[i]) + ", "
    out = out[0:len(out) - 2]
    out += "]"
    return out


def alien_order(words):

    # Step 0: Create data structures and find all unique letters.
    adj_list = defaultdict(set)
    # counts stores the number of unique letters
    print("\n\tGetting unique characters")
    counts = Counter({c: 0 for word in words for c in word})
    print("\t\t", counts.keys(), sep="")
    # Step 1: We need to populate adj_list and counts.
    # For each pair of adjacent words...
    print("\n\tComparing adjacent words")
    outer = 0
    for word1, word2 in zip(words, words[1:]):
        print("\t\tLoop index: ", outer, sep="")
        print("\t\t", print_array_with_markers(
            words, [outer, outer+1]), sep="")
        outer += 1
        print("\t\tWords to compare: ", word1, ", ", word2, sep="")
        print("\t\tIterating the words")
        inner = 0
        for c, d in zip(word1, word2):
            print("\t\t\tInner loop index: ", inner)
            print("\t\t\t\tword1: ", print_string_with_markers(
                word1, inner), ", c = ", c, sep="")
            print("\t\t\t\tword2: ", print_string_with_markers(
                word2, inner), ", d = ", d, sep="")
            inner += 1
            if c != d:
                print("\t\t\t\tThe characters are not the same")
                if d not in adj_list[c]:
                    print("\t\t\t\t\tAdding '", d, "' to ", c,
                          "'s children: ", adj_list[c], " ⟶ ", sep="", end="")
                    adj_list[c].add(d)
                    print(adj_list[c])
                    print("\t\t\t\t\tIncremeting count of '",
                          d, "' ⟶ ", sep="", end="")
                    counts[d] += 1
                    print(counts)
                break
            else:
                print("\t\t\t\tBoth characters are the same: '",
                      c, "', moving to the next character", sep="")
        else:  # Check that second word isn't a prefix of first word.
            if len(word2) < len(word1):
                return ""

    # Step 2: We need to repeatedly pick off nodes with an indegree of 0.
    result = []
    sources_queue = deque([c for c in counts if counts[c] == 0])
    print("\n\tRemoving the sources")
    print("\t\tSources: ", sources_queue, sep="")
    m = 0
    while sources_queue:
        print("\t\tLoop index: ", m, sep="")
        m += 1
        print("\t\t\tGetting the source by popping from the queue")
        print("\t\t\tSources: ", sources_queue, " ⟶ ", end="", sep="")
        c = sources_queue.popleft()
        print(sources_queue)
        print("\t\t\t\tSource: ", c)
        print("\t\t\t\tAppending to the result list: ",
              result, " ⟶ ", end="", sep="")
        result.append(c)
        print(result)
        print("\t\t\tUpdating the in-degrees of the children")
        print("\t\t\t\tSource: ", c, ", children: ", adj_list[c], sep="")
        n = 0
        for d in adj_list[c]:
            print("\t\t\t\tInner loop index: ", n)
            n += 1
            print("\t\t\t\t\tChild: ", d, sep="")
            print("\t\t\t\t\tDecrementing in-degree of ", d,
                  ": ", counts[d], " ⟶ ", counts[d] - 1, sep="")
            counts[d] -= 1
            if counts[d] == 0:
                print("\t\t\t\t\tSince in-degree of ", d,
                      " = 0, it's now a source.", sep="")
                print("\t\t\t\t\tAdding it to the sources queue: ",
                      sources_queue, " ⟶ ", end="", sep="")
                sources_queue.append(d)
                print(sources_queue)


# Driver code
def main():
    words = [
        ["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu",
            "suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],
        ["vanilla", "alpine", "algor", "port",
            "norm", "nylon", "ophellia", "hidden"],
        ["passengers", "to", "the", "unknown"],
        ["alpha", "bravo", "charlie", "delta"],
        ["jupyter", "ascending"]]

    for i in range(len(words)):
        print(i + 1, ".\twords = ", words[i], sep="")
        print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")
        print("-"*100)


if __name__ == "__main__":
    main()