This is a follow-up question to my Puzzling.SE question: I asked if there’s a function f mapping Boolean strings to Boolean strings, so that f(f(b)) = reverse(b) for all input strings b. (By reverse, I mean the function that reverses the order of bits.)

The above link contains a positive answer, with proof, by the great f'', but you might want to ponder the question for yourself before looking.

Implement such a function f in as few bytes as possible.

  • You may either read input from STDIN, or take a function argument; and either write the result string to STDOUT, or return it.

  • Either way, you may work with actual strings of two distinct bytes or characters of your choice (say 0 and 1, or \x00 and \x01), or with arrays/lists of truthy and falsy values. Pick two values and stick with those, though.

  • The result of a single application of f must be a binary string itself: no silly answers like b -> if b starts with 'x' then reverse(b[1:]) else 'x' + b...

  • Your function should be total; in particular, the input may be the empty string, or one bit long, etc. There’s no upper bound for the string’s length.

  • It should also be pure: don’t keep any global state between function calls; the input string must completely determine the output string.

  • \$\begingroup\$ Can output have different length than input? \$\endgroup\$ – Luis Mendo Mar 7 '16 at 20:02
  • \$\begingroup\$ Sure! (In fact, otherwise, the challenge is provably impossible.) \$\endgroup\$ – Lynn Mar 7 '16 at 20:05
  • \$\begingroup\$ Does it have to work for strings of length one or zero? \$\endgroup\$ – CalculatorFeline Mar 7 '16 at 20:11
  • \$\begingroup\$ Yes; the function has to be total. I’ve clarified this in the question! \$\endgroup\$ – Lynn Mar 7 '16 at 20:12
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Mar 7 '16 at 20:36

CJam, 32 bytes


Try it online.

Too long...

| improve this answer | |

Python 2, 64 69 bytes

def f(s):p=(s+s).find(s,1);return[s[~p::-1],s+s[:p]][len(s)/p%2]


def f(s):
    p = (s+s).find(s,1)
    n = len(s)/p
    return s[:p][::1|n%-2] * -~(n-1^1)

This finds the string's period, i.e. the minimal p such that s is a string of length p repeated n times (I found a golfy method on SO). Then if n is odd, it adds one more repetition of the period. If n is even, it removes one repeat of the period and reverses it.

Thanks to @Sp3000 for helping to implement the function mapping between 1<->2, 3<->4, etc.

| improve this answer | |
  • \$\begingroup\$ ...When will the ungolfed code be updated? \$\endgroup\$ – CalculatorFeline Mar 8 '16 at 5:16
  • \$\begingroup\$ @CatsAreFluffy I have no plan to modify the ungolfed code as it uses the same idea with only a trivial difference. The English on the other hand is up-to-date. \$\endgroup\$ – feersum Mar 8 '16 at 5:26

Perl, 49 47 bytes

Includes +2 for -lp

Based on @feersum's very nice algorithm

Run with input on STDIN, e.g.

perl -lp halfreverse.pl <<< "101001"




/^               $/         Match the complete input string
  (.+?)                     Non-greedy match. Try only one digit at the start,
                            if that doesn't work try 2, then 3 etc. The string
                            being tried is remembered in backreference \1
       ((\1\1?)*)           Try to repeat \1 as many times as possible but
                            prefer in groups of 2. Fall back to only 1 at the
                            end of the string if the trailing part has an odd
                            number of \1 (so the total count is even)

   $3eq$1                   So the last match $3 equals the first match $1
         ?                  if and only if the total count is even
          reverse$2         If total count is even drop the first instance of
                   :        \1 and reverse
                    $_.$1   If total count is odd extend $_ by one instance
$_=                         Assign result
| improve this answer | |
  • \$\begingroup\$ How does it work?? \$\endgroup\$ – CalculatorFeline Mar 8 '16 at 1:03

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.