24
\$\begingroup\$

To check whether a list of non-negative integers is balanced, one can imagine putting respective weights on a board and then try to balance the board on a pivot such that the summarized relative weights left and right of the pivot are the same. The relative weight is given by multiplying the weight with its distance to the pivot (see law of the lever).

wikipedia lever (Source: wikipedia)

This image corresponds to a list [100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]. This list is balanced because the 5 has a distance of 20 to the pivot, the 100 a distance of 1 and 5*20 = 100 = 100*1.

Examples

 3 1 5 7
#########
     ^

In this case the pivot is directly under the 5, the 3 has distance 2 and the 1 and 7 have distance 1. So both sides left and right of the pivot sum up to 7 (3*2 + 1*1 on the left and 7*1 on the right) and therefore the list [3, 1, 5, 7] is balanced.

Note, however, that the pivot does not have to be placed under one of the list elements, but might also be placed in-between two list elements:

 6 3 1
#######
  ^

In this case the distances become 0.5, 1.5, 2.5, ... and so on. This list is also balanced because 6*0.5 = 3 = 3*0.5 + 1*1.5.

The pivot can only be placed exactly below one number or exactly in the middle between two numbers, and not e.g. at two-thirds between two numbers.

Task

Given a list of non-negative integers in any reasonable format, output a truthy value if the list can be balanced and a falsy value otherwise.

You can assume that the input list contains at least two elements and that at least one element is non-zero.

This is a challenge, so the answer with the fewest amount of bytes in each language wins.

Truthy Testcases

[1, 0]
[3, 1, 5, 7]
[6, 3, 1]
[100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]
[10, 4, 3, 0, 2, 0, 5]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[7, 7, 7, 7]

Falsy Testcases

[1, 2]
[3, 6, 5, 1, 12]
[0, 0, 2, 0, 1, 0]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[6, 3, 2, 4, 0, 1, 2, 3]
[4, 0, 0, 2, 3, 5, 2, 0, 1, 2, 3, 0, 0, 1, 2, 4, 3, 1, 3, 0, 0, 2]
[100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]

A lot of related challenges where found while this challenge was sand-boxed: Is it a balanced number?, Equilibrium index of a sequence, Balance a set of weights on a seesaw, Balancing Words, Will I tip over? and Where does the pivot belong?

\$\endgroup\$
  • \$\begingroup\$ Can the pivot be placed before the first number or after the last number? \$\endgroup\$ – Erik the Outgolfer Dec 20 '17 at 15:45
  • \$\begingroup\$ @EriktheOutgolfer If all the weights are nonnegative, no. \$\endgroup\$ – Mnemonic Dec 20 '17 at 15:46
  • \$\begingroup\$ I think this might be a dupe. Or was it sitting in the Sandbox for a while? \$\endgroup\$ – Shaggy Dec 20 '17 at 16:07
  • \$\begingroup\$ related. (cc @Shaggy Maybe this was what you were thinking about) \$\endgroup\$ – Mr. Xcoder Dec 20 '17 at 16:33
  • 2
    \$\begingroup\$ @Giuseppe @Steadybox I added You can assume that the input list contains at least two elements and that at least one element is non-zero. \$\endgroup\$ – Laikoni Dec 20 '17 at 16:46

21 Answers 21

7
\$\begingroup\$

Pyth, 12 10 bytes

!%ys*VQUQs

Try it online

Saved 2 bytes thanks to Mr. Xcoder and Erik the Outgolfer.

Explanation

!%ys*VQUQs
    *VQUQ    Multiply each input by its index.
  ys         Take twice the sum (to handle half-integer positions).
!%       sQ  Check if that's a multiple of the total weight.
\$\endgroup\$
  • \$\begingroup\$ You can use y in place of *2 \$\endgroup\$ – Mr. Xcoder Dec 20 '17 at 15:49
  • \$\begingroup\$ 10 bytes: !%ys*VQUQs \$\endgroup\$ – Erik the Outgolfer Dec 20 '17 at 15:50
4
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

