[Week Five] Programming Contest - Isomorphic Strings

General Discussion Off Topic
1

Welcome back to week five of the weekly programming contests! As always, you can find the rules and information on the contests Posted Here

This weeks challenge is slightly similar to the anagram challenge in week two. Your job is to test whether or not two Strings are Isomorphic. For this challenge, Isomorphic Strings will be any two Strings in which it is possible to replace the characters in either one in order to get the other.

For example, “egg” and “add” would be isomorphic because e -> a and g -> d and the inverse works as well. However “coot” and “toot” would not be, because c -> t and t -> t which means that t maps to both t and c going the other way making isomorphicality impossible.

You have to implement this functionality in the method: public static boolean isomorphic(String a, String b) (The method can be renamed), which returns true if the Strings are isomorpic and false if they are not, case insensitive.

Some examples:

isomorphic(“egg”, “add”) -> true
isomorphic(“foo”, “bar”) -> false
isomorphic(“carrot”, “marria”) -> false
isomorphic(“merit”, “serif”) -> true
isomorphic(“turd”, “floor”) -> false
isomorphic(“coot”, “toot”) -> false
isomorphic(“cool”, “tool”) -> true
isomorphic(“fiddle”, “middle”) -> true

Imports are allowed for this challenge!

Challenge Closes: Sunday 12/6/15

Good luck!

2

This problem is really simple compared to my Modern Algebra class where we do the same thing but with abstract groups…

Minified version (371 chars). Could get it smaller but meh. Someone else can win and do the hard work :stuck_out_tongue:

public static boolean isomorphic(String a,String b){if(a.length()!=b.length())
return false;Map<Character,Character>map=new HashMap<>();for(int i=0;i<a.length();i++){if(!map.containsKey(a.charAt(i))&&!map.containsValue(b.charAt(i))){map.put(a.charAt(i),b.charAt(i));}
if(map.get(a.charAt(i))==null||!map.get(a.charAt(i)).equals(b.charAt(i))){return false;}}
return true;}

Pretty version. Just a simple Character map

public static boolean isomorphic(String a, String b) {
    if(a.length() != b.length())
        return false;
    Map<Character, Character> map = new HashMap<>();
    for (int i = 0; i < a.length(); i++) {
        if (!map.containsKey(a.charAt(i)) && !map.containsValue(b.charAt(i))) {
            map.put(a.charAt(i), b.charAt(i));
        }
        if (map.get(a.charAt(i)) == null || !map.get(a.charAt(i)).equals(b.charAt(i))) {
            return false;
        }
    }
    return true;
}
1 Like
3

Minified version: 147 chars (138 with method renamed to i)

public static boolean isomorphic(String a,String b){return Arrays.equals(a.chars().map(a::indexOf).toArray(),b.chars().map(b::indexOf).toArray());}

How it works:
A String is isomorphic to cool, if it contains four characters, of which all are different from each other except for the second and third character, which are the same.
Or, more verbose: The first character first occurs on positon 1. The second character first occurs on position 2. The third character first occurs on position 2. The fourth character first occurs on position 4.

So for each String I create a description in form of an int array (which for “cool” is {0,1,1,2}) by mapping each character to the position where it first occurs. Two Strings then are isomorphic if and only if their descriptions are equal.

Long code with unit test for the examples:

import java.util.Arrays;
import org.junit.Test;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertFalse;

public class IsomorphicString {

    public static boolean isomorphic(String a, String b) {
        return Arrays.equals(
                a.chars().map(a::indexOf).toArray(),
                b.chars().map(b::indexOf).toArray()
                );
    }

    @Test
    public void testCorrectReturnForExamples() {
        assertTrue (isomorphic("egg"   , "add"));
        assertFalse(isomorphic("foo"   , "bar"));
        assertFalse(isomorphic("carrot", "marria"));
        assertTrue (isomorphic("merit" , "serif"));
        assertFalse(isomorphic("turd"  , "floor"));
        assertFalse(isomorphic("coot"  , "toot"));
        assertTrue (isomorphic("cool"  , "tool"));
        assertTrue (isomorphic("fiddle", "middle"));
    }
}

Edit: Shaved off a total of 20 chars of the initial solution: 10 by removing fully qualified name as imports do not count towards code length and another 10 by using method references instead of lambda expressions.

5 Likes
5

I’d prefer scala for this, or if you use the Functional Java library, foldLeft would reduce this code by even more. But sticking to pure jdk, here’s an improvement on your take of this challenge.

This simplification works by the same logic @Saladoc used. Comparing the resulting mapped array via the first index of the char. Since they should be the same, the sums should also be the same. It passes the test that @Saladoc used for his function, and there might be an edge case, but to high to think of any. This works just fine for the contest.

Minified: (125 chars)

public static boolean isomorphic(String a,String b){return a.chars().map(a::indexOf).sum()==b.chars().map(b::indexOf).sum();}

Non-minified:

    public static boolean isomorphic(String a, String b) {
        return a.chars().map(a::indexOf).sum() == b.chars().map(b::indexOf).sum();
    }

Credits: Saladoc for actual logic and initial code. This is just an improvement to help those who don’t understand the power of functional style programming.

Note: This is smaller than @Saladoc’s answer, however, credit him with the winning solution if no one else can produce something shorter, because credit is due where its due.

3 Likes
6

Nice improvement. It will work for all the examples given by @kmecpp and will return true for every pair of isomorphic strings.
Sadly, there will be tons of false positives. For example, the strings “aaabb” and “aabbb” are obviously not isomorphic and will be described as {0,0,0,3,3} and {0,0,2,2,2} respectively. However, both of these descriptions have the same sum and therefore will be falsely recognised as isomorphic by your approach.

1 Like
7

I did state that there would be edge cases. Albeit I only did sum() due to testing against the provided values for this golf.

A fix would be to offset the indices so they begin from 1.
(139 chars)

public static boolean isomorphic(String a,String b){return a.chars().map(i->a.indexOf(i)+1).sum()==b.chars().map(i->b.indexOf(i)+1).sum();}

Scala version for the lulz (74 chars)

def isomorphic(a:String,b:String)=a.map(a.indexOf(_))==b.map(b.indexOf(_))
8

Well seeing as no one saw my note on case, i’ll just ignore that.

Congratulations to @Saladoc for once again winning the weekly programming contest! The next challenge will be posted shortly

1 Like