# Evaluation order of an APL n-train

From Codidact with permission.

## Description

APL trains are a series of functions, that get applied to an argument in this way:

(f g) x = f g x here f and g are prefix functions

(f g h) x = (f x) g (h x) here f and h are prefix functions, while g is an infix function

(a b c d e f) x = (a (b c (d e f))) x = a (b x) c (d x) e (f x) here f, d, b, and a are prefix functions, while e and c are infix functions

Trains evaluate from the right to the left, so in the last example, (f x) is evaluated, then (d x), then (d x) e (f x), then (b x), etc.

For the purposes of this challenge, when counting from the right, the the first, third, fifth, etc. functions are monads, and the second, fourth, sixth, etc. functions are dyads, except that if the leftmost function would be a dyad, it is instead a monad because there is nothing to its left that can provide it with a left argument.

The final evaluation order there is fdebca, or using numbers instead, 6 4 5 2 3 1.

## Challenge

Given a number n, output the evaluation order of a train with n functions. Your result can be 0 indexed or 1 indexed.

## Examples

Here are the first 10 outputs starting from n=1 (1 indexed)

1 (0 if 0 indexed)
2 1 (1 0 if 0 indexed)
3 1 2
4 2 3 1
5 3 4 1 2
6 4 5 2 3 1
7 5 6 3 4 1 2
8 6 7 4 5 2 3 1
9 7 8 5 6 3 4 1 2
10 8 9 6 7 4 5 2 3 1

• I'm a bit confused by the notation: are both f and g in the first example monads? So f is applied to the result of applying g to x? In the second example, is g a dyad and f, h are monads? So g is applied to both the results of f and h? Or how is (f x) g (h x) interpreted. I think you should spell out the general rule. I for one cannot infer it from the examples (but maybe I will when I understand the notation) Jun 7, 2021 at 22:06
• @LuisMendo Your understanding it correct, though.
Jun 7, 2021 at 22:07
• So what's the general rule to know which are monads and which are dyads? Jun 7, 2021 at 22:08
• @LuisMendo For the purposes of this challenge, when counting from the right, the the first, third, fifth, etc. functions are monads, and the second, fourth, sixth, etc. functions are dyads.
Jun 7, 2021 at 22:10
• Thanks. That's not at all obvious to non-APL programmers; shouldn't that be in the challenge spec? Jun 7, 2021 at 22:11

# J, 14 bytes

