12
\$\begingroup\$

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.

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

3 Answers 3

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ ...When will the ungolfed code be updated? \$\endgroup\$ Commented Mar 8, 2016 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\$ Commented Mar 8, 2016 at 5:26
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ How does it work?? \$\endgroup\$ Commented Mar 8, 2016 at 1:03
1
\$\begingroup\$

CJam, 32 bytes

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

Try it online.

Too long...

\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.