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\$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.