1
\$\begingroup\$

I was trying to solve a problem to determine if 2 strings are isomorphic. They are isomorphic when each character in string one can be replaced with another character in string 2. Two different characters may not map to the same value, and same character must not match to different values. Also the length of the strings must be same.

I've used exception for logic flow:

module Isomorphism

  class NotIsomorphicException < StandardError
    attr_reader :object
    def initialize(object)
      @object = object
    end
  end

  def self.isomorphic? string_a,string_b
    begin
      self.isomorphism string_a,string_b
      true
    rescue NotIsomorphicException => _
      return false
    end
  end

  protected
  def self.isomorphism string_a,string_b
    raise NotIsomorphicException.new("Unequal length") unless string_a.size == string_b.size

    isomorphism_map = {}
    associations = string_a.chars.zip string_b.chars

    associations.each do |char_one,char_two|
      if(isomorphism_map.key? char_one)
        raise NotIsomorphicException.new("Single character needs to map to multiple characters, not isomorphic") unless isomorphism_map[char_one] == char_two
      elsif(isomorphism_map.value? char_two)
        raise NotIsomorphicException.new("Two characters map to same value")
      end
      isomorphism_map[char_one] = char_two
    end
  end

end

Please let me know if it's okay to code this way and any improvements that I might be able to make this better.

Following are the specs, just in case:

describe Isomorphism do
  it "should return true for single character words" do
    expect(Isomorphism.isomorphic? "t","d").to be true
  end

  it "should return true for empty strings" do
    expect(Isomorphism.isomorphic? "","").to be true
  end

  it "should return false if strings are of unequal length" do
    expect(Isomorphism.isomorphic? "dh","dhruv").to be false
  end

  it "should return false when 2 characters need to map to same character" do
    expect(Isomorphism.isomorphic? "ab","aa").to be false
  end

  it "should return true for egg and add" do
    expect(Isomorphism.isomorphic? "egg","add").to be true
  end

  it "should return false for foo and bar" do
    expect(Isomorphism.isomorphic? "foo","bar").to be false
  end

  it "should return true for paper and title" do
    expect(Isomorphism.isomorphic? "paper","title").to be true
  end

  it "should return false for aab and aaa" do
    expect(Isomorphism.isomorphic? "aab","aaa").to be false
  end
end
\$\endgroup\$

3 Answers 3

Reset to default
2
\$\begingroup\$

Looking at your isomorphism helper function…

The flow of control is kind of nasty. In particular, burying an unless in here…

if …
  raise Exception.new(…) unless …
elsif …
  raise
end

… is too tricky, because:

  • You already have an if-elsif expression, and it would be better to work it into the same chain.
  • It's at the end of a very long line, where it is barely visible.
  • unless, being a negation, is automatically less preferable to an affirmative if.

Switching the naming convention from string_a, string_b to char_one, char_two is not ideal. Why not char_a, char_b? Or better yet, just a, b?

Doing Hash lookups in reverse using value? is not efficient. You would be better off making a "forward" map and an "inverse" map. See below for an even better way to decompose the problem.

As for the use of exceptions internally, I think it's a bad idea. It's just a cumbersome way to return false with commentary. You could just write a comment to avoid the overhead. Better yet, if you write the code well, I don't think there is a need for any comment. For example, in the implementation below, b != expected_b is pretty self-explanatory.

module Isomorphism

  def self.isomorphic?(string_a, string_b)
    surjective?(string_a, string_b) && surjective?(string_b, string_a)
  end

  protected
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    surjection = {}

    string_a.chars.zip(string_b.chars).each do |a, b|
      expected_b = surjection[a]
      if expected_b && (b != expected_b)
        return false
      end
      surjection[a] = b
    end
    true
  end

  # Alternate implementation: shorter, but won't detect failure as quickly
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    pairs = string_a.chars.zip(string_b.chars)
    surjection = Hash[pairs]
    pairs.all? { |a, b| surjection[a] == b }
  end

end
\$\endgroup\$
2
  • \$\begingroup\$ I used most of what I did to prevent returning true/false from a function that's can return isomorphic strings (currently its not doing that, but it can) Secondly for me, the symbol ! for not is very short and often skips my eyes, but I guess that's just me. I like how you captured rules in 2 calls to surjective. And yep I messed up naming conventions, but is a,b better than char_a,char_b? a,b doesn't tell me that these are chars... or is it okay to expect that from the context. Thanks for the suggestions though, your code if ofcourse much simplified :) \$\endgroup\$ Commented May 1, 2015 at 1:30
  • \$\begingroup\$ Related answer in Java \$\endgroup\$ Commented May 27, 2016 at 8:15
1
\$\begingroup\$

Well, 200_success beat me to it, but I'd already written this. I'm stealing the name surjective?, though.

I don't see the need for exceptions. Just return.

Sure, exceptions can tell more about why two strings aren't isomorphic, but you're not using that for anything - not even inside your module. And the exceptions don't bubble back to the caller, so it seems like you go to a lot of trouble to raise exceptions and then immediately rescue from them.

By the way, you could consider mixing this into the String class. Not saying you have to, but you could.

class String
  def isomorphic?(string)
    surjective?(string) && string.surjective?(self)
  end

  def surjective?(string)
    return false unless length == string.length
    chars.zip(string.chars).each_with_object({}) do |(a, b), map|
      return false if map[a] && map[a] != b
      map[a] = b
    end
    true
  end
end
\$\endgroup\$
3
  • \$\begingroup\$ Okay - if this is prod code will you put comments on why are we returning false? And thanks for each_with_object - didn't know about that function :) \$\endgroup\$ Commented May 1, 2015 at 1:34
  • \$\begingroup\$ And I'll upvote you for good use of open classes and unless once I've enough repo on the site \$\endgroup\$ Commented May 1, 2015 at 1:37
  • 1
    \$\begingroup\$ @DhruvKapur In production I'd probably document the methods overall, but I wouldn't bother with comments inside the method bodies. I'd write something like what you wrote in your question (i.e. this is what does isomorphic mean for strings). However, in production I tend to be very conservative about extending core classes like String. It's neat, but I won't go there unless it's really, really worth it. I did it in my answer just to present the idea. \$\endgroup\$ Commented May 1, 2015 at 2:29
0
\$\begingroup\$

I do not match Code Review with this a lot, but I found this problem to be interesting and would solve it without .zip and {}:

def isomorphic? a, b

  each_char_positions = lambda do |string|
    string.each_char.map.with_index.group_by(&:first).
      map{ |c, poss| poss.map(&:last) }.sort
  end

  each_char_positions[a] == each_char_positions[b]

end

Strings are isomorphic if arrays of their unique chars positions are the same. You may insert tap{ |s| p s }. line after group_by to see this for "paper" vs "title":

{"p"=>[["p", 0], ["p", 2]], "a"=>[["a", 1]], "e"=>[["e", 3]], "r"=>[["r", 4]]}  
{"t"=>[["t", 0], ["t", 2]], "i"=>[["i", 1]], "l"=>[["l", 3]], "e"=>[["e", 4]]}
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.