Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Determine the Order by rodka81
from collections import defaultdict, OrderedDict
from itertools import combinations
import operator
def independent_words(words):
found = False
for w1, w2 in combinations(words, 2):
if set(w1) & set(w2):
found = True
return not found
def remove_duplicates(words):
result = []
for word in list(words):
result.append("".join((OrderedDict.fromkeys(word))))
return result
def merge_words(words):
w = list(words)
merged = True
while merged:
merged = False
for w1, w2 in combinations(w, 2):
if w1 in w and w2 in w and w1[-1] == w2[0]:
w.remove(w1)
w.remove(w2)
w.append(w1[:-1]+w2)
merged = True
return w
def checkio(words):
words = merge_words(remove_duplicates(words))
if len(words) == 1:
return words[0]
after = defaultdict(set)
alphabet = defaultdict(list)
for word in words:
for l in word:
alphabet[l] = ord(l)
for first, second in combinations(enumerate(word), 2):
first_index, first_letter = first
second_index, second_letter = second
if second_index > first_index:
after[first_letter].add(second_letter)
if independent_words(words):
sorted_alphabet = sorted(alphabet.items(), key=operator.itemgetter(1))
return ''.join([l for l, _ in sorted_alphabet])
result = []
cur_letter = None
for letter in alphabet:
if letter not in after.keys():
cur_letter = letter
result.append(letter)
max_iter = 100
next_letters = set()
while len(result) < len(alphabet.keys()) and max_iter > 0:
for l, s in after.items():
if cur_letter in s:
s.remove(cur_letter)
for l, s in after.items():
if len(s) == 0 and l not in result:
next_letters.add(l)
if len(next_letters) > 0:
sorted_letters = sorted([(l, ord(l)) for l in next_letters], key=operator.itemgetter(1))
l, _ = sorted_letters[-1]
next_letters.remove(l)
sorted_letters.pop()
result.append(l)
cur_letter = l
max_iter -= 1
result.reverse()
return ''.join(result)
if __name__ == '__main__':
assert checkio(["acb", "bd", "zwa"]) == "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"
assert checkio(["my", "name", "myke"]) == "namyke"
assert checkio(["xxxyyz","yyww","wwtt","ttzz"]) == "xywtz"
assert checkio(["ghi", "abc", "def"]) == "abcdefghi"
assert checkio(["axton", "bxton"]) == "abxton"
assert checkio(["hfecba", "hgedba", "hgfdca"]) == "hgfedcba"
Dec. 19, 2016
Comments:
