Make the biggest and smallest numbers

Question

Inspired by this post over on Puzzling. Spoilers for that puzzle are below.

Given three positive integers as input, (x, y, z), construct the inclusive range [x, y], concatenate that range together, then remove z not-necessarily-consecutive digits to produce the largest and smallest positive integers possible. Leading zeros are not permitted (i.e., the numbers must start with [1-9]). Output those two numbers in either order.

For the example from the Puzzling post, for input (1, 100, 100), the largest number possible is 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100,
and the smallest number is 10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100,
following the below logic from jafe's answer posted there:

• We can't influence the number's length (there's a fixed number of digits), so to maximize the value we take the maximal first digit, then second digit etc.
• Remove the 84 first non-nines (16 digits left to remove): 999995051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
• The largest number within the next 17 digits is 7, so from here, the next digit in the answer can be at most 7 (we can't remove more than 16 digits). So remove 15 non-7's... (1 digit left to remove): 999997585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
• From here, the next digit can be at most 8 so remove one non-8 from the middle: 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
• Similar logic, but reversed (i.e., we want leading 1s instead of leading 9s) for the smallest number.

Here's a smaller example: (1, 10, 5).

We construct the range 12345678910 and determine which 5 digits we can remove leaving the largest possible number. Obviously, that means we want to maximize the leading digit, since we can't influence the length of the output. So, if we remove 12345, we're left with 678910, and that's the largest we can make. Making the smallest is a little bit trickier, since we can pluck out numbers from the middle instead, leaving 123410 as the smallest possible.

For (20, 25, 11), the result is rather boring, as 5 and 1.

Finally, to rule out answers that try leading zeros, (9, 11, 3) gives 91011 which in turn yields 91 and 10 as the largest and smallest.

I/O and Rules

• If it's easier/shorter, you can code two programs/functions -- one for the largest and one for the smallest -- in which case your score is the sum of both parts.
• The input and output can be given by any convenient method.
• The input can be assumed to fit in your language's native number type, however, neither the concatenated number nor the output can be assumed to do so.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

Haskell, 162 bytes

l=length
((m,f)%n)s|n>=l s=[]|n>0,(p,c:r)<-span(/=m(f$take(n+1)s))s=c:((m,id)%(n-l p)$r)|1>0=s
(x#y)z=[p%z$show=<<[x..y]|p<-[(maximum,id),(minimum,filter(>'0'))]]

Try it online!

Uses the algorithm described by jafe. Might be shorter to use a less efficient method, but this was more fun to write :)

The % operation takes 4 arguments (actually 3, but whatever): m which is a function that selects the "optimal" member from a list (either maximum or minimum depending on what we want); f which is a "filter" function; n the number of digits left to drop; and s the string. First we check whether n is equal to the number of digits left in the string (I used >= for safety) and drop the rest of s if so. Otherwise we check if we still need to drop digits (n>0), then we use span to break our string into three pieces: p the digits to drop, c the optimal reachable digit, and r the remaining string. We do this by passing span a predicate that checks for equality against our optimal digit. To find that digit we take the first n+1 digits of the string, filter it, then pass it to our "chooser" function. Now we just yield our optimal digit and recur, subtracting the length of p (the number of digits dropped) from n. Notice that we do not pass our filtering function to the recursive call, and, instead, we replace it with id. That's because the filter is only there to avoid selecting leading 0s in the minimum case which is only relevant on the first iteration. After that we no longer need any filter.

% is really only a helper function for # which is our "real" function, taking x, y, and z. We use a list comprehension just to avoid a bit of repetition, iterating over our function tuples and passing them to % along with z and the concatenated string. That string is created using the magic monad operator (=<<) which, in this context, works like concatMap.

Answer 2

Jelly, 17 bytes

r/VDœcL_¥¥ḷ/ƇVṢ.ị

Try it online!

Calculates all possibilities then keeps the largest and smallest.

Left argument: x,y to construct the range. Right argument: z digits to be removed.

r/VDœcL_¥¥ḷ/ƇVṢ.ị
r/                 Inclusive range from x to y
  V                Concatenate the digits together
   D               Get the resulting digits
         ¥         Dyad:
        ¥            Dyad:
      L                Length of the list of digits in the concatenated number.
       _               Subtract the number of digits to be removed.
    œc               Combinations without replacement. (remove z digits)
            Ƈ      Keep lists of digits that:
          ḷ/       have a positive first element (no leading zeros).
             V     Combine digits into integers. (vectorizes to ldepth 1)
              Ṣ    Sort the numbers
               .ị  Indexes at value 0.5 which yields the first and last elements.

Answer 3

Python 2, 143 bytes

import itertools
s,e,r=input()
l=''.join(map(str,range(s,e+1)))
L=[i for i in itertools.combinations(l,len(l)-r)if'0'<i[0]]
print min(L),max(L)

Try it online!

This works by calculating all combinations of the target size (the element order is preserved) and getting the smallest / biggest numbers from it

Answer 4

Charcoal, 56 bytes or 21 + 46 35 = 67 56 bytes

≔⪫…·ＮＮωθＦＮ≔⌈ＥθΦθ⁻λνθθ

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

≔⪫…·ＮＮωθ

Input x and y, create an inclusive range and join the numbers into a string.

ＦＮ

Loop once for each digit to be removed.

≔⌈ＥθΦθ⁻λνθ

Create a list of strings formed by removing each possible character from the current string and take the maximum.

θ

Print the result.

≔⪫…·ＮＮωθＦ⊕Ｎ⊞υωΦθ∧⁼ι⌊Φ✂θκＬυ¹∨κＩλ⊞Ｏυω

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

≔⪫…·ＮＮωθ

Input x and y, create an inclusive range and join the numbers into a string.

Ｆ⊕Ｎ⊞υω

Input z and increment it. I then create a list of that length: I need to be able to increment z inside the following filter, but only commands are allowed to increment variables; there is a loophole in that PushOperator increments the length of the list.

 θ                      String of digits
Φ                       Filter over characters
         κ              Current index
          Ｌυ            Length of list i.e. current `z` value
            ¹           Literal 1
       ✂θ               Slice string of digits
      Φ                 Filter over characters
              κ         Outer index
               Ｉλ       Cast inner character to number
             ∨          Logical OR
     ⌊                  Minimum
   ⁼ι                   Equals the outer character
  ∧              ⊞Ｏυω   And also push to list i.e. increment `z`
                        Implicitly print

Filter on the characters that are wanted by checking that there are no lower characters in the sliceable region. The region starts with the first z+1 characters (since it's possible to slice the first z away if necessary) and the end point increments for each character that is kept. Care is taken not to choose a zero for the first character.

The faster algorithm is 30 bytes when used to compute the largest possible number:

≔⪫…·ＮＮωθＦ⊕Ｎ⊞υωΦθ∧⁼ι⌈✂θκＬυ¹⊞Ｏυω

Try it online! Link is to verbose version of code. Edit: I've since been able to combine the above two into a second 56 byte solution which generates both results:

≔⪫…·ＮＮωθＦ⊕Ｎ⊞υω≔⮌υη⟦Φθ∧⁼ι⌈✂θκＬυ¹⊞ＯυωΦθ∧⁼ι⌊Φ✂θκＬη¹∨κＩλ⊞Ｏηω

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

≔⪫…·ＮＮωθ

Generate the initial string.

Ｆ⊕Ｎ⊞υω

Represent z+1 as the length of the list.

≔⮌υη

Reverse the list thus cloning it and save the result.

⟦

Print the two results on separate lines. (Another way of doing this is to separate the results with a literal \r character.)

Φθ∧⁼ι⌈✂θκＬυ¹⊞Ｏυω

Generate the largest possible number.

Φθ∧⁼ι⌊Φ✂θκＬη¹∨κＩλ⊞Ｏηω

Generate the smallest possible number using the cloned list to keep track of z.

Answer 5

Jelly,  19  18 bytes

rDẎœcL_⁵Ɗ$ị@Ƈ1ḌṢ.ị

Try it online!

Very inefficient, definately no point going for 1, 100, 100 as \$\binom{192}{92}=305812874887035355118559193163641366325011573739619723360\$

Answer 6

05AB1E, 16 bytes

ŸSDg³-.Æʒ¬Ā}{Ć`‚

Try it online!

Full program, reading inputs in this order: y, x, z. Outputs a list of two lists of characters.

Explanation

ŸSDg³-.Æʒ¬Ā}{Ć`‚    Full program. Inputs: y, x, z.
Ÿ                   Inclusive binary range from x to y. Push [x ... y].
 S                  Dump the digits separately in a list.
  Dg                Duplicate, and use the second copy to get its length.
    ³-              Subtract z from the length.
      .Æ            Retrieve all combinations of length - z elements from the digits.
        ʒ  }        Keep only those that...
         ¬Ā         Don't start with a 0 (head, then Python-style boolean).
            {       Sort the remaining elements.
             Ć      Enclose. Pushes list + list[0] (appends its tail to itself)
              `     Dump all elements separately on the stack.
               ,    Pair, to get the last two, min and max (after enclosing)

Answer 7

Matlab, 95 bytes

function[m]=f(s,e,c),a=sprintf('%d',s:e);x=str2num(combnk(a,length(a)-c));m=[min(x),max(x)];end

Try it Online!

Returns an 1x2 matrix with min and max.

How it works

% Full code
function[m]=f(s,e,c),a=sprintf('%d',s:e);x=str2num(combnk(a,length(a)-c));m=[min(x),max(x)];end

% The function
function[m]=f(s,e,c),                                                                       end

                     % Creates the range in a single string
                     a=sprintf('%d',s:e);

                                                   % Gets all the combinations
                                                   combnk(a,length(a)-c)

                                         % Converts the string combinations to integers
                                         x=str2num(                     );

                                                                          % Finds min and max
                                                                          m=[min(x),max(x)];