En un accidente muy inusual que involucra una pequeña muestra de radio, una ballena electrocutada y tres ositos de goma, se ha mutado parte del código fuente de The Management ™. Poco sabe el jefe de The Management ™, en realidad fueron los policías los responsables, en un intento por frustrar los planes "malvados" de The Management ™. Entonces, los Robbers® han sido contratados en un intento de recuperar el código original, porque ¿a quién no le gusta ser malvado a veces?

nota: Este desafío se inspiró en gran medida en Descifrar el código fuente .

Descripción

Este es un desafío de policías y ladrones .

• Los policías escribirán un programa (el código mutado) que realiza la Tarea # 1 (y también escriben un programa que realiza la Tarea # 2, pero se mantiene en secreto).
• Los ladrones intentarán revertir la "mutación" y cambiar este código original en un código que realice la Tarea # 2.

En este desafío, la Tarea n. ° 1 será la salida del nnúmero primo y la Tarea n. ° 2 será el nnúmero de Fibonacci (que de alguna manera es malo, de acuerdo con los Cops © de todos modos). La secuencia de Fibonacci se define como ( n=1→ 1; n=2→ 1; n=3→ 2; ...), y los números primos se definen como ( n=1→ 2; n=2→ 3; n=3→ 5; ...).

El objetivo de los policías es minimizar la diferencia entre los programas que completan la Tarea n. ° 1 y la Tarea n. ° 2, mientras se evita que los ladrones vuelvan a crear el código que completa la Tarea n. ° 2.

Reglas de policía

Los policías escribirán dos programas (uno que complete la Tarea # 1 y otro que complete la Tarea # 2), y harán pública la siguiente información:

• El primer programa (que genera el nnúmero primo th)
• La distancia de edición de Levenshtein entre el primer programa y el segundo programa
• El lenguaje de programación en el que ambos programas están escritos (debe ser el mismo lenguaje para ambos programas)

Las siguientes restricciones se aplican a ambos programas:

• Deben tener 128 caracteres de longitud o menos.
• Solo deben usar ASCII imprimible (más líneas nuevas, que también están permitidas).
• Deben tardar menos de 10 segundos en ejecutarse n=45y no están obligados a producir la salida correcta para ninguno n>45.
• No deben usar ninguna función hash o criptográfica.

Reglas de ladrones

El ladrón intentará cambiar el programa del policía (que completa la Tarea # 1) en un programa que complete la Tarea # 2 (no necesariamente el programa original escrito por el policía) en la distancia de edición especificada por el policía.

Un envío ya agrietado no se puede volver a agrietar (solo el primer ladrón que descifra un envío obtiene crédito).

Después de descifrar un envío, haga lo siguiente:

• Publique una respuesta a la pregunta adjunta (enlace) de este desafío , proporcionando el idioma, su solución y un enlace a la respuesta original.
• Deje un comentario con el texto "Agrietado" que se vincula a su respuesta publicada.
• Edite la respuesta del policía si tiene privilegios de edición (si no los tiene, espere hasta que otra persona con los privilegios necesarios lo haga por usted o sugiera una edición).

Tanteo

Si el programa de un policía permanece sin descifrar durante 1 semana, el policía puede publicar el código original que completa la Tarea # 2 (en la distancia de edición especificada), y el envío se considera a partir de ese momento "seguro". La presentación segura que tenga la menor distancia de edición ganará. En caso de empate, gana el programa más corto (el original que completa la Tarea # 1). Si dos envíos aún están empatados, el que se publicó anteriormente gana.

Si un ladrón descifra con éxito el envío de un policía, la puntuación del ladrón aumenta en la distancia de edición de ese envío. Por ejemplo, un ladrón que descifra un envío con una distancia de edición de 3 y uno con una distancia de 5 gana 8 puntos. El ladrón con el puntaje más alto gana. En caso de empate, el ladrón que obtuvo el puntaje primero gana.

Tabla de clasificación

1. Ruby, 6 (histocrat)

Una pequeña herramienta para calcular la distancia de Levenshtein

var f=document.getElementById("f"),g=document.getElementById("s"); function h(){var a=f.value,e=g.value;if(128<a.length)a="<span style='color:red'>First program is too long!</span>";else if(128<e.length)a="<span style='color:red'>Second program is too long!</span>";else{if(0===a.length)a=e.length;else if(0===e.length)a=a.length;else{var d=[],b;for(b=0;b<=e.length;b++)d[b]=[b];var c;for(c=0;c<=a.length;c++)d[0][c]=c;for(b=1;b<=e.length;b++)for(c=1;c<=a.length;c++)d[b][c]=e.charAt(b-1)===a.charAt(c-1)?d[b-1][c-1]:Math.min(d[b-1][c-1]+1,Math.min(d[b][c-1]+1,d[b-1][c]+ 1));a=d[e.length][a.length]}a="Distance = <strong>"+a+"</strong>"}document.getElementById("d").innerHTML=a}f.onkeyup=h;g.onkeyup=h;

<h3 id=ft>First program</h3>
<textarea id=f rows=7 cols=80 style="width:100%"></textarea>
<h3 id=st>Second program</h3>
<textarea id=s rows=7 cols=80 style="width:100%"></textarea>
<p id=d></p>

Python 2, distancia = 8 [ agrietada ]

from fractions import*
n=input()
k,=P=[2]
while n>len(P):k+=1;z=reduce(lambda x,y:x*y,P,1);P+=[k]*(gcd(z,k)<2)
print P[-1]

Finalmente conseguí este debajo del límite de char. No debería ser demasiado difícil, pero pensé que la idea era interesante.

Solución prevista:

from fractions import* n=input() k,=P=[1] while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[:-1],1);P+=[z]*(gcd(z,k)<2) print P[-1]

La idea era usar eso F(n+2) = 1 + (sum over F(k) from k = 1 to n), y el hecho de que los números consecutivos de Fibonacci son coprimos. Se 1suponía que el argumento in the reduce proporcionaba el +1.

¡Parece que Feersum encontró una línea de ataque diferente!

J, distancia = 5 [ Agrietado ]

f=:3 :'{.p:|.i.y'

Uso:

> f 45
197

Ruby, distancia 6 [seguro]

require'prime';p Prime.take(n=gets.to_i)[-1]
#p (((807462154311276410)**n/(5**0.5)).round)

Crear pares de fórmulas con distancias cortas de edición es divertido, pero parece que este enfoque podría ser más efectivo / molesto. Puede entender exactamente lo que hice, pero eso no significa que pueda revertirlo.

Solución:

require'prime';p=Prime.take(n=gets.to_i)[-1] p (((0742154311276/4e10)**n/(5**0.5)).round)

Explicación:

El código genera la proporción áurea a 11 decimales y la usa para calcular directamente la secuencia de Fibbonaci. Es suficiente precisión para obtener el número requerido de términos correctos. Esa parte no se ofuscó en absoluto, si conoces la fórmula. Para dificultar que la fuerza bruta revierta mis mutaciones y recupere la constante, utilicé la notación octal (el 0 principal) y la notación científica (4e10). Dividir entre 4e10 en lugar de 1e11 hace que parezca que estoy dividiendo entre algo .0para forzar la división de flotación, cuando en realidad cualquier cosa en notación científica es, por alguna razón, siempre una Flotación en Rubí, incluso cuando un Bignum parece tener más sentido. Pensé que estaba siendo inteligente con las p=cosas, pero la forma en que las escribí puede eliminarlas p. Yo podría'p=solución usando en p&&lugar de #en la segunda línea, pero no pensé en ello.

Python 2 - LD = 13 agrietado

n=1;j=input();
while j>0:
    n+=1;j-=1;
    while~-all(n%i for i in range(2,n)):n+=1;
print n

Una agradable, fácil (espero que no sea demasiado fácil) para comenzar las cosas :)

