Find the Translation Table

Question

Given two strings, find the translation table (substitution cipher) between the two, if the translation is not possible, output false. The answer must be minimized and created from left-to-right. The first character to be translated between words must be the first in the translation table. In addition to this, any letter that is not translated (in the same place as it was originally), should NOT be in the translation table.

Probably most easily defined through examples:

Valid Cases

"bat", "sap" => ["bt","sp"]

Notice the ordering, an output of ["tb","ps"] is not valid for this challenge.

"sense", "12n12" => ["se","12"]

Notice how the n isn't translated because it is a 1 to 1 relation.

"rabid", "snail" => ["rabd","snal"]

Notice how the i isn't translated because it is a 1 to 1 relation.

"ass", "all" => ["s","l"]

A is not included, it stays the same, s can map to l due to pattern match.

"3121212", "ABLBLBL" => ["312","ABL"]

Matches pattern perfectly.

Falsy Cases

"banana", "angular" => false

(not the same length, impossible).

"animal", "snails" => false

(each character can only be used ONCE on each side of the translation).

"can","cnn" => false

(n is implicitly used in translation, therefore, defining a translation table with n->a would be invalid)

Thusly, [aimal,sails] is an invalid answer, making this falsy.

"a1", "22" => false

See "caveats", this is listed as falsy. In this case, it's because a and 1 cannot both map to 2. (Each character can only be used ONCE on each side of the translation).

---

This answer seems to be a good benchmark: https://codegolf.stackexchange.com/a/116807/59376

If you have questions about the functionality of two unlisted word pairs, defer to this implementation.

---

I/O rules

• Input may be as a 2 element array or as 2 separate inputs.
• Output can be as an array or newline/space delimited, similar to how I have it shown.
• False output may be 0, -1 or false. Erroring/Empty output is also fine.
• You are guaranteed that a will not equal b and neither a nor b will be empty.
• a and b are printable-ASCII-only sequences of letters.

Caveats

• Translations must occur from left to right, see example 1.
• You must not output characters that remain the same.
• Your program may only take in two strings a and b.
• Each character can only be used ONCE on each side of the translation. This is what makes the translation from snails to animals impossible.
• Recursive replaces should not occur. Example of recursive replace: "a1","22"->[a1,12] where a is first replaced by a 1, then both resultant 1's are replaced with 2's. This is not correct, assume all translations occur independent of each other, meaning this is falsy. Meaning: "a1" with translation table of [a1,12] evaluates to 12 (not 22)

Answer 1

PHP >=7.1, 130 Bytes

18 Bytes saved by @Titus

for([,$x,$y]=$argv;a&$o=$y[$i];)$o==($p=$x[$i++])?:$k[$c[$p]=$o]=$p;echo$y==strtr($x,$c)&$x==strtr($y,$k)?join($k)." ".join($c):0;

Testcases

Expanded

for([,$x,$y]=$argv;a&$o=$y[$i];)
$o==($p=$x[$i++])?:$k[$c[$p]=$o]=$p; # if char string 1 not equal char string 2 make key=char1 value=char2 and key array
echo$y==strtr($x,$c) # boolean replacement string 1 equal to string 2
    &$x==strtr($y,$k) # boolean replacement string 2 equal to string 1
    ?join($k)." ".join($c) # output for true cases
:0; #Output false cases

PHP >=7.1, 148 Bytes

prints 0 for false Output true as string

for([,$x,$y]=$argv;a&$o=$y[$i];$i++)$x[$i]==$o?:$c[$x[$i]]=$o;echo$y==strtr($x,($f=array_flip)($k=$f($c)))&$x==strtr($y,$k)?join($k)." ".join($c):0;

Testcases

Expanded

for([,$x,$y]=$argv;a&$o=$y[$i];$i++)
$x[$i]==$o?:$c[$x[$i]]=$o; # if char string 1 not equal char string 2 set key=char1 value=char2
echo$y==strtr($x,($f=array_flip)($k=$f($c))) # boolean replacement string 1 equal to string 2
&$x==strtr($y,$k) # boolean replacement string 2 equal to string 1
    ?join($k)." ".join($c) # output for true cases
:0; #Output false cases

PHP >=7.1, 131 Bytes

