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!

\$\endgroup\$
0

31 Answers 31

15
\$\begingroup\$

APL(Dyalog Unicode), 4 bytes SBCS

-/⍣≡

Try it on APLgolf!

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

\$\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!

\$\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.

\$\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.
\$\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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$
    – naffetS
    Commented May 18, 2022 at 2:14
  • 1
    \$\begingroup\$ It looks like (i*=-1) can just be (i=-i) for -1 byte \$\endgroup\$
    – naffetS
    Commented 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\$ Commented 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--
    Commented 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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ ...I don't think it counts if you change the logic of your language just for a challenge? \$\endgroup\$
    – naffetS
    Commented 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
    Commented 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
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 11 bytes

({y-x}/|:)/

Try it online!

Port of @ovs' APL answer.

\$\endgroup\$
1
  • \$\begingroup\$ you can replace {y-x} with -1 \$\endgroup\$
    – Traws
    Commented 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.

\$\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.

\$\endgroup\$
4
  • \$\begingroup\$ 48 bytes with Reduce(`-`,,,T) and Map... \$\endgroup\$ Commented May 18, 2022 at 7:09
  • \$\begingroup\$ @DominicvanEssen I wonder, isn't it distinct enough for a separate answer? \$\endgroup\$
    – pajonk
    Commented 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\$ Commented May 18, 2022 at 7:23
  • \$\begingroup\$ @DominicvanEssen thanks! \$\endgroup\$
    – pajonk
    Commented 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.
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes

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

Try it online!

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

\$\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.

\$\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
\$\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 :).

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

Arturo, 52 bytes

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

Try it

\$\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);
}
\$\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
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 24 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 35 bytes

⊞υθFυFΦι⁺⟦⟧κ⊞υκF⮌υ⊞ι↨E⮌ιΣ⁺⟦⁰⟧⊟ι±¹Iθ

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

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

Get all of the sublists of the input.

F⮌υ

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

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

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.

Iθ

Output the final result.

\$\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
\$\endgroup\$
2
\$\begingroup\$

Factor, 73 bytes

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

Try it online!

\$\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.

\$\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!

\$\endgroup\$
3
  • \$\begingroup\$ Maybe f=a=>+a||a.map?.(n=>p-=(a=-a)*f(n),p=0,a=1)|p works? \$\endgroup\$
    – tsh
    Commented 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
    Commented 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\$ Commented 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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can remove "1 because it doesn't matter which axis is reduced first. \$\endgroup\$
    – Bubbler
    Commented Nov 7, 2023 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!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ (1-i%2*2) -> (1|i%-2) -> (-1)**i \$\endgroup\$
    – ovs
    Commented 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 -.

\$\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!

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

Vyxal, 12 bytes

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

Try it Online!

This is like, really, really, really bad.

\$\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)
        )
      )
    )))
  }
}
\$\endgroup\$

Your Answer

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

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