3
\$\begingroup\$

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

ESTATE 
DUELED 
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 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)
\$\endgroup\$
  • \$\begingroup\$ Is there a particular reason you want repetition_pattern to return a string? \$\endgroup\$ – jonrsharpe Jun 26 '15 at 14:55
  • \$\begingroup\$ @jonrsharpe no there isn't. \$\endgroup\$ – Caridorc Jun 27 '15 at 8:29
2
\$\begingroup\$
for index, unique_letter in enumerate(sorted(set(text), key=text.index)):
    text = text.replace(unique_letter, str(index))
return text

You 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 text

By 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_isomorph is a mix of plural/singular naming. Maybe isomorphic(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') is 0923456789. "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).
\$\endgroup\$
2
\$\begingroup\$

There is a Python feature that almost directly solves this problem, leading to a simple and fast solution.

from string import maketrans    # <-- Python 2, or
from str import maketrans       # <-- Python 3

def are_isomorph(string1, string2):
    return len(string1) == len(string2) and \
        string1.translate(maketrans(string1, string2)) == string2
        string2.translate(maketrans(string2, string1)) == string1
\$\endgroup\$
  • \$\begingroup\$ are_isomorph('abcdef', 'estate') returns true. This is because the order in which the translation table is made. Maybe instead you could use are_isomorph(a, b) and are_isomorph(b, a). \$\endgroup\$ – twohundredping Jun 26 '15 at 23:09
  • \$\begingroup\$ I get ImportError: No module named 'str' when I run this code. \$\endgroup\$ – Gareth Rees Jun 29 '15 at 14:43
2
\$\begingroup\$

The code in the post does not work! Here's an example where it fails:

>>> are_isomorph('decarbonist', 'decarbonized')
True

The problem is that the eleventh distinct character gets represented by 10, but an occurrence of the second distinct character followed by the first distinct character is also represented by 10. You could avoid this confusion by representing the pattern as a list instead of a string:

def repetition_pattern(s):
    """Return the repetition pattern of the string s as a list of numbers,
    with same/different characters getting same/different numbers.

    """
    return list(map({c: i for i, c in enumerate(s)}.get, s))

or, if you don't care about algorithmic efficiency:

    return list(map(s.find, s))

but an alternative approach avoids generating a repetition pattern at all, but instead considers the pairs of corresponding characters in the two strings. If we have:

ESTATE
DUELED

then the pairs are E↔D, S↔U, T↔E and A↔L. The two strings are isomorphic if and only if these pairs constitute a bijection: that is, iff the first characters of the pairs are all distinct, and so are the second characters.

def isomorphic(s, t):
    """Return True if strings s and t are isomorphic: that is, if they
    have the same pattern of characters.

    >>> isomorphic('estate', 'dueled')
    True
    >>> isomorphic('estate'*10**4, 'dueled'*10**4)
    True
    >>> isomorphic('foo', 'bar')
    False

    """
    if len(s) != len(t):
        return False
    pairs = set(zip(s, t))
    return all(len(pairs) == len(set(c)) for c in zip(*pairs))

From a purely code golf point of view, however, the following seems hard to beat (especially in Python 2, where you can drop the list calls):

list(map(s.find, s)) == list(map(t.find, t))
\$\endgroup\$
  • \$\begingroup\$ Ooh, I was wondering about where it switched to double digits, but decided that as long as both strings were the same it would work. I should have thought of different length strings. (Sorry, I was trying to edit my post with your correct name, but you got to it first). \$\endgroup\$ – TessellatingHeckler Jun 29 '15 at 16:22
  • 1
    \$\begingroup\$ @TessellatingHeckler: Even strings of the same length can go wrong. Consider abcdefgihjkba versus abcdefgihjbak. \$\endgroup\$ – Gareth Rees Jun 29 '15 at 16:28
0
\$\begingroup\$

text.replace() is \$\mathcal{O}(n)\$. Assuming we have a string of \$n\$ distinct characters your algorithm could devolve in to \$\mathcal{O}(n^2)\$. Of course your strings are likely never long enough for big O to matter.

In problems like this no matter what language you use it is often useful to build tables of characters.

def base_pattern(text):
    lst=[chr(i) for i in range(256)]

    for index, c in enumerate(text):
        lst[ord(c)] = index

    return [lst[ord(c)] for c in text]

def are_isomorph(word1, word2):
    return base_pattern(word1) == base_pattern(word2)
\$\endgroup\$
  • \$\begingroup\$ This is brittle: what if ord(c) is greater than 255? ord('\N{HIRAGANA LETTER KA}') → 12363. \$\endgroup\$ – Gareth Rees Jun 29 '15 at 15:06
  • \$\begingroup\$ @GarethRees This code was never meant to support anything other than ASCII. The codegolf even defines the range as A..Z. \$\endgroup\$ – twohundredping Jun 30 '15 at 19:14
  • \$\begingroup\$ Sure, but a robust implementation would also be shorter: d={c: i for i, c in enumerate(text)}; return [d[c] for c in text] \$\endgroup\$ – Gareth Rees Jun 30 '15 at 20:00
  • \$\begingroup\$ And then I would have a hash table which provides an \$\mathrm{O}(n^2)\$ worst case to the entire algorithm and goes against the point of my post. \$\endgroup\$ – twohundredping Jun 30 '15 at 20:34
  • \$\begingroup\$ All characters have different hashes, so the worst case is \$O(n)\$. \$\endgroup\$ – Gareth Rees Jun 30 '15 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.