14
\$\begingroup\$

Background

Adám and I were once discussing a way to properly extend some features in Dyalog APL. I came up with the following extension to Take, a function that takes some front or back elements (and an analogous extension to Drop). We agreed that it was a good idea, but it was incredibly hard to come up with a piece of code that imitates the behavior.

While the original proposal operates on multi-dimensional arrays, this challenge's scope is limited to 1D arrays of numbers. Whenever I mention "array", it implies a 1D array.

The Take function

takes two arguments. One is the array A (of length L), and the other is a single integer N (which can be 0, positive, or negative).

The behavior depends on the value of N:

  • If 0 ≤ N ≤ L, takes first N elements of A from the start.
  • If -L ≤ N < 0, takes last -N elements of A from the end.
  • If N > L or N < -L, performs "overtake", appending (for positive N) or prepending (for negative N) zeros until the array's length becomes abs(N).

It can be thought of applying a Boolean mask to an infinitely zero-padded version of A:

For all cases, A = [1, 2, 3, 4, 5]

For N = 3: (positive simple take)
A     :  ... 0 0 1 2 3 4 5 0 0 ...
Mask  :  ... 0 0 1 1 1 0 0 0 0 ...  # Fill 1s from the start of the array
Result:          1 2 3              # Elements at 0 mask are removed from the array

For N = -4: (negative simple take)
A     :  ... 0 0 1 2 3 4 5 0 0 ...
Mask  :  ... 0 0 0 1 1 1 1 0 0 ...  # Fill 1s from the end of the array
Result:            2 3 4 5

For N = 7: (positive overtake)
A     :  ... 0 0 1 2 3 4 5 0 0 0 ...
Mask  :  ... 0 0 1 1 1 1 1 1 1 0 ...  # The mask overflows the input array
Result:          1 2 3 4 5 0 0

For N = -8: (negative overtake)
A     :  ... 0 0 0 0 1 2 3 4 5 0 0 ...
Mask  :  ... 0 1 1 1 1 1 1 1 1 0 0 ...  # The mask is filled from the end,
                                        # overflowing through the start
Result:        0 0 0 1 2 3 4 5

The proposed extension ("Multi-Take")

The extension allows N to be an array of integers [N1, N2, N3, ..., Nn]. It conceptually generates all the masks to apply to A using each of Ni, and combines all of them by logical OR. Then the mask is applied to A in the same sense as above, giving the resulting array (which may have some contiguous middle elements removed, or have padding in both directions).

Because the identity element for OR is 0, empty N gives all-zero mask, resulting in an empty array (which is equivalent to giving a single zero as N).

For all cases, A = [1, 2, 3, 4, 5]

For N = [1, -2]: (removing a contiguous region)
A        :  1 2 3 4 5
Mask (1) :  1 0 0 0 0  # Taking from start
Mask (-2):  0 0 0 1 1  # Taking from end
OR       :  1 0 0 1 1
Result   :  1     4 5  # [1, 4, 5]

For N = [8, -7]: (padding in both direction)
A        :      1 2 3 4 5
Mask (8) :  0 0 1 1 1 1 1 1 1 1  # Overtaking from start
Mask (-7):  1 1 1 1 1 1 1 0 0 0  # Overtaking from end
OR       :  1 1 1 1 1 1 1 1 1 1
Result   :  0 0 1 2 3 4 5 0 0 0  # [0, 0, 1, 2, 3, 4, 5, 0, 0, 0]

For N = [2, 4, 7]: (for multiple values of same sign, some are simply shadowed)
A        :  1 2 3 4 5
Mask (2) :  1 1 0 0 0 0 0
Mask (4) :  1 1 1 1 0 0 0
Mask (7) :  1 1 1 1 1 1 1
OR       :  1 1 1 1 1 1 1  # Same as simply N = 7 or [7]
Result   :  1 2 3 4 5 0 0  # [1, 2, 3, 4, 5, 0, 0]

For N = []: (empty N gives empty result)
A     :  1 2 3 4 5
Mask  :  (None)     # No mask to apply
OR    :  0 0 0 0 0  # Identity element of OR
Result:  (Empty)    # []

Challenge

Implement the extension, i.e. a program or function that takes an array of numbers A and an array of take amounts N, and outputs the modified array using the mechanism described above.

