21
\$\begingroup\$

Given a multidimensional array, find the recursive alternating sum. An alternating sum is simply the sum of an array, where every other item (starting with the second) is negated. For example, the alternating sum of [7, 1, 6, -4, -2] is the sum of [7, -1, 6, 4, -2], or 14. In this challenge, you'll take the alternating sum of a multidimensional array.

Task:

Given an array like this:

[
    [
        [1, 2], [2, 4], [4, 8]
    ],
    [
        [-4, -4], [-1, 1], [2, -2]
    ]
]

First find the alternating sums of all of the deepest nested arrays:

[
    [-1, -2, -4],
    [0, -2, 4]
]

Then do this again:

[-3, 6]

And finally:

-9

You can choose how input is represented, but it must be able to handle multidimensional arrays of any number of dimensions possible in the language you use. You don't need to support ragged arrays.

Test cases:

[1]                                                         1
[-1]                                                        -1
[1, 2]                                                      -1
[2, 0, 4]                                                   6
[1, -2]                                                     3
[[1]]                                                       1
[[1, 2], [4, 8]]                                            3
[[-1, -1], [2, 2]]                                          0
[[[[1], [2]], [[4], [8]]]]                                  3
[[[1, 2], [2, 4], [4, 8]], [[-4, -4], [-1, 1], [2, -2]]]    -9

Other:

This is , so shortest answer (per language) wins!

Improve this question
\$\endgroup\$
0

31 Answers 31

Reset to default
1
2
15
\$\begingroup\$

APL(Dyalog Unicode), 4 bytes SBCS

-/⍣≡

Try it on APLgolf!

Alternating sum (aka right-reduce by subtraction) along last axis -/ until convergence ⍣≡.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python, 58 bytes

f=lambda a,s=-1:sum(f(x)*(s:=-s)for x in a)if[]==a*0else a

Attempt This Online!

Whython, 45 bytes

f=lambda a,s=-1:sum(f(x)*(s:=-s)for x in a)?a

Attempt This Online!

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python 2, 50 bytes

f=lambda A,*a:(f(*A)if f<A else A)-(a>()and f(*a))

Attempt This Online!

Expects splatted input. Test harness borrowed from @pxeger.

How?

Hybrid recursion implementing depth first traversal. Detail: f<A depends on Python 2's comparability of objects of different types.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Brachylog, 5 bytes

ċ↰ᵐ-|

Try it online!

 ↰ᵐ      Recur on each element
   -     then take the alternating sum
ċ   |    if it's a list, else return it unchanged.
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

C++ 20, 87 bytes

int f(int a){return a;}int f(auto a){int s=0,i=1;for(auto b:a)s+=f(b)*i,i=-i;return s;}

This answer is in the same spirit as @HatsuPointerKun's, but it (ab)uses C++ 20's auto parameter declaration, which allows us to ditch the whole #include<vector> shenanigans (it works with any container).

Attempt This Online!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$
    – naffetS
    May 18, 2022 at 2:14
  • 1
    \$\begingroup\$ It looks like (i*=-1) can just be (i=-i) for -1 byte \$\endgroup\$
    – naffetS
    May 18, 2022 at 2:16
  • \$\begingroup\$ When I click on 'execute' in the ATO link, the stdout seems empty. Am I doing something wrong? \$\endgroup\$
    – Dominic van Essen
    May 18, 2022 at 18:28
  • 1
    \$\begingroup\$ @DominicvanEssen the tests were using assert, since I had borrowed them from HatsuPointerKun's answer. I just changed them to output the results to stdout \$\endgroup\$
    – c--
    May 18, 2022 at 19:22
5
\$\begingroup\$

flax, 4 3 bytes

-/´

Try It Online!

Another port of @ovs' APL answer.

¯1 byte due to update changing direction of fold/scan to match evaluation order

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ ...I don't think it counts if you change the logic of your language just for a challenge? \$\endgroup\$
    – naffetS
    May 17, 2022 at 17:03
  • 1
    \$\begingroup\$ @Steffan i mean the change makes sense, as the evaluation order is right to left, fold and scan order should also be right to left.. \$\endgroup\$
    – zoomlogo
    May 17, 2022 at 17:10
5
\$\begingroup\$

Nekomata, 4 bytes

