Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
TopoHeapSort solution in Uncategorized category for Determine the Order by tjreedy
def checkio(data):
# What makes this problem different from normal topological sorting
# is selection of the minimum unblocked item rather than an arbitrary
# one. Use a heap rather than set to store and select.
import heapq
# Get the set of letters
letters = set()
for word in data:
for letter in word:
letters.add(letter)
# Initialize predessors of each letter, that block its selection
blocks = {let:set() for let in letters}
# Initialize followers of each letter, needed for unblocking
follow = {let:set() for let in letters}
# Fill in both for words longer than one letter
for word in data:
for i in range(1, len(word)):
a, b = word[i-1:i+1]
if a != b:
follow[a].add(b)
blocks[b].add(a)
# Initialize heap with unblocked letters, seq with nothing
heap = [let for let in letters if not blocks[let]]
heapq.heapify(heap)
seq = [] # answer, once joined
# Move min to seq, unblocked letters to heap
while heap:
let = heapq.heappop(heap)
seq.append(let)
for a in follow[let]:
ablock = blocks[a]
ablock.remove(let)
if not ablock:
heapq.heappush(heap, a)
return "".join(seq)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([]) == "zwacbd", \
"Just concatenate it"
assert checkio(["klm", "kadl", "lsm"]) == "kadlsm", \
"Paste in"
assert checkio(["a", "b", "c"]) == "abc", \
"Cant determine the order - use english alphabet"
assert checkio(["aazzss"]) == "azs", \
"Each symbol only once"
assert checkio(["dfg", "frt", "tyg"]) == "dfrtyg", \
"Concatenate and paste in"
May 23, 2013
Comments: