В этой задаче мы пытаемся решить две важные проблемы одновременно. Они есть:

Учитывая целые числа a и b , скажите, является ли a ^b -1 простым числом.
Даны целые числа a и b , вернуть nCr (a, b).

В частности, вы должны написать две программы, одна из которых выполняет первую задачу, а другая - другую. Поскольку мы хотим решить обе проблемы одновременно, рекомендуется использовать один и тот же кусок кода в обеих программах.

счет

Оценка ответа - расстояние Левенштейна между двумя программами. Чем ниже балл, тем лучше. В случае ничьей побеждает ответ с кратчайшим комбинированным кодом двух программ. Вы можете использовать этот скрипт для расчета баллов вашего решения.

правила

Вы должны написать две программы на одном языке, которые решают задачи, описанные выше. Вы можете использовать любые методы ввода / вывода, которые вы хотите. Для задачи 1 вы можете вернуть истинное / ложное значение или выбрать два значения, которые означают true и false, и вернуть их соответственно. Например. Вы можете выбрать, что "prime"означает истину, а "not prime"значит ложь.
Используемые вами алгоритмы должны работать для всех возможных входов, но это нормально, если код не подходит для больших чисел из-за ограничений используемого типа чисел. Вы можете предположить, что ввод действителен.
Никакое подмножество программы не должно решить проблему, т.е. код не должен работать, если какие-либо символы удалены. Например, следующий код недействителен, поскольку можно удалить неиспользуемый блок else, не нарушая программу:
```
if (1) { /* change to 0 to get the second program*/
    ...
} else {
    ...
}
```
Стандартные лазейки не допускаются.

Контрольные примеры

а ^б -1 простое число?

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

code-challenge number-theory primes combinatorics source-layout fergusq
источник

1

Это может быть удобно для вычисления расстояния Левенштейна

Луис Мендо

3

Идея хорошая, но я думаю, что вы все равно получите решения с расстоянием Левенштейна 1, которые смогут так или иначе предотвратить модификации неиспользуемых деталей, а затем эффективно привести к структуре, которую вы хотите запретить.

Мартин Эндер,

6

@ LuisMendo Проблема в том, что многие из этих решений действительно медленные. Вы можете использовать этот скрипт Mathics вместо этого.

Мартин Эндер,

3

Я думаю, что лучшей метрикой было бы расстояние Левенштейна, деленное на общую длину двух программ.

Грег Мартин

1

@GregMartin Не приведет ли это к боулингу кода? Можно искусственно увеличить программы и при этом утверждать, что в них нет ненужного кода.

fergusq

7

MATLAB, расстояние 10

простоты:

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

Ncr:

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

Steadybox
источник

4

Это то, что я искал!

Kritixi Lithos

7

PHP, расстояние 29

a^b-1 выводит 0 для истины и любое целочисленное значение> 0 для ложных

[,$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, расстояние 36

a^b-1 печатает 1 для истинного ничего для ложного

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

Йорг Хюльсерманн
источник

7

Рубин, расстояние 1, комбинированная длина 194

Первичная проверка:

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

Попробуйте онлайн!

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}

Попробуйте онлайн!

Как и предсказывалось в комментариях, некоторые рывки всегда должны идти вразрез с духом проблемы. Хотя было весело найти способ обойти это! Вот как это работает: у нас есть два отдельных решения проблем. Мы запускаем оба, помещаем их в массив, а затем либо выбираем 0-й элемент или 1-й для расстояния редактирования 1. Обычно это будет недопустимым, поскольку вы можете просто удалить все, кроме требуемого вычисления, и оно все равно будет работать , Однако каждый фрагмент кода написан так, чтобы полагаться на загрузку одной и той же стандартной библиотеки 'mathn':

Первый использует свой встроенный prime?
Второе полагается на mathnизменение того, как работает деление - перед загрузкой оно 3/4оценивается 0, а затем оно вычисляется до дроби (3/4). Поскольку промежуточный результат (a+1-i)/iне всегда является целым числом, общий результат неверен без библиотеки.

Теперь нам нужно сделать так, чтобы загрузка библиотеки зависела от остальной части кода, которая не была изменена. Мы делаем это, генерируя имя mathn, используя длину символа остальной части основного кода: объединенное вычисление имеет длину 55, которая удвоена до 110 - это значение ASCII для n. Таким образом, объединение этого в строку «математика» дает желаемую библиотеку.

В качестве бонуса, введение библиотечных зависимостей также заставляет код выполняться в разумные сроки. В частности, наивный подход к nCr не даст частичных промежуточных результатов.

histocrat
источник

5

05AB1E , расстояние 3

Ncr

sc

Попробуйте онлайн!

IsPrime (а ^ Ь-1)

m<p

Попробуйте онлайн!

Emigna
источник

4

С накоплением , расстояние 13

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

Попробуйте онлайн! Первое вычисляет nCr, второе простое значение, используя теорему Вильсона.

(f g h) fork!извлекает Nаргументы из стека (вызывает их a0 ... aN) и применяет a0 ... aN f a0 ... aN h g.

Для первой программы:

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

И для второго:

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

Конор О'Брайен
источник

4

