7
\$\begingroup\$

We're back! And this time with an objective scoring criteria!


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 combine and separate with respective types String × String → String and String → String × String such that separate ∘ combine = id.

More precisely, 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.

  • The functions need not actually be named combine and separate

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 ; the answer with the lowest score wins. Score is defined as number of bytes, except that it's -75% if combine ∘ separate = id as well (i.e., if combine is bijective and separate = combine⁻¹).

For brownie points, also try making your solution, in principle,

  • work on any alphabet rather than char, possibly including alphabets of size- 0, 1, or 2
  • generalize nicely to \$n\$-tuples or lists

Have fun!

\$\endgroup\$
9
  • \$\begingroup\$ Note: Bijection between binary strings and pairs thereof is very similar to this question. However, that question requires a bijection and works on bitstrings. I feel that while using strings as opposed to bitstrings is mathematically inconsequential, it will give rise to different kinds of answers. \$\endgroup\$
    – Quelklef
    Commented Mar 30, 2021 at 23:39
  • \$\begingroup\$ Also similar (originally from xnor): Surjection from one string to two strings, Injection from two strings to one string \$\endgroup\$
    – Quelklef
    Commented Mar 30, 2021 at 23:41
  • 7
    \$\begingroup\$ I'd suggest removing the deadline and just letting the challenge be open-ended. Additionally, see Things to avoid when writing challenges: Bonuses. Also, did you mean to remove the "Intent" section when copying over from the pop-con version? \$\endgroup\$ Commented Mar 31, 2021 at 0:03
  • \$\begingroup\$ @ChartZBelatedly Hey, thanks for the feedback. The "Intent" section is intentional (hah!), as that's still my goal with the challenge; it's just now in a code-golf format. The bonus is also intentional because I want to reward non-eval/repr solutions. Let me know if you think there is a better way to do that. \$\endgroup\$
    – Quelklef
    Commented Mar 31, 2021 at 0:56
  • \$\begingroup\$ Also, I've removed the deadline, as you suggested \$\endgroup\$
    – Quelklef
    Commented Mar 31, 2021 at 1:00

5 Answers 5

5
\$\begingroup\$

Jelly, 2 bytes

combine

Try it online!

separate

V

Try it online!

A boring, but short, solution. Uses Jelly's repr and eval atoms.

is the right-inverse of V, meaning that ṾV (the Jelly way of composing 2 functions) returns the argument unchanged. Therefore, if passed [A, B], ṾV will return [A, B]

The first program takes input as a pair [A, B] and unevals it. The second takes a string as input and evals it as a Jelly program


Just a quick precursor on strings and Jelly. Jelly does not like strings. At all. Internally, strings are just lists of characters to Jelly, and when outputting, Jelly will do all it can to "mash" everything together so that it doesn't look like it should. An example that you'd expect to output ['a', 'b', 'c', 2], or even ['abc', 2]. As such, the Footers of the two programs above contain code to print the strings as-is, as lists of characters. Unfortunately, this can make them difficult to read.

But how do the programs work? Well, most of the work is done by the combine function. The separate function is simply "eval the argument as Jelly code".

is a weird atom, as Jelly atoms go. It's entire purpose is to act as the inverse to V (as a side note, if an character has an "underdot" below it in Jelly, it's likely to be the "inverse" to the atom without that underdot. For example, O/ (ord/chr) or Y/ (join/split at newlines)) and the function it uses in the interpreter, jelly_uneval, is only used by one other atom, , which just prints the same value as .

However, does a pretty good job at yielding some Jelly code that, when evaluated, yields it's argument. I won't break down into the exact details, but it's able to handle when string delimiters such as are contained in the input, so is a pretty solid "uneval" atom, as these things go.

