Sort by what the digit pairs describe

Question

Given a positive integer, we can form a new number that's described by its digits taken pairwise (with a leading 0 added for numbers with odd number of digits).

For eg.:

• 1234 can be read as one 2, three 4s - so, the output for 1234 is 2444.

• 643 has an odd number of digits, so a leading zero is added to make it even. Then, 0643 can be read as: zero 6s, four 3s, hence the output would be 3333.

(This is OEIS A056967).

Task: Given an array of positive integers, sort them by their digit-pair-described value, in ascending order. Order does not matter between input numbers that lead to the same value.

Input: an array/list/set of positive integers. Leading zeros in the input are not allowed, and input as strings/lists of digits/etc. are not allowed - the inputs should be as close to an integer/numeric type as your language is capable of using.

Output: the array sorted in the above-mentioned way, returned in any of the usual ways (function return value/STDOUT/shouting into the void/etc.) You can print them individually, return them as numbers, strings, or lists of digits.

Test cases

Input 
Output

[19, 91, 2345, 2023]
[19, 2023, 2345, 91]

[25257, 725, 91, 5219, 146125, 14620512]
[725, 5219, 14620512, 91, 146125, 25257]

[123130415 3335 91 111111111 528 88]
[528, 111111111, 123130415, 3335, 88, 91]

[1 21 33 4 5]
[1 4 5 21 33]

[3725, 10, 2537, 1, 1225, 2512]
[10, 1, 1225, 2512, 2537, 3725]

[125, 26, 1115, 1024] 
[1115, 1024, 125, 26]

(In the 4th test case, 1, 4, and 5 all evaluate to 0, and so can be sorted among themselves in any order. Similarly in the fifth test case, 10 and 1 both evaluate to 0s, and so can be sorted in either order.)

(Related: Say what you see, One 1, Two 1's, One 2 One 1

Thanks to Kevin Cruijssen for help clarifying the question in the Sandbox.

Answer 1

APL (Dyalog), 26 bytes

Thanks ngn for saving 1 byte :)

{⍵[⍋⌽↑,⍨⌿⍴⌿0 10⊤⍵⊤⍨⍴⍨100]}

Try it online!

Inspiration take from dzaima & ngn

Answer 2

R, 141 bytes

(s<-scan(,""))[order(strtoi(sapply(s,function(x)paste(strrep((m=matrix(c(if(nchar(x)%%2)0,el(strsplit(x,""))),2))[2,],m[1,]),collapse=""))))]

Try it online!

Rather laborious answer - but it works on all test cases. Builds the digit-pair output and sorts the input according to this.

Answer 3

R, 120 bytes

(v=scan())[order(sapply(v,function(n,e=nchar(n))sum((a=rep((x=n%/%10^(0:(e-1-e%%2))%%10)[!0:1],x[!1:0]))*10^seq(a=a))))]

Try it online!

• -11 bytes thanks to @sundar "arithmetical" suggestion !

Ungolfed code with explanation :

# define a function G which takes a number 'n' and uncompress it multiplied by 10
# e.g. 2735 -> 775550, 61345 -> 355550 etc.
G=function(n){
  e = nchar(n)                   # get the n.of digits in the compressed number

  x = n%/%10^(0:(e-1-e%%2))%%10  # split 'n' into vector of digits reversed adding 
                                 # trailing zero if 'e' is odd (e.g. 123 -> c(0,3,2,1))

  even = x[!0:1]                 # take only the odd elements of 'x' (= even digits)
  odd  = x[!1:0]                 # take only the even elements of 'x' (= odd digits)
                                 # N.B. :
                                 # these tricks work because !0:1 is c(TRUE,FALSE)
                                 # and V[c(TRUE,FALSE)] exploits the fact that R 
                                 # automatically recycles the logical indexes up to the
                                 # length of the vector V

  a = rep(even,odd)              # repeat each value in 'even' 'odd' times obtaining the
                                 # uncompressed number as digits vector. Note that in
                                 #  case of single digit 'n', 'a' will be an empty vector

  sum(a*10^seq(a=a))             # multiplies 'a' * 10^(1:length(a)) and sum 
                                 # obtaining the uncompressed number multiplied by 10
                                 # N.B. in case of empty 'a', we get 0
}

v = scan()                       # take vector v from stdin

w = sapply(v,G(n))               # apply G to all numbers of 'v'

v[order(w)]                      # use the uncompressed values as weights to sort 'v'

Answer 4

Pyth, 14 bytes

