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.

• Jonah: Nice challenge but it needs test cases and a clearly defined rules.
• girobuz: What's reverse(reverse(10)) and reverse(2)?
• adam: @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
• Phelype Oleinik: 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 :-)
• adam: yes, we can use 0 based-indexing. in that case, the answer will increment by one

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

• adam: Nice solution. But what if we have x = 10**10. is there any way to optimize it
• 79037662: @veersingh I'm sure there is, but this is code golf so there is no reason to do so :)
• Christian Sievers: 73 bytes by improving the last line
• 79037662: @ChristianSievers Thanks for the help.

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

• pizzapants184: Welcome to Code Golf.SE! We generally require library #includes to be counted towards your byte count, so this would be 160 bytes
• ceilingcat: Suggest p=G?W=r,p<=G?G=&W,S++,s:p:s=G=&W instead of G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&W

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.

• Jitse: 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.
• Kevin Cruijssen: @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).
• Jitse: 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.

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

• 79037662: I think there's a way to save a few bytes here, not sure though
• AZTECCO: 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
• tsh: What is fill_n? It seems to be undefined function.
• Jo King: Where's the score? Surely you can golf this somewhat by removing whitespace and shortening variable names

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

Nθ≔0ηW⊖θ«F∧−⊖θXχ⊖Lθ¬%⊖θXχ÷⊕Lθ2«≦⮌θ≦⊕η»≦⊖θ≦⊕η»Iη

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

Nθ

Input the target.

≔0η

Set the number of steps to zero.

W⊖θ«

Repeat until the target becomes 1.

F∧−⊖θXχ⊖Lθ¬%⊖θXχ÷⊕Lθ2

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.

»Iη

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

• Neil: ... why the downvote?

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.