23
\$\begingroup\$

Given an N-dimensional orthogonal (non-ragged) array of non-negative integers, and an indication of which dimensions to reverse, return the array but reversed along those dimensions. The indication may be given as a Boolean list of length N or a list of a subset of the first N dimensions indexed from 0 or 1.

Please state your input formats. Code explanations are much appreciated.

Walked-through example

We are given the 2-layer 3-row 4-column 3D-array

[[[ 1, 2, 3, 4],
  [ 5, 6, 7, 8],
  [ 9,10,11,12]],

 [[13,14,15,16],
  [17,18,19,20],
  [21,22,23,24]]]

and one of

[true,false,true] (Boolean list)
[0,2] (0-indexed list)
[1,3] (1-indexed list)

We need to reverse order of the first and last dimensions, that is the layers and the elements of the rows (the columns), but not the rows of each layer. First (the actual order you do this in does not matter) we reverse the order of the layers:

[[[13,14,15,16],
  [17,18,19,20],
  [21,22,23,24]],

 [[ 1, 2, 3, 4],
  [ 5, 6, 7, 8],
  [ 9,10,11,12]]]

and then we reverse the order of the elements of each row:

[[[16,15,14,13],
  [20,19,18,17],
  [24,23,22,21]],

 [[ 4, 3, 2, 1],
  [ 8, 7, 6, 5],
  [12,11,10, 9]]]

Test cases

[[[1,2,3,4],[5,6,7,8],[9,10,11,12]],[[13,14,15,16],[17,18,19,20],[21,22,23,24]]]
[true,false,true]/[0,2]/[1,3]
 ↓ 
[[[16,15,14,13],[20,19,18,17],[24,23,22,21]],[[4,3,2,1],[8,7,6,5],[12,11,10,9]]]


[[1,2,3],[4,5,6]]
[true,false]/[0]/[1]
 ↓
[[4,5,6],[1,2,3]]


[[1],[4]]
[true,false]/[0]/[1]
 ↓
[[4],[1]]


[[7]]
[true,true]/[0,1]/[1,2]
 ↓
[[7]]


[1,2,3,4,5,6,7]
[true]/[0]/[1]
 ↓
[7,6,5,4,3,2,1]


[]
[true]/[0]/[1]
 ↓
[]


[[],[]]
[false,false]/[]/[]
 ↓
[[],[]]


[[[[3,1,4,1],[5,9,2,6]],[[5,3,5,8],[9,7,9,3]]],[[[2,3,8,4],[6,2,6,4]],[[3,3,8,3],[2,7,9,5]]]]
[true,false,true,true]/[0,2,3]/[1,3,4]
 ↓
[[[[4,6,2,6],[4,8,3,2]],[[5,9,7,2],[3,8,3,3]]],[[[6,2,9,5],[1,4,1,3]],[[3,9,7,9],[8,5,3,5]]]]


[[[[3,1,4,1],[5,9,2,6]],[[5,3,5,8],[9,7,9,3]]],[[[2,3,8,4],[6,2,6,4]],[[3,3,8,3],[2,7,9,5]]]]
[false,true,false,false]/[1]/[2]
 ↓
[[[[5,3,5,8],[9,7,9,3]],[[3,1,4,1],[5,9,2,6]]],[[[3,3,8,3],[2,7,9,5]],[[2,3,8,4],[6,2,6,4]]]]


[[[[3,1,4,1],[5,9,2,6]],[[5,3,5,8],[9,7,9,3]]],[[[2,3,8,4],[6,2,6,4]],[[3,3,8,3],[2,7,9,5]]]]
[false,false,false,false]/[]/[]
 ↓
[[[[3,1,4,1],[5,9,2,6]],[[5,3,5,8],[9,7,9,3]]],[[[2,3,8,4],[6,2,6,4]],[[3,3,8,3],[2,7,9,5]]]]

