Ce défi de code vous fera calculer le nombre de façons d'atteindre partir de utilisant des cartes de la forme (avec un entier non négatif), et cela en un minimum d'étapes.$n$$2$$x \mapsto x + x^j$$j$

(Remarque, cela est lié à la séquence OEIS A307092 .)

Exemple

Ainsi, par exemple, car trois cartes sont requises, et il existe deux séquences distinctes de trois cartes qui enverront de à 13 :$f(13) = 2$$2$$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}$$

Résultat: ou .$2 \to 3 \to 12 \to 13$$2 \to 6 \to 12 \to 13$

Exemples de valeurs

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

Défi

Le défi est de produire un programme qui prend un entier en entrée, et génère le nombre de chemins distincts de à via un nombre minimal de cartes de la forme .$n \ge 2$$2$$n$$x \mapsto x + x^j$

Il s'agit de code-golf , donc le moins d'octets gagne.

Gelée , 16 octets

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

Essayez-le en ligne!

Un programme complet prenant comme argument $n$ et renvoyant le nombre de façons d'atteindre $n$ utilisant la longueur de chemin minimale. Inefficace pour les $n$ plus grands .

JavaScript (ES6),  111 ... 84  80 octets

Renvoie vrai plutôt que $1$ pour $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)

Essayez-le en ligne!

Commenté

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 octets

Cette implémentation utilise une recherche à couper le souffle dans «l'arborescence» de tous les mappages nécessaires 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

Essayez-le en ligne!

Explication

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

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

Essayez-le en ligne!

Python 2 , 72 octets

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

Essayez-le en ligne!

Perl 5 ( -lp), 79 octets

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

TIO

CJam (27 octets)

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

Démo en ligne

Attention: cela devient très gourmand en mémoire très rapidement.

Dissection:

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

Les bonus 2s (pour gérer le cas particulier de l'entrée 2, car les whileboucles sont plus chères que les do-whileboucles) signifient que la taille de la liste augmente très rapidement, et l'utilisation d'exposants jusqu'à n-1signifie que les valeurs des plus grands nombres de la liste augmentent très vite.

Haskell , 65 octets

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

Essayez-le en ligne!

L'étendue de la recherche en premier sur les défauts du golf . J'ai aussi essayé de reculer n, mais c'était plus long:

73 octets

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]

Essayez-le en ligne!

R , 78 77 octets

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

Essayez-le en ligne!

Utilisation d'une recherche simplifiée en largeur

Code déroulé avec explication:

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
}   

---

Version plus courte avec une énorme allocation de mémoire (échec pour les cas plus gros):

R , 70 69 octets

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

Essayez-le en ligne!

-1 octet grâce à @RobinRyder

Pyth , 24 octets

VQIJ/mu+G^GHd2^U.lQ2NQJB

Essayez-le en ligne!

Cela devrait produire la sortie correcte, mais est très lent (le scénario de test 372 expire sur TIO). Je pourrais le raccourcir en le remplaçant .lQ2par Q, mais cela rendrait le temps d'exécution horrible.

Remarque: ne produit aucune sortie pour les numéros inaccessibles $(n \leq 1)$

Explication

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