The "array" can be any sequential container type in your language of choice.

You can assume the elements of A are given in any common number type in your language of choice (or, if you're doing string I/O, represented in the most natural format for your language). Your program should be able to handle empty A and A containing zeros or duplicate elements.

You may assume A contains only integers even if your program accepts floating-point numbers as input.

Standard rules apply. The shortest code in bytes wins.

Test cases

# These test cases all share A = 1 2 3 4 5
# Should work for any 5-element array A' = a b c d e
# giving the output's 1 2 3 4 5 substituted with a b c d e respectively,
# even if A' contains duplicates or zeros
N = (empty)
Output = (empty)
N = 3
Output = 1 2 3
N = 0
Output = (empty)
N = -4
Output = 2 3 4 5
N = 7
Output = 1 2 3 4 5 0 0
N = -8
Output = 0 0 0 1 2 3 4 5
N = 0 0 0 0 0
Output = (empty)
N = 0 4 2 3
Output = 1 2 3 4
N = -2 -1 0 -7
Output = 0 0 1 2 3 4 5
N = 0 2 -2 1 -1
Output = 1 2 4 5
N = -7 -5 -3 -1 1 3 5 7
Output = 0 0 1 2 3 4 5 0 0

-------------------------
# Noteworthy edge cases
A = 1 4 3 4 5
N = 0 2 -2
Output = 1 4 4 5

A = 1 2 0 4 5
N = 7 -8
Output = 0 0 0 1 2 0 4 5 0 0

-------------------------
# These test cases share A = (empty)
N = (empty)
Output = (empty)
N = 0 0 0 0 0
Output = (empty)
N = 3 1 4
Output = 0 0 0 0
N = -3 -1 -4
Output = 0 0 0 0
N = 3 1 -4 -1 5
Output = 0 0 0 0 0 0 0 0 0 (9 zeros)
\$\endgroup\$
  • \$\begingroup\$ If I'm understanding correctly, only the N values with the largest absolute value have any bearing on the final result? \$\endgroup\$ – Jonah Jul 7 at 3:59
  • \$\begingroup\$ @Jonah Yes, except that positive and negative numbers should be considered separately. \$\endgroup\$ – Bubbler Jul 7 at 4:31
  • \$\begingroup\$ I assume \$A\$ can also contain negative values? \$\endgroup\$ – Kevin Cruijssen Jul 7 at 10:29
  • \$\begingroup\$ @KevinCruijssen Yes. \$\endgroup\$ – Bubbler Jul 7 at 10:36
  • 1
    \$\begingroup\$ @Arnauld Actually no, you may assume A contains only integers. This is because it is the default number type in many languages. If you can somehow exploit that, go ahead! \$\endgroup\$ – Bubbler Jul 7 at 13:34
7
\$\begingroup\$

APL (Dyalog Unicode), 58 50 bytes

{{2⊃{⍵[⍒⍴¨⍵]}(⍺,⍵)A⍺(⍵,⍺↓⍨≢A)}/((⌈/,⌊/)0,⍵)↑¨⊂A←⎕}

Try it online!

What better way to implement this than in APL itself? That being said, some of the logic is nontrivial.

Anonymous function that takes N as the right argument and A in standard input.

-2 bytes thanks to @Bubbler

-1 byte thanks to @Adám

Explanation

Even though APL has the take function built-in, combining them requires a bit more work.

Firstly, as @Jonah noted, only the elements of N with the largest absolute value matter to the final result since all elements with smaller absolute value correspond to subarrays of those formed from higher absolute value. Aka, only the largest positive number and the most-negative negative number matter. We obtain those right off the bat with (⌈/,⌊/)0,⍵, where is N. This produces a pair of the smallest number and the highest number in 0 appended to N. Appending 0 is important because it guarantees that the two numbers obtained are respectively non-positive and non-negative.

The convenient part is ↑¨⊂A←⎕, where we use APL's built-in take () to obtain two arrays, one (call it m) counting backwards from the end, and one forwards from the start (call it M).

Here, it gets interesting. For non-trivial A, there are several cases to consider:

A =    1 2 3 4 5

1. M ⊆ m:
m: 0 0 1 2 3 4 5
M:     1 2 3
union: m

2. m ⊆ M:
m:         3 4 5
M:     1 2 3 4 5 0 0 0
union: M

3. Both m and M have 0s:
m: 0 0 1 2 3 4 5
M:     1 2 3 4 5 0 0 0
union: m,(the zeros of M)

4. Neither m nor M have 0s, but they overlap:
m:         3 4 5
M:     1 2 3 4
union: A

5. M and m do not overlap:
m:           4 5
M;     1 2
union: M,m

There are different ways to define the unions of the two arrays. For example, the union for case 3 could instead be (the zeros of m),M, but that is less useful for golfing due to precedence. Importantly, case 1 could analogously be defined as m,(the zeros of M) (same as case 3) since M has no zeros in case 1.

For cases 1 to 4, the union desired is the longest one out of A,M, and m,(the zeros of M). For example, in the example for case 2 , M has length 8, which is longer than the other two possibilities: A has length 5, and m,(the zeros of M) has length 6. This holds true for all four of these cases, so all we have to do is compute all 3 possibile unions, then take the longest one.

This evidently does not hold true for case 5. A always has more elements than the desired union, so it would always be selected over M,m. This is only one conditional, so it is not particularly difficult to add in a quick check. However, M,m is the longest in cases 1 to 4, so we can instead take the second-longest out of A,M, m,(the zeros of M), and M,m.

{{2⊃{⍵[⍒⍴¨⍵]}(⍺,⍵)A⍺(⍵,⍺↓⍨≢A)}/((⌈/,⌊/)0,⍵)↑¨⊂A←⎕}
{...}/(⌈/,⌊/)0,⍵}↑¨⊂A←⎕      ⍝ Compute m and M as discussed,
                             ⍝ then pass m as ⍺ and M as ⍵ to the following:
