Reuse your code!

Question

In this challenge we try to solve two important problems at once. They are:

1. Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number.
2. Given integers \$a\$ and \$b\$, return \$a\choose b\$.

Specifically, you must write two programs, one that does the first task and one that does the other. As we want to solve both problems at once, it is encouraged to use a same piece of code in both programs.

Scoring

The score of an answer is the Levenshtein distance between the two programs. Lower score is better. In case of a tie, the answer with the shortest combined code of the two programs wins. You can use this script to calculate the score of your solution.

Rules

1. You must write two programs in the same language that solve the tasks described above. You can use any I/O methods you want. For task 1, you can return a truthy/falsy value or choose two values to mean true and false and return them accordingly. Eg. you can choose that "prime" means true and "not prime" means false.

2. The algorithms you use must work for all possible inputs, but it is OK if the code fails for large numbers due to limitations of the used number type. You can assume that the input is valid.

3. No subset of the program must solve the problem, ie. the code must not work if any character(s) are removed. For example, the following code is not valid, because it is possible to remove the unused else-block without breaking the program:

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

4. Standard loopholes are not allowed.

Test cases

\$a^b-1\$ is prime?

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

\$a\choose b\$

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

• Luis Mendo: This may be handy to compute Levenshtein distance
• Martin Ender: The idea is nice, but I think you'll still get solutions with Levenshtein distance 1 that manage to prevent modifications to unused parts one way or another and then effectively result in the structure you want to prohibit.
• Martin Ender: @LuisMendo The issue is that many of those solutions are really slow. You can use this Mathics script instead.
• Greg Martin: I think a better metric would have been the Levenshtein distance divided by the total length of the two programs.
• fergusq: @GregMartin Wouldn't that result in code bowling? It is possible to artificially make programs larger and still claim that they don't have any unnecessary code.

Answer 1

Ruby, Distance 1, Combined Length 194

Prime check:

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

Try it 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}

Try it online!

As predicted in the comments, some jerk always has to go against the spirit of the problem. It was fun finding a way to work around it, though! Here's how it works: We have two separate solutions to the problems. We run both, put them into an array, and then either choose the 0th element or the 1st, for an edit distance of 1. This would ordinarily be illegal, since you could just delete everything but the calculation you wanted and it would still work. However, each code snippet is written to rely on the loading of the same standard library, 'mathn':

• The first uses its builtin prime?
• The second relies on mathn changing how division works--before loading it, 3/4 evaluates to 0, while afterwards it evaluates to the fraction (3/4). Since the intermediate result of (a+1-i)/i is not always a whole number, the overall result is wrong without the library.

Now we just need to make loading the library contingent on the rest of the code being unmodified. We do this by generating the name mathn using the character length of the rest of the main code: the combined calculation has length 55, which doubled to 110 is the ASCII value of 'n'. So concatenating this onto the string 'math' gives the desired library.

As a bonus, introducing the library dependencies also makes the code run in a reasonable amount of time. In particular, the naive approach to nCr wouldn't generate fractional intermediate results.

Answer 2

MATLAB, distance 10

Primality:

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

nCr:

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

• user41805: That's the built-in I was searching for!

Answer 3

PHP, distance 29

a^b-1 prints 0 for true and any integer value> 0 for 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, distance 36

a^b-1 prints 1 for true nothing for false

[,$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;

Answer 4

05AB1E, distance 3

nCr

sc

Try it online!

isPrime(a^b-1)

m<p

Try it online!

Answer 5

Stacked, distance 13

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

Try it online! The first calculates nCr, the second primality, using Wilson's theorem.

(f g h) fork! pops N args from the stack (call them a0 ... aN) and applies a0 ... aN f a0 ... aN h g.

For the first program:

[([@.!]$/{%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)!
 * *

And for the second:

[^#-:([]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

Answer 6

Python 2, distance 15, length 172

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

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

Try it online!

Answer 7

Mathematica, distance 10

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

Task 2: Binomial[#2,#]&

Both functions take the inputs in the order b,a.

Answer 8

Javascript ES7, distance 14

Thanks @Conor O'Brien for reducing the distance by 7

Primality:

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

Returns 1 if prime returns 0 if not prime.

Incredibly inefficient prime check, checks the number modulo every number smaller than it and greater than 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}

Multiplies 1 by each number from y+1 to x and divides by each number from 1 to x-y (x!/y!)/(x-y)!

• Conor O'Brien: Changing the second program to f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s} gives edit distance 14. Try it online!

Answer 9

Octave, distance (削除) 17 (削除ここまで) (削除) 16 (削除ここまで) 15

nCr

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

Try it online!

isprime(a^b-1)

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

Try it online!

I am not very fluent in Octave, so I don't know if there is a builtin to calculate nCr.

Answer 10

MATL, distance 4, length 6

Tell if a^b-1 is prime:

^qZq

Try it online!

Compute nCr(a,b):

Xn

Try it online!

How it works

Tell if a^b-1 is prime:

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

Compute nCr(a,b):

Xn % nchoosek with implicit inputs. Implicit display

Answer 11

Pyth, distance 4, total length 8

Primality of a^b-1

P_t^F

Try it online!

nCr(a, b)

.cF

Try it online!

Both take input as tuples/lists of integers (e.g. (1,2)).

Answer 12

PHP, distance 14

Writing a program with two functions and only calling one of them would lead to a distance of 1, but it ́d be too lame.

Prime Test, 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));

Answer 13

Jelly, distance 4, length 5

Task 1

*’ÆP

Task 2

c

Try it online!

How it works

Task 1

*’ÆP Main link. Argument: a, b
* Yield a**b.
 ’ Decrement; yield a**b-1.
 ÆP Test the result for primality.

Task 2

c nCr atom

Answer 14

JavaScript, Score:1, Length:(削除) 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])}

(削除) function(a,b){s="a=Math.pow(a,b)-s.length+79;for(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

Both subroutines use the other one's length to calculate its own constant, so no char can be removed (削除ここまで)