19
\$\begingroup\$

Take a positive integer \$k\$ as input. Start with \$n := 1\$ and repeatedly increase \$n\$ by the largest integer power of ten \$i\$ such that \$i \le n\$ and \$i + n \le k\$.

Repeat until \$n = k\$ and return a list of all intermediate values of \$n\$, including both the initial \$1\$ and the final \$k\$.

During this process, growth will initially be limited by the former inequality, and only afterwards by the latter; the growth will take the form of an initial "expansion" period, during which \$n\$ is increased by ever-larger powers, followed by a "contract" period, during which \$n\$ is increased by ever-smaller powers in order to "zoom in" on the correct number.

Test Cases

1 => [1]
10 => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
321 => [1,  2,  3,  4,  5,  6,  7,  8,  9,
        10, 20, 30, 40, 50, 60, 70, 80, 90,
        100, 200, 300, 310, 320, 321]
1002 => [1,   2,   3,   4,   5,   6,   7,   8,   9,
         10,  20,  30,  40,  50,  60,  70,  80,  90,
         100, 200, 300, 400, 500, 600, 700, 800, 900,
         1000, 1001, 1002]

This is , so the shortest answer (in bytes) wins.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ May we print the numbers instead of returning a list? \$\endgroup\$
    – Adám
    Apr 3, 2019 at 8:01
  • \$\begingroup\$ @Adám Yes, you may. \$\endgroup\$ Apr 3, 2019 at 16:32

15 Answers 15

8
\$\begingroup\$

Haskell, 72 68 64 63 bytes

f=(1!)
c!t|t==c=[c]|t>c=c:(c+10^(pred.length.show.min c$t-c))!t

Try it online!

Thanks Sriotchilism O'Zaic for -4 bytes!

Usage

f 321
[1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100,200,300,310,320,321]

Explanation

c!t         -- c=current number, t=target number
 |t==c=[c]  -- Target is reached, return last number
 |t>c=c:(c+10^(pred.length.show.min c$t-c))!t
      c:                                        -- Add current number to list
                                min c$t-c       -- The minimum of the current number, and the difference between the current number and the target
                    length.show.                -- The length of this number
               pred.                            -- Minus 1
           10^(                          )      -- Raise 10 to this power
         c+                                     -- Add that to the current number
        (                                 )!t   -- Recursion
\$\endgroup\$
9
  • 4
    \$\begingroup\$ Welcome to PPCG! Nice first answer. \$\endgroup\$
    – Arnauld
    Apr 3, 2019 at 9:13
  • 2
    \$\begingroup\$ I don't know Haskell, but maybe any of these tips might help: tips for golfing in Haskell and tips for golfing in <all languages>. But I agree, nice answer. +1 from me. \$\endgroup\$ Apr 3, 2019 at 9:21
  • 2
    \$\begingroup\$ Welcome to the site! Since (^) is higher precedence than (+) you don't need parentheses around the (^) expression. Same goes for (!) and (:) \$\endgroup\$
    – Wheat Wizard
    Apr 3, 2019 at 13:24
  • 1
    \$\begingroup\$ pred.length.show.min c$t-c can be shortened to length(show.min c$t-c)-1. Anonymous functions are acceptable, so you can drop the leading f= as explained in our guide to golfing rules in Haskell. \$\endgroup\$
    – Laikoni
    Apr 4, 2019 at 9:27
  • 1
    \$\begingroup\$ Instead of guards, you can use only one case and a conditional: c!t=c: if t>c then (c+10^(length(show.min c$t-c)-1))!t else []. This allows to apply this tip to save a few more bytes: Try it online! \$\endgroup\$
    – Laikoni
    Apr 4, 2019 at 9:37
6
\$\begingroup\$

JavaScript (ES6), 50 bytes

f=n=>n?[...f(n-(1+/(^10)?(0*$)/.exec(n)[2])),n]:[]

Try it online!

How?

Theory

The following steps are repeated until \$n=0\$:

  • look for the number \$k\$ of trailing zeros in the decimal representation of \$n\$
  • decrement \$k\$ if \$n\$ is an exact power of \$10\$
  • subtract \$x=10^k\$ from \$n\$

Implementation

The value of \$x\$ is directly computed as a string with the following expression:

+---- leading '1'
|
1 + /(^10)?(0*$)/.exec(n)[2]
     \____/\___/
        |    |
        |    +---- trailing zeros (the capturing group that is appended to the leading '1')
        +--------- discard one zero if n starts with '10'

Note: Excluding the leading '10' only affects exact powers of \$10\$ (e.g. \$n=\color{red}{10}\color{green}{00}\$) but does not change the number of captured trailing zeros for values such as \$n=\color{red}{10}23\color{green}{00}\$ (because of the extra non-zero middle digits, '10' is actually not matched at all in such cases).

\$\endgroup\$
1
  • \$\begingroup\$ Ingenious noting you can do the iteration "backwards" keeping track of only one variable! It's a bit confusing that you use k for something completely different than in the challenge description (in fact your n is a mix of OP's n and k and your x is their i.) \$\endgroup\$ Apr 4, 2019 at 17:36
3
\$\begingroup\$

Python 2, 61 bytes

f=lambda k,n=1:n<k and[n]+f(k,n+10**~-len(`min(n,k-n)`))or[n]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 48 41 bytes

->\k{1,{$_+10**min($_,k-$_).comb/10}...k}

Try it online!

Explanation:

->\k{                                   }  # Anonymous code block taking k
     1,                             ...k   # Start a sequence from 1 to k
       {                           }       # Where each element is
        $_+          # The previous element plus
           10**      # 10 to the power of
                           .comb     # The length of
               min($_,k-$_)          # The min of the current count and the remainder
                                /10  # Minus one
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 30 bytesSBCS