The second answer can be shorted to this if associative arrays are allowed

prints 0 for false Output true as associative array instead of string

for([,$x,$y]=$argv;a&$o=$y[$i];$i++)$x[$i]==$o?:$c[$x[$i]]=$o;print_r($y==strtr($x,($f=array_flip)($f($c)))&$x==strtr($y,$k)?$c:0);

Testcases

PHP >=7.1, 227 Bytes

prints 0 for false

[,$x,$y]=$argv;echo strlen($x)==strlen($y)?strtr($x,$c=array_filter(($f=array_flip)($z=$f(array_combine(($p=str_split)($x),$p($y)))),function($v,$k){return$k!=$v;},1))==$y&$x==strtr($y,$z)?join(array_keys($c))." ".join($c):0:0;

Testcases

Expanded

[,$x,$y]=$argv; # 
echo strlen($x)==strlen($y) #compare string lengths
?strtr($x,  # replace function
$c=array_filter( # filter 
($f=array_flip)($z=$f( # # remove doubles like in testcase: a1 => 22
    array_combine(($p=str_split)($x),$p($y))  # replacement array keys string 1 values string 2 
))
    ,function($v,$k){return$k!=$v;},1)) # remove all keys that equal to values in array
    ==$y # boolean replacement string 1 equal to string 2
&$x==strtr($y,$z) # boolean replacement string 2 equal to string 1        
?join(array_keys($c))." ".join($c) # output for true cases
    :0 # Output if replacement from string 1 is not equal to string 2
:0; #Output for different lengths

Answer 2

JavaScript (ES6), 128 bytes

f=
(s,t)=>!t[s.length]&&[...s].every((c,i)=>n[d=t[i]]==c||d&&!m[c]&&!n[d]&&(n[m[c]=d]=c,c==d||(a+=c,b+=d)),m={},n={},a=b='')&&[a,b]

<div oninput=o.textContent=f(s.value,t.value)><input id=s><input id=t><pre id=o>

Answer 3

JavaScript (ES6), 108 107 105 106 bytes

Edit: Fixed to support inputs such as "22" / "a1" that should be falsy.

---

Returns either 0 or an array of two strings.

f=(a,b,x)=>[...a].some((c,i)=>d[C=b[i]]?d[C]!=c:(d[C]=c)!=C&&(s+=c,t+=C,!C),s=t='',d=[])?0:x||f(b,a,[s,t])

Formatted and commented

f = (                       // given:
  a,                        // - a = first string
  b,                        // - b = second string
  x                         // - x = reference result from previous iteration,
) =>                        //       or undefined
  [...a].some((c, i) =>     // for each character c at position i in a:
    d[                      //   if we already have a translation
      C = b[i]              //   of the character C at the same position in b,
    ] ?                     //   then:
      d[C] != c             //     return true if it doesn't equal c
    :                       //   else:
      (d[C] = c) != C &&    //     store the translation C -> c in the dictionary
      (                     //     if the characters are different:
        s += c, t += C,     //       append them to the translation strings s and t
        !C                  //       return true if C is undefined
      ),                    //
    s = t = '', d = []      //   initialize s, t and d  
  ) ?                       // if some() returns true:
    0                       //   there was a translation error: abort
  :                         // else:
    x ||                    //   if this is the 2nd iteration, return x
    f(b, a, [s, t])         //   else do a recursive call with (b, a)

Test cases

f=(a,b,x)=>[...a].some((c,i)=>d[C=b[i]]?d[C]!=c:(d[C]=c)!=C&&(s+=c,t+=C,!C),s=t='',d=[])?0:x||f(b,a,[s,t])

// truthy
console.log(f('bat','sap'))
console.log(f('sense','12n12'))
console.log(f('rabid','snail'))
console.log(f('ass','all'))
console.log(f('3121212','ABLBLBL'))

// falsy
console.log(f('banana','angular'))
console.log(f('animal','snails'))
console.log(f('a1','22'))
console.log(f('22','a1'))
console.log(f('aaa','bab'))
console.log(f('abc','abcd'))
console.log(f('abcd','abc'))

Answer 4

Retina, 194 191 185 229 225 241 bytes

