Compute the inverse XOR

Question

Let f be the function that maps a bitfield ({0 1}) of size n+1 to bitfield of size n by applying XOR to the ith and i+1th bit and writing the result in the new bitfield.

Example: f("0101") = "111"

Informal calculation:

0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1

Let f_inverse be the inverse function of f. Since the inverse is not unique, f_inverse returns one valid solution.

Input: bitfield as string (i.e. "0101111101011") and a given natural number k

Output: bitfield as string, so that the string contains the result if f_inverse is applied k times to the input bitfield. (i.e. f_inverse(f_inverse(f_inverse(input))) )

Winning criteria: fewest Characters

Bonus:

-25 Characters if f_inverse is not applied recursively/iteratively, instead the output string is directly calculated

Testscript:

a = "011001"
k = 3

def f(a):
    k = len(a)
    r = ""
    for i in xrange(k-1):
        r += str(int(a[i]) ^ int(a[i+1]))
    return r

def iterate_f(a, k):
    print "Input ", a
    for i in xrange(k):
        a = f(a)
        print "Step " + str(i+1), a

iterate_f(a, k)

You can paste it for example here and then try it.

Answer 1

Pyth, 33 30 - 25 = 5 bytes

Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ

Run it by input from stdin like (online interpreter: https://pyth.herokuapp.com/):

111
3

and the result will be written to stdout.

This is a direct translation of:

Python 2, 127 118 79 - 25 = 54 bytes

def i(s,k):
 l=int(s,8);t=len(s)+k
 while k<1<<t:l^=l/8;k+=1
 print'%0*o'%(t,l)

Call it like i("111", 3), and the result will be written to stdout.

Note that we expect k not being too large, since for code-golfing purpose the inner loop will run for O(2^k) times.

---

I think we usually call this operation "xorshift" or something. If we express the input as big-endian integers, then the function f is simply:

• f(x) = x ⊕ (x ≫ 1)

If we apply f twice we will get:

• f²(x) = x ⊕ (x ≫ 2)

However applying 3 times will have a different pattern:

• f³(x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)

Applying 4 times get back to the basic form:

• f⁴(x) = x ⊕ (x ≫ 4)

And so on:

• f^2k(x) = x ⊕ (x ≫ 2^k)

Note that if we choose a big-enough 2^k, then (x ≫ 2^k) = 0, meaning f^2k(x) = x, and the inverse is trivially the identity function!

So the strategy for finding f^-k(x) without calling f^-1(x) at all is:

1. Find K such that:

   • K ≥ k
   • K > log₂ x
   • K is a power of 2

2. Express f^-k(x) = f^{-K + (K-k)}(x) = f^-K(f^K-k(x)) = f^K-k(x)

3. Thus, the result is f called K-k times

4. 25 chars profit :p

---

Update 1: Used octal representation instead of binary so that we could use % formatting to save lots of bytes.

Update 2: Exploit the periodic structure of f. Retired the iterative version since the non-iterative one is shorter even without the -25 bytes bonus.

Update 3: Reduced 3 bytes from Pyth, thanks isaacg!

Answer 2

CJam, 15 14 bytes

l~{0\{1$^}/]}*

Takes input like

"111" 3

Test it here.

Explanation

l~{0\{1$^}/]}*
l~             "Read and evaluate input.";
  {         }* "Repeat k times.";
   0\          "Push a 0 and swap it with the string/array.";
     {   }/    "For each element in the string/array.";
      1$       "Copy the previous element.";
        ^      "XOR.";
           ]   "Wrap everything in a string/array again.";

The result is automatically printed at the end of the program.

I say "string/array", because I start out with a string (which is just an array of characters), but I keep taking XORs between them and between numbers as well. Character Character ^ gives an integer (based on the XOR of the code points), Character Integer ^ and Integer Character ^ give a character (based on the XOR of the number with the code point - interpreted as a code point). And Integer Integer ^ of course just gives an integer.

So the types are flying all over the place, but luckily, whenever I have an integer it's either 0 or 1 and whenever I have a character it's either '0 and '1 and result is always the desired one (in either type). Since strings are just arrays of characters, mixing characters with numbers is not a problem at all. And at the end, when everything is printed, characters get no special delimiters, so the output is not affected by which bit is represented as a number or a character.

Answer 3

J, 17 chars

