11
\$\begingroup\$

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
\$\endgroup\$
7
  • 4
    \$\begingroup\$ What is "the MAD number of flights"? \$\endgroup\$
    – att
    Sep 28 at 22:43
  • \$\begingroup\$ @att Basically, you would want to minimize the maximum number of flights between two classes, and minimize how many times the student would have to climb that many flights. So, to sort [2, 4, 5, 6, 9], [2, 5, 9, 6, 4] would be preferred over [2, 4, 6, 9, 5] because it would be better for the student to climb 4 flights once than to climb 4 flights twice. \$\endgroup\$
    – Yousername
    Sep 28 at 23:02
  • 2
    \$\begingroup\$ You can pick your favorite MAD acronym here. :-p \$\endgroup\$
    – Arnauld
    Sep 28 at 23:11
  • 1
    \$\begingroup\$ It stands for Mean Average Deviation, which is how far, on average, numbers are from the mean of the numbers. \$\endgroup\$
    – Yousername
    Sep 28 at 23:16
  • 1
    \$\begingroup\$ @Taco タコス 1...n. \$\endgroup\$
    – Yousername
    Sep 29 at 16:09

15 Answers 15

13
\$\begingroup\$

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.
\$\endgroup\$
1
  • 15
    \$\begingroup\$ Shaking my yead. \$\endgroup\$
    – lyxal
    Sep 29 at 3:38
10
\$\begingroup\$

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.

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

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!

\$\endgroup\$
3
\$\begingroup\$

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 ]
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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 }
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 37 bytes (and I'm afraid to say that I often use a similar approach (1:n==1 to get every n-th) in non-golfed code...) \$\endgroup\$ Oct 4 at 21:37
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I think this is 118 bytes. TIO has a bug counting bytes for C source code. Try changing the language to ""bash" \$\endgroup\$
    – ceilingcat
    Oct 11 at 4:47
  • \$\begingroup\$ @ceilingcat This has come up a few times before and I'm always told by senior members that TIO is correct and is the official byte count. \$\endgroup\$
    – Noodle9
    Oct 11 at 8:19
0
\$\begingroup\$

Japt, 7 bytes

ÍcUÍÔ ë

Try it here

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

Wolfram, 33 bytes

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

Try it here!

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

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

Charcoal, 23 18 bytes

W⌈⁻θυF№θι≔⮌⊞OυιυIυ

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

W⌈⁻θυ

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

F№θι

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

≔⮌⊞Oυιυ

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

Iυ

Output the resulting list.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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