\$\endgroup\$
  • \$\begingroup\$ I feel like the hardest part in most statically typed languages will be golfing the type signatures involved. \$\endgroup\$ – Οurous Sep 3 '18 at 22:07
  • \$\begingroup\$ @Οurous How do those languages normally deal with arbitrary array data? \$\endgroup\$ – Adám Sep 3 '18 at 22:29
  • 1
    \$\begingroup\$ there's three cases for "normal" use as I see it: only worrying about one level of the array (eg: reverse works on arbitrary arrays but only cares about the first level), generics, or recursive classes (type / object classes depending on functional or OOP, but similar use-case). The latter two are usually far more verbose. \$\endgroup\$ – Οurous Sep 3 '18 at 22:39
  • \$\begingroup\$ Can we store the matrix as arrays of pointers to pointers (in C or asm), instead of proper multi-dimensional arrays where everything is contiguous in memory? I'm pretty sure all the normal higher-level / dynamically-typed languages with arbitrary nesting of lists are already treating things as lists of lists, not matrices, so I'm going to assume it's fine. \$\endgroup\$ – Peter Cordes Sep 5 '18 at 3:42
  • \$\begingroup\$ @PeterCordes Sure, go ahead. \$\endgroup\$ – Adám Sep 5 '18 at 5:35

15 Answers 15

8
\$\begingroup\$

APL (Dyalog), 20 9 bytes

⊃{⌽[⍺]⍵}/

Try it online!

How?

/ - reduce - take the rightmost element in the input (the array) and apply the function with next left element as left argument

{⌽[⍺]⍵} - reverse in the left argument () dimension

- flatten the enclosed array

\$\endgroup\$
8
\$\begingroup\$

APL (Dyalog Unicode), 9 bytes

⊃{⊖[⍺]⍵}⌿

Try it online!

It looks like Uriel edited into something almost identical first, but I developed it independently. I thought this input format is invalid.

\$\endgroup\$
8
\$\begingroup\$

JavaScript (Node.js), 58 55 53 45 bytes

Saved 8 bytes thanks to @Shaggy

Takes input as (indications)(array), where indications is a Boolean list.

f=([r,...b])=>a=>1/r?a.sort(_=>r).map(f(b)):a

Try it online!

Commented

f = (                // f is a function taking:
  [r,                //   r = next 'reverse' Boolean flag
      ...b]          //   b = array of remaining flags
) =>                 // and returning an anonymous function taking:
  a =>               //   a = array (or sub-array) to process, or atomic element
    1 / r ?          // if r is defined:
      a.sort(_ => r) //   reverse a if r = 1; leave it unchanged otherwise
      .map(f(b))     //   for each element in the resulting array: do a recursive call,
                     //   using f to generate a new callback function for the next flag
    :                // else:
      a              //   a must be an atomic element and is simply left unchanged
\$\endgroup\$
  • \$\begingroup\$ Just using r inplace of r||-1 seems to work. \$\endgroup\$ – Shaggy Sep 3 '18 at 15:18
  • \$\begingroup\$ Would f=([r,...b])=>a=>1/r?a.sort(_=>r).map(f(b)):a work? On my phone so can't test properly. \$\endgroup\$ – Shaggy Sep 3 '18 at 22:10
  • \$\begingroup\$ @Shaggy Nice! I like this rather unusual processing flow. \$\endgroup\$ – Arnauld Sep 4 '18 at 3:24
6
\$\begingroup\$

Python 2, 56 55 bytes

f=lambda a,t:t and[f(l,t[1:])for l in a][::1|-t[0]]or a

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Jelly, 8 bytes

”€ẋ”ṚpFv

Takes a 0-indexed list of dimensions.

Try it online!

How it works

”€ẋ”ṚpFv  Main link. Left arg: D (dimensions, 0-based), Right arg: A (array)

”€ẋ       Repeat '€' d times, for each d in D.
   ”Ṛp    Perform Cartesian product of ['Ṛ'] and each string of '€'s, prepending a
          'Ṛ' to each string of '€'s.
      F   Flatten the result.
          If, e.g., D = [0,2,4], we build the string "ṚṚ€€Ṛ€€€€".
       v  Eval the resulting string, using A as left argument.
