23
0
In this challenge we try to solve two important problems at once. They are:
- Given integers a and b, tell if ab-1 is a prime number.
- Given integers a and b, return nCr(a, 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
- 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. - 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.
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 { ... }
Standard loopholes are not allowed.
Test cases
ab-1 is prime?
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
1This may be handy to compute Levenshtein distance – Luis Mendo – 2017-04-02T16:08:52.913
3The 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 – 2017-04-02T16:13:51.377
6
@LuisMendo The issue is that many of those solutions are really slow. You can use this Mathics script instead.
– Martin Ender – 2017-04-02T16:31:22.6673I think a better metric would have been the Levenshtein distance divided by the total length of the two programs. – Greg Martin – 2017-04-02T21:06:42.180
1@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. – fergusq – 2017-04-03T06:12:45.107
What does tell us if mean? Are truthy/falsy values allowed? Do they have to be consistent? – Dennis – 2017-04-03T20:15:55.273
1Also, you say given integers. Can we assume the integers are non-negative? Can we assume that a in task 1 is positive? Can we assume that a ≥ b in task 2? – Dennis – 2017-04-03T20:36:34.773
@Dennis You can return a truthy/falsy value or choose two values and use them consistently. However, the truthy/falsy value doesn't need to be consistent. You can assume that the input is always valid. I added clarifications to the post. – fergusq – 2017-04-04T06:43:40.587