10
\$\begingroup\$

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 ; the answer with the highest score at noon on April 5th, UTC, is the winner.

Guidelines for voters, included to be a valid , 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!

\$\endgroup\$
14
  • 3
    \$\begingroup\$ Should combine ∘ separate also be an identity function? \$\endgroup\$ – user Mar 29 at 22:38
  • 7
    \$\begingroup\$ I've voted to close this as lacking an objective winning criteria. Popularity contests need clear rules about what voters should be looking for, rather than just specifying a task and saying "Do this, but creatively". The fact that this boring answer currently has a score of +3 means that either the voting on this challenge is too subjective, or voters aren't following your intent well enough for this to remain open \$\endgroup\$ – caird coinheringaahing Mar 29 at 23:07
  • 2
    \$\begingroup\$ @ChartZBelatedly If popularity contests require a winning criteria besides popularity, then I don't understand the point of the category. But that is a question for elsewhere. Truth is, I don't have another winning criteria; I just wanted to share what I think is an interesting challenge that can inspire creativity and that people will enjoy. I thought popularity-contest would be the right tag for that. Is there another? \$\endgroup\$ – Quelklef Mar 29 at 23:12
  • 6
    \$\begingroup\$ @Quelklef I'm sorry the Sandbox was really unhelpful here. I see that you Sandboxed this challenge, leaving it for four days and getting two upvotes, but nobody said anything about popularity contests or left any comments. If I'd read it, I'd have strongly suggested changing it to code-golf and still do now. I find that a lot of interesting unexpected approaches come out of trying to shorten code, by getting to the heart of the algorithm and playing to the strengths of each particular language. \$\endgroup\$ – xnor Mar 30 at 1:28
  • 4
7
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

⪫E²⪫ES℅λ,¦;

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

Separate

E⪪S;∧ι⭆⪪ι,℅Iλ

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

\$\endgroup\$
2
\$\begingroup\$

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

⪫E²⭆S⎇ι⁺λ,⁺,λ;

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

Separate

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

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

\$\endgroup\$
2
\$\begingroup\$

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.

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

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)

\$\endgroup\$
7
  • \$\begingroup\$ Are you sure this works if the strings to combine themselves contain asterisks? \$\endgroup\$ – xnor Mar 30 at 10:38
  • \$\begingroup\$ If the second one has an asterisk, it will be preserved (note the clever use of the split("*", 2), preventing more than one split): the only issue I can see is if the first one has an asterisk. I'm not sure how you would go around that (same with the second one) \$\endgroup\$ – StackMeter Mar 30 at 10:42
  • \$\begingroup\$ This is very interesting. What is the reason for repeating the string in the first solution? Also, as xnor and you have noticed, it seems that this will fail if the first string contains an asterisk. For the second solution, similar notes: what's the purpose of the hex encoding, and won't this fail if the first string contains a colon? \$\endgroup\$ – Quelklef Mar 30 at 15:43
  • 1
    \$\begingroup\$ To answer your questions - 1) No reason, really, just because I thought it would be cooler. 2) Yes, it would fail if the first string contained a colon (or asterisk in the other code), but unfortunately, I don't think split() works with non-printable ascii characters. \$\endgroup\$ – StackMeter Mar 30 at 16:46
  • \$\begingroup\$ For a solution to be valid, it technically must work for every possible string pair. If you want a valid solution, you're gonna have to get a little more clever ;) \$\endgroup\$ – Quelklef Mar 30 at 19:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.