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

25 Answers 25

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

C++ (GCC), 89 88 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);return s;}

This answer is in the same spirit as @HatsuPointerKun's, but (ab)uses C++ 20's auto parameter declaration, which allows us to ditch the whole #include<vector> shenanigans (it works with any container), and the same a similar trick as @Olivier Grégoire's Java solution to alternate the values of i.

Attempt This Online!

C++ (GCC), 79? bytes

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

Making use of this to avoid returning a in the base case saves 9 bytes in an unoptimized -O0 g++ build.

Attempt This Online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$
    – Steffan
    May 18 at 2:14
  • 1
    \$\begingroup\$ It looks like (i*=-1) can just be (i=-i) for -1 byte \$\endgroup\$
    – Steffan
    May 18 at 2:16
  • \$\begingroup\$ When I click on 'execute' in the ATO link, the stdout seems empty. Am I doing something wrong? \$\endgroup\$ May 18 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\$ May 18 at 19:22
5
\$\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\$
5
\$\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\$
5
\$\begingroup\$

flax, 4 3 bytes

-´ⁱ

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\$
    – Steffan
    May 17 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\$
    – PyGamer0
    May 17 at 17:10
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
    May 19 at 23:15
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 0,
                                       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\$
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\$ May 18 at 7:09
  • \$\begingroup\$ @DominicvanEssen I wonder, isn't it distinct enough for a separate answer? \$\endgroup\$
    – pajonk
    May 18 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\$ May 18 at 7:23
  • \$\begingroup\$ @DominicvanEssen thanks! \$\endgroup\$
    – pajonk
    May 18 at 7:29
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\$
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\$

C++, 194 147 bytes

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

The code :

#include<vector>
int f(int a){return a;}template<typename T>int f(std::vector<T>a){int s=0,i=0;for(;i<a.size();++i)s+=f(a[i])*(i%2?-1: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\$
1
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
    May 17 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 at 7:09
  • 1
    \$\begingroup\$ -3 bytes f=a=>a.map?.(n=>p-=(a=-a)*f(n),p=0,a=1)?p:a \$\endgroup\$ Jun 13 at 21:22
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
    May 16 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\$

Factor, 73 bytes

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

Try it online!

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

C++ (GCC), 135 133 bytes

  • -2 bytes thanks to ceilingcat
#include<numeric>
int f(int a){return a;}int f(auto&a){return std::accumulate(rbegin(a),rend(a),0,[](int l,auto&r){return f(r)-l;});}

Attempt This Online!

\$\endgroup\$
0

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.