# Reach the number in minimum steps

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.

• Nice challenge but it needs test cases and a clearly defined rules. Nov 1, 2019 at 15:14
• What's reverse(reverse(10)) and reverse(2)? Nov 1, 2019 at 22:16
• @girobuz reverse(10) will be 1 (After removing leading zeros) - I had missed it earlier. have added it in the second step. so reverse(reverse(10)) will be reverse(1) which is 1. reverse(2) -> 2
Nov 1, 2019 at 23:07
• Your counter-example (25 steps to reach 42) could be reduced to 1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>24>42 (16 steps), which is still more than the correct solution (15 steps), but... less worse :-) Nov 2, 2019 at 15:43
• yes, we can use 0 based-indexing. in that case, the answer will increment by one
Nov 5, 2019 at 9:30

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

• Nice solution. But what if we have x = 10**10. is there any way to optimize it
Nov 1, 2019 at 16:01
• @veersingh I'm sure there is, but this is code golf so there is no reason to do so :) Nov 1, 2019 at 16:05
• 73 bytes by improving the last line Nov 1, 2019 at 19:02
• @ChristianSievers Thanks for the help. Nov 1, 2019 at 19:17

# C++, 140159147 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

# 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

### 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 []
ċ€   - for each count the occurrences of (implicit N)
ċ0 - count the zeros (i.e. the number of lists that did not yet contain N)


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

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

Explanation:

1¸        # Push 1 and wrap it into a list: 
[       # 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.

• 14 bytes: You don't need to do the first merge, since the previous values don't matter. This is much faster, too. Also, OP mentioned that 0-indexing is also fine. Not sure if that could save more. Nov 6, 2019 at 10:29
• @Jitse Ah, of course. Thanks, that's indeed a lot faster! And it also opened up a second -1, since I no longer need the list four times but three instead, so the ©/® can be replaced with a swap. PS: 0-based indexing won't save bytes unfortunately. Creating a list with just 0 or just 1 is both 2 bytes (creating an empty list or list with an empty string is possible in 1 byte). Nov 6, 2019 at 12:17
• Nice find! I was also playing with that a bit, but I didn't know enough 05AB1E to get it working. I think I was confused by the fact that checking if a value is in the list also replaces the top of the stack. Nov 6, 2019 at 12:23

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;
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;
return 0;
}


• I think there's a way to save a few bytes here, not sure though Nov 2, 2019 at 7:48
• Try it online! , hello! this is [code-golf] so answers should be shortened as possible, I also suggest to use Tio, here is your solution golfed a bit Nov 2, 2019 at 15:03
• What is fill_n? It seems to be undefined function.
– tsh
Nov 4, 2019 at 9:55
• Where's the score? Surely you can golf this somewhat by removing whitespace and shortening variable names
– Jo King
Nov 4, 2019 at 13:33

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

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

• ... why the downvote?
– Neil
Nov 7, 2019 at 21:33

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

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

g


Try it online!

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

### Explanation:

g


The relevant function: call g with  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.