13
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Can you give some test cases to verify. \$\endgroup\$ – Optimizer Feb 6 '15 at 12:43
  • 3
    \$\begingroup\$ Could you please stop calling them {0-1}-Bitfields? Also I don't understand the definition of f, where does i come from? What is the second argument of XOR? how do we get 111 from 0101? \$\endgroup\$ – mniip Feb 6 '15 at 12:47
  • \$\begingroup\$ What is a better name? i denotes the index \$\endgroup\$ – nvidia Feb 6 '15 at 12:49
  • \$\begingroup\$ Just a "bitfield" would do. What is the /value/ of i? "0 XOR 1" = 1 "1 XOR 0" = 1 "0 XOR 1" = 1 doesn't explain anything: I know how XOR works, but what exactly are we XORing and where are we storing the result? \$\endgroup\$ – mniip Feb 6 '15 at 12:55
  • 9
    \$\begingroup\$ I think he means: f([a,b,c,d]) = [a^b, b^c, c^d]. And he wants the inverse of that function, i.e f'([x,y,z]) = [a,b,c,d] such that a^b=x, b^c=y, c^d=z. \$\endgroup\$ – marinus Feb 6 '15 at 12:58

11 Answers 11

14
\$\begingroup\$

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(2k) 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:

  • f2(x) = x ⊕ (x ≫ 2)

However applying 3 times will have a different pattern:

  • f3(x) = x ⊕ (x ≫ 1) ⊕ (x ≫ 2) ⊕ (x ≫ 3)

Applying 4 times get back to the basic form:

  • f4(x) = x ⊕ (x ≫ 4)

And so on:

  • f2k(x) = x ⊕ (x ≫ 2k)

Note that if we choose a big-enough 2k, then (x ≫ 2k) = 0, meaning f2k(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 > log2 x
    • K is a power of 2
  2. Express f-k(x) = f-K + (K-k)(x) = f-K(fK-k(x)) = fK-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!

\$\endgroup\$
  • \$\begingroup\$ As described in the tips: codegolf.stackexchange.com/a/45280/20080 you can replace the for loop and assignments with a reduce, like this: Jiz8K+lzQ%"%0*o",KuxG/G8rQ^2KJ \$\endgroup\$ – isaacg Feb 7 '15 at 22:43
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your excellent explanation of the character / number type behavior in CJam let me shave a byte off my solution, reaching 25 − 25 = 0 bytes. Thanks, and +1! \$\endgroup\$ – Ilmari Karonen Feb 7 '15 at 22:36
  • 2
    \$\begingroup\$ That type behavior is horrifying (+1). \$\endgroup\$ – ballesta25 Feb 8 '15 at 8:24
8
\$\begingroup\$

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

plot plot

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Couldn't run it on tryapl (how you give the inputs?) but ≠\ wouldn't work instead of 2|+\ ? \$\endgroup\$ – randomra Feb 6 '15 at 20:10
  • \$\begingroup\$ the ⎕'s are the inputs, if you use the same expression I wrote, the program should ask you for the numbers you want, first the binary vector, then a second time for the number of iterations. I used a and b in the link to tryapl, so it's executed without askin things. Also thanks for the ≠\!! \$\endgroup\$ – Moris Zucca Feb 6 '15 at 20:33
  • \$\begingroup\$ If I copy ((0,≠\)⍣⎕)⎕ I get invalid token. Tryapl can't handle inputs? \$\endgroup\$ – randomra Feb 6 '15 at 20:36
  • 1
    \$\begingroup\$ Hmmmm... you're right, it's happening the same to me. I'm using Dyalog APL and then tryapl just to post here, so I never noticed, sorry about that. \$\endgroup\$ – Moris Zucca Feb 6 '15 at 20:39
5
\$\begingroup\$

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

        bi,j := bi,(j−1)b(i−1),(j−1),

where b0,j is the j-th input bit (for j ≥ 1), bk,j is the j-th output bit, and bi,0 = 0 by assumption. The difference is that, whereas the iterative solutions, in effect, compute the recurrence "row by row" (i.e. first b1,j for all j, then b2,j, etc.), this solution instead computes it "column by column" (or, more accurately, "diagonal by diagonal"), first computing bi,i for 1 ≤ ik, then bi,i+1, then bi,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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ You need to accept a k parameter for the number of iterations. (The -25 bonus is for computing the result of the iterations without actually performing the iterations.) \$\endgroup\$ – Brilliand Feb 6 '15 at 21:33
  • \$\begingroup\$ I should've read specification carefully (facepalm) \$\endgroup\$ – Qwertiy Feb 6 '15 at 21:38
1
\$\begingroup\$

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])));
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$

CJam, 20 bytes

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

Input is like "111" 3

Try it online here

\$\endgroup\$
  • \$\begingroup\$ "011001" is the result from your code for your input but its not correct if you check \$\endgroup\$ – nvidia Feb 6 '15 at 13:25
  • \$\begingroup\$ @user3613886 Sorry, copied older version. Fixed now \$\endgroup\$ – Optimizer Feb 6 '15 at 13:30

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.