Always using 0 as the leading digit.

   (~:/\@]^:[,~[$0:)

   3 (~:/\@]^:[,~[$0:) 1 1 1 
0 0 0 1 0 0

Starting from top row's 128 1's state (left) and a random state (right), showing the last 128 digits through the first 129 iteration.

   viewmat (~:/\)^:(<129) 128$1               viewmat (~:/\)^:(<129) ?128$2

Answer 4

APL 11

((0,≠\)⍣⎕)⎕

Explanation:

≠\  compare increasing number of elements (1 1 1 ->1 0 1)
0,    add a starting zero
()⍣⎕  repeat the function in parenthesis ⎕ times, ⎕ is the second argument
()⎕   apply all to ⎕, that is first argument

Try on tryapl.org

Answer 5

CJam, 25 − 25 = 0 bytes

q~1,*_@{[\{1$^}/_](;)\}/;

This is just a straight CJam port of the GolfScript answer below, since, after reading Martin Büttner's answer, I realized that I could save one byte due to CJam's handling of integer and character types. (Basically, CJam doesn't need the 1& used to force ASCII characters into bits in the GolfScript code, but does require a prepended q to read the input.) I would usually consider such a trivial port a cheap trick, but achieving a zero score made it IMO worthwhile.

In any case, this program works exactly like the original GolfScript program below, so please refer to its description and usage instructions. As usual, you can test the CJam version using this online interpreter.

---

GolfScript, 26 − 25 = 1 byte

~1,*.@{[1&\{1$^}/.](;)\}/;

This solution iterates over the input string only once, so I believe it qualifies for the −25 byte bonus. It works by internally maintaining a k-element array that stores the current bit of each of the k pre-iterates.

Input should be given via stdin, in the format "1111111" 3, i.e. as a quoted string of 0 and 1 characters, followed by the number k. Output will be to stdout, as a bitstring without quotes.

Test this code online. (If the program times out, try re-running it; the Web GolfScript server is notorious for random timeouts.)

---

Here's an expanded version of this program, with comments:

~             # eval the input, leaving a string and the number k on the stack

1,*           # turn the number k into an array of k zeros ("the state array")
.             # make a copy of the array; it will be left on the stack, making up the
              # first k bits of the output (which are always zeros)

@             # move the input string to the top of the stack, to be iterated over
{
  [           # place a start-of-array marker on the stack, for later use
  1&          # zero out all but the lowest bit of this input byte
  \           # move the state array to the top of the stack, to be iterated over

  { 1$^ } /   # iterate over each element of the state array, XORing each
              # element with the previous value on the stack, and leave
              # the results on the stack

  .           # duplicate the last value on the stack (which is the output bit we want)
  ]           # collect all values put on the stack since the last [ into an array
  (;          # remove the first element of the array (the input bit)
  )           # pop the last element (the duplicated output bit) off the array
  \           # move the popped bit below the new state array on the stack
}
/             # iterate the preceding code block over the bytes in the input string

;             # discard the state array, leaving just the output bits on the stack

Basically, like most of the iterative solutions, this code can be understood as applying the recurrence

        b_i,j := b_i,(j−1) ⊕ b_{(i−1),(j−1)},

where b_0,j is the j-th input bit (for j ≥ 1), b_k,j is the j-th output bit, and b_i,0 = 0 by assumption. The difference is that, whereas the iterative solutions, in effect, compute the recurrence "row by row" (i.e. first b_1,j for all j, then b_2,j, etc.), this solution instead computes it "column by column" (or, more accurately, "diagonal by diagonal"), first computing b_i,i for 1 ≤ i ≤ k, then b_i,i+1, then b_i,i+2, etc.

One (theoretical) advantage of this approach is that, in principle, this method can process an arbitrarily long input string using only O(k) storage. Of course, the GolfScript interpreter automatically reads all the input into memory before running the program anyway, mostly negating this advantage.

Answer 6

Python, 94 78

Will be executed at least once and thus gives the same result for n=0 and n=1

def f(x,n):
 c='0'
 for i in x:c+='10'[i==c[-1]]
 return f(c,n-1)if n>1 else c

Old version which converts the string to a numeric array and "integrates" modulo 2

from numpy import*
g=lambda x,n:g(''.join(map(str,cumsum(map(int,'0'+x))%2)),n-1)if n>0 else x

Answer 7

Python 2, 68

g=lambda l,n,s=0:n and g(`s`+(l and g(l[1:],1,s^(l>='1'))),n-1)or l

A totally recusive solution. It's easier to understand if broken into two functions

f=lambda l,s=0:`s`+(l and f(l[1:],s^(l>='1')))
g=lambda l,n:n and g(f(l),n-1)or l

where f computes successive differences and g composes f with itself n times.

The function f compute the cumulative XOR-sums of l, which is the inverse operation to successive XOR-differences. Since input is given as a string, we need to extract int(l[0]), but do so shorter with the string comparison l>='1'.

---

Python 2, 69

An iterative solution using an exec loop turned out 1 char longer.

l,n=input()
exec"r=l;l='0'\nfor x in r:l+='10'[l[-1]==x]\n"*n
print l

Maybe there's a shorter way to deal with the string. If we could have input/outputs be lists of numbers, it would save 5 chars

l,n=input()
exec"r=l;l=[0]\nfor x in r:l+=[l[-1]^x]\n"*n
print l

Answer 8

Perl 5, 34

#!perl -p
s/ .*//;eval's/^|./$%^=$&/eg;'x$&

Parameters given on the standard input separated by a space.

$ perl a.pl  <<<"1101 20"
101111011011011011010110

Answer 9

Javascript ES6, 47 chars

f=(s,k)=>k?f(0+s.replace(s=/./g,x=>s^=x),--k):s

By the way, there is no side effects :)

Answer 10

C# - 178 161 115 characters

static string I(string a, int k){var s = "0";foreach(var c in a)s+=c==s[s.Length-1]?'0':'1';return k<2?s:I(s,--k);}

Ungolfed with harness

using System;
using System.Text;

namespace InverseXOR
{
    class Program
    {
        static string I(string a, int k)
        {
            var s = "0";
            foreach (var c in a)
                s += c == s[s.Length - 1] ? '0' : '1';
            return k < 2 ? s : I(s, --k);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(I(args[0], Convert.ToInt32(args[1])));
        }
    }
}

Answer 11

CJam, 20 bytes

q~{:~0\{1$!_!?}/]s}*

Input is like "111" 3

Try it online here