ʷ{£d

Attempt This Online!

ʷ      Repeat the following function until it fails:
 {     Start a block
  £d   Convert from base -1; fail if the input is not a list
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 11 bytes

({y-x}/|:)/

Try it online!

Port of @ovs' APL answer.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ you can replace {y-x} with -1 \$\endgroup\$
    – Traws
    May 19, 2022 at 23:15
4
\$\begingroup\$

Haskell + free, 14 bytes

iter$foldr(-)0

Try it online!

We need the free library to represent arbitrarily nested lists. This code works on any ragged list as well. foldr(-)0 computes the alternating sum of a flat list and iter applies it recursively to a free monad.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

R, 51 48 bytes

Edit: -3 bytes thanks to @Dominic van Essen.

f=\(l)"if"(is.list(l),Reduce(`-`,Map(f,l),,T),l)

Attempt This Online!

Takes input as a list of lists.

Old version:

f=\(l)"if"(is.list(l),sapply(l,f)%*%-(-1)^seq(l),l)

Attempt This Online!

Takes input as above. Outputs a \$1\times1\$ matrix.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 48 bytes with Reduce(`-`,,,T) and Map... \$\endgroup\$
    – Dominic van Essen
    May 18, 2022 at 7:09
  • \$\begingroup\$ @DominicvanEssen I wonder, isn't it distinct enough for a separate answer? \$\endgroup\$
    – pajonk
    May 18, 2022 at 7:17
  • \$\begingroup\$ I'm happy for you to just post an update: it's really just a different way to alternate the +s & -s... the recursive setup (which is the clever bit) is still the same. \$\endgroup\$
    – Dominic van Essen
    May 18, 2022 at 7:23
  • \$\begingroup\$ @DominicvanEssen thanks! \$\endgroup\$
    – pajonk
    May 18, 2022 at 7:29
4
\$\begingroup\$

PARI/GP, 33 bytes

f(a)=if(#a',f(a[1])-f(a[^1]),a,a)

Attempt This Online!

f(a)=if(#a',f(a[1])-f(a[^1]),a,a)
f(a)=                                Define a function `f` with argument `a`:
     if(#a',                         If the length of `a`'s derivative is nonzero,
                                       so `a` is a nonempty list:
            f(a[1])                    apply `f` to the first element of `a`,
                   -                   minus
                    f(a[^1]),          apply `f` to `a` with the first element removed.
                             a,      Otherwise, if `a` is truthy,
                                       so `a` is a nonzero integer:
                               a       return `a`.
                                )    (Implicitly) Otherwise, return 0.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes

Fold[#2-#&]@*Reverse//@#&

Try it online!

Right-fold subtraction on every level. Supports ragged arrays.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Haskell + hgl, 9 bytes

itr$lH(-)

Explanation

Seeing how short my haskell answer turned out I couldn't help but port it to hgl. This works basically the same.

It takes input as a free monad of lists, that is a ragged list. lH(-) is equivalent to the haskell foldl1(-) and calculates the alternating sum of a flat list. We use it with itr to recursively reduce a ragged list.

Reflection

This is pretty tight as far as things go.

It feels clunky to use (-) here but the alternative is fsb which would lose a byte due to spacing. In order for it to save bytes fsb would have to be 1 byte long.

The one thing that seems like it could be worthwhile would be an alternating sum builtin. It would probably save 2 bytes here.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

BQN, 15 bytes

{0==𝕩?𝕩;𝕊-˝⎉1𝕩}

Anonymous function. Takes a multidimensional array, returns a 0-dimensional array containing a number.

Explanation

{0==𝕩?𝕩;𝕊-˝⎉1𝕩}
{              }  Anonymous function:
   =               Rank (number of dimensions) of
    𝕩              the argument
 0=                equals zero?
     ?             If so:
      𝕩             Return the argument unchanged
       ;           If not:
          ˝         Right fold
         -          on subtraction
           ⎉1      the innermost axis of
              𝕩     the argument
        𝕊           and call this function recursively on that array
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Java 17, 101 bytes

int f(Object[]a){int s=0,m=-1;for(var i:a)s+=(m=-m)*(i instanceof Long j?j:f((Object[])i));return s;}

Attempt This Online!

Java 17+ is required for pattern matching; this is probably the first time it is useful in a golf :).

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Arturo, 52 bytes

f:$[a][(block? a)?->([]=a)?->0->-f a\0f drop a 1->a]

Try it

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C++, 194 147 141 130 bytes

-17 (6+11) bytes tanks to ceilingcat

TIO Link

This code uses templates to have any kind of vectors as input ( vector<int>, vector<vector<int>>, vector<vector<vector<int>>> ... )

The code :

#import<vector>
int f(int a){return a;}template<class T>int f(std::vector<T>a){int s=0,i=1;for(auto x:a)s-=f(x)*(i*=-1);return s;}

Here's the code for testing :

int main() {

    // Test case [1]
    std::vector<int> v1 = { 1 };
    assert(f(v1) == 1);

    // Test case [-1]
    std::vector<int> v2 = { -1 };
    assert(f(v2) == -1);

    // Test case [1,2]
    std::vector<int> v3 = { 1,2 };
    assert(f(v3) == -1);
    
    // Test case [2,0,4]
    std::vector<int> v4 = { 2,0,4 };
    assert(f(v4) == 6);

    // Test case [1,-2]
    std::vector<int> v5 = { 1,-2 };
    assert(f(v5) == 3);

    // Test case [[1]] = 1
    std::vector<std::vector<int>> v6 = { {1} };
    assert(f(v6) == 1);

    // Test case [[1, 2], [4, 8]]
    std::vector<std::vector<int>> v7 = { {1,2}, {4,8} };
    assert(f(v7) == 3);

    // Test case [[-1, -1], [2, 2]]
    std::vector<std::vector<int>> v8 = { {-1,-1},{2,2} };
    assert(f(v8) == 0);

    // Test case [[[[1], [2]], [[4], [8]]]]                                  3
    std::vector<std::vector<std::vector<std::vector<int>>>> v9 = { {{{1},{2}},{{4},{8}}} };
    assert(f(v9) == 3);

    // Test case [[[1, 2], [2, 4], [4, 8]], [[-4, -4], [-1, 1], [2, -2]]]
    std::vector<std::vector<std::vector<int>>> v10 = { {{1,2},{2,4},{4,8}},{{-4,-4},{-1,1},{2,-2}} };
    assert(f(v10) == -9);
}
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Uiua, 9 bytes

⍥(/-⇌)⧻△.

Try it online!

Similarly to BQN and K, alternating sum in Uiua requires a reverse before reduction by subtraction. Uiua doesn't have "converge" builtin, and "do while" isn't a good fit here because getting the iteration count directly is cheap.

⍥(/-⇌)⧻△.    input: a possibly multidimensional array
       ⧻△.    keep input and push number of dimensions
⍥(    )        repeat that many times:
   /-⇌         alternating sum over the leading axis
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 24 bytes

!x::Int=x
!x=!foldr(-,x)

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 35 bytes

⊞υθＦυＦΦι⁺⟦⟧κ⊞υκＦ⮌υ⊞ι↨Ｅ⮌ιΣ⁺⟦⁰⟧⊟ι±¹Ｉθ

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

⊞υθＦυＦΦι⁺⟦⟧κ⊞υκ

Get all of the sublists of the input.

Ｆ⮌υ

Loop over the sublists in reverse, i.e. from deepest back up to the original input.

⊞ι↨Ｅ⮌ιΣ⁺⟦⁰⟧⊟ι±¹

Remove all the elements of the sublist in reverse order, convert them from integers or sublists to integers, then interpret them as base -1 to obtain the alternating sum, and push the result back to the sublist.

Ｉθ

Output the final result.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 17 bytes

"ИÊi®δ.V}.«-"©.V

As always, 05AB1E and recursive functions are not a good match..

Try it online or verify all test cases.

Explanation:

"..."        # Create the recursive-string explained below
     ©       # Store it in variable `®` (without popping)
      .V     # Evaluate and execute it as 05AB1E code
             # (after which the result is output implicitly)
             #
Ð            # Triplicate the current list
 ˜           # Flatten the top copy
  Êi         # If the top two lists are NOT equal (so there is an inner list):
     δ       #  Map over each inner item:
    ® .V     #   Do a recursive call
   }         # After the if-statement, whether we've executed it or not
    .«       # Right-reduce the list by:
      -      #  Subtracting
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Factor, 73 bytes

: f ( s -- n ) dup array? [ [ 0 ] [ unclip f swap f - ] if-empty ] when ;

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

ŒJ’§-*ḋF

Try it online!

ŒJ          Enumerate the multidimensional indices of every element, in flat order.
  ’         Decrement each dimension (indexed from 1) of each index.
   §        Sum each index,
    -*      and raise -1 to the power of each sum.
      ḋF    Take the dot product of that with the flattened input.

Jelly, 10 9 bytes

߀ŒḊ¡U_@/

Try it online!

߀           Recur on each element of the argument
    ¡        as many times as
  ŒḊ         its depth.
     U       Reverse the list of results (or do nothing to the scalar argument)
      _@/    and left-reduce by reversed subtraction.

Previous solution was ߀NÐeSµ)Ƒ¡. Gaze upon it and despair.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 46 bytes

f=a=>1/a?+a:a.map(n=>p-=(a=-a)*f(n),p=0,a=1)|p

Try it online!

Or 43 bytes with optional chaining (ES11), as suggested by @MatthewJensen:

f=a=>a.map?.(n=>s-=(a=-a)*f(n),s=0,a=1)?s:a

Attempt This Online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Maybe f=a=>+a||a.map?.(n=>p-=(a=-a)*f(n),p=0,a=1)|p works? \$\endgroup\$
    – tsh
    May 17, 2022 at 2:01
  • 1
    \$\begingroup\$ @tsh The OP has clarified that 0's may appear in the input. So that would fail on [[2,0]], for instance. \$\endgroup\$
    – Arnauld
    May 17, 2022 at 7:09
  • 1
    \$\begingroup\$ -3 bytes f=a=>a.map?.(n=>p-=(a=-a)*f(n),p=0,a=1)?p:a \$\endgroup\$
    – Matthew Jensen
    Jun 13, 2022 at 21:22
2
\$\begingroup\$

J, 7 5 bytes

-/^:_

Try it online!

-2 thanks to Bubbler

Just a J translation of the APL answer, for completeness.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can remove "1 because it doesn't matter which axis is reduced first. \$\endgroup\$
    – Bubbler
    Nov 7 at 6:41
1
\$\begingroup\$

Python 3.8 (pre-release), 66 bytes

lambda n:n*0==0and n or sum((1-i%2*2)*f(e)for i,e in enumerate(n))

Try it online!

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ (1-i%2*2) -> (1|i%-2) -> (-1)**i \$\endgroup\$
    – ovs
    May 16, 2022 at 17:32
1
\$\begingroup\$

Retina 0.8.2, 108 bytes

\d+(?<=((])|(?<-2>\[)|(?(2).|((,)|.)))*)
$#4$*-$&
--

O^`-?\d+
(-)|\d+|.
$*1$1
1>`-

(1+)-\1
-
r`(1*)-?$
$.1

Try it online! Link includes test cases. Explanation:

\d+(?<=((])|(?<-2>\[)|(?(2).|((,)|.)))*)
$#4$*-$&

Negate each value a number of times given by the sum of its multidimensional indices.

--

Simplify any double negations.

O^`-?\d+

Sort the negative numbers to the end.

(-)|\d+|.
$*1$1

Convert the values to unary but delete everything else that isn't a -. This sums the positive values together.

1>`-

Sum the negative values together.

(1+)-\1
-

Take the difference between the positive and negative values.

r`(1*)-?$
$.1

Convert to decimal, ignoring any trailing -.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

BQN, 6 bytesSBCS

-´⚇1⍟≡

-´ alternating sum

⚇1 at depth 1 (simple lists)

⍟≡ repeated as many times as the depth of the argument

Run online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 12 bytes

λ∑u$e;€f?fÞ•

Try it Online!

This is like, really, really, really bad.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala, 100 bytes

Golfed version. Try it online!

a=>{var(s,m)=(0,-1);for(i<-a){m= -m;i match{case j:Long=>s+=m*j.toInt;case b:Seq[_]=>s+=m*f(b)}};s;}

Ungolfed version. Try it online!

object Main {
  def f(a: Array[_]): Int = {
    var s = 0
    var m = -1
    for (i <- a) {
      m = -m
      i match {
        case j: Long => s += m * j.toInt
        case arr: Array[_] => s += m * f(arr)
      }
    }
    s
  }

  def main(args: Array[String]): Unit = {
    println(f(Array(1L)))
    println(f(Array(-1L)))
    println(f(Array(1L,2L)))
    println(f(Array(2L,0L,4L)))
    println(f(Array(1L,-2L)))
    println(f(Array(Array(1L))))
    println(f(Array(Array(1L, 2L), Array(4L,8L))))
    println(f(Array(Array(-1L, -1L), Array(2L,2L))))
    println(f(Array(
      Array(
        Array(
          Array(1L),
          Array(2L)
        ),
        Array(
          Array(4L),
          Array(8L)
        )
      )
    )))
  }
}
Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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