Minimizing flights of stairs climbed

Question

Challenge

Given input as a list/array of natural numbers that each represent the floor of a class a student has to go to, sort the numbers in a way such that the MAD (mean average deviation) number of flights between classes is minimized, thus saving energy and preventing the chance of being late to a class.

When sorted like this, the highest floor is in the middle of the list/array and the lowest floors are on the sides.

Rules

• The student starts and ends on the first floor for entering and exiting the school building.
• The student only uses the stairs to get to each class.
• The list is in sequential order.
• This is code-golf, so answers will be scored in bytes with fewer bytes being the goal.

Test cases

Input	Possible Outputs
8, 9, 6, 4, 7, 10, 5, 7, 8	4, 6, 7, 8, 10, 9, 8, 7, 5 5, 7, 8, 9, 10, 8, 7, 6, 4
4, 7, 3, 5, 7, 8, 4, 2, 4	2, 4, 4, 7, 8, 7, 5, 4, 3 3, 4, 5, 7, 8, 7, 4, 4, 2
4, 1, 2, 3, 2, 9, 4, 6, 2, 8	2, 2, 4, 6, 9, 8, 4, 3, 2, 1 1, 2, 3, 4, 8, 9, 6, 4, 2, 2

Answer 1

Vyxal, 3 bytes

smy

Try it Online!

Look ma, no Unicode!

s   # Sort
 m  # Mirror, appending the reverse
  y # Push every second item, and the rest.

Answer 2

Python 2 or 3,  40  35 bytes

lambda a:a.sort()or(a+a[::-1])[::2]

Try it online!

How?

Sort the input list, append (+) the sorted input list in reverse ([::-1]), take every other value ([::2]).

Note that a.sort() sorts a and returns None, which is falsey, and, as such, the or evaluates its right argument, (a+a[::-1])[::2] where we use the now sorted a.

Answer 3

jq, 26 bytes

Takes a list of numbers as input, outputs as a stream. Uses the same method as Jonathan Allan answers.

sort|(.+reverse)[keys[]*2]

Try it online!

Answer 4

JavaScript (ES6), 54 bytes

f=a=>+a?a:[a.sort((a,b)=>b-a).pop(),...f(a)].reverse()

Try it online!

How?

At each iteration, we pick the smallest element from the original array, append the result of a recursive call and reverse the resulting array. We stop when there's only one element remaining in the original array.

For the input [8, 9, 6, 4, 7], this gives:

5th iteration: [ 9 ]
4th iteration: [ 8, 9 ] -> [ 9, 8 ]
3rd iteration: [ 7, 9, 8 ] -> [ 8, 9, 7 ]
2nd iteration: [ 6, 8, 9, 7 ] -> [ 7, 9, 8, 6 ]
1st iteration: [ 4, 7, 9, 8, 6 ] -> [ 6, 8, 9, 7, 4 ]

Answer 5

Jelly, 5 bytes

Ṣm0m2

A monadic Link that accepts a list of positive integers and yields a list of positive integers.

Try it online!

How?

Ṣm0m2 - Link: list of positive integers, F
Ṣ     - sort F
 m0   - append the reverse (m is overloaded to do this when given 0) 
   m2 - modulo-2 slice (get every other value)

Answer 6

Factor, 55 bytes

[ natural-sort dup <evens> swap <odds> reverse append ]

Try it online!

Explanation

It's a quotation (anonymous function) that takes a sequence from the data stack and leaves a sequence on the data stack. Assuming { 8 9 6 4 7 10 5 7 8 } is on the data stack when this quotation is called...

Word	Comment	Data stack (top on right)
natural-sort	Sort into ascending order	{ 4 5 6 7 7 8 8 9 10 }
dup	Copy top of stack	{ 4 5 6 7 7 8 8 9 10 } { 4 5 6 7 7 8 8 9 10 }
<evens>	Get elements at even indices as a virtual sequence	{ 4 5 6 7 7 8 8 9 10 } T{ evens { seq { 4 5 6 7 7 8 8 9 10 } } }
swap	Swap top two data stack objects	T{ evens { seq { 4 5 6 7 7 8 8 9 10 } } } { 4 5 6 7 7 8 8 9 10 }
<odds>	Get elements at odd indices as a virtual sequence	T{ evens { seq { 4 5 6 7 7 8 8 9 10 } } } T{ odds { seq { 4 5 6 7 7 8 8 9 10 } } }
reverse	Reverse a sequence	T{ evens { seq { 4 5 6 7 7 8 8 9 10 } } } { 9 8 7 5 }
append	Append a sequence to another sequence	{ 4 6 7 8 10 9 8 7 5 }

