Codegolf — Найдите Количество Способов Подняться По Лестнице.

Канистро

Испытание:

Найдите количество способов подняться по лестнице с n ступенями и некоторыми ограничениями. Вы сможете запустить приведенные ниже тесты на TIO. https://tio.run/ без тайм-аута. – 60 секунд. (Обычно для большинства языков вполне достижима доля секунды, если применяется хорошая стратегия оптимизации).

Входные данные представляют собой список положительных чисел:

первое число во входных данных — это общее количество ступенек на лестнице
Остальная часть входных данных — это различное количество ступенек, на которые вам разрешено подняться одновременно, но вам разрешено использовать n ступенек максимум n раз, если n>1. Таким образом, если разрешено 2, вам разрешено сделать 2 шага максимум 2 раза. И 3 шага максимум 3 раза и так для всех n>1. Таким образом, если разрешено 1, вы можете делать 1 шаг столько раз, сколько захотите.
не следует «переступать», поскольку лестница из 5 ступенек и разрешено только 2 ступеньки сразу, подняться по ней невозможно (выход 0)

Допустимые допущения: все входные числа являются целыми положительными числами, не менее 1 (0, отрицательные и дробные числа не требуют специальной обработки). Список разрешенных шагов представляет собой уникальные номера и упорядочен, если это помогает. Также размер лестницы может быть последним числом или отдельной частью входных данных, если это полезно для вашей реализации («реорганизация» входных данных не должна быть частью проблемы)

Выход:

число, обозначающее количество способов подняться по лестнице

Примеры:

Входные данные: 3,1 Выходные данные: 1 (поскольку существует только один путь, когда вам разрешен только один шаг за раз)
Вход: 3,1,2 Выход: 3 (так как подняться можно тремя способами: 1+1+1 или 1+2 или 2+1)
Ввод: 3,4 Вывод: 0 (вы всегда должны заканчивать наверху, вы не можете сделать 4 ступеньки, так как на лестнице всего 3)
Вход: 4,1,2,3 Выход: 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3 )
Ввод: 6,2 Вывод: 0 (поскольку нельзя сделать 2 шага 3 раза)
Вход: 6,2,1 Выход: 12 (2+2+1+1, 2+1+2+1, 2+1+1+2, 2+1+1+1+1, 1+2+2 +1, 1+2+1+2, 1+2+1+1+1, 1+1+2+2, 1+1+2+1+1, 1+1+1+2+1, 1 +1+1+1+2, 1+1+1+1+1+1, но 2+2+2 не допускается.)
Ввод: 99,99,1 Вывод: 2 (99 или 1+1+1+1+...99 раз)

Еще тесты:

 2,1        → 1
10,1       → 1
3,1,2      → 3
3,4        → 0
3,2        → 0
4,1,2      → 5
4,1,2,3    → 7
6,2        → 0
6,2,1      → 12
7,1,2      → 17
5,1,2,3    → 13
15,1,2,7   → 266
39,3,2,7   → 301
99,11,3,2  → 1981

#код-гольф #ограниченное время

Татьяна Анатоль

JavaScript (ES6), 71 байт

Ожидает

                     sub g{+&f}

.

sub f($z,$w,%a){$z&&map{%b=%a;++$b{$_}>$_&$_>1|$_>$z?():f($z-$_,$w,%b)}@$w}

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

Прокомментировал

