Can this list be balanced?

23

3

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?

Laikoni

Posted 2017-12-20T15:25:37.880

Reputation: 23 676

Can the pivot be placed before the first number or after the last number? – Erik the Outgolfer – 2017-12-20T15:45:18.387

@EriktheOutgolfer If all the weights are nonnegative, no. – None – 2017-12-20T15:46:36.567

I think this might be a dupe. Or was it sitting in the Sandbox for a while? – Shaggy – 2017-12-20T16:07:00.933

related. (cc @Shaggy Maybe this was what you were thinking about) – Mr. Xcoder – 2017-12-20T16:33:53.053

2@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. – Laikoni – 2017-12-20T16:46:29.870

@Shaggy The challenge was in the sandbox for over a year: https://codegolf.meta.stackexchange.com/a/10521/56433 (only visible for high-rep users)

– Laikoni – 2017-12-20T16:48:51.603

That's probably why I recognised it, so. – Shaggy – 2017-12-20T16:50:26.163

Answers

7

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.

user48543

Posted 2017-12-20T15:25:37.880

Reputation:

You can use y in place of *2 – Mr. Xcoder – 2017-12-20T15:49:31.910

10 bytes: !%ys*VQUQs – Erik the Outgolfer – 2017-12-20T15:50:24.160

4

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!

Kelly Lowder

Posted 2017-12-20T15:25:37.880

Reputation: 3 225

4

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.

Mr. Xcoder

Posted 2017-12-20T15:25:37.880

Reputation: 39 774

Seems to fail on [1,1] (should be truthy). It seems the implicit doubling isn't actually there. – Zgarb – 2017-12-21T16:46:58.107

@Zgarb Fixed (?) – Mr. Xcoder – 2017-12-21T17:51:26.390

2

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).

Erik the Outgolfer

Posted 2017-12-20T15:25:37.880

Reputation: 38 134

Would this work?

– Leaky Nun – 2017-12-20T16:20:03.717

@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) – Erik the Outgolfer – 2017-12-20T16:22:19.647

2

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.

Giuseppe

Posted 2017-12-20T15:25:37.880

Reputation: 21 077

2

Julia, 31 27 bytes

4 bytes saved thanks to @Dennis

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

Try it online!

Uriel

Posted 2017-12-20T15:25:37.880

Reputation: 11 708

2

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!

Dennis

Posted 2017-12-20T15:25:37.880

Reputation: 196 637

2

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.

Oliver

Posted 2017-12-20T15:25:37.880

Reputation: 7 160

2

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!

Tom Lazar

Posted 2017-12-20T15:25:37.880

Reputation: 41

1

Welcome to PPCG! Nice first answer. 47 bytes

– Mr. Xcoder – 2017-12-20T20:54:30.757

1

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!

Steadybox

Posted 2017-12-20T15:25:37.880

Reputation: 15 798

1

Python 3, 51 bytes

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

Try it online!

Mr. Xcoder

Posted 2017-12-20T15:25:37.880

Reputation: 39 774

1

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 (*½).

Shaggy

Posted 2017-12-20T15:25:37.880

Reputation: 24 623

Save a byte with m* x*2 vUx. This makes me wonder if m* x*2 can be reduced further... – ETHproductions – 2017-12-21T18:05:40.700

Thanks, @ETHproductions; that's another new trick I've learned today. – Shaggy – 2017-12-21T18:11:04.157

I've got it, just use x* and check if it's divisible by Ux*½ :) – ETHproductions – 2017-12-21T18:11:04.633

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}) – ETHproductions – 2017-12-21T18:12:41.763

Oh, now, that's just ingenious, @ETHproductions. :) – Shaggy – 2017-12-21T18:17:53.030

1

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 ｢$_｣)
}

Brad Gilbert b2gills

Posted 2017-12-20T15:25:37.880

Reputation: 12 713

1

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

auhmaan

Posted 2017-12-20T15:25:37.880

Reputation: 906

0

APL (Dyalog), 15 bytes

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

Try it online!

Looks very ungolfy to me...

Erik the Outgolfer

Posted 2017-12-20T15:25:37.880

Reputation: 38 134

0

Haskell, 39 bytes

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

Try it online!

totallyhuman

Posted 2017-12-20T15:25:37.880

Reputation: 15 378

0

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!

ovs

Posted 2017-12-20T15:25:37.880

Reputation: 21 408

2No need for the space in 0 in. Also no need for the 0 in range(0,len(l)*2).. – Mr. Xcoder – 2017-12-20T16:30:03.117

0

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!

Mic1780

Posted 2017-12-20T15:25:37.880

Reputation: 121

1Unless I misunderstand this [https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/5330#5330] 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. – manassehkatz-Moving 2 Codidact – 2017-12-21T05:03:25.507

@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 – Mic1780 – 2017-12-21T15:49:41.237

0

Julia 0.6, 25 bytes

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

Try it online!

Dennis

Posted 2017-12-20T15:25:37.880

Reputation: 196 637

0

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!

Herman L

Posted 2017-12-20T15:25:37.880

Reputation: 3 611

0

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

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

Try it online!

Xcali

Posted 2017-12-20T15:25:37.880

Reputation: 7 671

Asked: 2017-12-20T15:25:37.880

Viewed: 1 664 times

Active: 2017-12-21T19:39:43.360