Parece que fue demasiado fácil;) Me siento bastante tonto porque olvidé que podrías usar comentarios: /

Haskell, distancia = 13

import Data.List
x=id=<<snd(mapAccumL(\m n->(,)=<<(++m)$[n|and[n`mod`m1/=0|m1<-m]])[1+1][3..])
main=print.(!!)(0:2:x)=<<readLn

Esto podría ser más legible, pero se importcomió demasiados bytes, así que tuve que jugar un poco.

Rubí, distancia 14 ( Agrietada )

p [x=2,y=1,*(1..200).map{|i|y==(y*x**(i-1)+x%2).divmod(i)[x-1]?i:1}].-([x-1])[gets.to_i-1]

CJam, distancia 10 (agrietada)

1l~{{)_mp!}g}*

Solo ponte nSTDIN. Pruébalo aquí.

Como referencia, la solución original utilizaba lo raro j.

Original:

T1]l~\{(_j\(j+}j

J, distancia = 4 [seguro]

f =: 3 :  '{. (p:) (+) / 0 , y - 1x'

Solución:

f =: 3: '{. 2 (x :) (+%) / 0, y $ 1x '

Método:

Denominador {. 2(x:)de la fracción continua (+%)1 + 1 / (... (1 + 1 / (1 + 1 / (1 + 1 / (1))))).

Python 3, distancia = 14 [ agrietada ]

n = int(input())
P = [2]
k = 2
while n > len(P):
 k += 1
 for x in P:
  if k%x == 0: break
 else: P += [k]
print(k)

Tenía algunos caracteres adicionales, así que puse un poco de espacio en blanco para mayor claridad :)

JAGL Alpha 1.2 - Distancia = 16 [ Agrietado ]

T~2S]{]S1{D[dmn}wDS}wSP

No debería ser demasiado difícil, veremos qué pasa ...

TI-BASIC , distancia 38

Input N:{2>L1:For(A,3,E99:If min(1=gcd(A,seq(A,A,2,$(A:A>L1(1+dim(L1:End:L1(N

>representa la STO→clave y $representa el símbolo de la raíz cuadrada.

Python 2 - distancia = 12 [ Agrietado ]

Estoy un poco contento con cómo resultó esto.

f=lambda p,i:p if p[45:]else f(p+[i]if all(i%q for q in p[1:])else p,-~i)
print f([1,2,3],2)[input()]

Veamos cuánto tiempo lleva ... supongo que todavía estará resquebrajado.

Editar: código acortado un poco, sin efecto en la operación / distancia.

Solución prevista

Traté de no hacer comentarios o cambios en la nueva línea.

f=lambda p,i:p if p[45:]else f(p+[p[i]+p[-2]]if all(i|q for q in p[1:])else p,-~i) print f([1,1,1],2)[input()]

Python 3 - Distancia = 14 [ Agrietado ]

a,c,n=1,2,int(input())
while n-1:
 c+=1
 while 1!=list(map(c.__mod__,range(2,46))).count(0):
  c,a=a+c,a
 n-=1
print(c)

Veremos cuánto dura esto ...