Kann diese Liste ausgeglichen werden?

23

Um zu überprüfen, ob eine Liste nicht negativer Ganzzahlen ausgeglichen ist , kann man sich vorstellen, die entsprechenden Gewichte auf eine Tafel zu setzen und dann zu versuchen, die Tafel auf einem Pivot so auszugleichen, dass die zusammengefassten relativen Gewichte links und rechts vom Pivot gleich sind. Das relative Gewicht ergibt sich durch Multiplikation des Gewichts mit dem Abstand zum Drehpunkt (siehe Gesetz des Hebels ).

Wikipedia-Hebel (Quelle: Wikipedia )

Dieses Bild entspricht einer Liste [100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]. Diese Liste ist ausgeglichen, da die 5einen Abstand von 20 zum Drehpunkt hat, die 100einen Abstand von 1 und 5*20 = 100 = 100*1.

Beispiele

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

In diesem Fall befindet sich der Pivot direkt unter dem 5, der 3Abstand 2 hat und der 1und 7Abstand 1. Also addieren sich beide Seiten links und rechts des Pivots 7( 3*2 + 1*1links und 7*1rechts) und daher ist die Liste [3, 1, 5, 7]ausgeglichen.

Beachten Sie jedoch, dass der Pivot nicht unter einem der Listenelemente platziert werden muss, sondern auch zwischen zwei Listenelementen platziert werden kann:

 6 3 1
#######
  ^

In diesem Fall werden die Entfernungen 0.5, 1.5, 2.5, ...und so weiter. Diese Liste ist auch deshalb ausgewogen 6*0.5 = 3 = 3*0.5 + 1*1.5.

Der Drehpunkt kann nur genau unter einer Zahl oder genau in der Mitte zwischen zwei Zahlen platziert werden und nicht z. B. bei zwei Dritteln zwischen zwei Zahlen.

Aufgabe

Wenn Sie eine Liste nicht negativer Ganzzahlen in einem angemessenen Format haben, geben Sie einen truthyWert aus, wenn die Liste ausgeglichen werden kann, und einen anderen falsyWert.

Sie können davon ausgehen, dass die Eingabeliste mindestens zwei Elemente enthält und mindestens ein Element ungleich Null ist.

Dies ist eine Code-Golf- Herausforderung, daher gewinnt die Antwort mit der geringsten Anzahl von Bytes in jeder Sprache.

Wahrheits-Testfälle

[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]

Viele verwandte Herausforderungen wurden gefunden, während diese Herausforderung im Sandkasten lag : Ist es eine ausgeglichene Zahl? , Equilibrium Index einer Sequenz , Gleichgewicht ein Satz von Gewichten auf einer Wippe , Wörter Balancing , Will ich umkippen? und wohin gehört der Pivot?

code-golf array-manipulation decision-problem physics Laikoni
quelle
Kann der Pivot vor der ersten Nummer oder nach der letzten Nummer platziert werden?
Erik the Outgolfer
@EriktheOutgolfer Wenn alle Gewichte nicht negativ sind, nein.
Ich denke, das könnte ein Betrug sein. Oder saß es eine Weile im Sandkasten?
Shaggy
verwandt . (cc @Shaggy Vielleicht haben Sie darüber nachgedacht)
Mr. Xcoder
2
@ Giuseppe @ Steadybox Ich fügte hinzuYou can assume that the input list contains at least two elements and that at least one element is non-zero.
Laikoni

Antworten:

7

Pyth, 12 10 Bytes

!%ys*VQUQs

Probieren Sie es online aus

2 Bytes gespart dank Mr. Xcoder und Erik the Outgolfer.

Erläuterung

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

quelle
Sie können yanstelle von*2
Mr. Xcoder
10 Bytes:!%ys*VQUQs
Erik der Outgolfer
4

Wolfram Language (Mathematica) , 36 Byte

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

Dies ist ein Massenschwerpunktproblem in einem Koordinatensystem mit dem Ursprung an einem der Punkte, und Sie bestimmen dann, ob der CM auf einen Gitterpunkt fällt, bei dem die Gitterbreite = 1/2 ist.

Probieren Sie es online!

Kelly Lowder
quelle
4

05AB1E , 6 Bytes

ƶO·IOÖ

Probieren Sie es online!

Wie?

ƶO · IOÖ ~ Volles Programm. I = Eingabe.

