Reach the number in minimum steps

Question

In this challenge, you are given a number x. You have to find the minimum number of steps required to reach x from 1. At a particular point, you have two choices:

1) Increment the number by 1.

2) Reverse the integer (remove leading zeros after reversing)

Input: n=42    
Output: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>41>42 **(15 steps)**

The minimum steps to reach 42 from 1 is 15. This can be achieved if we increment numbers by 1 from 1 to 14 (13 steps). After reaching 14 we can reverse the number which will give us 41 (1 step). From 41 we can increment number by 1 to reach 42(1 step). Hence the total number is 15 steps, which is then the minimum.

Note that if we reverse the number after reaching 12 or 13, we will not get the minimum steps.

1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>32>33>34>35>36>37>38>39>40>41>42 (25 steps)

Input: n=16
Output: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16 **(15 steps)**

In this case we have to increment the numbers until we get 16, which will give us a minimum of 15 steps.

Note: Starting from 0 is also allowed, which will increase all output by 1.

Answer 1

Haskell, 82 73 bytes

r=read.reverse.show
f 1=0
f a=1+(minimum$f(a-1):[f$r a|r a<a,mod a 10>0])

Try it online!

Simplest recursion method.

-9 bytes thanks to Christian Sievers

Answer 2

C++, 140 159 147 145 bytes

Edit: new solution without standard library, using a recursive function and pointer magic (constant 20 experimentally determined and not the same on other compilers)

Edit 2: -2 bytes thanks to ceilingcat

int*s,S,*G,x;int F(int Z,int*p=&x){int W=1,a=(*p)++,r=0;for(;r=r*10+a%10,a/=10;);G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&W;return*p-Z&&W-Z?F(Z,p-20):S;}

Try it online!

int *s,S,*G,x;
int F(int Z,int*p=&x)
{
    int W=1,a=(*p)++,r=0;
    for(;r=r*10+a%10,a/=10;);
    G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&W;
    return *p-Z&&W-Z?F(Z,p-20):S;
}

---

Old solution with standard library (159 bytes)

#include<set>
int Z(int N){int C=0,r,a;std::set T{1},S{1};for(;;++C,T=S,S={})for(int i:T){if(i==N)return C;for(r=0,a=i;r=r*10+a%10,a/=10;);S.insert({i+1,r});}}

Try it online!

int Z(int N)
{
    int C = 0, r, a;
    set T{ 1 }, S{ 1 };
    for (;; ++C, T = S, S = {})
        for (int i : T)
        {
            if (i == N)
                return C;
            for (r = 0, a = i; r = r * 10 + a % 10, a /= 10;);
            S.insert({ i + 1,r });
        }
}

Edit: add #include to byte count

Answer 3

Jelly, 16 bytes

^{Recursion might well end up being less bytes.}

ṚḌ;‘))Fṭ
1Ç¡ċ€ċ0

A monadic Link accepting a positive integer which yields a non-negative integer

Try it online!
Or try a faster, 17 byte version

How?

ṚḌ;‘))Fṭ - Helper Link: next(achievable lists)
     )   - for each (list so far):
    )    -   for each (value, V, in that list):
Ṛ        -     reverse the digits of V
 Ḍ       -     convert that to an integer
   ‘     -     increment V
  ;      -     concatenate these results
      F  - flatten the results
         -   * with a Q here we de-duplicate these results making things faster
       ṭ - tack that to the input achievable lists

1Ç¡ċ€ċ0 - Main Link: positive integer, N
1       - literal one
  ¡     - repeat this (implicit N) times:
 Ç      -   the last Link as a monad - N.B. 1 works just as well as the list of lists [[1]]
   ċ€   - for each count the occurrences of (implicit N)
     ċ0 - count the zeros (i.e. the number of lists that did not yet contain N)

Answer 4

Perl 6, 26 25 bytes

{+(1,{1+$_|+.flip}...$_)}

Try it online!

Does pretty much as the question asks. Starting from 1, either increment the Junction of values or flip it, repeating this until we find the one value we're looking for. Then return the length of the sequence. This is zero-indexed (as in, 1 returns 1)

This times out for testcases with a larger number of steps, since for every step we're doubling the size of the Junction by running two operations over the entire thing.

Answer 5

05AB1E (legacy), 15 13 bytes