If[#>0,                     (* if there are still stairs to climb, *)

If[##3'~Count~i>=i>1,0,   (*   and we haven't used up our quota of i-steps, *)

#0[#-i,##2,i]]          (*     check how many ways there are after an i-step, *)

~Sum~{i,#2},             (*   and add those up for all possible step sizes. *)

1+Sign@#]&                (* otherwise, check if we overshot. *)

||answer||

Древесный уголь, 62 байта

If[#>0,If[##3'~Count~i>=i>1,0,#0[#-i,##2,i]]~Sum~{i,#2},1+Sign@#]&

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Sum[                                   ,{a,FrobeniusSolve@##}]& (* for each way to climb with the given step increments, sum *)

Multinomial@@a                         (* the number of rearrangements *)

UnitStep@@(--+#(#-a))                                       (* if no quotas are surpassed *)

Начните поиск в ширину с кортежа из списка шагов и оставшихся счетчиков (за исключением того, что счетчиком для одного шага является общее количество шагов) и количеством шагов, предпринятых на данный момент.

Sum[UnitStep@@(--+#(#-a))Multinomial@@a,{a,FrobeniusSolve@##}]&

Перебираем все возможные перестановки шагов.

int f(int z,int[]...v){int s=1/~z,i=0,a[];for(int y:v[0])s-=--(a=v[v.length-1].clone())[i++]<0&y>1|y>z?0:f(z-y,v[0],a);return-s;}

Если сумма не достигнута, то...

% =>b=>1 to%map{b.flatMap($=>Seq.fill(if($<2)%else $)($))combinations _ flatMap(_.permutations)count(_.sum== %)}sum

... перебираем оставшиеся шаги и...

f=lambda n,s,p=[]:0**n+sum(f(n-d,s,p+1%d*[d])for d in s if p.count(d)<d<=n)

... нажмите кортеж списка с удаленным на один шаг (полностью, если счетчик упадет до нуля) и будет достигнута новая позиция.

def f(z,w,a=0,s=0,i=0):

for x in w:b=(a or w)[:];b[i]-=1;s+=b[i]*(x-1)>=0and(f(z-x,w,b)if z>x else z==x);i+=1

return s

Подсчитайте, сколько раз желаемая сумма была достигнута точно.

Karax

Р, 171 байт

If[#<1,0,Length@Flatten[Permutations/@(S=Select)[IntegerPartitions[#,All,#2],And@@(#>=#2&@@@S[Tally@#,#&@@#>1&])&],1]]&

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

Тайм-аут для большого split .

Это тяжело для Р. Глядя на это рекурсивное решение что по-прежнему неверно, но достойное начало, если кто-то захочет продолжить с того места, на котором я остановился, — учтите, что для этого требуется S to be sorted ascending due to N .

MedoBloogue

Язык Wolfram (Математика), 119 байт

function(N,S){s=S;s[s==1]=N
for(i in 1:N){m=expand.grid(rep(list(S),i))
m=t(m[rowSums(m)==N,])
if(z<-ncol(m))for(j in 1:z){R=m[,j]
t=table(factor(R,S))
F=F+all(t<=s)}}
+F}

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

Sv0la4

Питон 3, 120 байт

Ｉ№Ｅυ⊟ιθ

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

Dr.Fuad

Питон 3, 75 байт

⊞υ⟦ΦＥ§ι⁰Ｅμ⁻ξ∧π⁼μλ§μ¹⁺§ι¹§λ⁰⟧

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

На основе решение доната.

Dmitry_Z

Скала, 123 118 115 байт

Спасибо пользователю x2

Ｆ§ι⁰

Ввод: (#шаги)=>(список). Алгоритм создает список всех разрешенных шагов, анализирует все перестановки комбинаций из n элементов (n от 1 до количества ступеней) и подсчитывает те, которые в сумме дают количество шагов.

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

Sерж

Java (JDK), 129 байт

Ｆ‹§ι¹θ

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

Уменьшено со 167 до 161 по подсказке потолочного кота.

Дальше уменьшилось до 153, 136, 132 сейчас.

С 132 до 129 благодаря потолочному коту.

Sergegru

Язык Wolfram (Математика), 74 65 63 байта

Ｆυ

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

⊞υ⟦Ｅη⟦ι⎇⊖ιιθ⟧⁰⟧

66 байт

⊞υ⟦Ｅη⟦ι⎇⊖ιιθ⟧⁰⟧ＦυＦ‹§ι¹θＦ§ι⁰⊞υ⟦ΦＥ§ι⁰Ｅμ⁻ξ∧π⁼μλ§μ¹⁺§ι¹§λ⁰⟧Ｉ№Ｅυ⊟ιθ

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

Рекурсивная функция. Переместите внешнее условие в сумму, чтобы оно соответствовало исходной спецификации: 68 байт.

(a, t = 0) =>           // a[] = input list, t = output
g = n =>                // g is a recursive function taking the number of steps n

n > 0 ?               // if n is positive:

a.map(x =>          //   for each value x in a[]:

--g[              //     decrement g[x] afterwards

(g[x] = -~g[x]) //       increment g[x]

+ ~x |          //       if g[x] is not equal to x + 1

x < 2 &&        //       or x = 1:

g(n - x),     //         do a recursive call with n - x

x               //       actual index to update g[x]

]                 //     end of entry update: this is guaranteed to be 0 on

//     the first iteration; therefore, .map() is coerced to

//     0 by the the bitwise OR even if a[] is a singleton

) | t               //   end of map(); yield t

:                     // else:

t += !n             //   increment t if n = 0

||answer||

Перл 5, 75 байт

(a,t=0)=>g=n=>n>0?a.map(x=>--g[(g[x]=-~g[x])+~x|x<2&&g(n-x),x])|t:t+=!n

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

Функция возвращает список нулей. Perl преобразует его в количество его элементов при оценке в скалярном контексте. Это будет результат.

Вычисление в скалярном контексте может быть вызвано такой вспомогательной функцией:

(list)(n)

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

Похожие темы	Дата
Школа Лемуров: Надежный блог за один вечер	19.12.2024, 05:12
Codegolf - Родинки В Носках?	19.12.2024, 05:12
Codegolf - Hexagolf: Validagons	19.12.2024, 05:12
Codegolf - Сочини Песню!	19.12.2024, 05:12
Codegolf — Внедрить Bogosort	19.12.2024, 05:12
Codegolf - Переворот-Сложение Палиндрома	19.12.2024, 05:12
Codegolf - Последовательность С Максимальным Расхождением-2 С Минимальной Энтропией	19.12.2024, 05:12
Codegolf – Создайте Тест Скорости Набора Текста/Измерение Цены За Тысячу Показов	19.12.2024, 05:12
Codegolf — Равенство Суммы Других Элементов	19.12.2024, 05:12
Codegolf - Найдите N-Ю Пару Простых Чисел-Близнецов	19.12.2024, 05:12

Codegolf — Найдите Количество Способов Подняться По Лестнице.

Канистро

JavaScript (ES6), 71 байт

Прокомментировал

Древесный уголь, 62 байта

Татьяна Анатоль

Р, 171 байт

Karax

Язык Wolfram (Математика), 119 байт

MedoBloogue

Питон 3, 120 байт

Sv0la4

Питон 3, 75 байт

Dr.Fuad

Скала, 123 118 115 байт

Dmitry_Z

Java (JDK), 129 байт

Sерж

Язык Wolfram (Математика), 74 65 63 байта

66 байт

Перл 5, 75 байт

Sergegru

I AM

Интересно