(Σ*)² ⟲ Σ* (aka Round-Trip a String Pair) [closed]

Question

This is a challenge I thought of recently which I think is not hard but allows for a wide range of possible solutions. Seems like a perfect fit for the creativity of PPCG users :)

Your Task

Define two functions which together form a lossless round-trip String × String → String → String × String.

More specifically, define two functions combine and separate with repsective types String × String → String and String → String × String such that separate ∘ combine = id.

Even more specifically, define two functions (or methods/procedures/etc), which I will refer to as combine and separate, and which exhibit the following characteristics:

• When invoked with a single string, separate produces two strings as results. (You may use any reasonable string type. Most languages don't canonically allow producing multiple values, so feel free to to do something equivalent, such as returning a 2-tuple or modifying two global variables.)

• When invoked with two strings, combine produces a single string as result. (You may accept input to separate in the same form that combine produces, or any other reasonable form.)

• For any two strings a and b, separate(combine(a, b)) must result in two strings which are (structurally) equivalent to a and b.

• The above bullets are the only restrictions on combine and separate. So, for instance, combine ∘ separate need not be id, and separate can even be a partial function, if you like.

(Defer to the final and more-verbose description if there are any ambiguities between the three)

Intent

My goal with this challenge is to inspire creative and interesting solutions. As such, in order to avoid priming/suggesting your thinking about how to solve this problem, I will not be providing test cases, and I strongly suggest that you do not look at the existing answers until you submit your own.

Winning Criteria

This challenge is a popularity-contest; the answer with the highest score at noon on April 5th, UTC, is the winner.

Guidelines for voters, included to be a valid popularity-contest, are as follows:

• Strongly prefer answers which you do not immediately comprehend, are not obviously correct, and/or surprise you
• Prefer answers which go beyond strings, i.e., those which make use of more than the problem statement did (functions, strings, pairs)
• Avoid answers which are similar to your own solution(s)
• Avoid answers which boil down to language builtins

---

Have fun!

Answer 1

I know this is extra credit, but your problem got me thinking a lot about this and what interested me the most was not just separate being the left inverse of combine, but having them be true inverses of each other. This ends up with us defining a bijection from String -> String x String. The path I took was as follows

• Define a bijection from String -> N
• Define a bijection from N -> N x N
• Combine them to get the functions we need

String -> N

Let r be the size of the character set you're working with and give each character a unique value from 1 to r, say f(c) = n. Going from right to left and indexing starting from zero, create the number f(s[0])r^0 + f(s[1])r^1 + f(s[2])r^2 ... f(s[length(s)])r^(length(s)). The lowest number you can get this way is 1, so we let the empty string equal 0.

N -> N x N

Take n in any base you like. Separate even digits into one part of the tuple and the odd digits into the other to make a pair of numbers. E.g. 12345 -> (24, 135). To work your way back, combine the numbers in the opposite way, inserting extra zeros as necessary.

Putting it all together

Haskell

module Main where

import Data.Function ((&))
-- tio is saying this isn't correct for some reason so gotta define it manually
-- import Data.Functor ((<&>))

main :: IO ()
main = do
  putStrLn $ show $ separate "Hello, world!"
  putStrLn $ combine ("Hello, world!", "")
  putStrLn $ show $ separate $ combine ("Hello, world!", "")
  putStrLn $ combine $ separate "Hello, world!" 

separate :: String -> (String, String)
separate str =
  str
  <&> toInt
  & fromNZ
  & split
  & tmap toNZ
  & tmap (map fromInt)

combine :: (String, String) -> String
combine strs =
  strs
  & tmap (map toInt)
  & tmap fromNZ
  & join
  & toNZ
  <&> fromInt

base :: Int
base = 95

toInt :: Char -> Int
toInt c = fromEnum c - 31

fromInt :: Int -> Char
fromInt i = toEnum $ i + 31

strip :: [Int] -> [Int]
strip is = case is of
  0 : i : tail -> strip $ i : tail
  _ -> is

split :: [Int] -> ([Int], [Int])
split =
  tmap strip . fst . foldr
    (\a ((acc1, acc0), i) ->
      (if mod i 2 == 0 then
        (acc1, a : acc0)
      else
        (a : acc1, acc0)
      , i + 1
      )
    )
    (([], []), 0)

join :: ([Int], [Int]) -> [Int]
join (l1, l2)= strip $ reverse $ go [] (reverse l1, reverse l2)
  where
    go :: [Int] -> ([Int], [Int]) -> [Int]
    go acc (l1', l2') = case (l1', l2') of
      (head1 : tail1, head2 : tail2) -> head2 : head1 : go acc (tail1, tail2)
      ([], head : tail) -> head : 0 : go acc ([], tail)
      (head : tail, []) -> 0 : head : go acc (tail, [])
      ([], []) ->  acc

tmap :: (a -> b) -> (a, a) -> (b, b)
tmap f (a1, a2) = (f a1, f a2)

fromNZ :: [Int] -> [Int]
fromNZ is =
  if is == [] then [0]
  else let
    (result, finalCarry) =
      foldr
        (\i' (acc, carry) ->
          let
            i =
              if carry then i' + 1
              else i'
          in
            if i >= base then (i - base : acc, True)
            else (i : acc, False)
        )
        ([], False)
        is
  in
    if finalCarry then 1 : result
    else result

toNZ :: [Int] -> [Int]
toNZ is =
  if is == [0] then []
  else let
    (result, finalUncarry) =
      foldr
        (\i' (acc, uncarry) ->
          let
            i =
              if uncarry then i' - 1
              else i'
          in
            if i <= 0 then (i + base : acc, True)
            else (i : acc, False)
        )
        ([], False)
        is
  in
    if finalUncarry then
      case result of
        a : tail ->
          if a == base then tail
          else result
        _ -> result
    else result

m <&> f = f <$> m
infixl 1 <&>

Try it online!

Answer 2

Charcoal

Simply lists the code points in both strings. Within each string, code points are delimited with commas, and the two strings's code points are separated with a semicolon. The only gotcha is to ensure that empty strings decode to empty strings.

Combine

⪫Ｅ²⪫ＥＳ℅λ,¦;

Try it online! Link is to verbose version of code.

Separate

Ｅ⪪Ｓ;∧ι⭆⪪ι,℅Ｉλ

Try it online! Link is to verbose version of code.

Answer 3

Charcoal

Works by prefixing each character of the first string with a comma, suffixing each character of the second string with a comma, and then joining the strings with a semicolon. This simplifies decoding as there are an equal number of commas and original characters. There is a slight Charcoal gotcha in that it can't chop a zero-length string, so to obtains the first string the decoder chops the original string at the semicolon before stripping the commas (still one byte shorter than slicing though), while for the second string it can strip the commas first and then slice from where the semicolon used to be.

Combine

⪫Ｅ²⭆Ｓ⎇ι⁺λ,⁺,λ;

Try it online! Link is to verbose version of code.

Separate

≔⌕Φθ¬﹪κ²;η⟦Φ…θ⊗η﹪κ²✂Φθ﹪κ²η

Try it online! Link is to verbose version of code.

Answer 4

JavaScript

const obfuscate = str => [...str].map(e=>e.charCodeAt(0).toString(36) + '?').join``;
const combine = (first, second) => obfuscate(first) + ' ' + obfuscate(second);
const separate = string => string.split(' ').map(x =>x.split('?').filter(b=>b).map(el => String.fromCharCode(parseInt(el, 36))).join``);

In this case, separate is a partial function because it is only defined on specially formatted strings generated by combine. The obfuscate helper function turns the input string into an array of strings composed of the base-36 representation of the current character codepoint, plus a question mark. The array is then joined and returned. Then, combine returns the obfuscation of the first string, a space, then an obfuscation of a second string. separate undoes obfuscate on both strings and returns the array, in essence. Upon reading the answers, I found out that I sorta ported @Neil's answer with the difference being that I used a base-36 representation.

Answer 5

Can't let @Mason have it for free (edit 1: also @Neil posted as I write this), so I'm dropping in with answer number 4 and 5 (edit 2: goddamn someone posted another answer): the python convertors.

Answer One: the easy version

(string conversion using split())

import math
def combine(stringA, stringB):
  stringC = stringA + "\n" + stringB
  len1 = len(stringC)
  stringD = stringC * len1
  return stringD
def seperate(stringE):
  len2 = math.isqrt(len(stringE))
  stringF = stringE[0:len2]
  stringG, stringH = stringF.split("*", 2)
  return stringG, stringH

This functions takes two strings, combines them with an asterisk and then multiplies them by their combined length (plus the asterisk). To decode, it takes the square root of the length, splits ton the asterisk, and returns the strings (tested).

Now for the hard version.

Answer Two: the actually hard version

(hex conversion)

def combine2(stringI, stringJ):
  stringK = stringI + "\n" + stringJ 
  integerA = stringK.encode().hex()
  integerB = int(integerA, 16)
  return integerB
def seperate2(integerC):
  integerD = (int(integerC))
  integerE = hex(integerD)
  stringL = str(integerE)
  stringM = stringL[2:]
  stringN = bytes.fromhex(stringM).decode('ascii')
  stringO, stringP = stringN.split(":")
  return stringO, stringP

Three years later and I've actually done it: this code can first convert a string to hex, return that, then take that hex string (note, leave the 0x in or the first character will be removed) and convert it to the string that you originally had (again, painfully tested). (Edit 3: now you can't break it - newlines can't appear in input)