Anonymous tacit prefix function. Prints numbers on separate lines to stdout.

{⍺=⍵:⍺⋄⍺∇⍵+10*⌊/⌊10⍟⍵,⍺-⎕←⍵}∘1

Try it online!

{}∘1 anonymous infix lambda with 1 curried as initial \$n\$:

⍺=⍵ if \$k\$ and \$n\$ are equal:

   return (and implicitly print) \$k\$

  else:

  ⎕←⍵ print \$n\$

  ⍺- subtract that from \$k\$

  ⍵, prepend \$n\$

  10⍟\$\log_{10}\$ of those

   floor those

  ⌊/ minimum of those

  10* ten raised to the power of that

  ⍵+\$n\$ plus that

  ⍺∇ recurse using same \$k\$ and new \$n\$

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 15 bytes

1[=ÐIαD_#‚ßg<°+

Port of @PaulMutser's (first) Haskell answer, so make sure to upvote him!!

Try it online or verify all test cases.

Outputs the numbers newline delimited.
If it must be a list, I'd have to add 3 bytes:

X[DˆÐIαD_#‚ßg<°+}¯

Try it online or verify all test cases.

Explanation:

1             # Push a 1 to the stack
 [            # Start an infinite loop
  =           #  Print the current number with trailing newline (without popping it)
  Ð           #  Triplicate the current number
   Iα         #  Get the absolute difference with the input
     D        #  Duplicate that absolute difference
      _       #  If this difference is 0:
       #      #   Stop the infinite loop
      ‚ß      #  Pair it with the current number, and pop and push the minimum
        g<°   #  Calculate 10 to the power of the length of the minimum minus 1
           +  #  And add it to the current number
\$\endgroup\$
1
\$\begingroup\$

Jelly, 19 bytes

1µ«³_$DL’⁵*$+µ<³$п

Try it online!

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

Wolfram Language (Mathematica), 51 bytes

Union@NestList[#+10^Floor@Log10@Min[s-#,#]&,1,s=#]&

Try it online!

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

Batch, 131 bytes

@set/an=i=1
:e
@if %n%==%i%0 set i=%i%0
@echo %n%
:c
@set/an+=i
@if %n% leq %1 goto e
@set/an-=i,i/=10
@if %i% neq 0 goto c

Takes input as a command-line parameter and outputs the list of numbers to STDOUT. Explanation:

@set/an=i=1

Start with n=1 and i=1 representing the power of 10.

:e
@if %n%==%i%0 set i=%i%0

Multiply i by 10 if n has reached the next power of 10.

@echo %n%

Output the current value of n.

:c
@set/an+=i
@if %n% leq %1 goto e

Repeat while i can be added to n without it exceeding the input.

@set/an-=i,i/=10

Restore the previous value of n and divide i by 10.

@if %i% neq 0 goto c

If i is not zero then try adding i to n again.

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

R, 67 65 bytes

-2 bytes thanks to Giuseppe

k=scan();o=1;i=10^(k:0);while(T<k)o=c(o,T<-T+i[i<=T&i+T<=k][1]);o

Pretty simple. It takes a set of powers of 10 beyond what would be needed in reverse order i.

(I would prefer to use i=10^rev(0:log10(k)) instead of i=10^(k:0) since the latter is computationally ineffecient, but golf is golf!).

Then in a while loop, applies the conditions to i and takes the first (i.e. largest); updates n, and appends to output

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Save a byte using T instead of n; it should be 2 but I don't think that TRUE is acceptable output for k=1, so we set o=+T. Try it! \$\endgroup\$
    – Giuseppe
    Apr 3, 2019 at 13:15
  • 2
    \$\begingroup\$ That is horrendous coding, I like it. incidently, I can set o=1, and get that second byte. \$\endgroup\$ Apr 3, 2019 at 13:23
1
\$\begingroup\$

Jelly, 12 bytes

1+«ạæḟ⁵«Ɗɗ¥Ƭ

Try it online!

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

Pip, 27 bytes

Wa>Po+:y/t*Y1Ty>o|o+y>ay*:t

Try it online!

In pseudocode:

a = args[0]
o = 1
print o
while a > o {
  y = 1
  till y > o || o + y > a
    y *= 10
  o += y / 10
  print o
}

I'm pretty pleased with the golfing tricks I was able to apply to shorten this algorithm. By initializing, updating, and printing stuff in the loop header, I was able to avoid needing curly braces for the loop body. There's probably a golfier algorithm, though.

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

Japt, 18 bytes

ÆT±ApTmTnU)sÊÉÃf§U

Try it

ÆT±ApTmTnU)sÊÉÃf§U     :Implicit input of integer U
Æ                      :Map the range [0,U)
 T±                    :  Increment T (initially 0) by
   A                   :  10
    p                  :  Raised to the power of
     Tm                :    The minimum of T and
       TnU             :      T subtracted from U
          )            :    End minimum
           s           :    Convert to string
            Ê          :    Length
             É         :    Subtract 1
              Ã        :End map
               f       :Filter
                §U     :  Less than or equal to U
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 123 122 bytes

m=>{var a=new[]{1}.ToList();int s;for(;(s=a.Last())<m;)a.Add(s+(int)Math.Pow(10,(int)Math.Log(s<m-s?s:m-s,10)));return a;}

Try it online!

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

Prolog (SWI), 142 bytes

L-D-M:-append(L,[D],M).
N-L-C-X-R-I:-I=1,C is X*10,N-L-C-C-R-1;D is C+X,(D<N,L-D-M,N-M-D-X-R-I;D>N,N-L-C-(X/10)-R-0;L-D-R).
N-R:-N-[]-0-1-R-1.

Try it online!

Explanation coming tomorrow or something

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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