Подсчитайте количество кратчайших путей до n

21

Эта задача кода заставит вас вычислить количество способов достижения n начиная с 2 используя карты вида x↦x+xj (с j - неотрицательное целое число) и делая это за минимальное количество шагов.

(Обратите внимание, это относится к последовательности OEIS A307092 .)

пример

Так, например, f(13)=2 потому что требуются три карты, и есть две отдельные последовательности из трех карт, которые отправят от 2 до :13

x↦x+x0x↦x+x2x↦x+x0orx↦x+x2x↦x+x1x↦x+x0

В результате 2→3→12→13 или 2→6→12→13 .

Пример значений

f(2)   = 1 (via [])
f(3)   = 1 (via [0])
f(4)   = 1 (via [1])
f(5)   = 1 (via [1,0])
f(12)  = 2 (via [0,2] or [2,1])
f(13)  = 2 (via [0,2,0] or [2,1,0], shown above)
f(19)  = 1 (via [4,0])
f(20)  = 2 (via [1,2] or [3,1])
f(226) = 3 (via [2,0,2,1,0,1], [3,2,0,0,0,1], or [2,3,0,0,0,0])
f(372) = 4 (via [3,0,1,0,1,1,0,1,1], [1,1,0,2,0,0,0,1,1], [0,2,0,2,0,0,0,0,1], or [2,1,0,2,0,0,0,0,1])

Вызов

Задача состоит в том, чтобы создать программу, которая принимает целое число n≥2 в качестве входных данных и выводит количество различных путей от 2 до n через минимальное количество карт вида x↦x+xj .

Это код-гольф , поэтому побеждает меньше байтов.

code-golf sequence combinatorics Питер Кейджи
источник
1
Я думаю, что следует четко отметить, что ^символ обозначает возведение в степень. Это может быть также XOR (например, C использует ^для побитового XOR).
Рамилли
1
@Ramillies Может быть, это должно быть изменено на MathJax. Т.е. вместо . Иксзнак равноИкс+ИксJx -> x + x^j
Кевин Круйссен
@KevinCruijssen: Хорошо, это, безусловно, поможет.
Рамилли
Я добавил это к OEIS как A309997 . (Это будет проект, пока не будет одобрен.)
Питер Кейдж

Ответы:

2

Желе , 16 байт

2+*¥þ³Ḷ¤F$n³Ạ$¿ċ

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

Полная программа, принимающая в качестве аргумента N и возвращающая количество способов достижения N используя минимальную длину пути. Неэффективно для большего N .

Ник Кеннеди
источник
5

JavaScript (ES6),  111 ... 84  80 байт

Возвращает true, а не 1 для Nзнак равно2 .

f=(n,j)=>(g=(i,x,e=1)=>i?e>n?g(i-1,x):g(i-1,x+e)+g(i,x,e*x):x==n)(j,2)||f(n,-~j)

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

комментарии

f = (                     // f is the main recursive function taking:
  n,                      //   n = input
  j                       //   j = maximum number of steps
) => (                    //
  g = (                   // g is another recursive function taking:
    i,                    //   i = number of remaining steps
    x,                    //   x = current sum
    e = 1                 //   e = current exponentiated part
  ) =>                    //
    i ?                   // if there's still at least one step to go:
      e > n ?             //   if e is greater than n:
                          //     add the result of a recursive call with:
        g(i - 1, x)       //       i - 1, x unchanged and e = 1
      :                   //   else:
                          //     add the sum of recursive calls with:
        g(i - 1, x + e) + //       i - 1, x + e and e = 1
        g(i, x, e * x)    //       i unchanged, x unchanged and e = e * x
    :                     // else:
      x == n              //   stop recursion; return 1 if x = n
)(j, 2)                   // initial call to g with i = j and x = 2
|| f(n, -~j)              // if it fails, try again with j + 1
Arnauld
источник
4

Haskell , 78 75 байт

Эта реализация использует поиск по принципу «дыхание первым» в «дереве» итеративно всех необходимых отображений x -> x + x^j.

j#x=x+x^j
f n=[sum[1|x<-l,x==n]|l<-iterate((#)<$>[0..n]<*>)[2],n`elem`l]!!0

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

объяснение

-- computes the mapping x -> x + x^j
j#x=x+x^j                          
--iteratively apply this function for all exponents [0,1,...,n] (for all previous values, starting with the only value [2])
                            iterate((#)<$>[0..n]<*>)[2] 
-- find each iteration where our target number occurs
    [                   |l<-...........................,n`elem`l] 
-- find how many times it occurs
     sum   [1|x<-l,x==n] 
-- pick the first entry
f n=.............................................................!!0
flawr
источник
1

Perl 5 ( -lp), 79 байт

$e=$_;@,=(2);@,=map{$x=$_;map$x+$x**$_,0..log($e)/log$x}@,until$_=grep$_==$e,@,

TIO

Науэль Фуйе
источник
1

CJam (27 байт)

qi2a{{_W$,f#f+~2}%_W$&!}ge=

Онлайн демо

Предупреждение: это очень быстро загружает память.

Вскрытие:

qi            e# Read input and parse to int n (accessed from the bottom of the stack as W$)
2a            e# Start with [2]
{             e# Loop
  {           e#   Map each integer x in the current list
    _W$,f#f+~ e#     to x+x^i for 0 <= i < n
    2         e#   and add a bonus 2 for the special case
  }%          e#   Gather these in the new list
  _W$&!       e#   Until the list contains an n
}g
e=            e# Count occurrences

Бонус 2s (для обработки особого случая ввода 2, поскольку whileциклы дороже, чем do-whileциклы) означает, что размер списка растет очень быстро, а использование показателей степени вплоть до n-1означает, что значения больших чисел в списке растут очень быстро.

Питер Тейлор
источник
1

R , 78 77 байт

function(n,x=2){while(!{a=sum(x==n)})x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^')
a}

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

Использование упрощенного поиска в ширину

Развернутый код с объяснением:

function(n){                              # function taking the target value n

  x=2                                     # initialize vector of x's with 2

  while(!(a<-sum(x==n))) {                # count how many x's are equal to n and store in a
                                          # loop while a == 0

    x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^') # recreate the vector of x's 
                                          # with the next values: x + x^0:n
  }
a                                         # return a
}

Укороченная версия с огромным распределением памяти (не подходит для больших случаев):

R , 70 69 байт

function(n,x=2){while(!{a=sum(x==n)})x=rep(x,n+1)+outer(x,0:n,'^')
a}

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

-1 байт благодаря @RobinRyder

digEmAll
источник
!(a<-sum(x==n))может быть !{a=sum(x==n)}за -1 байт в обоих случаях.
Робин Райдер
0

Pyth , 24 байта

VQIJ/mu+G^GHd2^U.lQ2NQJB

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

Это должно привести к правильному выводу, но это очень медленно (372 тестовых случая истекло на TIO). Я мог бы сделать его короче, заменив .lQ2с Q, но это будет сделать во время выполнения ужасающим.

Примечание. Не выводит данные о недоступных номерах. (N≤1)

объяснение

VQ                        # for N in range(Q (=input)):
   J                      #   J =
     m                    #     map(lambda d:
      u                   #       reduce(lambda G,H:
       +G^GH              #         G + G^H,
            d2            #         d (list), 2 (starting value) ),
              ^U.lQ2N     #       cartesian_product(range(log(Q, 2)), N)
    /                Q    #     .count(Q)
  IJ                  JB  #   if J: print(J); break
ar4093
источник