2⊃{⍵[⍒⍴¨⍵]} ⍝ Get the second-longest of:
 ⍺,⍵         ⍝ m,M
 A           ⍝ A
 ⍺           ⍝ M
 ⍵,⍺↓⍨≢A    ⍝ m,(the zeros of M)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, it doesn't work with duplicate elements in A (e.g. A←1 4 3 4 5 and N←0 ¯2 2). \$\endgroup\$ – Bubbler Jul 7 at 5:38
  • \$\begingroup\$ @Bubbler Conveniently, my new golf shouldn't require the set intersection , which was causing the problems ... almost done implementing. \$\endgroup\$ – fireflame241 Jul 7 at 5:40
  • \$\begingroup\$ @Bubbler Yep, it worked. Added A←1 4 3 4 5 and N←0 ¯2 2 as a new test case in the TIO link (You might want to add it to the question too). \$\endgroup\$ – fireflame241 Jul 7 at 5:49
  • \$\begingroup\$ ...and when A has zeros (e.g. A←1 2 0 4 5 and N←7 ¯8). I think changing ⍺[⍸0=⍺] to ⍺↓⍨≢A will fix it. \$\endgroup\$ – Bubbler Jul 7 at 5:55
  • \$\begingroup\$ @Bubbler Yes, it does and saves 2 bytes. Strange how these bugfixes tend to be golfier. \$\endgroup\$ – fireflame241 Jul 7 at 6:05
6
\$\begingroup\$

JavaScript (ES6),  103 97  96 bytes

Expects (A)(N).

a=>b=>Object.keys(g=x=>x&&g(g[x<0?a.length+x++:--x]=x),b.map(g)).sort((a,b)=>a-b).map(i=>~~a[i])

Try it online!

How?

When it's called with \$x>0\$, the helper function \$g\$ creates a key in its own underlying object for each value in the range:

$$[x - 1, x - 2, ..., 0]$$

When it's called with \$x<0\$, it does the same thing with the range:

$$[L + x, L + x + 1, ..., L - 1]$$

where \$L\$ is the length of the input array \$a\$.

When it's called with \$x=0\$, it does nothing.

g = x =>               // x = input
  x &&                 // stop the recursion if x = 0
  g(                   // otherwise, do a recursive call:
    g[                 //   create a new key in g:
      x < 0 ?          //     if x is negative:
        a.length + x++ //       use a.length + x and post-increment x
      :                //     else:
        --x            //       use x, pre-decremented
    ] = x              //   the value associated to this key doesn't matter,
                       //   so we just use the argument for the next call
  )                    // end of recursive call

