Bisakah daftar ini seimbang?

23

Untuk memeriksa apakah daftar bilangan bulat non-negatif seimbang , orang dapat membayangkan menempatkan bobot masing-masing di papan dan kemudian mencoba untuk menyeimbangkan papan pada pivot sehingga bobot relatif yang dirangkum kiri dan kanan pivot adalah sama. Berat relatif diberikan dengan mengalikan berat dengan jaraknya ke pivot (lihat hukum tuas ).

tuas wikipedia (Sumber: wikipedia )

Gambar ini sesuai dengan daftar [100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5]. Daftar ini seimbang karena 5memiliki jarak 20 ke pivot, 100jarak 1 dan 5*20 = 100 = 100*1.

Contohnya

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

Dalam hal ini pivot berada tepat di bawah 5, 3memiliki jarak 2 dan dan 1dan 7memiliki jarak 1. Jadi kedua sisi kiri dan kanan pivot dijumlahkan ke 7( 3*2 + 1*1di kiri dan 7*1di kanan) dan oleh karena itu daftarnya [3, 1, 5, 7]seimbang.

Namun, perhatikan bahwa pivot tidak harus ditempatkan di bawah salah satu elemen daftar, tetapi juga dapat ditempatkan di antara dua elemen daftar:

 6 3 1
#######
  ^

Dalam hal ini jarak menjadi 0.5, 1.5, 2.5, ...dan seterusnya. Daftar ini juga seimbang karena 6*0.5 = 3 = 3*0.5 + 1*1.5.

Pivot hanya dapat ditempatkan tepat di bawah satu angka atau tepat di tengah di antara dua angka, dan bukan misalnya di dua pertiga antara dua angka.

Tugas

Diberikan daftar bilangan bulat non-negatif dalam format wajar apa pun, output truthynilai jika daftar dapat diseimbangkan dan falsynilai sebaliknya.

Anda dapat mengasumsikan bahwa daftar input berisi setidaknya dua elemen dan setidaknya satu elemen adalah nol.

Ini adalah tantangan kode-golf , jadi jawabannya dengan jumlah byte paling sedikit di setiap bahasa akan menang.

Testcases Sejati

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

Testis Palsu

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

Banyak tantangan terkait di mana ditemukan saat tantangan ini berpasir : Apakah angka itu seimbang? , Indeks keseimbangan urutan , Saldo satu set bobot pada jungkat-jungkit , Kata-kata Penyeimbang , Akankah saya terbalik? dan Di mana poros itu berada?

code-golf array-manipulation decision-problem physics Laikoni
sumber
Bisakah pivot diletakkan sebelum angka pertama atau setelah angka terakhir?
Erik the Outgolfer
@EriktheOutgolfer Jika semua bobotnya tidak negatif, tidak.
Saya pikir ini mungkin sebuah penipuan. Atau apakah itu duduk di Sandbox sebentar?
Shaggy
terkait . (cc @Shaggy Mungkin ini yang Anda pikirkan)
Tn. Xcoder
2
@Giuseppe @Steadybox Saya menambahkanYou can assume that the input list contains at least two elements and that at least one element is non-zero.
Laikoni

Jawaban:

7

Pyth, 12 10 byte

!%ys*VQUQs

Cobalah online

Disimpan 2 byte berkat Tn. Xcoder dan Erik the Outgolfer.

Penjelasan

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

sumber
Anda dapat menggunakannya ysebagai pengganti*2
Tn. Xcoder
10 byte:!%ys*VQUQs
Erik the Outgolfer
4

Bahasa Wolfram (Mathematica) , 36 byte

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

Ini adalah pusat masalah massa dalam sistem koordinat dengan asal pada salah satu titik dan kemudian Anda menentukan apakah CM jatuh pada titik kisi di mana lebar kisi = 1/2.

Cobalah online!

Kelly Lowder
sumber
4

05AB1E , 6 byte

ƶO·IOÖ

Cobalah online!

Bagaimana?

ƶO · IOÖ ~ Program lengkap. I = input.

ƶ ~ Angkat I. Kalikan setiap elemen dengan indeks berbasis 1.
 O ~ Jumlah.
  · ~ Ganda. 
     Ö ~ Apakah kelipatan?
   IO ~ Jumlah I.
Tuan Xcoder
sumber
Tampaknya gagal [1,1](harus jujur). Tampaknya penggandaan implisit tidak benar-benar ada.
Zgarb
@Zgarb Fixed (?)
Mr. Xcoder
2

Jelly , 6 byte

×JSḤọS

Cobalah online!

