patternpythonMinor
Are the words isomorph?
Viewed 0 times
arewordstheisomorph
Problem
Are the words isomorphs? (Code-Golf)
This is my non-golfed, readable and linear (quasi-linear?) in complexity take of the above problem. For completeness I include the description:
Two words are isomorphs if they have the same pattern of letter
repetitions. For example, both ESTATE and DUELED have pattern abcdca
because letters 1 and 6 are the same, letters 3 and 5 are the same,
and nothing further. This also means the words are related by a
substitution cipher, here with the matching
Write code that takes two words and checks whether they are isomorphs.
As always tests are included for easier understanding and modification.
This is my non-golfed, readable and linear (quasi-linear?) in complexity take of the above problem. For completeness I include the description:
Two words are isomorphs if they have the same pattern of letter
repetitions. For example, both ESTATE and DUELED have pattern abcdca
ESTATE
DUELED
abcdcabecause letters 1 and 6 are the same, letters 3 and 5 are the same,
and nothing further. This also means the words are related by a
substitution cipher, here with the matching
E D, S U, T E, A L.Write code that takes two words and checks whether they are isomorphs.
As always tests are included for easier understanding and modification.
def repetition_pattern(text):
"""
Same letters get same numbers, small numbers are used first.
Note: two-digits or higher numbers may be used if the the text is too long.
>>> repetition_pattern('estate')
'012320'
>>> repetition_pattern('dueled')
'012320'
>>> repetition_pattern('longer example')
'012345647891004'
# ^ ^ ^ 4 stands for 'e' because 'e' is at 4-th position.
# ^^ Note the use of 10 after 9.
"""
for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
text = text.replace(unique_letter, str(index))
return text
def are_isomorph(word_1, word_2):
"""
Have the words (or string of arbitrary characters)
the same the same `repetition_pattern` of letter repetitions?
All the words with all different letters are trivially isomorphs to each other.
>>> are_isomorph('estate', 'dueled')
True
>>> are_isomorph('estate'*10**4, 'dueled'*10**4)
True
>>> are_isomorph('foo', 'bar')
False
"""
return repetition_pattern(word_1) == repetition_pattern(word_2)Solution
for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
text = text.replace(unique_letter, str(index))
return textYou don't need to go through the set and sort, you can do:
for index, letter in enumerate(text):
text = text.replace(letter, str(index))
return textBy the time it gets to the last "e" in "estate" and tries to replace it with "5", it will already have replaced it with "0" earlier on, and there won't be any "e"s left to replace. And it's not changing something while iterating over it, because strings are immutable.
More golf-ish and less readable is:
return ''.join(str(text.index(letter)) for letter in text)Edit: Note for posterity: the above two methods have the same bug Gareth Rees identified, comparing 'decarbonist' and 'decarbonized', where one ends by adding number 10 and the other is a character longer and ends by adding numbers 1, 0 and they compare equally.End Edit
But @jonsharpe's comment asks if you need it to return a string; if you don't, then it could be a list of numbers, which is still very readable:
return [text.index(letter) for letter in text]Minor things:
are_isomorphis a mix of plural/singular naming. Maybeisomorphic(a, b)?
- Your code doesn't take uppercase/lowercase into account - should it?
- This approach will break without warning for an input with numbers in it, e.g.
repetition_pattern('abcdefghi1')is0923456789. "b" changes to 1, then changes to 9 because the "1" at the end catches it, then it appears the two were originally the same character. (It might be outside the scope of the question and not a problem).
Code Snippets
for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
text = text.replace(unique_letter, str(index))
return textfor index, letter in enumerate(text):
text = text.replace(letter, str(index))
return textreturn ''.join(str(text.index(letter)) for letter in text)return [text.index(letter) for letter in text]Context
StackExchange Code Review Q#94776, answer score: 2
Revisions (0)
No revisions yet.