W tym wyzwaniu kodu będziesz musiał obliczyć liczbę sposobów osiągnięcia $n$ zaczynając od $2$ używając map w postaci $x \mapsto x + x^j$ (z $j$ nieujemną liczbą całkowitą) i robiąc to w minimalnej liczbie kroków.

(Uwaga: jest to związane z sekwencją OEIS A307092 .)

Przykład

Na przykład $f(13) = 2$ ponieważ wymagane są trzy mapy, i istnieją dwie odrębne sekwencje trzech map, które wyślą $2$ do $13$ :

$$\begin{array}{c} x \mapsto x + x^0 \\ x \mapsto x + x^2 \\ x \mapsto x + x^0\end{array} \qquad \textrm{or} \qquad \begin{array}{c}x \mapsto x + x^2 \\ x \mapsto x + x^1 \\ x \mapsto x + x^0\end{array}$$

Wynikający z $2 \to 3 \to 12 \to 13$ lub $2 \to 6 \to 12 \to 13$ .

Przykładowe wartości

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

Wyzwanie

Wyzwanie polega na stworzeniu programu, który przyjmuje liczbę całkowitą $n \ge 2$ jako dane wejściowe i wyprowadza liczbę różnych ścieżek od $2$ do $n$ poprzez minimalną liczbę map w postaci $x \mapsto x + x^j$ .

To jest golf golfowy , więc wygrywa najmniej bajtów.

Galaretka , 16 bajtów

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

Wypróbuj online!

Pełny program przyjmuje jako argument $n$ i zwraca liczbę sposobów osiągnięcia $n$ przy użyciu minimalnej długości ścieżki. Nieefektywne dla większych $n$ .

JavaScript (ES6),  111 ... 84  80 bajtów

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

Wypróbuj online!

Skomentował

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

Haskell , 78 75 bajtów

Ta implementacja wykorzystuje pierwsze wyszukiwanie w „drzewie” iteracyjnie wszystkich niezbędnych mapowań 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

Wypróbuj online!

Wyjaśnienie

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

05AB1E , 17 bajtów

2¸[˜DIå#εIÝmy+]I¢

Wypróbuj online!

Python 2 , 72 bajty

f=lambda n,l=[2]:l.count(n)or f(n,[x+x**j for x in l for j in range(n)])

Wypróbuj online!

Perl 5 ( -lp), 79 bajtów

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

TIO

CJam (27 bajtów)

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

Demo online

Ostrzeżenie: bardzo szybko zapełnia się pamięć.

Sekcja:

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

Premia 2s (do obsługi specjalnego przypadku wprowadzania 2, ponieważ whilepętle są droższe niż do-whilepętle) oznacza, że ​​rozmiar listy rośnie bardzo szybko, a użycie wykładników w górę n-1oznacza, że ​​rosną wartości większych liczb na liście bardzo szybki.

Haskell , 65 bajtów

([2]%)
l%n|elem n l=sum[1|x<-l,x==n]|1>0=[x+x^k|x<-l,k<-[0..n]]%n

Wypróbuj online!

Gra w golfa Flawr po raz pierwszy . Próbowałem też cofnąć się n, ale było to dłużej:

73 bajty

q.pure
q l|elem 2l=sum[1|2<-l]|1>0=q[x|n<-l,x<-[0..n],i<-[0..n],x+x^i==n]

Wypróbuj online!

R , 78 77 bajtów

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

Wypróbuj online!

Korzystanie z uproszczonego wyszukiwania pierwszego zakresu

Kod rozwinięty z wyjaśnieniem:

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
}   

---

Krótsza wersja z ogromnym przydziałem pamięci (nie działa w większych przypadkach):

R , 70 69 bajtów

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

Wypróbuj online!

-1 bajt dzięki @RobinRyder

Pyth , 24 bajty

VQIJ/mu+G^GHd2^U.lQ2NQJB

Wypróbuj online!

Powinno to dać poprawne wyjście, ale jest bardzo wolne (372 przypadków testowych przekroczyło limit czasu dla TIO). Mogłem go skrócić, zastępując .lQ2go Q, ale to spowodowałoby, że środowisko wykonawcze byłoby przerażające.

Uwaga: Nie generuje danych wyjściowych dla nieosiągalnych liczb $(n \leq 1)$

Wyjaśnienie

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