\$\endgroup\$
  • 1
    \$\begingroup\$ That's horrible. Very nice! \$\endgroup\$ – Adám Sep 3 '18 at 17:58
5
\$\begingroup\$

R, 80 78 77 bytes

Create the call to R's extractor [ by creating a list of sequences reversed where indicated. They actually contain zeros, which are silently ignored. The drop=F is needed to prevent R's default dropping of dimensions. We need the rev call to the dimension reverse indicator, because of the way R fills arrays.

-2 thanks @Giuseppe

-1 using in-line assignment.

function(x,a,d=dim(x))do.call("[",c(list(x),Map(seq,r<-d*rev(a),d-r),drop=F))

Try it online!

Honorable mention to @JayCe who came up with a variation that gets the same result in the same length:

function(x,a,d=dim(x))array(x[t(t(expand.grid(Map(seq,r<-d*rev(a),d-r))))],d)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 78 bytes very nice answer! \$\endgroup\$ – Giuseppe Sep 3 '18 at 19:38
  • 1
    \$\begingroup\$ Very profound answer. It took me a while to understand it completely. I tried replicating it without using do.call - it's longer at 83 bytes, still posting this here as a comment for reference: TIO \$\endgroup\$ – JayCe Sep 4 '18 at 14:01
  • \$\begingroup\$ Well actually, @JayCe, your great answer can also be golfed to 78 bytes! \$\endgroup\$ – J.Doe Sep 4 '18 at 14:11
5
\$\begingroup\$

Haskell, 120 119 bytes

the function f takes the N-dimensional list and a list of bool as input

class F r where f::[Bool]->r->r
instance F Int where f=seq
instance F r=>F[r]where f(a:y)=last(id:[reverse|a]).map(f y)
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need parentheses around F r. \$\endgroup\$ – Ørjan Johansen Sep 3 '18 at 18:01
  • 1
    \$\begingroup\$ TIO link with test cases and OJ's 1-byte golf. \$\endgroup\$ – Khuldraeseth na'Barya Sep 3 '18 at 19:37
4
\$\begingroup\$

05AB1E, 23 11 10 bytes

'€s×'R«J.V

Try it online.

-12 bytes thanks to @Mr.Xcoder.

Input as 0-indexed truthy-values (i.e. [0,2,3]), which is the first input.

Explanation:

'€s×           # Repeat "€" the indices amount of times
               #  i.e. [0,2,3] → ["","€€","€€€"]
    'R«        # Append each with "R"
               #  i.e. ["","€€","€€€"] → ["R","€€R","€€€R"]
        J      # Join them all together
               #  i.e. ["R","€€R","€€€R"] → R€€R€€€R
         .V    # Execute string as 05AB1E code

For example: if the indices input-list is [0,2,3], it will create the following string:

R€€R€€€R

Which will:

    €€€R    # Reverse the items in the most inner (4th level) lists
 €€R        # Reverse the most inner (3rd level) lists themselves
            # Do nothing with the inner (2nd level) lists 
R           # Reverse the entire outer (1st level) list

Original 23 byte answer:

ćURvy„ RèJ…εÿ}}„ RXèJ.V

Input as boolean-list (i.e. [1,0,1,1]), which is the first input.

Try it online.

Explanation:

ćU                 # Pop and save the first boolean in variable `X`
  R                # Reverse the remaining boolean-list
   v    }          # Loop `y` over each of them:
    „ Rè           #  Take the string "R ", and index the current boolean (0 or 1) in it
    J              #  Join it together with the string of the previous iteration
    …εÿ}           #  Surround it with "ε" and "}"
         „ RXè     # Index variable `X` also in "R "
              J    # Join it together with the rest
.V                 # Execute string as 05AB1E code

For example: If the boolean input-list is [1,0,1,1], it will create the following string:

εεεR}R} }R

Which will:

  εR}         # Reverse the items in the most inner (4th level) lists
 ε   R}       # Reverse the most inner (3rd level) lists themselves