oir9c.[Z2jNT2T

Try it here! | Test suite! | 12 bytes with list of digits I/O

How it works?

oir9c.[Z2jNT2T – Full program.
o              – Sort the input list by the results of the following code (variable: N).
         jNT   – Cast the current element to a list of digits.
     .[Z2      – Pad it on the left with 0s to the nearest multiple of 2.
    c       2  – Split in pieces of length 2.
  r9           – Run length decode.
 i           T – Cast the list of digits to a base 10 integer.

Answer 5

Dyalog APL, 41 39 36 35 31 30 29 bytes

f←⊂⌷¨⍨∘⍋{10⊥∊⍴⌿0 10⊤100⊥⍣¯1⊢⍵}¨

Try it online!

-2 thanks to Cows quack
-4 (plus -4 for the base conversion idea) thanks to ngn
-2 thanks so H.PWiz

Answer 6

Jelly, 10 bytes

ṚẋƝm2ṚFḌµÞ

Try it online!

Check out a test suite!

How it works

ṚẋƝm2ṚFḌµÞ    Monadic link / Full program.                            | Example: [25257, 725, 91, 5219, 146125, 14620512]
        µÞ    Sort the input list by the result of the monadic link:  | Example: 725
Ṛ             Promote N to its digit array and reverse it.            | [5, 2, 7]
 ẋƝ           For each two consecutive digits x, y, repeat x y times. | [[5, 5], [2, 2, 2, 2, 2, 2, 2]]
   m2         Modular 2. Take every other element of this array.      | [[5, 5]]
     Ṛ        Reverse.                                                | [[5, 5]]
      F       Flatten.                                                | [5, 5]
       Ḍ      Convert from decimal to integer.                        | 55

Answer 7

C (gcc) (32bit systems), 188 177 176 bytes

char*p,*q,c[99],b[99]="0";i;d(x){for(p=b+!(sprintf(b+1,"%d",x)&1),q=c;i=*p++;++p)for(i-=48;i--;*q++=*p);*q=0;atoi(c);}m(int*a,int*b){return d(*a)-d(*b);}s(l,c){qsort(l,c,4,m);}

Try it online!

on amd64 add flag -m32 for compiling.

Usage: s(x,n); where x points to an array of integers to sort and n is the length of that array.

Second test case gives wrong result because converting 25257 gives 2222277777 which overflows a 32bit integer -- added a 5th test case without that number.

Explanation:

char*p,                                     // d(): input pointer
    *q,                                     // d(): output pointer
    c[99],                                  // d(): output buffer
    b[99]="0";                              // d(): input buffer
                                            //      (fixed first char 0)
i;                                          // d(): repeat counter

d(x){                                       // conversion function
    for(
            p=b+!(sprintf(b+1,"%d",x)&1),   // print number in decimal to
                                            // input buffer, starting at second
                                            // character, initialize input
                                            // pointer to first or second char
                                            // depending on the length of the
                                            // number
            q=c;                            // initialize output pointer
            i=*p++;                         // set repeat counter to digit and
                                            // point to next digit, stop when
                                            // NUL character is found
            ++p)                            // point to next digit after loop
        for(i-=48;i--;*q++=*p);             // inner loop, append current digit
                                            // i-48 ('0') times to output buffer
    *q=0;                                   // terminate output with NUL
    atoi(c);                                // convert to number, 'return' not
                                            // needed as atoi() leaves result
                                            // on the stack
}

m(int*a,int*b){                             // comparison function for qsort
    return d(*a)-d(*b);                     // return difference of converted
}                                           // values

s(l,c){                                     // sorting function
    qsort(l,c,4,m);                         // only "wrap" qsort, assuming
}                                           // sizeof(int) is 4

Answer 8

Perl 6, 53 bytes

*.sort(+*.flip.comb.rotor(2).map({[x] $_}).join.flip)

Try it online!

Anonymous Whatever lambda that takes a list of values and sorts it by what the pairs of numbers describe.

In this case, I'm reversing the number, then rotoring the list by two to get each pair of numbers. This will exclude the first digit for numbers of odd length, but since that translates to 0 times that number, it's okay. Plus, it lines up the values to use [x] correctly.

Answer 9

Haskell, 89 88 bytes

Saved a byte thanks to ovs

import Data.List
(%)=mod
m?n|n<1=0|n%100<10=m?div n 100|w<-n-10=m*10?w+m*n%10
sortOn(1?)

The last line defines an anonymous function that can be used like so:

> sortOn(1?)[19, 91, 2345, 2023]
[19,2023,2345,91]

The core functionality is provided by the infix operator (?) which keeps track of a multiplier, m, and the remaining RLE input n. (?) continually subtracts 10 from n whilst there is a tens digit to subtract from, and as it does so it pushes another copy of the final digit to the front of the output (via the multiplier m, which is increased by 10 each time). When the tens place is exhausted, the final two digits are discarded and the process repeats until the number is reduced to 0. Finally, we use the operator (with an initial multiplier of 1) as a sort key.

Answer 10

Python 2, 80 74 bytes

def g(l):l.sort(key=f)
f=lambda n:+(n>9)and int(`f(n/100)`+n/10%10*`n%10`)

Try it online!

Answer 11

Husk, 10 bytes

ÖödṁΓ*C_2d

Try it online!

Explanation

ÖödṁΓ*C_2d    Full function
Ö             Sort the input list by the result of...
 ö            The composition of these four functions:
         d      Convert to a list of digits
      C_2       Split into length-2 sublists starting at the end
   ṁ            Map the following function and concatenate the results:
    Γ*            Repeat the list tail X times, where X is the list head
  d             Convert back to an integer

Answer 12

Python 2, 102 101 97 101 bytes

lambda l:sorted(l,key=lambda x:int(''.join(v*int(c)for c,v in zip(*[iter(`x`[len(`x`)%2:])]*2))or 0))

Try it online!

Answer 13

Japt, 13 bytes

ñ_ì_ò2n)®rçì

Try it or run all test cases

---

Explanation

ñ_                :Sort by passing each integer through a function
  ì_              :  Split to an array of digits, pass it through the following function and implicitly convert back to an integer
    ò2n)          :    Starting from the end of the array, split at every second element
        ®         :    Map
         rç       :      Reduce X & Y by repeating X Y times
           Ã      :    End mapping
            ¬     :    Join

Answer 14

Brachylog, 18 bytes

{↔ġ₂ẹ{Ċj₎|Ȯt}ˢ↔c}ᵒ

Try it online!

Explanation

Loads of small stuff needed to account for the three different cases: odd number of digits, pair of 0 times a number, and normal pairs.

{               }ᵒ     Order the Input according to the output of this predicate
 ↔                       Reverse the number
  ġ₂                     Group into pairs; the last digit is alone if there are
                           an odd number of them
    ẹ{      }ˢ           For each group:
      Ċ                    If there are two elements
       j₎                  Juxtapose the first one as many times as the second
                             element (won't work if the second element is 0)
         |                 Else
          Ȯ                If there is one element (odd number of digits)
           t               just take that element
                           (Else don't select anything, i.e. 0 repetitions)
              ↔c         Reverse and concatenate back into an integer

Answer 15

Perl 5, 76 bytes

A function instead of a one-liner for once.

Quite straight forward: g sorts the inputs numerically, using h to convert the numbers. h does this by using the regex s/(.)(.)/$2x$1/gre (which is probably readable enough). And the 0 left-padding is done with 0 x("@_"=~y///c%2)."@_" (where y///c is a shorted way of writing length, x is the repetition operator and . the concatenation).

sub h{(0 x("@_"=~y///c%2)."@_")=~s/(.)(.)/$2x$1/gre}sub g{sort{h($a)-h$b}@_}

Try it online!

I'm expecting to see some shorter Perl answers though!

Answer 16

05AB1E, 20 19 bytes

ΣDgÉi¦}2ôε`sиJ}J0ìï

Bug-fixed for +1 byte, and then golfed by -2 bytes thanks to @sundar.

Try it online or verify all test cases.

Can definitely be golfed.. Not too happy about it tbh..

Explanation:

Σ                    # Sort by:
 Dg                  #  Duplicate the current number, and take it's length
                     #   i.e. 25257 → 5
                     #   i.e. 4 → 1
   Éi }              #  If this length is odd:
     ¦               #   Remove the first digit
                     #    i.e. 25257 → '5257'
                     #    i.e. 4 → ''
       2ô            #  Then split the number in pieces of 2
                     #   i.e. '5257' → ['52','57']
                     #   i.e. '' → []
         ε    }      #  And map each to:
          `          #   Push both digits to the stack
                     #    i.e. '52' → '5' and '2'
           s         #   Swap them
            и        #   Repeat the first digit the second digit amount of times
                     #    i.e. '2' and '5' → ['2','2','2','2','2']
             J       #   Join the list of digits together
                     #    i.e. ['2','2','2','2','2'] → '22222'
               J     #  Join all numbers back together again
                     #   i.e. ['','22222','77777'] → '2222277777'
                     #   i.e. [] → ''
                0ì   #  Prepend a 0 (because `Σ` will put all '' at the back)
                     #   i.e. 2222277777 → '02222277777'
                     #   i.e. '' → '0'
                  ï  #  Cast it to an integer, because sorting is done string-wise by
                     #  default despite 05AB1E's interchangeability of strings and numbers;
                     #  and it's also to remove all leading zeros
                     #   i.e. '02222277777' → 2222277777
                     #   i.e. '0' → 0

Answer 17

Retina, 44 bytes

^.?((..)*)$
$1 $&
%)`\G(\d)(.)
$1*$2
N`
.+ 

Try it online! Generating the sort key at the start of the line is harder but the short sort stage results in an overall 3 byte saving. Explanation:

%)`

Apply the first two stages on each line individually.

^.?((..)*)$
$1 $&

Match and copy an even number of trailing digits.

\G(\d)(.)
$1*$2

Replace each digit pair with their described value. The \G\d causes the match to stop at the space.

N`

Sort numerically.

.+ 

Delete the sort keys.

Answer 18

JavaScript (ES8), 72 70 bytes

a=>a.sort((a,b)=>(g=n=>n&&g(n/100|0)+''.padEnd(n/10%10,n%10))(a)-g(b))

Try it online!

Answer 19

Attache, 50 bytes

SortBy!N@Flip##~`&&>PadRight&0&2=>Chop&2@Flip@List

Try it online!

Explanation

SortBy!N@Flip##~`&&>PadRight&0&2=>Chop&2@Flip@List      anonymous function, argument: [a1..aN]
SortBy!                                                 sort the given array by grading f[ai]
                                                        e.g. 42513
                                              List      digits of ai
                                                        e.g. [4, 2, 5, 1, 3]
                                         Flip@          flip the digits around
                                                        e.g. [3, 1, 5, 2, 4]
                                  Chop&2@               chop into groups of 2
                                                        e.g. [[3, 1], [5, 2], [4]]
                    PadRight&0&2=>                      pad each group to size 2 with 0's
                                                        e.g. [[3, 1], [5, 2], [0, 4]]
                  &>                                    using each sub array as arguments...
               ~`&                                      ...repeat the 2nd the 1st amount of times
                                                        e.g. [[1, 1, 1], [2, 2, 2, 2, 2], []]
             ##                                         then:
         Flip                                           reverse the groups
                                                        e.g. [[2, 2, 2, 2, 2], [1, 1, 1]]
       N@                                               then convert it to an number
                                                        e.g. 22222111

Answer 20

Jelly, 14 bytes

DŻLḂ$¡ẋ@2/ẎḌµÞ

Try it online!

Answer 21

Java 11, 204 189 bytes

L->{L.sort((a,b)->Long.compare(s(a+""),s(b+"")));}long s(String s){var r="";for(int l=s.length(),i=l%2;i<l;)r+=s.split("")[++i].repeat(s.charAt(i++-1)-48);return r.isEmpty()?0:new Long(r);}

Takes a List of Longs as parameter and sorts this input-List (without returning a new List).

Try it online (NOTE: String.repeat(int) is emulated as repeat(String,int) because Java 11 isn't on TIO yet. The byte-count remains the same.)

Explanation:

L->{                     // Method with ArrayList<Long> parameter and no return-type
  L.sort(                //  Sort the list by:
   (a,b)->Long.compare(  //   Using a builtin Long-comparator with:
     s(a+""),s(b+"")));} //   The correctly formatted values as described in the challenge

long s(String s){        // Separated method with String parameter and long return-type
  var r="";              //  Temp-String, starting empty
  for(int l=s.length(),  //  The length of the input-String
      i=l%2;i<l;)        //   If the length is even:
                         //    Loop `i` in the range [0,`l`) (in steps of 2)
                         //   Else (the length is odd):
                         //    Loop `i` in the range [1,`l`) (in steps of 2) instead
    r+=                  //   Append the result-String with:
      s.split("")[++i].  //    The digit at index `i+1`
      .repeat(s.charAt(i++-1)-48);
                         //    Repeated the digit at index `i` amount of times
  return r.isEmpty()?    //  If the temp-String is empty:
          0              //   Return 0
         :               //  Else:
          new Long(r);}  //   Convert the temp-String to a long and return it

Answer 22

Ruby, 71 bytes

->a{a.sort_by{|a|s='';s,a=[a%10]*(a/10%10)*''+s,a/100while a>0;s.to_i}}

Try it online!