entry #1
written by IFcoltransG
submitted at
2 likes
guesses
- IFcoltransG (by moshikoi)
- moshikoi (by LyricLy)
- moshikoi (by olus2000)
- moshikoi (by soup girl)
- soup girl (by seshoumara)
comments 0
cg30.py ASCII text
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | def entry(str1, str2): alphabet = alphabet_all(str1, str2) # removing useless letters canonical_words = [canonical(word, extras(word, alphabet)) for word in (str1, str2)] maximums = max_extras(canonical_words) alphabet = alphabet_any(*canonical_words) length = max(map(len, canonical_words)) min_length = min(map(len, canonical_words)) # every string with length n from alphabet perms = space(alphabet, length) # limiting strings not on shortest path trimmed = trim(perms, canonical_words, maximums, min_length) # adding strings reached by deleting letters extended = extend_down(trimmed) # connecting graph edges linked_perms = link(extended, canonical_words, alphabet, maximums, min_length) path_length = a_star(linked_perms, *canonical_words) return path_length def heuristic(start, goal): return max(len(start), len(goal)) - sum(min(start.count(letter), goal.count(letter)) for letter in set(start) & set(goal)) def a_star(linked_perms, start, goal): dist = {start: 0} open_set = {start} closed_set = set() while open_set: current = min(open_set, key=lambda x: heuristic(x, goal) + dist[x]) open_set.remove(current) closed_set.add(current) if current == goal: return dist[goal] for neighbor in linked_perms[current]: if neighbor in closed_set: continue dist_from_current = dist[current] + 1 if neighbor not in dist or dist_from_current < dist[neighbor]: dist[neighbor] = dist_from_current if neighbor not in open_set: open_set.add(neighbor) def alphabet_any(*word_list): return frozenset("".join(word_list)) def alphabet_all(*word_list): return frozenset(character for character in "".join(word_list) if all(character in word for word in word_list)) def max_extras(word_list): characters = list("".join(word_list)) return { character: characters.count(character) for character in set(characters) } def extras(word, alphabet): return frozenset(l for l in word if l not in alphabet) def canonical(word, unneeded): if unneeded: canon_char = set(unneeded).pop() for char in unneeded: word = word.replace(char, canon_char) return word def space(alphabet, repeats): return frozenset(map("".join, __import__("itertools").product(alphabet, repeat=repeats))) def lcs_upper_bound(*word_list): return {letter: min(word.count(letter) for word in word_list) for letter in alphabet_all(*word_list)} def reachable(word, canonical_words, max_counts, base_length): if sum(lcs_upper_bound(*canonical_words, word).values()) < base_length - len(word): return False return all(word.count(character) <= max_count for character, max_count in max_counts.items()) def trim(word_list, canonical_words, max_counts, base_length): return frozenset(word for word in word_list if reachable(word, canonical_words, max_counts, base_length)) def others(word, alphabet): return frozenset( other for i in range(len(word)) for other in others_at(word, i, alphabet) ) def others_at(word, index, alphabet): return [ word[:index] + char + word[index + 1:] for char in alphabet if char != word[index] ] def cut_at(word, index): return word[:index] + word[index + 1:] def cut(word): return frozenset(cut_at(word, i) for i in range(len(word))) def extend_down(top_level): if not top_level: return top_level cuts = frozenset( cut_word for word in top_level for cut_word in cut(word) ) extension = extend_down(cuts) return extension | top_level def link_directed(word_list, alphabet): return { word: cut(word) | others(word, alphabet) for word in word_list } def reversed_dict(dictionary): new_dict = {} for key, values in dictionary.items(): for value in values: new_dict.setdefault(value, set()).add(key) return new_dict def link(word_list, canonical_words, alphabet, max_counts, base_length): directed = link_directed(word_list, alphabet) reverse_directed = reversed_dict(directed) return { word: trim( directed.get(word, set()) | reverse_directed.get(word, set()), canonical_words, max_counts, base_length ) for word in trim(word_list, canonical_words, max_counts, base_length) } |
post a comment