.+
$&;$&
+`^\w(\w*;)\w
$1
^;\w.*|.+;;.*|;;

^((.)*)(.)(.*;(?<-2>.)*(?(2)(?!)))\3
$1$4
+`((.)(.)*)\2((.)*;.*(.)(?<-3>.)*(?(3)(?!)))\6((?<-5>.)*(?(5)(?!)))$
$1$4$7
^(.)*(.)(.)*(\2)?.*;(?<-1>.)*(?(1)(?!))(.)(?<-3>.)*(?(3)(?!))(?(4)(?!\5)|\5).*

Try it online!

Takes input ;-separated. Output is also ; separated. False inputs are signified by empty outputs.

I know this is painfully verbose, I am still trying to cut down bytes. Most of these bytes go into deleting false inputs.

Edits

• It turns out that I had a significant flaw with my program. It's fixed now, but at the cost of over 40 bytes.

• Another mistake was found where my program did not declare the input a1;22 false, but I was able to keep the program under 250 bytes after fixing it

Explanation

(a more detailed explanation will be coming shortly)

First we have to check if the lengths of strings a and b are the same or not. If they are not, we delete everything.

Duplicates the input to preserve it while we do some length-testing.

.+                      Matches everything
$&;$&                   $& indicates the match, so $&;$& will duplicate the match and separate it with a semi-colon

Now in a loop, we delete the first character of a and the first character of b until one of the strings become empty.

+`                     Repeatedly (until no more substitutions could be made) replace
  ^\w                   A word character (letter or number) at the beginning
     (\w*;)             Capture Group 1: matches any number of word characters and a semicolon
           \w           And a word character after the semi-colon
                       with
$1                      The result of the first capture group

Now there are there possibilities for the "pattern space".

• ;;abc Both strings are of equal length
• def;;abc a is longer than b
• ;def;abc b is longer than a

Now we have to empty the input if the strings are not of the same length (scenarios 2 and 3). This is what this substitution below does. It removes text that matches scenarios 2 and 3.

^;\w.*|.+;;.*|;;

This removes characters that are not transliterated in strings a and b. abc;1b2 => ac;12

^((.)*)(.)(.*;(?<-2>.)*(?(2)(?!)))\3
$1$4

After that, we have to remove duplicate characters. sese;1212 => se;12, but this preserves inputs like aba;123

+`((.)(.)*)\2((.)*;.*(.)(?<-3>.)*(?(3)(?!)))\6((?<-5>.)*(?(5)(?!)))$
$1$4$7

Finally, we delete the input if there are duplicate characters that map to different characters like aba;123 or a1;22.

^(.)*(.)(.)*(\2)?.*;(?.)*(?(1)(?!))(.)(?.)*(?(3)(?!))(?(4)(?!\5)|\5).*

And finally, remove duplicate characters.

Answer 5

Jelly, 18 bytes

ẠaQ⁼µ€Ạ
z0EÐḟQZẋÇ$

Unnamed monadic link (one-input function) taking a list, which returns:
an empty list in the falsey cases; or
a list containing two lists of characters in the truthy cases.

Try it online! (the footer splits the list with a space to avoid printing a smushed representation)
...or see a test suite.

How?

ẠaQ⁼µ€Ạ - Link 1, valid?: mapping list
    µ€  - perform the code to the left for €ach mapping entry