IntegerQ[2#.Range[t=Tr[1^#]]/(t-1)]&

This is a center of mass problem in a coordinate system with the origin at one of the points and then you determine if the CM falls on a lattice point where the lattice width = 1/2.

Try it online!

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 6 bytes

ƶO·IOÖ

Try it online!

How?

ƶO·IOÖ ~ Full program. I = input.

ƶ      ~ Lift I. Multiply each element with its 1-based index.
 O     ~ Sum.
  ·    ~ Double. 
     Ö ~ Is a multiple of?
   IO  ~ The sum of I.
\$\endgroup\$
  • \$\begingroup\$ Seems to fail on [1,1] (should be truthy). It seems the implicit doubling isn't actually there. \$\endgroup\$ – Zgarb Dec 21 '17 at 16:46
  • \$\begingroup\$ @Zgarb Fixed (?) \$\endgroup\$ – Mr. Xcoder Dec 21 '17 at 17:51
3
\$\begingroup\$

Jelly, 6 bytes

×JSḤọS

Try it online!

Well, looks like Leaky Nun pointed the pointless out.

Using Mnemonic's Pyth approach.

Returns a positive integer (truthy) or zero (falsy).

\$\endgroup\$
  • \$\begingroup\$ Would this work? \$\endgroup\$ – Leaky Nun Dec 20 '17 at 16:20
  • \$\begingroup\$ @LeakyNun Not so sure, that's why I used LḶ instead (although it would succeed for all test cases). EDIT: Oooh, now that I think about it again, it seems so...(b | a ⇔ b | a + b duh) \$\endgroup\$ – Erik the Outgolfer Dec 20 '17 at 16:22
2
\$\begingroup\$

R, 34 bytes

function(n)!(n%*%seq(n)*2)%%sum(n)

Try it online!

Takes input as a vector. Ports mnemonic's answer. Returns a 1x1 matrix.

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

Japt, 10 bytes

í* x*2 vUx

Try it online!

Explanation:

 í* x*2 vUx
U            // Implicit Input                 [3, 1, 5, 7]
 í           // Pair the input with its index  [[3,0],[1,1],[5,2],[7,3]]
  *          // Multiply each item             [0,1,10,21]
    x        // Sum                            32
     *2      // Double                         64
        v    // Divisible by:
         Ux  //   Sum of Input                 16
             // Explicit Output                1

Returns 1 for truthy, 0 for falsy.

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

Python 2, 41 bytes

S=s=0
for n in input():S-=s;s-=n
1>>2*S%s

Output is via exit code, so 0 is truthy and 1 is falsy.

Try it online!

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

Julia, 31 27 bytes

4 bytes saved thanks to @Dennis

!n=2n[i=1:end]⋅i%sum(n)<1

Try it online!

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

Ruby, 47 bytes

Saved 2 bytes thanks to Mr. Xcoder

->k{(k.map.with_index{|x,i|x*i*2}.sum%k.sum)<1}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Nice first answer. 47 bytes \$\endgroup\$ – Mr. Xcoder Dec 20 '17 at 20:54
1
\$\begingroup\$

C,  140  137 bytes

float l,r;i,j,t;f(L,n)int*L;{for(i=t=-1;++i<2*n;t*=l-r)for(l=r=j=0;j<n;++j)l+=j<i/2.?L[j]*(i/2.-j):0,r+=j>i/2.?L[j]*(j-i/2.):0;return!t;}

Try it online!

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

Python 3, 51 bytes

lambda k:sum(i*e*2for i,e in enumerate(k))%sum(k)<1

Try it online!

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

Perl 6, 23 bytes

{sum(1..*Z*$_)*2%%.sum}

Test it

Uses the algorithm from various other entries.

Expanded:

{  # bare block lambda with implicit parameter 「$_」

    sum(

        1 .. *  # Range starting from 1

      Z*        # Zip using &infix:«*»

        $_      # the input

    ) * 2

  %%            # is divisible by

    .sum        # the sum of the input (implicit method call on 「$_」)
}
\$\endgroup\$
1
\$\begingroup\$

Japt, 11 10 8 bytes

Originally inspired by Mnemonic's solution

x* vUx*½

Try it

1 3 bytes saved thanks to ETHproductions.


Explanation

Implicit input of array U. Reduce by addition (x), multiplying each element by its 0-based index (*) in the process. Check if the result is evenly divisible (v) by the sum of the original input (Ux) with each element being multiplied by 0.5 ().

\$\endgroup\$
  • \$\begingroup\$ Save a byte with m* x*2 vUx. This makes me wonder if m* x*2 can be reduced further... \$\endgroup\$ – ETHproductions Dec 21 '17 at 18:05
  • \$\begingroup\$ Thanks, @ETHproductions; that's another new trick I've learned today. \$\endgroup\$ – Shaggy Dec 21 '17 at 18:11
  • \$\begingroup\$ I've got it, just use x* and check if it's divisible by Ux*½ :) \$\endgroup\$ – ETHproductions Dec 21 '17 at 18:11
  • \$\begingroup\$ Yes, I don't think that trick is documented anywhere... But whenever you use a binary operator as an auto-function with no second argument, it uses the index by default (like if you did XY{X*Y}) \$\endgroup\$ – ETHproductions Dec 21 '17 at 18:12
  • \$\begingroup\$ Oh, now, that's just ingenious, @ETHproductions. :) \$\endgroup\$ – Shaggy Dec 21 '17 at 18:17
