Evaluation order of an APL n-train
Description
APL trains are a series of functions, that get applied to an argument in this way:
(f g) x = f g x
(f g h) x = (f x) g (h x)
(a b c d e f) x = (a (b c (d e f))) x = a (b x) c (d x) e (f x)
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.
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
BQN, 8 bytesSBCS ``` ⍒↕+2| …
3y ago
[Jelly], 8 bytes ṖUs2Uṭ …
3y ago
[Jelly], 5 bytes ḶHĊUỤ …
3y ago
[Haskell], 52 48 45 42 bytes …
3y ago
posix SH + [GNU sed], 43 bytes …
3y ago
Japt, 10 bytes o ÅÔò cÔ …
3y ago
[Husk], 8 bytes ηÖ↔mo⌈½ …
3y ago
7 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
BQN, 8 bytesSBCS
⍒↕+2|⊢+↕
The solution itself is an 8-train, so its evaluation order is given by the sequence 7 5 6 3 4 1 2 0: first the rightmost ↕, then the ⊢, then the + between them, and so on—it's fully expanded below. Although it's organized as a train, the computation itself doesn't take advantage of BQN's support for trains.
⍒↕+2|⊢+↕ # Tacit function (suppose 𝕩=3)
↕ # Range of 𝕩 0‿1‿2
⊢ # 𝕩, unchanged 3
+ # Add 3‿4‿5
2 # 2
| # Remainder mod ^ 1‿0‿1
↕ # Range again 0‿1‿2
+ # Add 1‿1‿3
⍒ # Descending grade 2‿0‿1
The idea is to start with ascending indices, then group them into mostly-twos by adding one to the first part of each pair. We do this by taking indices modulo 2. However, this means the first pair starts on element index 1—in english, the second element—which is correct for even lengths but wrong for odd lengths. So we flip the odd lengths by adding 𝕩 to the range. Subtracting would also work, in either order: perhaps a more intuitive version is ⊢-↕, which is the distance from each position to one after the end.
After doing this we have a number for each function, and the ordering goes from high to low numbers but left to right for functions with the same number. Descending Grade does exactly this.
0 comment threads
Jelly, 8 bytes
ṖUs2UṭµF
-1 byte thanks to caird coinheringaahing
(Also posted on Stack Exchange by myself)
ṖUs2UṭµF Main Link
Ṗ pop (remove last element; for numbers, comes with an implicit range)
U reverse
s2 slice into chunks of length 2
U reverse each chunk
ṭ tack; prepend the input
µ (new chain)
F flatten the list
0 comment threads
Jelly, 5 bytes
ḶHĊUỤ
Uses xash's method over on CGCC
How it works
ḶHĊUỤ - Main link. Takes n on the left
Ḷ - Range from 0 to n-1
H - Halve
Ċ - Ceiling
U - Reverse
Ụ - Grade; Sort the indices of n by its elements
0 comment threads
Haskell, 52 48 45 42 bytes
Caught mistake thanks to rak1507
Saved 3 bytes thanks to Hakerh400
f n=n:g[n-1,n-2..1]
g(b:c:t)=c:b:g t
g t=t
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]
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
posix SH, 50 bytes
seq $1|tac|sed -zE 's/(\n[^\n]+)(\n[^\n]+)/\2\1/g'
Old 52 bytes, outputting spaces:
seq -s' ' $1 -1 1|sed -r 's/( [^ ]+)( [^ ]+)/\2\1/g'
0 comment threads
1 comment thread