Ạ       -     none of mapping entry falsey? (this & Main's z0 handle unequal input lengths)
  Q     -     deduplicate mapping entry
   ⁼    -     is equal to mapping list? (non-vectorising)
 a      -     and
      Ạ - none falsey (both mapping lists must pass that test)
        - The whole function returns 1 if the mapping list is acceptable, 0 if not

z0EÐḟQZẋÇ$ - Main link: list of strings
z0         - transpose with filler 0 (unequal lengths make pairs containing zeros)
   Ðḟ      - filter discard:
  E        -     all equal? (removes the untranslated character pairs)
     Q     - deduplicate (removes the repeated translation pairs)
      Z    - transpose (list of pairs to pair of lists)
         $ - last two links as a monad:
       ẋ   -     repeat list this many times:
        Ç  -         call last link (1) as a monad

Answer 6

Jelly, 28 26 bytes

QL$€⁼L€
EÐḟQZK0Ç?
ZÇ0L€E$?

Try it online!

QL$€⁼L€      Checks validity of mapping
QL$€          number of unique characters in mapping
    ⁼         equals
     L€       number of characters in mapping

EÐḟQZK0Ç?  Writes valid mapping or 0
EÐḟ           filter maps where a = b
   Q          filter duplicate maps
    Z         zip by column [["ac"],["bd"]] => ["ab","cd"]
     K0Ç?   print if valid map, else print 0

ZÇ0L€E$?      main link: takes an array of 2 strings
Z              zip by column: ["ab", "cd"] => [["ac"],["bd"]]
 Ç     ?       print mapping if
   L€E$         all pairs are same length (returns 0 if initial strings were
  0             else 0

Answer 7

Ruby, 133 bytes

->a,b{a.size!=b.size||(m=a.chars.zip b.chars).any?{|i,j|m.any?{|k,l|(i==k)^(j==l)}}?0:m.select{|x,y|x!=y}.uniq.transpose.map(&:join)}

Try it online!

More readably:

->a, b{
    # Pair the letters in each string - [AB, AB, AB,...]
    pairs = a.chars.zip(b.chars)

    # If there's any combination of two pairs that share one character but not both,
    # or if the strings have different lengths, then the input's invalid.
    if a.size != b.size || pairs.any?{|i,j| pairs.any? {|k, l| (i==k)!=(j==l) }} 
        return 0 # 0 isn't actually falsy in Ruby, but this challenge allows it anyway
    end
    return pairs.select{|x,y| x != y} # Remove unchanged letters
                .uniq                 # Remove duplicates
                .transpose            # Change [AB, AB, AB] form to [AAA, BBB] form.
                .map(&:join)          # Convert the arrays back into strings
}

Just for kicks, here's an 84 byte version in Goruby, which is Ruby, but with a golf flag set when compiling the interpreter. Among other things, it allows you to abbreviate method calls to their shortest unique identifier.

->a,b{a.sz!=b.sz||(m=a.ch.z b).ay?{|i,j|m.y?{|k,l|(i==k)^(j==l)}}?0:m.rj{|x,y|x==y}.u.tr.m(&:j)}

Answer 8

Python 3.6, 211 185 181 178 bytes

Exits with an error for falsy results.

def f(x,y,d={}):
    for a,b in zip(x,y):1/(a not in d or b==d[a]or len(x)-len(y));d[a]=b;1/([*d.values()].count(b)<2)
    return map(''.join,zip(*[x for x in d.items()if x[0]!=x[1]]))

This requires Python 3.6, which you can run in a shell here.

You can test it without the correct output ordering on TIO here. (TIO doesn't have 3.6).

Ungolfed:

from collections import*
d=OrderedDict()                     # keep order
x,y=input()
if len(x)!=len(y):1/0               # equal lengths
for a,b in zip(x,y):
    if a in d and d[a]!=b:1/0       # no duplicate keys
    else:d[a]=b
    if d.values().count(b)>1:1/0    # no duplicate values
print map(''.join,zip(*[x for x in d.items()if x[0]!=x[1]])) # format, no no-ops

If only order didn't matter...

Answer 9

Python 2, 198,193,189,182,179,175,169,165 bytes

def f(a,b):
 r=([""]*2,0)[len(a)!=len(b)]
 for u,v in zip(a,b):
	if r:
		q,w=r
		f=q.find(u)
		if u!=v:r=(([q+u,w+v],r)[f>-1 and w[f]==v],0)[f<0 and v in w]
 print r

Try it online!

• -4 bytes! thanks to mbomb007 for suggesting the use of tab instead of space.

• modified the input format, again thanks to mbomb007.

Answer 10

Röda, 108 119 bytes

{c=[{_<>_|[[_,_]]|orderedUniq}()]d=[]e=[]c|_|{{d+=a;e+=b}if[a!=b]}for a,b[d,e]if[0,1]|{|n|c|[_[n]]|sort|count|[_2=1]}_}

Try it online!

This is a function that takes two lists of characters from the stream and pushes two lists to the stream.

This could be sorter if I was allowed to return pairs.

Explanation (out-dated):

{
    c=[{
        _<>_|       /* pull two lists and interleave them */
        [[_,_]]|    /* "unflat", create lists from pairs */
        orderedUniq /* remove duplicates */
    }()]            /* c is a list of the pairs */
    d=[]
    e=[]
    c| /* push the pairs to the stream */
    _| /* flat */
    {  /* for each pair (a, b): */
        { /* if a != b (remove "1-to-1 relations"):  */
            d+=a;
            e+=b
        }if[a!=b]
    }for a,b
    /* return d and e if no character is mapped to more than one character */
    [d,e]if c|[_[0]]|sort|count|[_2=1]
}

Here's an underscore solution that contains no variables (114 bytes):

{[[{_<>_}()|[[_,_]]|unorderedUniq]]|[[_()|_|[_]if[_1!=_2]],[_1()|_|[_2]if[_1!=_2]]]if[[_1()|_][::2],[_1()|_][1::2]]|[sort(_)|count|[_2=1]]}

That's a lot of underscores.

Answer 11

AWK, 140 bytes

BEGIN{RS="(.)"}RT~/\W/{S=1}RT~/\w/&&S{if(RT!=x=A[++b]){if(B[z=RT]==""){B[z]=x
c=c x
d=d z}a=B[z]!=x?0:a}}!S{A[++a]=RT}END{if(a==b)print c,d}

Usage: Place code in FILE then:

awk -f FILE <<< "string1 string2"

The input strings need to be whitespace separated.

The output is empty if they fail, or 2 strings separated by a space.

Answer 12

k, 28 bytes

{$[(y?y)~x?x;+?(~=/)#x,'y;]}

Explanation:

{                          } /function that takes in two strings, x and y
 $[         ;            ;]  /if statement (to check if there is a mapping)
         x?x                 /first index of [each letter in x] in x
   (y?y)                     /first index of [each letter in y] in y
        ~                    /make sure they match
                     x,'y    /zip together the two strings
               (~=/)#        /remove equal pairs
              ?              /unique pairs only
             +               /transpose ("unzip", in a way)

Answer 13

APL (Dyalog) with AGL, 22 bytes

{≡/⍳⍨¨⍺⍵:↓⍉↑∪⍺(≠é,¨)⍵}

Try it online!

{…} anonymous function:

 If…

  ⍺⍵ the arguments

  ⍳⍨¨ when self-indexed (i.e. the first occurrences of their elements in themselves)

  ≡/ are equivalent

 : then:

  ⍺(…)⍵ apply the following tacit function to the arguments:

   ,¨ concatenate corresponding elements (errors on mismatching lengths)

   é then filter by (é is just the primitive function /)

   ≠ where the strings are different

  ∪ unique (remove duplicates)

  ↓⍉↑ transpose list-of-pairs to pair-of-lists (lit. mix into table, transpose table, split into lists)

 else, do nothing

Answer 14

CJam, 38 bytes

{_:,~={1\/;}:K~z{)\c=!},L|z_{_L|=K}%;}

Input and output are arrays on the stack.

Answer 15

PHP (>=7.1), 165 bytes

for([,$x,$y]=$argv;a&$c=$x[$i];$t[$c]=$d)$z+=($d=$y[$i++])&&$d==($t[$c]??$d);foreach($t as$a=>$b)$a==$b?:$r[$a]=$b;print_r($z<$i|array_unique($r)<$t||a&$y[$i]?0:$t);

prints 0 for falsy, associative array else. Run with -r or test it online.

breakdown

for([,$x,$y]=$argv;         # import arguments to $x and $y
    a&$c=$x[$i];            # loop through $x
    $t[$c]=$d)                  # 2. add pair to translation
$z+=                            # 1. increment $z if
    ($d=$y[$i++])&&             # there is a corresponding character in $y and
    $d==($t[$c]??$d);           # it equals a possible previous replacement
                            # remove identities from translation
foreach($t as$a=>$b)$a==$b?:$r[$a]=$b;
print_r(
    $z<$i                   # if not all tests passed
    |array_unique($t)<$t    # or there are duplicates in the translation
    ||a&$y[$i]              # or $y has more characters
    ?0                      # then print 0
    :$r                     # else print translation
);