ε       }     # Do nothing with the inner (2nd level) lists 
         R    # Reverse the entire outer (1st level) list
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer, but... uhm... would this 11 byter work? \$\endgroup\$ – Mr. Xcoder Sep 3 '18 at 15:31
  • \$\begingroup\$ @Mr.Xcoder Thanks! That's indeed a lot easier. And been able to golf 1 more byte by appending each, instead of prepending and then reversing. \$\endgroup\$ – Kevin Cruijssen Sep 3 '18 at 17:10
  • \$\begingroup\$ @Mr.Xcoder Btw, why does 'x* work to repeat x n amount of times without using a swap, but it doesn't work with '€*?.. EDIT: Only in the legacy though.. \$\endgroup\$ – Kevin Cruijssen Sep 3 '18 at 17:12
  • \$\begingroup\$ The legacy version is quite buggy, it might be due to the fact that is still parsed as an operator even though it's in a char literal? Not sure to be honest. In the new version, * doesn't behave the same way nonetheless. \$\endgroup\$ – Mr. Xcoder Sep 3 '18 at 17:18
3
\$\begingroup\$

JavaScript (Node.js), 60 bytes

A different (recursive) approach. doesn't beat Arnauld's answer ... yet....

Takes the input as array, boolean list

f=(a,r)=>r>[]?(r[0]?a.reverse():a).map(c=>f(c,r.slice(1))):a

f=(a,r)=>r>[]?(r[0]?a.reverse():a).map(c=>f(c,r.slice(1))):a

console.log(f([[[[3,1,4,1],[5,9,2,6]],[[5,3,5,8],[9,7,9,3]]],[[[2,3,8,4],[6,2,6,4]],[[3,3,8,3],[2,7,9,5]]]],[true,false,true,true]))

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

Pyth, 15 bytes

.v+jk.n*\_*L\ME

Try it here!

Annoyingly, handling the empty dimension list case takes no less than 2 bytes... I'd rather use ss in place of jk.n but :| Assumes that the list to be transformed can be given in native Pyth syntax, as a string. I've written a converter to Pyth syntax to make testing easier. In the unfortunate case that the OP chooses not to allow this, a 17-byter will "fix" it:

.v+jk.n*\_*L\ME\E
\$\endgroup\$
3
\$\begingroup\$

Japt, 15 14 bytes

With some inspiration from Arnauld's solution.

Takes the indications as the first input, as a boolean array of 1s and 0s.

Ê?Vn@ÎãßUÅX:V

Try it


Explanation

                   :Implicit input of boolean array U=indications and multi-dimensional integer array V
Ê                  :Get the length of U
 ?                 :If truthy (i.e., >0)
  Vn               :  Sort V
    @ÎÃ            :   Function that gets the first element of U; 0 will leave the array untouched, 1 will reverse it.
       £           :  Map each X
        ß          :  Run the programme again with the following inputs
         UÅ        :   U with the first element removed
           X       :   X will serve as the new value of V
            :      :Else
             V     :  Just return V
\$\endgroup\$
3
\$\begingroup\$

Clean, 122 112 bytes

import StdEnv
class$r::[Bool]->r->r
instance$r where$_=id
instance$[r]| $r where$[a:y]=if(a)reverse id o map($y)

Try it online!

A version of Damien's Haskell answer using Clean's golfier type system. Really shows the extensive similarities between the two languages.

Explained:

import StdEnv                 // import basic stuff
class $ r :: [Bool] -> r -> r // $ takes a boolean list and returns a function on r to r
instance $ r                  // instance on all types, taken when no more specific instances exist
    where $ _ = id            // return the identity function for all arguments
instance $ [r] | $ r          // instance for lists of a type which has an instance itself
    where $ [a: y]
        = if(a) reverse id    // reverse if the head of the argument is true
            o map ($ y)       // composed with the map function acting on $ applied to the tail
\$\endgroup\$
2
\$\begingroup\$

Ruby, 54 bytes