[:\:0 _2#:i.@-


Try it online!

Alternative solution that makes use of divmod with negative divisor.

### How it works

Example using n = 5:

• i.@- Generate descending range 4 3 2 1 0
• 0 _2#: Divmod each number by negative 2:
_2  0
_2 _1
_1  0
_1 _1
0  0

• [:\: Grade down; sort indices in the descending order of above 4 2 3 0 1

Alternatively, ranking (grade up twice) on the forward range also works:

# J, 15 bytes

[:/:@/:0 _2#:i.


Try it online!

# Japt, 10 bytes

Trying out insomniac golfing.

o ÅÔò cÔiU


Try it

o ÅÔò cÔiU     :Implicit input of integer U
o              :Range [0,U)
Å            :Slice off the first element
Ô           :Reverse
ò          :Partitions of length 2
c        :Map then flatten
Ô       :  Reverse
iU     :Prepend U


# J, 16 14 bytes

[:/:>.@-:@i.@-


Try it online!

For 5:

[:/:>.@-:@i.@-
i.@- 4 3 2 1 0 count down
>.@-:@     2 2 1 1 0 halve and round up
[:/:           4 2 3 0 1 grade up
(indices of lowest to highest values:
4 for 0,
2 for the first 1,
3 for the second 1, …)

• +1 Works for J too :-)
Jun 7, 2021 at 23:17

# K (oK), 8 bytes

<-2!-!-:


Try it online!

A port of xash's J solution.

### How it works

<-2!-!-:  Monadic train; input = n
-!-:  Generate n..1; colon attached to force a monadic train
-2!      Truncating division by 2


# JavaScript (ES6), 35 bytes

Returns a 0-indexed, comma-separated string.

n=>(g=k=>--n?n-k+[,g(-k|1)]:+!~k)


Try it online!

# JavaScript (ES6),  39  38 bytes

Returns a 1-indexed array.

n=>(g=k=>n?[n---k||1,...g(-k|1)]:[])


Try it online!

### How?

We start with k = 0. At each iteration, we output n - k || 1, decrement n afterwards and update k to -k | 1, which means that we alternate between 1 and -1.

The || 1 in n - k || 1 is required for the last iteration if there's an even number of terms in the sequence:

 n          | 10  9  8  7  6  5  4  3  2  1
k          |  0  1 -1  1 -1  1 -1  1 -1  1
n - k      | 10  8  9  6  7  4  5  2  3  0
n - k || 1 | 10  8  9  6  7  4  5  2  3  1


# Jelly, 7 bytes

ṖUs2U;ƒ


Try it online!

-2 bytes thanks to caird coinheringaahing

# Jelly, 5 bytes

ḶHĊUỤ


Try it online!

# Python 3, 47 46 45 bytes

Saved a byte thanks to Arnauld!!!
Saved another byte thanks to ovs!!!

f=lambda n,k=0:n*[0]and[n-k or 1]+f(n-1,-k|1)


Try it online!

Uses idea from Arnauld's JavaScript answer.

• 45 bytes
– ovs
Jun 8, 2021 at 8:28
• @ovs Sweet - thanks! :D Jun 8, 2021 at 10:45

# Python 3, 44 bytes

lambda n:sorted(range(n),key=lambda i:n-i^1)


Try it online!

Thanks xnor for -3 bytes by change the key function for sorting.

• It looks like you can actually sort by n-i^1: TIO
– xnor
Jun 8, 2021 at 8:30

Caught mistake thanks to rak1507

Saved 3 bytes thanks to Hakerh400 on Codidact

f n=n:g[n-1,n-2..1]
g(b:c:t)=c:b:g t
g t=t


Try it online!

g takes the rest of the trains.

-- This is a fork, so append c (monad) and b (dyad)
-- and continue with the rest of the train
g(b:c:t)#=[c,b]++g t
-- t is either empty or a single monad, so finish it off
g t=t


f simply starts it off with the last function n and the other trains 1..n-1 (in reverse).

f n=n:g[n-1,n-2..1]

• This seems to give the wrong answers Jun 8, 2021 at 8:46
• @rak1507 Whoops, I dropped the parens around a++[c,b] without realizing they were necessary.
– user
Jun 8, 2021 at 12:52

# posix SH + GNU sed, 43 bytes

seq $1|tac|sed -zE 's/(\n.+)(\n.+)/\2\1/mg'  seq$1                 # 1..the argument (inclusive)
|tac|            # reverse
sed         # replace
-z      # null terminated. basically this means that \n is
# treated as a normal character, needed because
# seq and tr operate on lines
E     # extended regex so we can use () instead of 
' do this replacement  '

s/(\n.+)(\n.+)/\2\1/mg
s/            /    /mg  # replace all occurences of
\n.+                 # a newline followed by non-newlines
# the (GNU extension) m modifier makes
# . not match a newline
(    )(....)          # twice
/         # with
\2\1     # swap their places


seq $1|tac|sed -zE 's/(\n[^\n]+)(\n[^\n]+)/\2\1/g'  From codidact with permission • Try using a line-based approach, i.e. without -z. Aug 30, 2021 at 12:11 # Python 3, 48 44 bytes f=lambda n,x=2:-~n*[n]and[n][:n]+f(n-x,-x|3)  Try it online! The forward differences are always -2, +1, -3, +1, -3, ..., except for the last one for even cases. [:n] removes a 0 that would occur if we always use the same sequence of forward differences. -x|3 maps 2 and 3 to -1 and -1 to 3. # R, 42 bytes function(n)pmax(n:1-c(0,(-1)^(1:n)[-1]),1)  Try it online! Implementing @Arnauld's algoritm # Retina 0.8.2, 28 bytes .+$*
1
$.'¶ (¶.+)(¶.+)$2$1  Try it online! Link includes test cases. 0-indexed. Explanation: .+$*


Convert to decimal.

1
$.'¶  Create the range in reverse. (¶.+)(¶.+)$2\$1


Swap pairs of values after the first.

# Charcoal, 13 bytes

⟦θ⟧Ｆ⪪⮌…¹Ｎ²Ｉ⮌ι


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

⟦θ⟧


Print the input on its own line.

Ｆ⪪⮌…¹Ｎ²


Reverse the range from 1 to the input, split into pairs, and loop over each pair.

Ｉ⮌ι


Print the reversed pair.