Nah, sepertinya Leaky Nun menunjukkan hal yang tidak ada gunanya.

Menggunakan pendekatan Pyth Mnemonic.

Mengembalikan bilangan bulat positif (kebenaran) atau nol (salah).

Erik the Outgolfer
sumber
Apakah ini akan berhasil?
Leaky Nun
@ LeakyNun Tidak begitu yakin, itu sebabnya saya menggunakan LḶsebagai gantinya (meskipun itu akan berhasil untuk semua kasus uji). EDIT: Oooh, sekarang aku memikirkannya lagi, sepertinya begitu ... ( b | a ⇔ b | a + b duh)
Erik the Outgolfer
2

Japt , 10 byte

í* x*2 vUx

Cobalah online!

Penjelasan:

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

Pengembalian 1untuk kebenaran, 0untuk kepalsuan.

Oliver
sumber
2

Python 2 , 41 byte

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

Output adalah melalui kode keluar, jadi 0 benar dan 1 palsu.

Cobalah online!

Dennis
sumber
2

Julia , 31 27 byte

4 byte disimpan berkat @Dennis

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

Cobalah online!

Uriel
sumber
2

Ruby , 47 byte

Disimpan 2 byte berkat Tn. Xcoder

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

Cobalah online!

Tom Lazar
sumber
1
Selamat datang di PPCG! Jawaban pertama yang bagus. 47 bytes
Mr. Xcoder
1

C,  140  137 byte

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

Cobalah online!

Steadybox
sumber
1

Perl 6 , 23 byte

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

Menguji

Menggunakan algoritma dari berbagai entri lainnya.

Diperluas:

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

Japt, 11 10 8 byte

Awalnya terinspirasi oleh solusi Mnemonic

x* vUx*½

Cobalah

1 3 byte disimpan berkat ETHproductions.

Penjelasan

Input array secara implisit U. Kurangi dengan penambahan ( x), gandakan setiap elemen dengan indeks berbasis-0 ( *) dalam proses. Periksa apakah hasilnya dibagi rata ( v) dengan jumlah input asli ( Ux) dengan setiap elemen dikalikan 0,5 ( *½).

Shaggy
sumber
Simpan satu byte dengan m* x*2 vUx. Ini membuat saya bertanya-tanya apakah m* x*2dapat dikurangi lebih lanjut ...
ETHproduk
Terima kasih, @ETHproductions; itu trik baru yang saya pelajari hari ini.
Shaggy
Saya sudah mendapatkannya, cukup gunakan x*dan periksa apakah itu habis dibagi Ux*½:)
ETHproduk
Ya, saya tidak berpikir trik itu didokumentasikan di mana saja ... Tetapi setiap kali Anda menggunakan operator biner sebagai fungsi otomatis tanpa argumen kedua, ia menggunakan indeks secara default (seperti jika Anda melakukannya XY{X*Y})
ETHproduksi
Oh, sekarang, itu hanya cerdik, @ ETHproduksi. :)
Shaggy
1

C # , 71 byte

Golf

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

Tidak disatukan

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

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

    return 2 * S % s < 1;
};

Kode lengkap

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

Rilis

  • v1.0 - 71 bytes- Solusi awal.

Catatan

Saya mungkin memiliki, atau mungkin tidak, secara terang-terangan "meminjam" solusi Dennis Python 2 ...

auhmaan
sumber
0

APL (Dyalog) , 15 byte

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

Cobalah online!

Terlihat sangat ungolfy bagi saya ...

Erik the Outgolfer
sumber
0

Python 2 , 78 75 byte

terima kasih kepada Tn. Xcoder untuk -3 byte

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

Cobalah online!

ovs
sumber
2
Tidak perlu ruang dalam 0 in. Juga tidak perlu 0masuk range(0,len(l)*2)..
Tn. Xcoder
0

PHP , 139 128 byte

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

Cobalah online!

Mic1780
sumber
1
Kecuali aku salah paham [ini codegolf.meta.stackexchange.com/questions/2447/... Anda harus dapat menggunakan die(1)dan die(0)dan Hemat 4 byte dengan menggunakan kode keluar bukannya string dicetak.
manassehkatz-Reinstate Monica
@manassehkatz Jika Anda menggunakan die tanpa tanda kutip pada tio.run ia akan memperlakukannya sebagai kode status (yang seharusnya) dan tidak memasukkannya di bagian Output. Jadi saya baru saja menambahkan tanda kutip untuk mencegah orang melakukan nitpicking
Mic1780
0

Swift , 76 byte

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

Cobalah online!

Herman L.
sumber