Este desafío de código hará que calcules la cantidad de formas de llegar a partir de usando mapas de la forma (con j un número entero no negativo), y hacerlo en el número mínimo de pasos.$n$$2$$x \mapsto x + x^j$$j$

(Tenga en cuenta que esto está relacionado con la secuencia OEIS A307092 ).

Ejemplo

Entonces, por ejemplo, $f(13) = 2$ porque se requieren tres mapas, y hay dos secuencias distintas de tres mapas que enviarán de $2$ a $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}$$

Resultando en $2 \to 3 \to 12 \to 13$ o $2 \to 6 \to 12 \to 13$ .

Valores de ejemplo

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

Reto

El desafío es producir un programa que tome un número entero $n \ge 2$ como entrada y genere el número de rutas distintas de $2$ a $n$ mediante un número mínimo de mapas de la forma $x \mapsto x + x^j$ .

Este es el código de golf , por lo que gana menos bytes.

Jalea , 16 bytes

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

Pruébalo en línea!

Un programa completo que toma como argumento y devuelve el número de formas de llegar a usando la longitud mínima de la ruta. Ineficiente para grandes .$n$$n$$n$

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

Devuelve verdadero en lugar de para .$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)

Pruébalo en línea!

Comentado

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 bytes

Esta implementación utiliza una búsqueda de aliento primero en el "árbol" de forma iterativa todas las asignaciones necesarias 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

Pruébalo en línea!

Explicación

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

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

Pruébalo en línea!

Python 2 , 72 bytes

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

Pruébalo en línea!

Perl 5 ( -lp), 79 bytes

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

TIO

CJam (27 bytes)

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

Demostración en línea

Advertencia: esto consume mucha memoria muy rápido.

Disección:

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

La bonificación 2s (para manejar el caso especial de entrada 2, porque los whilebucles son más caros que los do-whilebucles) significa que el tamaño de la lista crece muy rápido, y el uso de exponentes hasta n-1significa que los valores de los números más grandes en la lista crecen muy rapido.

Haskell , 65 bytes

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

Pruébalo en línea!

La búsqueda del golf es lo primero en amplitud . También intenté retroceder n, pero fue más largo:

73 bytes

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]

Pruébalo en línea!

R , 78 77 bytes

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

Pruébalo en línea!

Uso de una búsqueda simplificada de Breadth-first

Código desenrollado con explicación:

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
}   

---

Versión más corta con gran asignación de memoria (falla para casos más grandes):

R , 70 69 bytes

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

Pruébalo en línea!

-1 byte gracias a @RobinRyder

Pyth , 24 bytes

VQIJ/mu+G^GHd2^U.lQ2NQJB

Pruébalo en línea!

Esto debería producir la salida correcta, pero es muy lenta (el caso de prueba 372 agota el tiempo de espera en TIO). Podría hacerlo más corto reemplazando .lQ2con Q, pero esto haría que el tiempo de ejecución sea horrible.

$(n \leq 1)$

Explicación

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