Answer 7

05AB1E, 4 bytes

{«ι

Outputs both possible results. If this is not allowed, add a trailing н or θ to leave just the first or last list of the pair instead.

Try it online or verify all test cases.

Explanation:

{     # Sort the (implicit) input-list
 Â    # Bifurcate it, short for Duplicate & Reverse copy
  «   # Merge the lists together
   ι  # Uninterleave it into two lists
      # (after which this pair of lists is output implicitly as result)

Answer 8

Ruby, 45 38 36 bytes

->l{a=0;l+l.sort!.map{l.slice!a-=1}}

Try it online!

How on earth?

I think this should be undefined behaviour, but somehow it works:

• l.sort! is the first step, we need a sorted array to perform our magic
• l.sort!.map does not iterate on the original array and will stop as soon as it reaches the last element of the current array.
• l.slice!a-=1 gets the elements in reverse order, skipping one at every iteration. The first element will be the max, on the second iteration, we will get the second last, which will be the 3rd highest number (because the max was removed, and the last element is now the 2nd highest number). And so on.
• Finally, l+l.sort!.map{...} will join the remaining element in l with the result of the mapping operation. Again, we are not using the original array to perform the addition, but the current array.

Answer 9

MathGolf, 11 7 bytes

]êsx{▐x

-4 bytes by porting @Arnauld's JavaScript answer (with an iterative instead of recursive approach).

Try it online.

Explanation:

]        # Wrap the stack into a list, so we start with an empty list []
 ê       # Push the inputs as an integer-array
  s      # Sort it
   x     # Reverse it
    {    # Loop over these descending sorted values:
     ▐   #  Append the current value to the list
      x  #  And reverse the entire list
         # (after the loop the entire stack is output implicitly as result)

Answer 10

Wolfram, 33 bytes

Join[#,Reverse@#][[;;;;2]]&@*Sort

Try it here!

Logic copied from other answers. Sort, join with reverse, take every other item

Answer 11

R, 41 37 bytes

-4 bytes thanks to @Dominic van Essen.

function(x)c(y<-sort(x),rev(y))[!1:0]

Try it online!

Uses the most common strategy here.

The index !1:0 is recycled to vector length and therefore alternates FALSE TRUE FALSE TRUE... to get every second element.

Answer 12

C (gcc), ^{154 \$\cdots\$ 119} 117 bytes

i;j;k;*b;*f(a,l)int*a;{i=j=qsort(a,l,4,L"\x62b078bǃ");b=malloc(4*l);for(k=-~l-l%2;i<l;j+=2)b[i++]=a[j/l?k-=2:j];a=b;}

Try it online!

Saved a whopping 21 bytes thanks to ceilingcat and his execstack magic!!!

Inputs the a pointer to an array of floors of classes that a student has to go to as natural numbers \${1 \dots n}\$, and the array's length (because pointers in C carry no length information).
Return a pointer to an array of the floors sorted so that the mean average deviation of flights between classes are minimized.

Answer 13

Japt, 7 bytes

ÍcUÍÔ ë

Try it here

Answer 14

Charcoal, 23 18 bytes

Ｗ⌈⁻θυＦ№θι≔⮌⊞ＯυιυＩυ

Try it online! Link is to verbose version of code. Explanation: Port of @KevinCruijssen's answer.

Ｗ⌈⁻θυ

Repeat until the output contains all of the floors in the input list (fortunately floors are 1-indexed in the US, so the maximum only becomes falsy when the set difference is empty).

Ｆ№θι

Repeat once for each occurrence of the maximum floor in the input list.

≔⮌⊞Ｏυιυ

Push the maximum floor to the predefined empty list, then reverse it.

Ｉυ

Output the resulting list.

Answer 15

TI-Basic, 49 bytes

Prompt A
SortA(ʟA
dim(ʟA
seq(2fPart(I/2)(I-Ans-.5)+Ans-I/2+1,I,1,Ans→B
SortA(ʟB,ʟA

Input is sorted in-place.