13
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ Nice challenge but it needs test cases and a clearly defined rules. \$\endgroup\$ – Jonah Nov 1 at 15:14
  • \$\begingroup\$ What's reverse(reverse(10)) and reverse(2)? \$\endgroup\$ – girobuz Nov 1 at 22:16
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – adam Nov 1 at 23:07
  • \$\begingroup\$ 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 :-) \$\endgroup\$ – Phelype Oleinik Nov 2 at 15:43
  • 2
    \$\begingroup\$ yes, we can use 0 based-indexing. in that case, the answer will increment by one \$\endgroup\$ – adam Nov 5 at 9:30

10 Answers 10

7
\$\begingroup\$

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

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

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

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ I think there's a way to save a few bytes here, not sure though \$\endgroup\$ – 79037662 Nov 2 at 7:48
  • 4
    \$\begingroup\$ 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 \$\endgroup\$ – AZTECCO Nov 2 at 15:03
  • \$\begingroup\$ What is fill_n? It seems to be undefined function. \$\endgroup\$ – tsh Nov 4 at 9:55
  • \$\begingroup\$ Where's the score? Surely you can golf this somewhat by removing whitespace and shortening variable names \$\endgroup\$ – Jo King Nov 4 at 13:33
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Jitse Nov 6 at 10:29
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – Kevin Cruijssen Nov 6 at 12:17
  • \$\begingroup\$ 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. \$\endgroup\$ – Jitse Nov 6 at 12:23
0
\$\begingroup\$

Charcoal, 47 bytes

Nθ≔⁰ηW⊖θ«F∧⁻⊖θXχ⊖Lθ¬﹪⊖θXχ÷⊕L貫≦⮌θ≦⊕η»≦⊖θ≦⊕η»Iη

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

Nθ

Input the target.

≔⁰η

Set the number of steps to zero.

W⊖θ«

Repeat until the target becomes 1.

F∧⁻⊖θXχ⊖Lθ¬﹪⊖θXχ÷⊕Lθ²

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.

\$\endgroup\$
  • \$\begingroup\$ ... why the downvote? \$\endgroup\$ – Neil Nov 7 at 21:33
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.