15
\$\begingroup\$

Inspired by this

Your task today: given two strings, find the string with the lowest maximum Levenshtein distance to the input strings. For example, using Steffan and Seggan, the average string will be Steggan. It is distance 2 from Steffan (replace the gg with ff), and 1 from Seggan (add a t). That gives it a maximum distance of 2.

Other constraints:

  • If there are multiple possibilities, output any of them or all of them (duplicates are OK)
  • The inputs are distinct
  • The input will be given in uppercase or lowercase ASCII, you choose
  • There will always be common letters in the inputs
  • The outputs will only have letters from the inputs
  • There will always be a solution satisfying the above constraints

As this is , shortest code in bytes wins.

Testcases

seggan, steffan -> ['seffan', 'sefgan', 'segfan', 'stefgan', 'stegfan', 'steggan'] (2)
hello, ho -> ['hllo', 'hlo', 'helo', 'heo'] (2)
string, ring -> ['tring', 'sring'] (1),
aaa, aaaa -> ['aaa', 'aaaa'] (1)
abc, abcd -> ['abc', 'abcd', 'abd', 'abca', 'abcb', 'abcc'] (1)
\$\endgroup\$
10
  • \$\begingroup\$ Can't abc, abcd also be abd? \$\endgroup\$
    – Steffan
    Aug 3 at 18:22
  • \$\begingroup\$ @Steffan yeah, it can \$\endgroup\$
    – Seggan
    Aug 3 at 18:28
  • \$\begingroup\$ I get that hello, ho is ["heo", "hlo", "hel", "elo", "heol", "helo", "hleo", "ehlo", "elho", "hll", "llo", "holl", "hllo"]. All of those have a max distance of 2 between hello, ho. \$\endgroup\$
    – Steffan
    Aug 3 at 20:43
  • \$\begingroup\$ Also, I asked in the sandbox but no one responded. The test cases imply that the outputs can only contain letters in the inputs. Is that so? Several of these test cases could have way more possiblities if so. \$\endgroup\$
    – Steffan
    Aug 3 at 20:44
  • \$\begingroup\$ @Steffan yes, it is so \$\endgroup\$
    – Seggan
    Aug 3 at 20:45

5 Answers 5

6
\$\begingroup\$

Vyxal, 14 bytes

Þ∪Þx:ƛ□꘍GN;ÞMİ

Try it Online!

I think Þ∪ can be J, but that makes it so slow that it's practically impossible to run.

This is already really, really, really slow.

Þ∪Þx:ƛ□꘍GN;ÞMİ
Þ∪             # Get the multiset union of the two strings
  Þx           # Get all combinations without replacement of all lengths and of all orders
    :          # Duplicate (call this X)
     ƛ         # Over each:
      □꘍       #  For each of the inputs, get the Levenshthein distance between that input and this string
        G      #  Get the maximum of that
         N     #  Negate that
          ;    # Close map
           ÞM  # Get the indices of maximal elements. (If Vyxal had an "indices of minimal elements" builtin, then negate could be removed.)
             İ # Index this into X
\$\endgroup\$
1
  • 10
    \$\begingroup\$ It's bad form to answer your own challenge so soon... Oh, wait, \$\endgroup\$ Aug 3 at 18:40
4
\$\begingroup\$

05AB1E, 9 bytes

JæΣ.L{R}н

Outputs one possible result.

Try it online or verify all test cases.

Explanation:

J        # Join the (implicit) input-pair together to a single string
 æ       # Pop and get the powerset of this string
  Σ      # Sort it by:
   .L    #  Get the Levenshtein distance of the two strings with the (implicit) input
     {   #  Sort the pair from lowest to highest
      R  #  Reverse it from highest to lowest
  }н     # After the sort-by: leave the first result
         # (which is output implicitly as result)

Note: if we'd use à (max) instead of {R, it would also give results where the Levensthein distance is [2,2] even if [1,2] are available. If we'd use just {, it would give results where the Levensthein distance is [0,3] over [1,2]. So using the {R ensures the minimum pair while prioritizing the maximum of the pair.


Although it works for the test cases, I'm not 100% sure if is always correct. Using an additional group-by (and uniquify) to get all results shows that Stegfan and Segfan aren't among them for example, since the powerset builtin uses characters of the joined string in order. This could be fixed by changing it to Jœ€æ˜ [+3 bytes] (powerset of each permutation of the joined string), but it becomes extremely slow and it'll timeout.

\$\endgroup\$
4
\$\begingroup\$

Factor + lcs math.combinatorics, 123 120 78 bytes

[ 2dup append all-subsets [ tuck [ levenshtein ] 2bi@ max ] 2with infimum-by ]

Attempt This Online!

-42 bytes(!) using the idea behind @KevinCruijssen's 05AB1E answer.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 bytes

∑ṗµ?꘍sṘ;h

Try it Online!

Port of Kevin Cruijssen's answer, go upvote that!

\$\endgroup\$
1
\$\begingroup\$

Python, 150 bytes

n=lambda A,B:{a[:x]+y+a[z:]for a in A for x in range(len(a)+1)for z in[x,x+1]for b in B for y in[*b,""]}
f=lambda A,B:(N:=n(A,B))&(M:=n(B,A))or f(N,M)

Attempt This Online!

\$\endgroup\$

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.