Sea fla función que asigna un bitfield ( {0 1}) de tamaño n+1a bitfield de tamaño nal aplicar XORel ith y i+1th bit y escribir el resultado en el nuevo bitfield.

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

Cálculo informal:

0 XOR 1 = 1

1 XOR 0 = 1

0 XOR 1 = 1

Dejado f_inverseser la función inversa de f. Como el inverso no es único, f_inversedevuelve una solución válida.

Entrada: campo de bits como cadena (es decir "0101111101011") y un número natural dadok

Salida: campo de bits como cadena, de modo que la cadena contenga el resultado si f_inversese aplica kveces al campo de bits de entrada. (es decir f_inverse(f_inverse(f_inverse(input))))

Criterios ganadores: menos personajes

Prima:

-25Caracteres si f_inverseno se aplica de forma recursiva / iterativa, en su lugar, la cadena de salida se calcula directamente

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)

Puede pegarlo, por ejemplo, aquí y luego probarlo.

Pyth 33 30-25 = 5 bytes

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

Ejecútelo por entrada de stdin like (intérprete en línea: https://pyth.herokuapp.com/ ):

111
3

y el resultado se escribirá en stdout.

Esta es una traducción directa de:

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)

Llámalo como i("111", 3), y el resultado se escribirá en stdout.

Tenga en cuenta que esperamos que k no sea demasiado grande, ya que para el código de golf, el bucle interno se ejecutará O (2 ^k ) veces.

Creo que generalmente llamamos a esta operación "xorshift" o algo así. Si expresamos la entrada como enteros big-endian, entonces la función f es simplemente:

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

Si aplicamos f dos veces obtendremos:

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

Sin embargo, aplicar 3 veces tendrá un patrón diferente:

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

Aplicando 4 veces vuelve a la forma básica:

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

Y así:

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

Tenga en cuenta que si elegimos un 2 ^{k lo} suficientemente grande , entonces (x ≫ 2 ^k ) = 0, lo que significa f ^{2 k} (x) = x, ¡y la inversa es trivialmente la función de identidad!

Por lo que la estrategia para encontrar f ^k (x) sin llamar a f ^-1 (x) en absoluto es:

1. Encuentra K tal que:

   • K ≥ k
   • K> log ₂ x
   • K es una potencia de 2

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

3. Por lo tanto, el resultado se fllama Kk veces

4. 25 caracteres de beneficio: p

Actualización 1 : Se utilizó la representación octal en lugar de la binaria para poder usar el %formato para guardar muchos bytes.

Actualización 2 : Explotar la estructura periódica de f. Retiró la versión iterativa ya que la no iterativa es más corta incluso sin la bonificación de -25 bytes.

Actualización 3 : reducción de 3 bytes de Pyth, ¡gracias isaacg!

CJam, 15 14 bytes

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

Toma entrada como

"111" 3

Pruébalo aquí.

Explicación

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.";

El resultado se imprime automáticamente al final del programa.

Digo "cadena / matriz", porque empiezo con una cadena (que es solo una matriz de caracteres), pero sigo tomando XOR entre ellos y también entre números. Character Character ^da un número entero (basado en el XOR de los puntos de código) Character Integer ^y Integer Character ^da un carácter (basado en el XOR del número con el punto de código, interpretado como un punto de código). Y, Integer Integer ^por supuesto, solo da un número entero.

Entonces, los tipos están volando por todo el lugar, pero afortunadamente, cada vez que tengo un número entero es 0o1 y cada vez que tengo un personaje que es ya sea '0e '1y el resultado es siempre el uno deseado (en cualquier tipo). Dado que las cadenas son solo matrices de caracteres, mezclar caracteres con números no es un problema en absoluto. Y al final, cuando todo se imprime, los caracteres no obtienen delimitadores especiales, por lo que la salida no se ve afectada por qué bit se representa como un número o un carácter.

J, 17 caracteres

Siempre usando 0 como el primer dígito.

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

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

Comenzando desde el estado 128 1 de la fila superior (izquierda) y un estado aleatorio (derecha), que muestra los últimos 128 dígitos hasta la primera iteración 129.

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