\$\endgroup\$
5
  • \$\begingroup\$ I don't think this is getting beaten in a while, so you win (also, you can apply the 75% bonus to get 0.5 score) \$\endgroup\$ Commented Mar 31, 2021 at 14:47
  • \$\begingroup\$ Can you explain how V (evaluate as a Jelly program) is able to 'produce two strings as a result' when given any single string as an argument, especially if the string isn't a valid Jelly program? I tried it online with the input string def and it didn't seem to work (but maybe I don't understand the TIO footer gubbins...) \$\endgroup\$ Commented Apr 1, 2021 at 8:20
  • \$\begingroup\$ @DominicvanEssen V (in this case) takes the output of as its argument. This will be a string containing at least one comma, where the two things either side of that comma are valid Jelly strings. For example "“abc”,”d". It then evals this and returns a two element list containing the separated strings. The TIO Footer just prints the input and output of the function, but prints their "internal" representation as Jelly messes with string output quite a lot \$\endgroup\$ Commented Apr 1, 2021 at 8:49
  • 2
    \$\begingroup\$ I think this is invalid. The spec says that 'separate' should 'produce two strins as a result' when 'invoked with a single string'. It doesn't say that you can selectively choose only strings that were previously generated with your 'combine' function. \$\endgroup\$ Commented Apr 1, 2021 at 8:55
  • \$\begingroup\$ @DominicvanEssen I read the question to mean that (because you don't have to handle a bike toon), that the input to separate would always be a combined string. If the OP days otherwise, I'll happily delete/fix the answer \$\endgroup\$ Commented Apr 1, 2021 at 11:23
2
\$\begingroup\$

R, 280 202 207 196 (39+157) bytes

Edit: +5 bytes to fix bug pointed-out by ChartZ Belatedly

Combine, 39 bytes

function(a,b,`-`=nchar)paste(-a,-b,a,b)

Try it online!

Separate, 157 bytes

function(x,`-`=nchar,s=substring,q=as.double(el(strsplit(x," "))[1:2]),y=s(x,sum(3,-q)))`if`(any(is.na(q))||-y!=sum(q)+1,c(x,""),s(y,c(1,q[1]+2),c(q[1],-y)))

Try it online!

Not bijective and probably not shorter than a Cantor-pairing based approach, but I like this because all the output is kind-of readable.

combine function calculates the lengths of strings a and b, encodes them as printable-ASCII, and prefixes them to the concatenated strings (with single space separators).
separate reads the characters before the first spaces, converts these to expected string-lengths, and splits-up the string accordingly. If there are any problems (which will almost always occur if the string wasn't contructed using combine) it outputs a zero-length second string.


R, 111 84 (41+43) bytes

Edit: -27 bytes by simply filling the first output string of 'separate' with an error message if the input string wasn't generated by 'combine'.

Combine, 41 bytes

function(a,b)capture.output(dput(c(a,b)))

Try it online!

Separate, 43 bytes

function(x)c(try(eval(parse(t=x))),'')[1:2]

Try it online!

Still not bijective, but a bit more competitive at the cost of being boring. A loose port of ChartZ's Jelly eval-uneval approach, but adjusted so that it will yield 2 strings as output with any string, not just with eval-able R code.

combine function constructs a string expression representing R vector containing the two strings a and b.
separate tries to evaluate its argument as R code, and puts an error message into an output string if it fails. It then appends an empty string, and returns the first two elements (so non-R code, as well as valid R code that would output more than one string-like return value, all finally output 2 strings).

\$\endgroup\$
4
  • \$\begingroup\$ Cool! So for instance combine "fancy" "pants" would be "5 5 fancypants"? \$\endgroup\$
    – Quelklef
    Commented Mar 31, 2021 at 16:47
  • 1
    \$\begingroup\$ Embarassingly, the "fancy" "pants" test case exposed an unforeseen bug! It's fixed now (pleasingly for less bytes), and it indeed outputs more-or-less as you say: see the TIO links. \$\endgroup\$ Commented Mar 31, 2021 at 18:06
  • \$\begingroup\$ This fails if one of the strings starts with a number and a space \$\endgroup\$ Commented Apr 1, 2021 at 8:55
  • \$\begingroup\$ @ChartZBelatedly - Yikes! You're right! Fixed now (I think)... thanks for spotting that! \$\endgroup\$ Commented Apr 1, 2021 at 9:05
1
\$\begingroup\$

Python 3.8 (pre-release), 44 bytes

c=lambda *args:repr(args)
s=lambda x:eval(x)

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The separate command does not seem to work on the string "abc": try it... \$\endgroup\$ Commented Apr 1, 2021 at 15:45
  • \$\begingroup\$ @DominicvanEssen you're right, I approached it as combine first, separate second. On the other hand I think it's reasonable for separate to accept only strings that the corresponding combine could have produced. Especially since separate(combine(a,b)) MUST work. \$\endgroup\$
    – hugovdberg
    Commented Apr 1, 2021 at 15:57
1
\$\begingroup\$

Husk, 59 (21+38) bytes -75% = score of 14.75

Combine, 21 bytes:

mcB128FS+ȯΣḣ+moB128mc

Try it online!

Separate, 38 bytes

momcB128₁B128mc
§e_o+₂¹-¹½S*→₂
÷2←√→*8

Try it online!

Bijective functions: each functions converts the input string(s) to a number by interpreting the codepoints in base-128, and then applies Cantor pairing to exchange between an integer and a pair of integers, before converting back to a string. This can result in strings that contain unprintable characters, so the following testing links use modified versions that output the codepoints:

separate to codepoints = converts "abcd" into the strings with codepoints [6,5] and [1,24,21]
combine from codepoints = converts that back to "abcd"

combine to codepoints = converts strings "abc" and "def" to the string with codepoints [1,26,2,55,4,35,112]
separate from codepoints = converts that back to "abc", "def"

Alternatively, here (combine (27 bytes); separate (44 bytes) - score of 17.75) are versions with input/output restricted to the printable ASCII values 32-126.

\$\endgroup\$
4
  • \$\begingroup\$ Cool! Would this have any issues with \x00-prefixed strings? \$\endgroup\$
    – Quelklef
    Commented Apr 2, 2021 at 15:35
  • \$\begingroup\$ @Quelklef - Good Q. No. Husk doesn't seem to be worried about null bytes in strings (I've just tested it!): Here is a program that creates a string with codepoints 0...127, and here is one that converts this back to codepoints (to check whether the null byte was somehow lost: it wasn't!). \$\endgroup\$ Commented Apr 4, 2021 at 14:44
  • \$\begingroup\$ @Quelklef - in any case (and to make testing easier), I've added a modified version that restricts input/output to printable ASCII from 32-126... \$\endgroup\$ Commented Apr 4, 2021 at 14:46
  • \$\begingroup\$ Cool! I'd have thought any "treat it as a number"-based solution would have trouble with leading zeros. \$\endgroup\$
    – Quelklef
    Commented Apr 5, 2021 at 15:30
1
\$\begingroup\$

Python 3.8 (pre-release), 196 bytes

import itertools as i
c=lambda a,b:(f:=chr(ord((sorted(a[-1:]+b[-1:])or'\x00')[-1])+1))+''.join(sum(i.zip_longest(a,b,fillvalue=f),start=()))
s=lambda x:(x[1::2].rstrip(x[0]),x[2::2].rstrip(x[0]))

Try it online!

Slightly less boring than my other try, at the expense of being much longer. Unfortunately c(s(x)) might not return exactly the same string, if a different fill value is specified than automatically would be determined.

How it works

c(ombine) interleaves the two strings, with input a on the even positions and input b on the odd positions. As the strings need not be of equal lenght the shortest one is padded with fill character f. This is determined by taking the last character of both strings, sorting them and then taking the next codepoint as fillvalue. This fill value is then also prepended to the output to tell separate which characters to strip.

s simply takes every other character from the second character on, and strips all occurences of the fill value that's stored in the first character of the input, and then does the same for every other character from the third character on.

\$\endgroup\$
3
  • \$\begingroup\$ How does it work? \$\endgroup\$
    – Quelklef
    Commented Apr 2, 2021 at 15:34
  • \$\begingroup\$ What will happen if either of the strings contains the last possible codepoint value in an alphabet? Will the fill-value wrap-around, or will it crash? And, if wrapping-around, what would happen if either string also already contains the first codepoint value? Or, worst-case scenario, all codepoint values? \$\endgroup\$ Commented Apr 9, 2021 at 7:25
  • \$\begingroup\$ Luckily it doesn't remove all occurences of the fill value, but just the right padding. As we take only two strings as input there are exactly two codepoint values we need to consider, so there would be no problem if the rest of the string would be all codepoint values. Currently it will crash if either ends with the last possible codepoint value, as it does not wrap around. Knew that limitation but did not know a robust way to prevent collision with the other string. \$\endgroup\$
    – hugovdberg
    Commented Apr 9, 2021 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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