# Half-reverse a binary string

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.

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

# CJam, 32 bytes

1q1]s:~__W%.&_,2/0t0#2%{2>W%2>}|


Try it online.

Too long...

# 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]


Ungolfed:

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.

• ...When will the ungolfed code be updated? – CalculatorFeline Mar 8 '16 at 5:16
• @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. – 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"


halfreverse.pl:

/^(.+?)((\1\1?)*)$/;$_=$3eq$1?reverse$2:$_.$1  ## Explanation /^$/         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

• How does it work?? – CalculatorFeline Mar 8 '16 at 1:03