Питон 2 , расстояние 15 , длина 172

Задание 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)

Задача 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)

Попробуйте онлайн!

Деннис
источник

3

Mathematica, расстояние 10

Задание 1: PrimeQ[#2^#-1]&

Задача 2: Binomial[#2,#]&

Обе функции принимают входные данные в порядке b,a.

Грег Мартин
источник

3

Javascript ES7, расстояние 14

Спасибо @Conor O'Brien за сокращение расстояния на 7

простоты:

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

Возвращает 1, если простое число возвращает 0, если не простое число.

Невероятно неэффективная первичная проверка, проверяет число по модулю каждое число меньше его и больше 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}

Умножает 1 на каждое число от y + 1 до x и делит на каждое число от 1 до xy (x! / Y!) / (Xy)!

fənɛtɪk
источник

Изменение второй программы f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}дает расстояние редактирования 14. Попробуйте онлайн!

Конор О'Брайен

2

Октава, расстояние 17 16 15

Ncr

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

Попробуйте онлайн!

`isprime(a^b-1)`

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

Попробуйте онлайн!

Я не очень хорошо говорю в Octave, поэтому я не знаю, есть ли встроенная функция для вычисления nCr.

Kritixi Lithos
источник

1

MATL , расстояние 4, длина 6

Скажите, если `a^b-1`прост:

^qZq

Попробуйте онлайн!

Вычислить `nCr(a,b)`:

Xn

Попробуйте онлайн!

Как это работает

Скажите, если `a^b-1`прост:

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

Вычислить `nCr(a,b)`:

Xn     % nchoosek with implicit inputs. Implicit display

Луис Мендо
источник

1

Pyth, расстояние 4, общая длина 8

Первичность `a^b-1`

P_t^F

Попробуйте онлайн!

нКр (а, б)

.cF

Попробуйте онлайн!

Оба принимают входные данные как кортежи / списки целых чисел (например (1,2)).

notjagan
источник

1

PHP, расстояние 14

Написание программы с двумя функциями и вызов только одной из них приведет к расстоянию 1, но это будет слишком неубедительно.

Prime Test, 100 байт:

[,$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 байт:

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

Titus
источник

0

Желе , расстояние 4, длина 5

Задание 1

*’ÆP

Задача 2

Попробуйте онлайн!

Как это работает

Задание 1

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

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

Задача 2

c     nCr atom

Деннис
источник

0

JavaScript, оценка: 1, длина: 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])}

~~функция (а, б) {s = "а = Math.pow (а, б) -s.length + 79; для (Ь = 2, A% B ++;); б> a1for (т = 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~~

Обе подпрограммы используют длину другой для вычисления своей собственной константы, поэтому ни один символ не может быть удален

l4m2
источник

Повторно используйте ваш код!

счет

правила

Контрольные примеры

а ^б -1 простое число?

Ncr

Ответы:

MATLAB, расстояние 10

PHP, расстояние 29

PHP, расстояние 36

Рубин, расстояние 1, комбинированная длина 194

05AB1E , расстояние 3

С накоплением , расстояние 13

Питон 2 , расстояние 15 , длина 172

Задание 1

Задача 2

Mathematica, расстояние 10

Javascript ES7, расстояние 14

Октава, расстояние 17 16 15

Ncr

`isprime(a^b-1)`

MATL , расстояние 4, длина 6

Скажите, если `a^b-1`прост:

Вычислить `nCr(a,b)`:

Как это работает

Скажите, если `a^b-1`прост:

Вычислить `nCr(a,b)`:

Pyth, расстояние 4, общая длина 8

Первичность `a^b-1`

нКр (а, б)

PHP, расстояние 14

Желе , расстояние 4, длина 5

Задание 1

Задача 2

Как это работает

Задание 1

Задача 2

JavaScript, оценка: 1, длина: 144 142 126 117

Повторно используйте ваш код!

счет

правила

Контрольные примеры

а б -1 простое число?

Ncr

Ответы:

MATLAB, расстояние 10

PHP, расстояние 29

PHP, расстояние 36

Рубин, расстояние 1, комбинированная длина 194

05AB1E , расстояние 3

С накоплением , расстояние 13

Питон 2 , расстояние 15 , длина 172

Задание 1

Задача 2

Mathematica, расстояние 10

Javascript ES7, расстояние 14

Октава, расстояние 17 16 15

Ncr

isprime(a^b-1)

MATL , расстояние 4, длина 6

Скажите, если a^b-1прост:

Вычислить nCr(a,b):

Как это работает

Скажите, если a^b-1прост:

Вычислить nCr(a,b):

Pyth, расстояние 4, общая длина 8

Первичность a^b-1

нКр (а, б)

PHP, расстояние 14

Желе , расстояние 4, длина 5

Задание 1

Задача 2

Как это работает

Задание 1

Задача 2

JavaScript, оценка: 1, длина: 144 142 126 117

а ^б -1 простое число?

`isprime(a^b-1)`

Скажите, если `a^b-1`прост:

Вычислить `nCr(a,b)`:

Скажите, если `a^b-1`прост:

Вычислить `nCr(a,b)`:

Первичность `a^b-1`