# Expand and Contract

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.

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

# Haskell, 726864 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  • Welcome to PPCG! Nice first answer. Apr 3, 2019 at 9:13 • 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. Apr 3, 2019 at 9:21 • Welcome to the site! Since (^) is higher precedence than (+) you don't need parentheses around the (^) expression. Same goes for (!) and (:) Apr 3, 2019 at 13:24 • 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. Apr 4, 2019 at 9:27 • 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! Apr 4, 2019 at 9:37

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

• 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.) Apr 4, 2019 at 17:36

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

# 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


# 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\$$

# 05AB1E, 15 bytes

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


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

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

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


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


# Jelly, 19 bytes

1µ«³_$DL’⁵*$+µ<³\$Ð¿


Try it online!

# Wolfram Language (Mathematica), 51 bytes

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


Try it online!

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

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

• 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! Apr 3, 2019 at 13:15
• That is horrendous coding, I like it. incidently, I can set o=1, and get that second byte. Apr 3, 2019 at 13:23

# Jelly, 12 bytes

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


Try it online!

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

# 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


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

# 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