We sort all keys created by invoking \$g(x),x\in b\$ in ascending order and map the resulting indices to the values of \$a\$, forcing \$0\$'s when they are out of range.

a => b =>
  Object.keys(
    g = …,
    b.map(g)
  )
  .sort((a, b) => a - b)
  .map(i => ~~a[i])
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Python 3, 113 103 bytes

def f(A,N):k=len(A);N+=0,;return[+(-1<i<k)and A[i]for i in sorted({*range(max(N)),*range(k+min(N),k)})]

Try it online!

Bit naive of an approach, but it works pretty well.

-10 bytes thanks to @ovs

Explanation

We generate the sets of all indices of m and M, 0-indexed relative to the start of A. A simple union of these two sets combines the two masks.

def f(A,N):
    k=len(A);
    N+=0,; # Append 0 to ensure that the min/max functions never error
    [
        +(-1<i<len(A))and A[i] # try to get the i-th element of A
        for i in sorted({  # sort the indices to appear in proper order
            # generate the indices
            # 0-indexed starting at the first element of A
            *range(max(N)), # the set of all indices of M¸union:
            *range(k+min(N),k) # the set of all indices of m
        })
    ]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 111 bytes using a normal function and creating the indices of m using just a range. \$\endgroup\$ – ovs Jul 7 at 12:36
  • \$\begingroup\$ And +(-1<i<len(A))and A[i] for another -1. \$\endgroup\$ – ovs Jul 7 at 12:39
  • \$\begingroup\$ 103 bytes by optimizing the second range a little further. \$\endgroup\$ – ovs Jul 7 at 14:38
  • \$\begingroup\$ @ovs Good ideas. Annoyingly, "assignment expression cannot be used in a comprehension iterable expression," otherwise using Python 3.8 could save a few more bytes. \$\endgroup\$ – fireflame241 Jul 7 at 16:39
  • \$\begingroup\$ The code you're displaying isn't what's there if you follow the TIO link. \$\endgroup\$ – Noodle9 Jul 8 at 6:07
3
\$\begingroup\$

Charcoal, 34 bytes

⊞η⁰E⁻±⌊ηLθ0IΦθ∨‹κ⌈η›⁻⊕κLθ⌊ηE⁻⌈ηLθ0

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

⊞η⁰

Much like the other answers, a 0 is pushed to the take list, so that the maximum is at least 0 and the minimum is at most 0.

E⁻±⌊ηLθ0

Print 0s for each element taken before the first.

IΦθ∨‹κ⌈η›⁻⊕κLθ⌊η

Print those elements which fall in either the positive or negative range.

E⁻⌈ηLθ0

Print 0s for each element taken after the last.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 28 26 bytes

εݨyd≠iIg+<]˜êεIg‹yd*iyèë¾

Inputs in the order \$N,A\$.

Try it online or verify all test cases.

Explanation:

ε              # Map each value `y` in the (implicit) input-list `N` to:
 Ý             #  Push a list in the range [0,`y`]
  ¨            #  Remove the last value to make the range [0,`y`)
   yd≠i        #  If `y` is negative:
       Ig+     #   Add the input-length of `A` to each value
          <    #   And decrease each value by 1
]              # Close the if-statement and map
 ˜             # Flatten the list of indices
  ê            # Sort and uniquify these indices
   ε           # Map each index `y` to:
    Ig‹        #  Check if `y` is smaller than the input-length of `A`
       yd      #  Check if `y` is non-negative (>= 0)
         *i    #  If both are truthy:
           yè  #   Index `y` into the (implicit) input-list `A`
          ë    #  Else:
           ¾   #   Push a 0 instead
               # (after which the resulting list is output implicitly)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Clojure, 90 bytes

#(for[j(sort(set(for[i %2 x(range(Math/abs i))](if(< i 0)(+(count %)i x)x))))](get % j 0))

Try it online!

Takes input in the order: data, indices

Ungolfed

#(for [j 
  (-> 
    ; for each i in indices generate a range from 0 to abs(i)
    (for [i %2 x (range (Math/abs i))] 
      ; for negative indices add the offset = length(data) + i
      (if (< i 0) (+ (count %) i x) x))
    set ; keep unique values
    sort)] ; sort in ascending order
  ; for each j, get the jth item in data, or 0 if out of bounds
  (get % j 0)) 
| improve this answer | |
\$\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.