17
\$\begingroup\$

Your task is to input a sequence of integers and chunk sort it. You may assume the input list can always be chunked into groups of 1, 2, and 3.

Definition

Chunk sorting (a term I made up for the purpose of this challenge) is the action of first chunking a sequence into groups of 1, 2, and 3 in a cycle and then sorting each group.

Test cases

[1, 2, 3, 4, 5, 6, 7, 8, 9] => [[1], [2, 3], [4, 5, 6], [7], [8, 9]]
[5, 9, -2, 8, -6, 4, 5, 9, 1] => [[5], [-2, 9], [-6, 4, 8], [5], [1, 9]]
[8, 3, -1, 6, -8, 7, -1] => [[8], [-1, 3], [-8, 6, 7], [-1]]

Scoring

The shortest code wins!

Rules

No standard loopholes, please.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ An invitation to look for nonstandard loopholes! \$\endgroup\$
    – Stef
    Dec 13, 2021 at 16:02

25 Answers 25

12
\$\begingroup\$

Ruby, 49 bytes

->l{x=5;l.chunk{441[(x+=1)%12]}.map{|a,b|b.sort}}

Try it online!

Literally: chunk, then sort.

The magic number 441 is a bitmask with 1,2,3 binary digits alternatively seto to 1 or 0:

000 11 0 111 00 1

Since there are only 2 binary digits, I can't make it 3 chunks, so I make it 6 and so I use mod 12 to rotate.

\$\endgroup\$
12
\$\begingroup\$

Jelly, 10 8 bytes

3Rṁx@JṢƙ

Try it online!

How it works

3Rṁx@JṢƙ - Main link. Takes L on the left
3R       - [1,2,3]
  ṁ      - Mold to length L, repeating
     J   - Yield [1,2,...,len(L)]
   x@    - Repeat 1 once, 2 twice, 3 thrice, 4 once, 5 twice, etc.
      Ṣƙ - Sort chunks of L, grouped by the elements of [1,2,2,3,3,3,4,...]
\$\endgroup\$
1
8
\$\begingroup\$

Husk, 6 bytes

mOC¢ḣ3

Try it online!

How?

    ḣ3      # 1..3
   ¢        # repeated infinitely;
  C         # now split the input into sublists
            # of these lengths (discarding any 
            # extra, unused lengths);
m           # finally, for each sublist:
 O          # sort it.
\$\endgroup\$
8
\$\begingroup\$

05AB1E, 10 bytes