f=->a,d{r,*z=d;r&&a.reverse!;d==[]?a:a.map{|w|f[w,z]}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

(untested but I think correct. compiler asm output looks like what I expect. Will update if/when I find time to write a test harness that creates and prints this data structure.)

GNU C++ (portable) 148 bytes

#include<algorithm>
#include<cstdint>
struct m{intptr_t d,l,a[];void R(int*r){if(*r)std::reverse(a,a+l);for(int i=0;d&&i<l;((m*)a[i++])->R(r+1));}};

GNU C++ (int=pointer and falls off a non-void function UB) 120 bytes

#include<algorithm>
struct m{int d,l,a[],R(int*r){if(*r)std::reverse(a,a+l);for(int i=0;d&&i<l;((m*)a[i++])->R(r+1));}};

This is a struct of depth counter, length, array of {integers or pointers}. In the bottom level of this non-binary tree (depth==0), the array of intptr_t is an array of integers. In higher levels, it's a struct m* stored in intptr_t. Traversal takes a cast.

The R() reverse function is a member function because that saves declaring an arg, and saves a lot of p-> syntax to reference the struct members vs. the implicit this pointer.

The only GNU extension is the C99 flexible array member to make a variable-sized struct, which is supported in C++ as a GNU extension. I could have used a *a member pointing to a separately-allocated array and have this be plain ISO C++. (And that would actually save a byte without requiring any other changes). I wrote this as a mockup / reference implementation for an asm version.


The shorter version with just int also declares R() as returning int instead of void. These two bits of hackery are unrelated; this is just the "works on at least one implementation" version.

It should work fine on 32-bit targets (where int can hold a pointer), as long as you compile with gcc7 or older, or disable optimizations. (gcc8 -O3 assumes that execution can't reach the bottom of a non-void function because that would be UB.) x86 gcc -m32 -O3 should work fine with gcc7, like on Godbolt where I included both versions (in different namespaces) and a non-member-function version.

Ungolfed

The function arg, int r[], is an array of 0 / non-zero integers that indicate whether a given depth should be swapped, starting with the outer-most level.

#include<algorithm>  // for std::reverse
#include<cstdint>    // for intptr_t.  GNU C defines __intptr_t, so we could use that...

struct m{
    __intptr_t d,l,a[];    // depth = 0 means values, >0 means pointers.
    // l = length
    //__intptr_t a[];  // flexible array member: array contiguous with the struct

    void R(int r[]) {
        if(*r)
            std::reverse(a, a+l);   // *r && std::reverse() doesn't work because it returns void.

        if(d) // recurse if this isn't the bottom depth
            for(int i=0 ; i<l ; i++)  // tree traversal
                ((m*)a[i])->R(r+1);   // with the rest of the depth list
    }

}; // struct m

When we recurse, we pass r+1, so checking the current depth is always *r.

An earlier version just passed r unchanged, and checked r[d]. With a flexible array member, I needed to store some kind of last-level indicator because a[] is not a pointer, it's a true array with no indirection. But with a intptr_t *a member, I couldn't just have that be nullptr for the leaf level, because I want it to be values.

Reversing the current level before or after the tree traversal shouldn't matter. I didn't try to do it during.

I'm not sure that std::reverse is worth the byte count vs. a manual loop, especially if I can work in calling R() on each pointer exactly once somewhere inside that loop. But only if d!=0

\$\endgroup\$
  • \$\begingroup\$ Whoa, impressive. \$\endgroup\$ – Adám Sep 5 '18 at 8:08
  • \$\begingroup\$ @Adám: thanks, it golfed down surprisingly naturally and well after I wrote it. I'm curious to see what I can do in x86 machine code :P \$\endgroup\$ – Peter Cordes Sep 5 '18 at 8:29
1
\$\begingroup\$

Mathematica, 7 bytes

Reverse

Function. Give it a nested list as the first argument, and the 1-based list of levels/dimensions to reverse as the second argument. Try it online!

Finally, another challenge where Mathematica has a builtin!

\$\endgroup\$
  • \$\begingroup\$ layers to reverse? TIO link maybe? \$\endgroup\$ – Adám Sep 5 '18 at 1:52
  • \$\begingroup\$ @Adám That is, the list of dimensions to reverse, generally referred to as levels in Mathematica. \$\endgroup\$ – LegionMammal978 Sep 5 '18 at 10:18

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.