Largest and smallest values from concatenated integers

Question

This problem is from Five programming problems every Software Engineer should be able to solve in less than 1 hour which itself is an interesting read. The first few problems are trivial, but the fourth one can be a bit more interesting.

Given a list of integers separated by a single space on standard input, print out the largest and smallest values that can be obtained by concatenating the integers together on their own line.

For example:

Input:

5 56 50

Output:

50556
56550

Various points of order:

• The order of the results are smallest then largest.
• Only the smallest and largest values may be printed out (iterating over all the variations and printing them out isn't valid).
• There will always be two or more integers in the list.
• It is possible for the largest and smallest results to be the same. In the case of input 5 55, the number 555 should be printed twice.
• The integers are not necessarily distinct. 5 5 is valid input.
• Leading 0s on integers are not valid input. You will not need to account for 05 55.

As this is code golf, shortest entry wins.

Answer 1

CJam, 14 13 bytes

qS/e!:s$(N@W=

Pretty straight forward. This is how it works:

qS/                  e# Split the input on spaces
   e!                e# Get all permutations of the input numbers
     :s              e# Join each permutation order into a single string
       $             e# Sort them. This sorts the strings based on each digit's value
        (N@W=        e# Choose the first and the last out of the array separated by '\n'

Try it online here

Answer 2

Pyth, 14 13 bytes

hJSmsd.pcz)eJ

Generates all permutations and sorts them, printing the first and last element.

Answer 3

Python 2, 104 99 bytes

Yep.

from itertools import*;z=[''.join(x)for x in permutations(raw_input().split())];print min(z),max(z)

Edit: thanks to xnor for -5 bytes!

Answer 4

Mathematica, 64 58 bytes

Print/@Sort[""<>#&/@Permutations@StringSplit@#][[{1,-1}]]&

This defines an unnamed function taking a string and printing the two lines. It's pretty straightforward as the others: get all permutations, join them together, sort them and print the first and last result.

Six bytes saved thanks to alephalpha.

Answer 5

JavaScript (ES6) 54 72 85

That's easier than it seems. Just sort them lexicographically. The good news is: that's exactly how plain javascript sort works.Well ... no, that's wrong ... still a (more convoluted) lexicograph compare can do the job.

Note: having a and b numeric, a+[b] is a shortcut for a+''+b, as we need a string concatenation and not a sum.
Note 2: the newline inside `` is significant and must be counted

Edit Don't argue with a moderator (...just kidding)

Edit2 Fixed I/O format using popups (see Default for Code Golf: Input/Output methods)

// Complete program with I/O
// The sorting function is shorter as input are strings

alert((l=prompt().split(' ')).sort((a,b)=>a+b>b+a).join('')+`
`+l.reverse().join(''))

// Testable function (67 chars)
// With an integer array parameter, the sorting function must convert to string 

F=l=>(l.sort((a,b)=>a+[b]>b+[a]).join('')+`
`+l.reverse().join(''))

Test In Firefox / FireBug console

F([50, 2, 1, 9])
F([5,56,50])
F([52,36,526])
F([52,36,525])
F([52,36,524]

12509
95021

50556
56550

3652526
5265236

3652525
5255236

3652452
5252436

Answer 6

J, 34 ^{36, 42} bytes

simple brute force:

h=:3 :'0 _1{/:~;"1":&.>y A.~i.!#y'

h 5 50 56
50556 
56550

h 50 2 1 9
12509
95021

Answer 7

R, 59 bytes

write(range(combinat:::permn(scan(),paste,collapse="")),"")

Answer 8

05AB1E, 8 bytes

#œJ{¬sθ»

Try it online.

Explanation:

#         # Split the (implicit) input by spaces
 œ        # Get all permutations of this list
  J       # Join each permutation together to a single string
   {      # Sort this list
    ¬     # Push the first item (without popping the list)
     s    # Swap to get the list again
      θ   # Pop and push its last item
       »  # And join all (both) values on the stack by newlines
          # (after which the result is output implicitly)

Answer 9

R, 96 95 bytes

a=scan();`+`=sort;range(combn(rep(a,L),L<-sum(a|1),function(x)Reduce(paste0,x[all(+x==+a)]),F))

Attempt This Online!

I guess I can justify this rather long golf with the quotation from an unknown author: the verbosity is the price for freedom =).

This solution is indeed independent from any package. Since the permutation function is not provided in the standard R library, I have constructed all possible permutations with the combn function by taking the excess amount of the list elements and filtering out the combinations with the repetitions of the elements. In the combinations that left, the elements get concatenated and minimum and maximum elements are output.

Answer 10

Haskell, 98 bytes

import Data.List
g=sort.map concat.permutations.words
h i=unlines[g i!!0,last$g i]
main=interact h

Split input string at spaces, concatenate every permutation and sort. Print first and last element.

Answer 11

Julia, 77 bytes

v->(Q=extrema([int(join(x)) for x in permutations(v)]);print(Q[1],"\n",Q[2]))

This creates an unnamed function that accepts a vector as input and prints the minimum and maximum of the permutations of the joined elements. To call it, give it a name, e.g. f=v->....

Ungolfed + explanation:

function f(v)
    # Create an integer vector of the joined permutations using comprehension,
    # then get the minimum and maximum as a tuple using extrema().

    Q = extrema([int(join(x)) for x in permutations(v)])

    # Print the minimum and the maximum, separated by a newline.
    print(Q[1], "\n", Q[2])
end

Suggestions are welcome!

Answer 12

Javascript (ES6) 134

Sadly, there's no built-in permutation function in JS :(

f=(o,y,i,a)=>y?o.concat(a[1]?a.filter((k,j)=>j^i).reduce(f,[]).map(z=>y+z):y):(q=o.split(' ').reduce(f,[])).sort().shift()+`
`+q.pop()

<!-- Snippet Demo (Firefox only) -->

<input id="input" value="5 56 50" />
<input type="button" onclick="output.innerHTML=f(input.value)" value="Run" />
<pre id="output"></pre>

Answer 13

Ruby 75

Not my 'native' language, but one I thought I'd give a try at... thus this could (possibly) use some golfing tips. Still, not a bad entrant.

puts STDIN.read.split(" ").permutation.map{|x|x.join}.sort.values_at(0,-1)

I wouldn't say it is elegant other that everything is built in to the language. It should be fairly obvious exactly how this works.

Answer 14

Perl, 79 70B (68+2)

use Math::Combinatorics;say for(sort map{join'',@$_}permute@F)[0,-1]

Call with echo 13 42 532 3 6|perl -M5.10.0 -an scratch.pl. There's a +2 byte penalty for -an. Shame about the length of the module name...

Answer 15

Scala, 90 bytes

val x=Console.in.readLine.split(" ").permutations.map(_.mkString).toSeq
print(x.min,x.max)

Try it online!

Answer 16

JavaScript (ES6), 85 bytes

F=a=>(c=a.split(" ").sort((b,a)=>b+a-(a+b)),`${c.join("")}
${c.reverse().join("")}`)

usage:

F("50 2 1 9")
/*
    12509
    95021
*/

Answer 17

Stax, 11 bytes

ú∙n90≤╣*.vâ

Run and debug it

Link is to unpacked version of code.

Explanation

L|T{$mc|MP|mp implicit input
L             put all inputs in a list
 |T           get the unique orders of the list of inputs
   {$m        convert each list to string
      c       duplicate the array of strings
       |mP    print the minimum element
          |mp print the maximum element

Answer 18

Jelly, 6 bytes

Œ!VṢ.ị

Try it online!

Input and output as lists of integers. +3 bytes to input with spaces and output with newlines

How it works

Œ!VṢ.ị - Main link. Takes a list L on the left e.g. [5, 56, 50]
Œ!     - All permutations of L                      [[5, 56, 50], [5, 50, 56], [56, 5, 50], [56, 50, 5], [50, 5, 56], [50, 56, 5]]
  V    - Concatenate each into numbers              [55650, 55056, 56550, 56505, 50556, 50565]
   Ṣ   - Sort                                       [50556, 50565, 55056, 55650, 56505, 56550]
    .ị - Take the first and last elements           [56550, 50556]

Answer 19

Japt, 11 bytes

¸á m¬Íé gAì

Try it

Answer 20

Setanta \$O(n^2 2^n)\$ dynamic programming solution, 208 bytes

l:=roinn@(leigh())(" ")C:=cmhcht@mata u:=[""]v:=[""]le i idir(1,C(2,fad@l)){p:="A"q:=""le j idir(0,fad@l){k:=C(2,j)ma i//k%2{p=ios(p,u[i-k]+l[j])q=uas(q,v[i-k]+l[j])}}u+=[p]v+=[q]}scriobh(u[-1])scriobh(v[-1])

Try on try-setanta.ie