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 by Santiago Valdarrama. 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.

• Optimizer: If one of the input numbers contain a leading 0 (like 05), do we consider it as 05 or simply 5 ?
• user12166: @Optimizer leading zeros are not valid input.
• Tim: Are leading 0s allowed in output?
• Martin Ender: @Tim Where would those come from if there are no leading zeroes in the input?
• Tim: @MartinBüttner oh yes, being silly!

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

• Dennis: OK, I give up. I didn't now e! existed (doesn't even appear in the wiki yet).
• Optimizer: @Dennis there you go
• Dennis: Sweet read. Lots of useful new stuff.
• user12166: It might be useful to update Tips for golfing in CJam with these additional tricks.
• Optimizer: @MichaelT tips generally are not supposed to contain answer which explain the in built features of a language. A couple of answer might need updating as they might benefit from these new features though.

Answer 2

Pyth, (削除) 14 (削除ここまで) 13 bytes

hJSmsd.pcz)eJ

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

• izzyg: Assign J inline: hJSmsd.pcz)eJ
• orlp: @isaacg Good one! I just knew we wouldn't be inferior to that filthy filthy CJam!

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!

• xnor: The comprehension inside sorted works without brackets, but you also can avoid sorting and just take min and max.
• ShadowRanger: Shave eight by using map instead of a listcomp to define z: z=map(''.join,permutations(raw_input().split())). Since it's Python 2, you don't even need to listify (map will produce a new list anyway).

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.

• alephalpha: {#&@@#,Last@#}=>#[[{1,-1}]]
• Martin Ender: @alephalpha Sometimes simpler is better. Thanks! :D

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

• nimi: I think your input format is wrong. Should be "integers separated by a single space on standard input".
• edc65: @nimi you're right.Fixed

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="")),"")

• Alex A.: Nice work. You can save a byte by using just two colons though, i.e. combinat::permn.
• flodel: I thought :: required the package to be loaded (via library or require) but not :::. I could be wrong; need to read a little more about it. Thanks.
• Alex A.: If the library is loaded, you don't need the colons at all; you can just call the function directly since the package is attached to the namespace. If the package is installed but not loaded, you can reference functions in a particular package with two colons.
• flodel: So 58 it can be. I would not allow myself using permn directly without a library(combinat).
• Alex A.: Yeah, because you have to load the library with library(combinat) before you could use permn anyway. ;)

Answer 8

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.

• Andrew: You can replace {|x|x.join} with (&:join) for a 3 byte savings.
• blutorange: A few more ruby shortcuts for 48 bytes: puts$<.read.split.permutation.map(&:join).minmax
• blutorange: If pattern is omitted, the value of $; is used. If $; is nil (which is the default), str is split on whitespace as if ` ‘ were specified.
• blutorange: gets is even shorter for reading input: puts gets.split.permutation.map(&:join).minmax

Answer 9

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 10

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.

• Glory2Ukraine: @Giuseppe fixed that and thanks for debugging! (There was a failure due to the operator precedence in ?x==?a)

Answer 11

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 12

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 13

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

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 16

Scala, 90 bytes

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

Try it online!

Answer 17

Japt, 11 bytes

 ̧á m¬Íé gAì

Try it

Answer 18

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
*/

• edc65: Don't fall in love with template strings. a+` `+b is shorter than `${a} ${b}`

Answer 19

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

Answer 21

AWK, 172 bytes

func p(k,n,l,m,s){if(1~k){for(;l++<n;)s=s a[l]
!e++&&N=s
s<N&&N=s
s>X&&X=s}else{p(k-1,n)
for(;++m<k;p(k-1,n)){t=a[f=k%2?1:m];a[f]=a[k];a[k]=t}}}{p(g=split(0,ドルa),g)}0ドル=N" "X

Attempt This Online!

Answer 22

Uiua, 17 bytes

⊃⊣⊢⍆≡/◇⊂⧅≠∞⊜□しろいしかく⊸≠@ 

There is a single trailing space at the end of the program

Try it in the pad!

Explanation

Simple brute force method

⊃⊣⊢⍆≡/◇⊂⧅≠∞⊜□しろいしかく⊸≠@ 
 ⊜□しろいしかく⊸≠@ # Split on spaces
 ⧅≠∞ # All permutations
 ≡/◇⊂ # Join each together
 ⍆ # Sort them
⊃⊣⊢ # Get the first and last

Answer 23

C, 218 bytes

s(a,b)char**a,**b;{char*p=*a,*q=*b;for(;*p|*q&&*(p=*p?p:*a)==*(q=*q?q:*b);++p,++q);return*q-*p;}int
main(c,v)char**v;{qsort(++v,--c,sizeof*v,s);for(;c--;)printf("%s",v[c]);puts("");for(;*v;)printf("%s",*v++);puts("");}

How it works

We sort with a modified comparison function that sorts e.g. 5 between 54 and 55, by wrapping around at the end of string.

#include <stdio.h>
#include <stdlib.h>
compare(const void *av, const void *bv)
{
 char *const *const a = av;
 char *const *const b = bv;
 char *p;
 char *q;
 for (p = *a, q = *b ; *p != '0円' || *q != '0円'; ++p, ++q) {
 if (!*p) {
 /* wrap around to beginning again */
 p = *a;
 }
 if (!*q) {
 /* wrap around to beginning again */
 q = *b;
 }
 if (*p != *q) {
 /* found a mismatch */
 break;
 }
 }
 /* either a mismatch or both strings ended together */
 return *q - *p;
}
int main(int argc, char **argv)
{
 ++argv; --argc; /* skip over program name */
 qsort(argv, argc, sizeof *argv, compare);
 /* print smallest→largest */
 for (int i = argc-1; i >= 0; --i) {
 printf("%s", argv[i]);
 }
 puts(""); /* newline to separate results */
 /* print largest→smallest */
 for (int i = 0; i < argc; ++i) {
 printf("%s", argv[i]);
 }
}

• ceilingcat: 193 bytes

Answer 24

C++, 303 bytes

#include<algorithm>
#include<ranges>
using namespace std::ranges;namespace V=views;using S=std::string;auto
c(auto r){return r|V::join|to<S>();}auto m(auto&s,int n){return
c(V::repeat(s,n));}auto f(auto&r){sort(r,[](S a,S b){return
m(a,b.size())<m(b,a.size());});return std::pair{c(r),c(r|V::reverse)};}

How it works

#include <algorithm>
#include <ranges>
#include <string>
std::string concat(std::ranges::input_range auto&& r)
{
 return r
 | std::views::join
 | std::ranges::to<std::string>();
}
std::string multiply(std::string s, int count)
{
 return concat(std::views::repeat(s, count));
}
auto f(std::ranges::random_access_range auto&& r)
{
 auto compare = [](std::string const& a, std::string const& b) {
 return multiply(a, b.size()) < multiply(b, a.size());
 };
 std::ranges::sort(r, compare);
 return std::pair{ concat(r), concat(r|std::views::reverse) };
}

Test/demo

Accepts the numbers as command-line arguments, and writes the results to standard output stream.

#include <iostream>
#include <string>
#include <vector>
int main(int argc, char **argv)
{
 std::vector<std::string> s{argv+1, argv+argc};
 auto[lo,hi] = f(s);
 std::cout << lo << '\n'
 << hi << '\n';
}

• ceilingcat: 237 bytes