ƶ ~ Lift I. Multiplizieren Sie jedes Element mit seinem 1-basierten Index.
 O ~ Sum.
  · ~ Double. 
     Ö ~ Ist ein Vielfaches von?
   IO ~ Die Summe von I.
Mr. Xcoder
quelle
Scheint zu scheitern [1,1](sollte wahr sein). Es scheint, dass die implizite Verdopplung nicht wirklich vorhanden ist.
Zgarb
@ Zgarb Fixed (?)
Mr. Xcoder
2

Gelee , 6 Bytes

×JSḤọS

Probieren Sie es online!

Sieht so aus, als hätte Leaky Nun auf das Sinnlose hingewiesen.

Verwendung des Pyth-Ansatzes von Mnemonic.

Gibt eine positive Ganzzahl (wahr) oder Null (falsch) zurück.

Erik der Outgolfer
quelle
Würde das funktionieren?
Undichte Nonne
@LeakyNun Nicht so sicher, deshalb habe ich LḶstattdessen verwendet (obwohl es für alle Testfälle gelingen würde ). EDIT: Oh, jetzt, wo ich wieder darüber nachdenke, scheint es so ... ( b | a | b | a + b duh)
Erik der Outgolfer 20.12.17
2

Japt , 10 Bytes

í* x*2 vUx

Probieren Sie es online!

Erläuterung:

 í* 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

1Kehrt zurück für Wahres, 0für Falsches.

Oliver
quelle
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;}

Probieren Sie es online!

Steadybox
quelle
1

Perl 6 , 23 Bytes

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

Probier es aus

Verwendet den Algorithmus aus verschiedenen anderen Einträgen.

Erweitert:

{  # 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
quelle
1

Japt, 11 10 8 Bytes

Ursprünglich inspiriert von der Lösung von Mnemonic

x* vUx*½

Versuch es

1 3 Bytes gespart dank ETHproductions.

Erläuterung

Implizite Eingabe eines Arrays U. Reduzieren Sie durch Addition ( x) und multiplizieren Sie dabei jedes Element mit seinem auf 0 basierenden Index ( *). Überprüfen Sie, ob das Ergebnis gleichmäßig vdurch die Summe der ursprünglichen Eingabe ( Ux) teilbar ist ( ), wobei jedes Element mit 0,5 ( *½) multipliziert wird .

Zottelig
quelle
Speichern Sie ein Byte mit m* x*2 vUx. Ich frage mich daher, ob m* x*2es noch weiter reduziert werden kann ...
ETHproductions
Vielen Dank, @ETHproductions; Das ist ein weiterer neuer Trick, den ich heute gelernt habe.
Shaggy
Ich habe es, benutze es x*und überprüfe, ob es durch Ux*½:) teilbar ist
ETHproductions
Ja, ich glaube nicht, dass dieser Trick irgendwo dokumentiert ist ... Aber wenn Sie einen binären Operator als Auto-Funktion ohne zweites Argument verwenden, wird standardmäßig der Index verwendet (wie wenn Sie es getan hätten XY{X*Y})
ETHproductions
Oh, das ist einfach genial, @ETHproductions. :)
Shaggy
1

C # , 71 Bytes

Golf gespielt

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;
};

Vollständiger 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- Anfangslösung.

Anmerkungen

Möglicherweise habe ich mir die Dennis Python 2-Lösung "ausgeliehen" oder nicht ...

auhmaan
quelle
0

Python 2 , 78 75 Bytes

danke an herr xcoder für -3 bytes

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

Probieren Sie es online!

ovs
quelle
2
Keine Notwendigkeit für den Raum in 0 in. Auch keine Notwendigkeit für die 0in range(0,len(l)*2)..
Mr. Xcoder
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);}?>

Probieren Sie es online!

Mic1780
quelle
1
Sofern ich dies nicht falsch verstehe [ codegolf.meta.stackexchange.com/questions/2447/… , sollten Sie in der Lage sein, 4 Bytes zu verwenden die(1)und zu die(0)speichern, indem Sie den Exit-Code anstelle einer gedruckten Zeichenfolge verwenden.
Manassehkatz-Reinstate Monica
@manassehkatz Wenn Sie bei tio.run die ohne Anführungszeichen verwenden, wird sie als Statuscode behandelt (was auch immer der Fall sein sollte) und nicht in den Bereich "Ausgabe" gestellt. Also habe ich nur Anführungszeichen hinzugefügt, um zu verhindern, dass Leute mitspielen
Mic1780
0

Schnell , 76 Bytes

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

Probieren Sie es online!

Herman L
quelle