1
\$\begingroup\$

C#, 71 bytes


Golfed

a=>{int i,s,S=s=i=0;while(i<a.Length){S-=s;s-=a[i++];}return 2*S%s<1;};

Ungolfed

a => {
    int
        i, s, S = s = i = 0;

    while( i < a.Length ) {
        S -= s;
        s -= a[ i++ ];
    }

    return 2 * S % s < 1;
};

Full code

using System;

namespace Namespace {
    class Program {
        static void Main( String[] args ) {
            Func<Int32[], Boolean> f = a => {
                int
                    i, s, S = s = i = 0;

                while( i < a.Length ) {
                    S -= s;
                    s -= a[ i++ ];
                }

                return 2 * S % s < 1;
            };

            List<Int32[]>
                testCases = new List<Int32[]>() {
                    new Int32[] {1, 0},
                    new Int32[] {3, 1, 5, 7},
                    new Int32[] {6, 3, 1},
                    new Int32[] {100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5},
                    new Int32[] {10, 4, 3, 0, 2, 0, 5},
                    new Int32[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
                    new Int32[] {7, 7, 7, 7},

                    new Int32[] {1, 2},
                    new Int32[] {3, 6, 5, 1, 12},
                    new Int32[] {0, 0, 2, 0, 1, 0},
                    new Int32[] {1, 2, 3, 4, 5, 6, 7, 8, 9},
                    new Int32[] {6, 3, 2, 4, 0, 1, 2, 3},
                    new Int32[] {4, 0, 0, 2, 3, 5, 2, 0, 1, 2, 3, 0, 0, 1, 2, 4, 3, 1, 3, 0, 0, 2},
                    new Int32[] {100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5},
                };

            foreach( Int32[] testCase in testCases ) {
                Console.WriteLine( $"{{ {String.Join(", ", testCase)} }}\n{f( testCase )}" );
            }

            Console.ReadLine();
        }
    }
}

Releases

  • v1.0 - 71 bytes - Initial solution.

Notes

I might have, or might have not, blatantly "borrowed" Dennis Python 2 solution...

\$\endgroup\$
0
\$\begingroup\$

Haskell, 39 bytes

f l=2*sum(zipWith(*)l[0..])`mod`sum l<1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog), 15 bytes

0≡+⌿|(+⌿+⍨×⍳∘≢)

Try it online!

Looks very ungolfy to me...

\$\endgroup\$
0
\$\begingroup\$

Python 2, 78 75 bytes

thanks to Mr. Xcoder for -3 bytes

lambda l:0in[sum(v*(i-y*2)for y,v in enumerate(l))for i in range(len(l)*2)]

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ No need for the space in 0 in. Also no need for the 0 in range(0,len(l)*2).. \$\endgroup\$ – Mr. Xcoder Dec 20 '17 at 16:30
0
\$\begingroup\$

Julia 0.6, 25 bytes

~=sum
!x=~cumsum(2x)%~x<1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 139 128 bytes

<?php $a=explode(',',fgets(STDIN));for($i=0;$i<count($a)-.5;$i+=.5){$z=0;foreach($a as $k=>$v)$z+=($k-$i)*$v;if($z==0)die(1);}?>

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Unless I misunderstand this [codegolf.meta.stackexchange.com/questions/2447/… you should be able to use die(1) and die(0) and save 4 bytes by using the exit code instead of a printed string. \$\endgroup\$ – manassehkatz Dec 21 '17 at 5:03
  • \$\begingroup\$ @manassehkatz If you use die without quotes on tio.run it will treat it as a status code (which it should) and not put it in the Output section. So I just added quotes to prevent people from nitpicking \$\endgroup\$ – Mic1780 Dec 21 '17 at 15:49
0
\$\begingroup\$

Swift, 76 bytes

{var i=0,t=0;print($0.reduce(0){$0+($1*i,t+=$1,i+=1).0}*2%t<1)}as([Int])->()

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 55 + 1 (a) = 56 bytes

$.=0;map$.+=$p++*$_,@F;$#F+($p=$i-=.5)&&$.&&redo;say!$.

Try it online!

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