Neste desafio, tentamos resolver dois problemas importantes ao mesmo tempo. Eles são:

1. Inteiros dadas a e b , dizer se um ^b -1 é um número primo.
2. Dados os números a e b , retorne nCr (a, b).

Especificamente, você deve escrever dois programas, um que executa a primeira tarefa e outro que executa a outra. Como queremos resolver os dois problemas ao mesmo tempo, é recomendável usar o mesmo trecho de código nos dois programas.

Pontuação

A pontuação de uma resposta é a distância de Levenshtein entre os dois programas. Menor pontuação é melhor. Em caso de empate, a resposta com o código combinado mais curto dos dois programas vence. Você pode usar esse script para calcular a pontuação da sua solução.

Regras

1. Você deve escrever dois programas no mesmo idioma que resolvam as tarefas descritas acima. Você pode usar qualquer método de E / S que desejar. Para a tarefa 1, você pode retornar um valor de verdade / falsidade ou escolher dois valores para significar verdadeiro e falso e retorná-los de acordo. Por exemplo. você pode escolher que "prime"significa verdadeiro e "not prime"falso.
2. Os algoritmos que você usa devem funcionar para todas as entradas possíveis, mas tudo bem se o código falhar para números grandes devido a limitações do tipo de número usado. Você pode assumir que a entrada é válida.

3. Nenhum subconjunto do programa deve resolver o problema, ou seja. o código não deve funcionar se algum caractere for removido. Por exemplo, o código a seguir não é válido, porque é possível remover o outro bloco não utilizado sem interromper o programa:

   if (1) { /* change to 0 to get the second program*/
       ...
   } else {
       ...
   }
   

4. As brechas padrão não são permitidas.

Casos de teste

a ^b -1 é primo?

a b
1 1 false
2 3 true
5 2 false
2 5 true
4 3 false
2 7 true

nCr

a b nCr(a,b)
1 1 1
5 2 10
4 3 4
10 7 120
12 5 792

MATLAB, distância 10

Primalidade:

function x=f(a,b);x=isprime(a^b-1);

nCr:

function x=f(a,b);x=nchoosek(a,b);

PHP, distância 29

a^b-1 imprime 0 para true e qualquer valor inteiro> 0 para false

[,$a,$b]=$argv;for($c=-$i=1;$i<=$d=$a**$b-1;$d%++$i?:$c++);echo$c;

nCr(a,b)

[,$a,$b]=$argv;for($c=$i=1;$i<=$a;$c*=$i**(1-($i<=$a-$b)-($i<=$b)),$i++);echo$c;

PHP, distância 36

a^b-1 imprime 1 para verdadeiro nada para falso

[,$a,$b]=$argv;for($c=-1,$i=1;$i<=$d=-1+$a**$b;)$d%++$i?:$c++;echo$c<1;

nCr(a,b)

[,$a,$b]=$argv;for($c=$d=$i=1;$i<=$a;$c*=$i++)$d*=$i**(($i<=$a-$b)+($i<=$b));echo$c/$d;

Rubi, Distância 1, Comprimento combinado 194

Verificação Prime:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][0]';require'math'<<s.size*2;eval s}

Experimente online!

nCr:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][1]';require'math'<<s.size*2;eval s}

Experimente online!

Como previsto nos comentários, algum idiota sempre tem que ir contra o espírito do problema. Foi divertido encontrar uma maneira de contornar isso! Eis como funciona: Temos duas soluções separadas para os problemas. Executamos os dois, os colocamos em uma matriz e, em seguida, escolhemos o 0º elemento ou o 1º, para uma distância de edição de 1. Isso normalmente seria ilegal, já que você poderia excluir tudo, exceto o cálculo desejado e ainda funcionaria. . No entanto, cada snippet de código é gravado para depender do carregamento da mesma biblioteca padrão 'mathn':

• O primeiro usa seu builtin prime?
• O segundo se baseia em mathnmudar a forma como a divisão funciona - antes de carregá-la, 3/4avalia como 0, enquanto depois avalia a fração (3/4). Como o resultado intermediário (a+1-i)/inem sempre é um número inteiro, o resultado geral está errado sem a biblioteca.

Agora, apenas precisamos tornar o carregamento da biblioteca contingente, pois o restante do código não é modificado. Fazemos isso gerando o nome mathn usando o comprimento do caractere do restante do código principal: o cálculo combinado tem o comprimento 55, que dobrou para 110 e é o valor ASCII de 'n'. Portanto, concatenar isso na string 'math' fornece a biblioteca desejada.

Como um bônus, a introdução das dependências da biblioteca também faz com que o código seja executado em um período de tempo razoável. Em particular, a abordagem ingênua do nCr não geraria resultados intermediários fracionários.

05AB1E , distância 3

nCr

sc

Experimente online!

isPrime (a ^ b-1)

m<p

Experimente online!

Empilhado , distância 13