1¸[ÐIå#ís>«}N

-1 byte and much faster thanks to @Jitse, which also opened an opportunity for a second -1 byte.

Try it online or verify the first 100 test cases (with added Ù -uniquify- to increase the speed).

Explanation:

1¸        # Push 1 and wrap it into a list: [1]
  [       # Start an infinite loop:
   Ð      #  Triplicate the list
    Iå    #  If the input-integer is in this list:
      #   #   Stop the infinite loop
    í     #  Reverse each integer in the copy-list
     s    #  Swap to get the initial list again which we triplicated
      >   #  Increase each value by 1
       «  #  And also merge it
  }N      # After the infinite loop: push the loop-index
          # (which is output implicitly as result)

Uses the legacy version of 05AB1E, because using the index N outside a loop like that doesn't work in the new version.

Answer 6

C++ Recursive Solution:

int reverse(int n)//reverses the number
{
    int rev=0;
    while(n>0)
    {
        rev=rev*10+n%10;
        n/=10;
    }

    return rev;
}

int sol(int n, int x)
{
    if(n==x)// base case
        return 0;

    if(n>x)// base case
        return 1e5;

    if(reverse(n)<=n)// otherwise, recursion will happen infinitely
        return 1+sol(n+1,x);

    return 1+min(sol(n+1,x),sol(reverse(n),x));

}

int main() 
{   
   cout<<sol(1,42);
   return 0;
}

C++ Dynamic Programming Solution:

int dp[1000];
int reverse(int n)//reverses the number
{
    int rev=0;
    while(n>0)
    {
        rev=rev*10+n%10;
        n/=10;
    }

    return rev;
}

int sol(int n, int x)
{
    if(n==x)// base case
        return 0;

    if(n>x)// base case
        return 1e5;

    if(dp[n]!=-1)
        return dp[n];

    if(reverse(n)<=n)// otherwise, recursion will happen infinitely
        return dp[n]=1+sol(n+1,x);

    return dp[n]=1+min(sol(n+1,x),sol(reverse(n),x));

}

int main() 
{

    fill_n(dp,1000,-1);

    sol(1,42);
    cout<<dp[1];
    return 0;
}

Answer 7

Ruby, 67 bytes

Starts from 0. I noticed GB's Ruby solution after I finished my own, but the approaches used are drastically different (recursive vs. non-recursive) so I decided to post anyways.

f=->n{r=n.digits.join.to_i;n<9?n:[f[n-1],n>r&&n%10>0?f[r]:n].min+1}

Try it online!

Answer 8

Charcoal, 47 bytes

Ｎθ≔⁰ηＷ⊖θ«Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌ貫≦⮌θ≦⊕η»≦⊖θ≦⊕η»Ｉη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the target.

≔⁰η

Set the number of steps to zero.

Ｗ⊖θ«

Repeat until the target becomes 1.

Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌθ²

Look to see if the target is of the form xxx0001 or xxxx0001, but not 10..01. (This expression fails for 1, but fortunately the loop stops before we get here.)

«≦⮌θ≦⊕η»

If so then reverse the target and increment the number of steps.

≦⊖θ≦⊕η

Decrement the target and increment the number of steps.

»Ｉη

Output the number of steps once the target has been reduced to 1.

Answer 9

Ruby, 72 bytes

->i{*w=0;(0..i).find{[]==[i]-w=w.flat_map{|z|[z+1,z.digits.join.to_i]}}}

Try it online!

Answer 10

Python 3, 78 bytes

f=lambda n,s={1}:n in s or-~f(n,{int(str(i)[::-1])for i in s}|{i+1for i in s})

Try it online!

Uses 0-indexing. Note that in Python True == 1.

Answer 11

Haskell, 71 60 bytes

g[1]
g l x|elem x l=0|1>0=g([succ,read.reverse.show]<*>l)x+1

Try it online!

Considerably less efficient than 79037662's existing Haskell answer, but 2 13 bytes is 2 13 bytes.

Explanation:

g[1]

The relevant function: call g with [1] as its first argument, l.

g l x|elem x l=0

g takes two arguments, l and x, and returns 0 if l contains x.

|1>0=g( ... )x+1

Otherwise, it returns 1 plus its return value for a modified value of l:

[ ... ]<*>l

Apply each function from a list of functions to each element of l, returning the results in a flat list, using the Applicative instance of lists. succ adds 1, and...

read.reverse.show

takes the string representation of its argument, reverses it, then re-interprets it as whatever the type is of the other list elements.