APL 11

((0,≠\)⍣⎕)⎕

Explicación:

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

Probar en tryapl.org

CJam, 25-25 = 0 bytes

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

Este es solo un puerto directo de CJam de la respuesta de GolfScript a continuación, ya que, después de leer la respuesta de Martin Büttner , me di cuenta de que podía guardar un byte debido al manejo de CJam de tipos enteros y de caracteres. (Básicamente, CJam no necesita el 1&usado para forzar caracteres ASCII en bits en el código GolfScript, pero requiere un antecedenteq para leer la entrada). Normalmente consideraría que un puerto tan trivial es un truco barato, pero lograr un puntaje cero hizo OMI vale la pena.

En cualquier caso, este programa funciona exactamente como el programa GolfScript original a continuación, por lo tanto, consulte su descripción y las instrucciones de uso. Como de costumbre, puede probar la versión de CJam utilizando este intérprete en línea .

GolfScript, 26-25 = 1 byte

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

Esta solución itera sobre la cadena de entrada solo una vez, por lo que creo que califica para la bonificación de −25 bytes. Funciona manteniendo internamente una matriz de elementos k que almacena el bit actual de cada una de las k iteraciones previas.

La entrada debe darse a través de stdin, en el formato "1111111" 3, es decir, como una cadena entre comillas 0y 1caracteres, seguida del número k . La salida será stdout, como una cadena de bits sin comillas.

Prueba este código en línea. (Si el programa se agota, intente volver a ejecutarlo; el servidor Web GolfScript es conocido por los tiempos de espera aleatorios).

Aquí hay una versión ampliada de este programa, con comentarios:

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

Básicamente, como la mayoría de las soluciones iterativas, se puede entender que este código aplica la recurrencia

        b _{i , j} : = b _{i , ( j −1)} ⊕ b _{( i −1), ( j −1)} ,

donde b _{0, j} es el j -ésimo bit de entrada (para j ≥ 1), b _{k , j} es el j -ésimo bit de salida, y b _{i , 0} = 0 por supuesto. La diferencia es que, mientras que las soluciones iterativas, en efecto, calculan la recurrencia "fila por fila" (es decir, primero b _{1, j} para todo j , luego b _{2, j} , etc.), esta solución en cambio la calcula "columna por columna "(o, más exactamente," diagonal por diagonal "), primero computando b _{i , i} para 1 ≤ i≤ k , luego b _{i , i +1} , luego b _{i , i +2} , etc.

Una ventaja (teórica) de este enfoque es que, en principio, este método puede procesar una cadena de entrada arbitrariamente larga utilizando solo almacenamiento O ( k ). Por supuesto, el intérprete de GolfScript lee automáticamente todas las entradas en la memoria antes de ejecutar el programa de todos modos, sobre todo negando esta ventaja.

Python, 94 78

Se ejecutará al menos una vez y, por lo tanto, da el mismo resultado para n=0yn=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

Versión anterior que convierte la cadena en una matriz numérica y "integra" el módulo 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

Pitón 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

Una solución totalmente recusiva. Es más fácil de entender si se divide en dos funciones.

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

donde fcalcula diferencias sucesivas y gcompone fconsigo mismo n veces.

La función fcalcula las sumas XOR acumulativas de l, que es la operación inversa a las sucesivas diferencias XOR. Dado que la entrada se da como una cadena, necesitamos extraer int(l[0]), pero hacerlo más corto con la comparación de cadenasl>='1' .

Pitón 2, 69

Una solución iterativa usando un execbucle resultó 1 char más tiempo.

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

Tal vez hay una forma más corta de lidiar con la cuerda. Si pudiéramos tener entradas / salidas como listas de números, ahorraríamos 5 caracteres

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

Perl 5, 34

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

Parámetros dados en la entrada estándar separados por un espacio.

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

Javascript ES6, 47 caracteres

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

Por cierto, no hay efectos secundarios :)

C # - 178 161 115 caracteres

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);}

Sin golfista con arnés

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])));
        }
    }
}

CJam, 20 bytes

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

La entrada es como "111" 3

Pruébalo en línea aquí