[([@.!]$/{%y!x y-!*})fork!]
[^#-:([]1/$%{!n 1-!})fork!=]

Experimente online! O primeiro calcula nCr, a segunda primalidade, usando o teorema de Wilson.

(f g h) fork!aparece Nargs da pilha (chame-os a0 ... aN) e aplica-se a0 ... aN f a0 ... aN h g.

Para o primeiro programa:

[([@.!]$/{%y!x y-!*})fork!]
[(                  )fork!]  apply the fork of:
  [@.!]                      equiv. { x y : x ! } => `x!`
       $/                    divided by
         {%        }         two-arg function
           y!                y!
             x y-                 (x - y)!
                 *              *

E para o segundo:

[^#-:([]1/$%{!n 1-!})fork!=]  
[^                         ]  exponentiate  (a^b)
  #-                          decrement     (a^b-1)
    :                         duplicate     (a^b-1 a^b-1)
     (              )fork!    apply the fork to:
      []1/                    1-arg identity function
          $%                  modulus by
            {!     }          1-arg with `n`:
              n 1-             (n-1)
                  !                 !
                          =   check for equality

Python 2 , distância 15 , comprimento 172

Tarefa 1

D=lambda k:max(k-1,1)
P=lambda n,k=0:n<k or P(n-1,k)*n/k
lambda a,b:P(a**b-2)**2%D(a**b)

Tarefa 2

D=lambda k:max(k-1,1)
P=lambda n,k=1:n<k or P(n-1,D(k))*n/k
lambda a,b:P(a,b)/P(a-b)

Experimente online!

Mathematica, distância 10

Tarefa 1: PrimeQ[#2^#-1]&

Tarefa 2: Binomial[#2,#]&

Ambas as funções recebem as entradas na ordem b,a.

Javascript ES7, distância 14

Obrigado @Conor O'Brien por reduzir a distância em 7

Primalidade:

f=x=>y=>{t=x**y-1;s=1;for(i=2;i<t;i++){if(!t%i)s=i-i}return s}

Retorna 1 se prime retorna 0 se não for prime.

Verificação de primos incrivelmente ineficiente, verifica o módulo numérico cada número menor que ele e maior que 1 ...

nCr:

f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}

Multiplica 1 por cada número de y + 1 a x e divide por cada número de 1 a xy (x! / Y!) / (Xy)!

Oitava, distância 17 16 15

nCr

a=input("");b=input("");f=@(x)factorial(x);printf("%d",f(a)/f(b)/f(a-b))

Experimente online!

isprime(a^b-1)

a=input("");b=input("");f=@(x)isprime(x);printf("%d",f(a^b-f(8-6)))

Experimente online!

Eu não sou muito fluente em Oitava, então não sei se existe algum componente para calcular nCr.

MATL , distância 4, comprimento 6

Diga se a^b-1é primo:

^qZq

Experimente online!

Computar nCr(a,b):

Xn

Experimente online!

Como funciona

Diga se a^b-1é primo:

^      % Power with implicit inputs
q      % Subtract 1
Zq     % Is prime? Implicit display

Computar nCr(a,b):

Xn     % nchoosek with implicit inputs. Implicit display

Pitão, distância 4, comprimento total 8

Primalidade de a^b-1

P_t^F

Experimente online!

nCr (a, b)

.cF

Experimente online!

Ambos recebem entrada como tuplas / listas de números inteiros (por exemplo (1,2)).

PHP, distância 14

Escrever um programa com duas funções e chamar apenas uma delas levaria a uma distância de 1, mas seria muito ruim.

Teste Principal, 100 bytes:

[,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n%$i;);return$i==1;}echo f($a**$b*-1)*(1|f($a-$b));

nCr, 98 bytes:

[,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n*=$i;);return$n*=1;}echo f($a)/(f($b)*f($a-$b));

Gelatina , distância 4, comprimento 5

Tarefa 1

*’ÆP

Tarefa 2

c

Experimente online!

Como funciona

Tarefa 1

*’ÆP  Main link. Argument: a, b

*     Yield a**b.
 ’    Decrement; yield a**b-1.
  ÆP  Test the result for primality.

Tarefa 2

c     nCr atom

JavaScript, Pontuação: 1, Comprimento: 144 142 126 117

function(a,b){s="a=Math.pow(a,b)-t;for(b=2;a%b++;);b>a1for(;b;)t=t*a--/b--";t=s.length-56;return eval(s.split(1)[0])}

função (a, b) {s = "a = Math.pow (a, b) -s.length + 79; para (b = 2; a% b ++;); b> a1for (t = s.length-79 ; b;) t = t * a - / b - "; return eval (s.split (1) [1])}

function A(a,b){a=Math.pow(a,b)-(B+0).length+63;for(b=2;a%b++;);return b>a;}
function B(a,b){for(t=(A+0).length-76;b;)t=t*a--/b--;return t;}
F=A

Ambas as sub-rotinas usam o comprimento da outra para calcular sua própria constante, para que nenhum caractere possa ser removido