3LI∍£€{ʒgĀ

Try it online or verify all test cases.

Or alternatively (thanks to @ovs for N6%tò):

.yN6%tò}€{

Try it online or verify all test cases.

Explanation:

3L          # Push list [1,2,3]
  I∍        # Extend the [1,2,3] list to the same size as the input-list
    £       # Split the (implicit) input-list into those parts,
            # which includes trailing empty lists at the end
     €{     # Sort each inner list
       ʒgĀ  # Remove the empty lists:
       ʒ    #  Filter the list of lists:
        gĀ  #   Check if the list-length is not 0
            # (after which the result is output implicitly)

.y          # Adjacent group the (implicit) input-list by:
  N         #  Push the 0-based group-by index
   6%       #  Modulo-6
     t      #  Take the square-root of that
      ò     #  Round it to the nearest integer
 }€{        # After the group-by: sort each inner list
            # (after which the result is output implicitly)

The N6%tò results in the sequence [0,1,1,2,2,2,0,1,1,2,2,2,...], causing the adjacent group-by to split the input-list into parts of sizes [1,2,3,1,2,3,...], which is what we want.


The first program could be 9 bytes if the input-length is guaranteed to be \$n>1\$:

3LI∍£€{Ô¨

See all test cases, and how it unfortunately fails for [1]. (Adding Ć after I would fix that edge-case, but unfortunately we'll then have another 10-bytes alternative.)

\$\endgroup\$
2
  • \$\begingroup\$ I haven't found anything shorter yet, but there are a lot of interesting 12-byters using the .y ... }€{ approach, where .y} is an adjacent group-by and €{ is a sort-each. Here a test battery if anyone wants to try to find something very short for the inner portion which could be any repeating abbccc pattern based on index N. \$\endgroup\$ Dec 10, 2021 at 19:14
  • 1
    \$\begingroup\$ N6%tò works for another 10-byter, but I doubt this approach can be any shorter \$\endgroup\$
    – ovs
    Dec 11, 2021 at 22:19
7
\$\begingroup\$

Jelly, 10 bytes

J%6B§=1ÄṢƙ

Try It Online!

J%6B§=1ÄṢƙ  Main Link
J           [1, 2, 3, ..., len(input)]
 %6         [1, 2, 3, 4, 5, 0, 1, 2, 3, ...]
   B        Binary; [[1], [1, 0], [1, 1], [1, 0, 0], [1, 0, 1], [0], ...]
    §       Sum each; [1, 1, 2, 1, 2, 0, ...]
     =1     Equal to 1?; [1, 1, 0, 1, 0, 0, ...]
       Ä    Cumulative sum; [1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, ...]
        Ṣƙ  Sort chunks of the input grouped based on equal elements on the left side
\$\endgroup\$
0
7
\$\begingroup\$

Python, 86 65 63 bytes

def f(a,i=0):
 for x in a:a[i:i%3-~i]=sorted(a[i:i%3-~i]),;i+=1

Attempt This Online!

Modifies the list in-place; kinda cursed.

\$\endgroup\$
2
  • \$\begingroup\$ I'm surprised that l[a:b:c].sort() doesn't work to sort a slice of a list in place. \$\endgroup\$
    – xnor
    Dec 11, 2021 at 13:20
  • 1
    \$\begingroup\$ @xnor I agree, it's a bit inconsistent that slicing on the LHS is a mutable reference, but makes a copy on the RHS. \$\endgroup\$
    – pxeger
    Dec 12, 2021 at 18:34
7
\$\begingroup\$

Python 2, 50 bytes

f=lambda a,i=1:a and[sorted(a[:i])]+f(a[i:],i%3+1)

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Pip -xp, 24 23 18 bytes

$AL:SN*_^@^13Ma<>6

Replit! Or, here's a 20-byte equivalent in Pip classic (with a header to simulate the -x flag): Try it online!

Explanation

$AL:SN*_^@^13Ma<>6
              a     First command-line arg
               <>6  Group into length-6 chunks
             M      Map this function to each chunk:
          ^13        Split 13 into a list of digits [1;3]
       _^@           Split the argument at those indices
    SN*              Sort each sublist using numeric comparison
$AL:                Fold the result on append-list (flattening by one level)
\$\endgroup\$
6
\$\begingroup\$

R, 70 63 59 bytes

function(a)Map(sort,split(a,rep(l<-seq(!a)-1,l%%3+1)[l+1]))

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Getting rid of ! in seq and using Map(sort,...) (from your comment) matches Dominic's 59. \$\endgroup\$
    – pajonk
    Dec 10, 2021 at 21:15
  • \$\begingroup\$ I think the ! needs to be there for input of length one--Dominic's solution of using [<- neatly avoids that, but I think I can still tie it. \$\endgroup\$
    – Giuseppe
    Dec 10, 2021 at 21:49
  • \$\begingroup\$ Does it actually work with input of length one now, though? \$\endgroup\$ Dec 11, 2021 at 7:11
  • \$\begingroup\$ Looks like it's back to the tie again. Anyway, well done! \$\endgroup\$
    – pajonk
    Dec 11, 2021 at 9:19
6
\$\begingroup\$

Wolfram Language (Mathematica), 53 bytes

Sort/@TakeList[#,i=0;UpTo@Mod[++i,4]&/@#]/.{}->Set@$&

Try it online!

-6 bytes thanks to @alephalpha
-3 bytes thanks to @theorist
-2 bytes thanks to @att

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Tips: NestWhile can always be replaced by //.: 68 bytes \$\endgroup\$
    – alephalpha
    Dec 11, 2021 at 0:45
  • \$\begingroup\$ –3 bytes: Sort/@TakeList[#,Take[Join@@Table[Range@3,q=Tr[1^#]],⌈q/2⌉]]& tio.run/##NcvBC4IwFMfxu3/FA6HTG2Napgdh5@gQ5W0sWDHWKBVtN/Fe4F/… \$\endgroup\$
    – theorist
    Dec 11, 2021 at 6:44
  • \$\begingroup\$ 55 bytes assuming input is nonempty, 56 if we can't. \$\endgroup\$
    – att
    Dec 29, 2021 at 0:27
  • \$\begingroup\$ actually, we can get another -2 from there \$\endgroup\$
    – att
    Dec 29, 2021 at 0:30
5
\$\begingroup\$

JavaScript (ES6), 61 bytes

-4 and -1 thanks to Arnauld

x=>(f=n=>x+x&&[x.splice(0,++n).sort((w,z)=>w-z),...f(n%3)])``
\$\endgroup\$
0
4
\$\begingroup\$

R, 59 bytes

function(x,`*`=`[<-`)Map(sort,split(x,x*rep(seq(x),x*1:3)))

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Hmm, I have 60 bytes if I use the Map(sort,...) instead of lapply. I'm catching up! \$\endgroup\$
    – Giuseppe
    Dec 10, 2021 at 20:38
4
\$\begingroup\$

Retina, 24 bytes

5,6,S`,
%,,2S`,
%N`[^,]+

Try it online! Explanation:

5,6,S`,

Split the input into groups of up to six values. Limits are 0-indexed in Retina 1, so the first six values are numbered 0 to 5 and therefore the comma after the sixth value is also numbered 5, however subsequent splits are every six commas as expected, until the end of the input.

%,,2S`,

Split each group into groups of 1, 2 and 3 values (if possible). The syntax ,,2 is short for ,2,2 so it only splits on the first and third comma; ,2 would be a range and so would also split on the second comma.

%N`[^,]+

Sort the values in each group.

\$\endgroup\$
4
\$\begingroup\$

Bash 4.4.23, 142 bytes

f()(
i=1
a=("$@")
while [ ${#a[@]} -gt 0 ]
do
r=$r"["$(printf "%s\n" "${a[@]:0:$i}" |sort -n)"]"
a=("${a[@]:${i}}")
((i=i==3?1:i+1))
done
echo $r
)

Try it here!

Explanation

i=1                                           > used to keep track of chunk size         
a=("$@")                                      > transforms the parameters as an array
while [ ${#a[@]} -gt 0 ]                      > while there is still some elements to "chuck sort"
do
r=$r[$(printf "%s\n" "${a[@]:0:$i}"|sort -n)] > construct the final result by picking only the required chunk from the array and sorts it. Store sort result in r and ad some delimiters
a=("${a[@]:${i}}")                            > remove processed chunk from the array
((i=i==3?1:i+1))                              > set size of next chunk
done
echo $r
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf. Nice first answer! \$\endgroup\$ Dec 11, 2021 at 21:57
  • \$\begingroup\$ You don't need to make a copy of "$@", although remember that parameter indices start at 1, you can use $# for the number of parameters, and you can use shift $i to remove parameters. Also, ((i=i%3+1)) works to calculate the size of the next chunk. \$\endgroup\$
    – Neil
    Dec 15, 2021 at 14:59
  • \$\begingroup\$ @Neil I will check that out this week end. Thanks for the tips :) \$\endgroup\$ Dec 15, 2021 at 16:36
4
+50
\$\begingroup\$

BQN, 24 23 22 21 20 bytes

-1 thanks to Dominic van Essen

∧¨⊢⊔˜¯1+`(0=∾↑↕3)⥊˜≠

Anonymous tacit function that takes an array of numbers as its right argument. Run it online!

Explanation

The explanation uses an example argument of ⟨ 8 3 ¯1 6 ¯8 7 ¯1 ⟩:

∧¨⊢⊔˜¯1+`(0=∾↑↕3)⥊˜≠
          (      )      Generate the array ⟨ 1 1 0 1 0 0 ⟩:
               ↕3         Range(3): ⟨ 0 1 2 ⟩
              ↑           Prefixes: ⟨ ⟨⟩ ⟨ 0 ⟩ ⟨ 0 1 ⟩ ⟨ 0 1 2 ⟩ ⟩
             ∾             Join: ⟨ 0 0 1 0 1 2 ⟩
           0=              Equal 0: ⟨ 1 1 0 1 0 0 ⟩
                  ⥊˜   Reshape it to
                     ≠  the length of the argument: ⟨ 1 1 0 1 0 0 1 ⟩
        +`              Cumulative sum
      ¯1                starting at -1: ⟨ 0 1 1 2 2 2 3 ⟩
    ⊔˜                 Using that list as a categorizer, group
   ⊢                   the argument: ⟨ ⟨ 8 ⟩ ⟨ 3 ¯1 ⟩ ⟨ 6 ¯8 7 ⟩ ⟨ ¯1 ⟩ ⟩
∧¨                     Sort each: ⟨ ⟨ 8 ⟩ ⟨ ¯1 3 ⟩ ⟨ ¯8 6 7 ⟩ ⟨ ¯1 ⟩ ⟩
\$\endgroup\$
5
  • \$\begingroup\$ -2: ∧¨(+`0‿1‿0‿1‿0‿0⥊˜≠)⊸⊔ \$\endgroup\$
    – Razetime
    Dec 14, 2021 at 3:05
  • \$\begingroup\$ @Razetime That doesn't cycle correctly. For example, when reshaped to length 9, the 0/1 list should be ⟨ 0 1 0 1 0 0 1 1 0 ⟩, but yours gives ⟨ 0 1 0 1 0 0 0 1 0 ⟩. \$\endgroup\$
    – DLosc
    Dec 14, 2021 at 17:08
  • \$\begingroup\$ ah ok, must not have seen it \$\endgroup\$
    – Razetime
    Dec 15, 2021 at 3:01
  • \$\begingroup\$ 20 bytes by using ↑↕3 instead of ↕¨↕4... \$\endgroup\$ Dec 27, 2021 at 16:32
  • \$\begingroup\$ @DominicvanEssen Ah, nice. ↕¨↕4 is a translation of how I would do it in Pip: ,,4. \$\endgroup\$
    – DLosc
    Dec 27, 2021 at 16:42
3
\$\begingroup\$

Vyxal, 7 bytes

ẏǒʀÞṁvs

Try it Online!

I'm way late to the party, but who cares when the program looks like it spells something with heavy skamtebord vibes.

Explained

ẏǒʀÞṁvs
ẏ       # The range [0...len(input)]
 ǒ      # modulo each by 3 to get the chunk sizes
  ʀ     # cast each to range [0...n] for shape
   Þṁ   # mold the input to that, without repeating elements
     vs # sort each sublist 
\$\endgroup\$
2
\$\begingroup\$

J, 24 15 bytes

<@/:~/.~#$#\##\

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 48 40 bytes

≔⮌AθWθ⊞υE⊕﹪Lυ³⊟θIEυ✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Lι

Try it online! Link is to verbose version of code. Explanation: Charcoal really struggles here as it has no variable length split, flatten or sort primitive (at least not on TIO).

≔⮌Aθ

Reverse the input array.

Wθ

Repeat until the input array has been chunked.

⊞υE⊕﹪Lυ³⊟θ

Create a chunk of size depending on the number of chunks so far.

IEυ✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Lι

For each chunk, get the minimum, middle and maximum elements, but skip the middle if the chunk's size is less than 3 and skip the maximum if its size is less than 2.

Previous 48-byte version didn't require the input to be completely chunkable:

WθF³«⊞υ✂θ⁰⊕κ≔✂θ⊕κLθ¹θ»IEΦυι✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Lι

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

Wθ

Repeat until the input is empty.

F³«

Take three chunks.

⊞υ✂θ⁰⊕κ

Save the chunk.

≔✂θ⊕κLθ¹θ

Remove the chunk from the input.

»IEΦυι✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Lι

For each non-empty chunk, get the minimum, middle and maximum elements, but skip the middle if the chunk's size is less than 3 and skip the maximum if its size is less than 2.

\$\endgroup\$
2
\$\begingroup\$

HBL, 17 bytes

?.(1(%(0,.))('?(2,.)(+(?(<,<),
).1

Try it!

Explanation

The first line is a recursive function that does most of the work. It takes two arguments, a list and an integer, where the integer represents the current chunk size (1, 2, or 3).

?.(1(%(0,.))('?(2,.)(+(?(<,<),
?                               If
 .                              Argument 1
                                is truthy (non-empty):
  (1                             Construct a list from
        ,                         Argument 2
      (0  )                       Take that many elements of
         .                        Arg1
    (%     )                      Sorted
                                 prepended to
            ('?                   Recursive call with two arguments:
               (2,.)               Drop (arg2) elements of arg1
                                  and
                    (+             Increment
                      (?            If
                          ,         Arg2
                        (<  )       is less than
                           <        3:
                             ,       Arg2
                                    Else, 0
                                Else, empty list

Then the main function on the second line is simply:

)    Call the previous function with these arguments:
 .    Argument 1 of the main function
     and
  1   1
\$\endgroup\$
2
\$\begingroup\$

Stax, 6 bytes

£ñ+Ü5▬

Run and debug it

\$\endgroup\$
2
  • 1
    \$\begingroup\$ first time use of |/ in an answer? \$\endgroup\$
    – Razetime
    Dec 11, 2021 at 2:04
  • \$\begingroup\$ I can't say I've seen it used anywhere before. \$\endgroup\$
    – recursive
    Dec 13, 2021 at 19:37
2
\$\begingroup\$

C (gcc), 73 70 bytes

l;f(a,n)int*a;{for(l=0;n;n-=l,a+=l,l%=3)qsort(a,++l,4,L"\x62b078bǃ");}

Try it online!

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Chunk sorts the array in place.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 76 71 bytes

import Data.List
f=(%)1
n%[]=[]
n%x=sort(take n x):(mod n 3+1)%drop n x

Try it Online!

-5 bytes thanks to xnor

Calling f on a list chunk sorts it.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a few bytes by defining g as an infix function: TIO \$\endgroup\$
    – xnor
    Dec 14, 2021 at 4:40
  • \$\begingroup\$ Ah, I forgot about infix functions! Thanks for the tip, xnor! \$\endgroup\$ Dec 14, 2021 at 18:46
2
+200
\$\begingroup\$

tinylisp, 194 170 146 bytes

(load library
(d C(q((L P)(i L(c(map head(zip L(1to P)))(i(e P 3)(C(t(t(t L)))1)(i(e P 2)(C(t(t L))3)(C(t L)2))))(
(d S(q((L)(map merge-sort(C L 1

Try it online!

-24 thanks to DLosc suggesting implementing take instead of the hodge-podge mess of cs I was using before. -24 again by implementing take more golfily.

\$\endgroup\$
2
  • \$\begingroup\$ @DLosc great suggestion, thanks! I'll definitely be keeping list in mind but looks like take was shorter here after all. \$\endgroup\$
    – Giuseppe
    Feb 8, 2022 at 20:56
  • \$\begingroup\$ Hm, and with the library you can do a shorter version of take: (d T(q((L N)(map head(zip L(1to N)))))), which isn't recursive so it can just be inlined: Try it online! \$\endgroup\$
    – DLosc
    Feb 8, 2022 at 21:40
1
\$\begingroup\$

Pari/GP, 53 bytes

a->i=0;c=2;[vecsort(a[i+1..i=j+1])|b<-a,#a>j=i+c++%3]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 131 bytes

function(&$a){for($a=array_chunk($a,3),$i=-1;$a[++$i];sort($a[$i]))!$a[$i][1]|$i%3?:array_splice($a,$i,0,[[array_shift($a[$i])]]);}

Try it online!

This is a first take, it feels awfully long, there has to be a better way.. damn these "array_" prefixes!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.