Напишите программу или функцию, которая принимает непустой список натуральных чисел. Вы можете предположить, что это ввод в разумном удобном формате, таком как "1 2 3 4"или [1, 2, 3, 4].

Числа в списке ввода представляют срезы полной круговой диаграммы, где каждый размер среза пропорционален соответствующему номеру, а все срезы расположены вокруг диаграммы в указанном порядке.

Например, пирог для 1 2 3 4это:

Вопрос, на который должен ответить ваш код: является ли круговая диаграмма пополам ? То есть существует ли когда-нибудь идеально прямая линия от одной стороны круга к другой, симметрично разделив ее на две части?

Вам нужно вывести истинное значение, если есть хотя бы один биссектрису, и вывести ложное значение, если их нет .

В 1 2 3 4примере есть бисекция между 4 1и 2 3поэтому выходом будет truthy.

Но для ввода 1 2 3 4 5нет биссектрисы, поэтому результат будет ложным:

Дополнительные примеры

Расположение чисел по-разному может удалить биссектрисы.
например 2 1 3 4→ ложь:

Если во входном списке только одно число, круг не разделен пополам.
например 10→ ложь:

Там может быть несколько биссектрисы. Пока их больше нуля, вывод правдив.
например, 6 6 12 12 12 11 1 12→ правдивый: (здесь есть 3 биссектрисы)

Бисекции могут существовать, даже если они не являются визуально очевидными.
например 1000000 1000001→ ложь:

например, 1000000 1000001 1→ правдиво:

(Спасибо nces.ed.gov за создание круговых диаграмм.)

Тестовые случаи

Truthy
1 2 3 4
6 6 12 12 12 11 1 12
1000000 1000001 1
1 2 3
1 1
42 42
1 17 9 13 2 7 3
3 1 2
10 20 10

Falsy
1 2 3 4 5
2 1 3 4
10
1000000 1000001
1
1 2
3 1 1
1 2 1 2 1 2
10 20 10 1

счет

Самый короткий код в байтах побеждает. Tiebreaker - более ранний ответ.

J, 18 байт

5 байтов благодаря Денису.

+/e.[:,/2*+/\-/+/\

@HelkaHomba : Нет.

использование

>> f =: +/e.[:,/2*+/\-/+/\
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic  =: +/\-/+/\
doubled_bm   =: 2 * black_magic
flatten      =: ,/
sum          =: +/
is_member_of =: e.
f =: sum is_member_of monadic flatten doubled_bm

Предыдущая 23-байтовая версия:

[:+/[:+/+/=+:@-/~@(+/\)

использование

>> f =: [:+/[:+/+/=+:@-/~@(+/\)
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic =: -/~@(+/\)
double      =: +:
equals      =: =
sum         =: +/
monadic     =: [:
of          =: @
f =: monadic sum monadic sum (sum equals double of black_magic)

объяснение

Сумма всех подстрок рассчитывается по black_magic. +/\Вычисления частичных сумм.

Например, a b c dстановится a a+b a+b+c a+b+c+d.

-/~Затем создает таблицу вычитания , основанный на входе, так что x y zстановится:

x-x x-y x-z
y-x y-y y-z
z-x z-y z-z

Применительно к a a+b a+b+c a+b+c+dрезультат будет:

    0  -b -b-c -b-c-d
    b   0   -c   -c-d
  b+c   c    0     -d
b+c+d c+d    d      0

Это вычислило суммы всех подстрок, которые не содержат a.

Это гарантирует, что этого будет достаточно, так как, если один бисек содержит a, другой бисек не будет содержать, aа также не будет обернуть вокруг.

Желе , 9 8 байт

Ḥ+\©_Sf®

Вернуть непустой список (правда) или пустой список (ложь). Попробуйте онлайн! или проверьте все контрольные примеры .

Как это работает

Ḥ+\©_Sf®  Main link. Argument: A (list)

Ḥ         Double all integers in A.
 +\       Take the cumulative sum of 2A.
   ©      Copy; store the result in the register.
    _S    Subtract the sum of A from each partial sum of 2A.
      f®  Filter; intersect this list with the list in the register.

Юлия, 34 30 29 байт

!x=sum(x)∈cumsum!(x,2x).-x'

Спасибо @GlenO за отыгрывание 1 байта!

Попробуйте онлайн!

Как это работает

После сохранения накопленной суммы 2x в x мы вычитаем вектор строки x ' из вектора столбца x , получая матрицу всех возможных различий. По сути, это вычисляет суммы всех смежных подмассивов x, которые не содержат первое значение, их негативы и 0 в диагонали.

Наконец, мы проверяем, принадлежит ли сумма исходного массива x к сгенерированной матрице. Если это так, то сумма, по крайней мере, одного из соседних подсписков равна ровно половине суммы всего списка, что означает, что есть, по крайней мере, один биссектрис.

Python 2, 64 байта

f=lambda l,s=0:l>[]and(sum(l)==s)|f(l[1:],s+l[0])|f(l,s+l.pop())

Рекурсивно пытается удалить элементы с начала или до конца, пока сумма того, что остается, равна сумме того, что было удалено, и сохранено s . Занимает экспоненциальное время в длине списка.

Деннис сохранил 3 байта с pop.

Haskell, 41 байт

f l=elem(sum l/2)$scanr(:)[]l>>=scanl(+)0

Идея состоит в том, чтобы проверить, существует ли подсписок, lчья сумма равна sum l/2. Мы генерируем суммы этих подсписков как scanr(:)[]l>>=scanl(+)0. Давайте посмотрим, как это работает сl=[1,2,3]

>> scanr(:)[]l
[[1,2,3],[2,3],[3],[]] 
-- the suffixes of l

>> scanl(+)0 [2,3,4]
[0,2,5,9]
-- the cumulative sums of the input

>> scanr(:)[]l>>=scanl(+)0
[0,1,3,6,0,2,5,0,3,0]
-- the cumulative sums of the suffixes of l, flattened to a single list

Старые 43 байта:

f l|c<-scanl1(+)l=elem(sum l/2)$(-)<$>c<*>c

Формирует список cкумулятивных сумм. Затем проверяет, отличаются ли любые две из этих сумм sum l/2, проверяя, является ли это элементом списка различий (-)<$>c<*>c.

Pyth, 10 9 байтов

}sQmysd.:

Проверьте это в компиляторе Pyth .

Как это работает

       .:  Generate the list of all adjacent sublists.
   m       Map over the result:
     sd       Add the integers of the sublist.
    y         Double the sum.
 sQ        Compute the sum of the input.
}          Check if it belongs to the list of doubled sublist sums.

На самом деле, 21 байт

;Σ@2*;lR@τ╗`╜V♂Σi`Míu

Попробуйте онлайн!

Эта программа распечатывает 0для ложных случаев и положительное целое для истинных случаев.

Объяснение:

;Σ@2*;lR@τ╗`╜V♂Σi`Míu
;Σ                     sum of copy of input
  @2*                  double values in other copy
     ;lR               copy, range(1, len(input)+1)
        @τ             append other copy to itself
          ╗            save in reg0
           `╜V♂Σi`M    map: generate cyclic cumulative sums
                   íu  1-based index of sum of input (0 if not found)

Неконкурентная версия, 10 байт

;Σ@2*σ;)-∩

Попробуйте онлайн!

Эта программа выводит пустой список для ложных случаев и непустой список в противном случае. Это по сути порт Дениса Желе ответ . Это не конкурирует, потому что накопленная сумма и векторизованная разность функционируют позже проблемы.

Объяснение:

;Σ@2*σ;)-∩
;Σ          sum of copy of input
  @2*       multiply values in other copy by 2
     σ;     two copies of cumulative sum
       )-   subtract sum of input from each element in one copy
         ∩  set intersection with other copy

Python 2, 76 74 70 66 байт

def f(x):n=sum(x);print n in[2*sum(x[k/n:k%n])for k in range(n*n)]

Спасибо @xnor за 4 8 байтов!

Проверьте это на Ideone . (большие тестовые случаи исключены)

MATL , 10 байт

EYst!-Gs=z

На выходе получается количество биссектрис.

Попробуйте онлайн!

объяснение

Тот же подход, что и у Дениса Джулии .

E       % Implicit input. Multiply by 2 element-wise 
Ys      % Cumulative sum 
t!-     % Compute all pairwise differences. Gives a 2D array 
Gs      % Sum of input 
=       % Test for equality, element-wise 
z       % Number of nonzero elements. Implicit display 

Рубин, 60 53 байта

->a{a.any?{r=eval a*?+;a.rotate!.any?{|i|0==r-=2*i}}}

Создает все возможные разбиения, беря каждый оборот входного массива, а затем беря все срезы длиной 1 .. n, где nразмер входного массива. Затем проверяет, существует ли какой-либо раздел с суммой, равной половине общей суммы входного массива.

JavaScript (ES6), 83 байта

a=>a.map(_=>a.slice(--n).map(m=>s.push(t+=m),t=0),s=[],n=a.length)&&s.includes(t/2)

Генерирует все возможные суммы, затем проверяет, появляется ли половина последней суммы (которая является суммой всего списка) в списке. (Генерация сумм в несколько неудобном порядке, чтобы определить сумму, которую я должен был сделать в последний раз, экономит 4 байта.)

Дьялог АПЛ, 12 байт

+/∊2×+\∘.-+\

Проверьте это с TryAPL .

Как это работает

+/∊2×+\∘.-+\  Monadic function train. Right argument: y (vector)

     +\   +\  Yield the cumulative sum of y.
       ∘.-    Compute all differences of all partial sums.
              This computes the sums of all adjacent subvectors of y that do not
              contain the first value, their negatives, and 0's in the diagonal.
   2×         Multiply all differences by 2.
+/            Yield the sum of y.
  ∊           Test for membership.

Python 2 , 47 байт

k=t=1
for x in input():t<<=x;k|=t*t
print k&k/t

Попробуйте онлайн!

Я вернулся через 2,75 года, чтобы победить мое старое решение более чем на 25%, используя новый метод.

Эта 1-байтовая более длинная версия немного понятнее.

k=t=0
for x in input():t+=x;k|=4**t
print k&k>>t

Попробуйте онлайн!

Идея состоит в том, чтобы сохранить набор накопленных сумм в tвиде битов k, установив бит, 2*tчтобы указать, что tэто накопительная сумма. Затем мы проверяем, отличаются ли какие-либо две кумулятивные суммы на половину суммы списка (окончательной t), сдвигая биты kтак сильно и выполняя битовую обработку &с оригиналом, чтобы увидеть результат, отличный от нуля (истинный).

APL, 25 символов

Предполагая, что список дан в X ← 1 2 3 4.

(+/X)∊∘.{2×+/⍺↑⍵↓X,X}⍨⍳⍴X←⎕

Объяснение:

Сначала обратите внимание, что APL оценивает форму справа налево. Затем:

• X←⎕ принимает пользовательский ввод и сохраняет его в X

• ⍴X дает длину X

• ⍳⍴X цифры от 1 до ⍴X

• ⍺И ⍵в {2×+/⍺↑⍵↓X,X}левый и правый аргумент диадического функции мы определяем в фигурных скобках.

  • Теперь о ⍺↑⍵↓X,Xчасти: X,Xпросто соединяем X с собой; ↑и ↓взять и бросить.
  • +/уменьшает / сгибает +список справа

  Итак 2 {2×+/⍺↑⍵↓X,X} 1= 2×+/2↑1↓X,X= 2×+/2↑1↓1 2 3 4 1 2 3 4=

  = 2×+/2↑2 3 4 1 2 3 4= 2×+/2 3= 2×5= 10.

• ∘.brace⍨idxэто просто idx ∘.brace idx. ( ⍨это диагональная карта;∘. является внешним произведением)

  Таким образом , это дает нам ⍴Xна ⍴Xматрицу , которая содержит в два раза больше суммы всех подключенных подсписков.

   4  6  8  2
  10 14 10  6
  18 16 14 12
  20 20 20 20
  

  Последнее, что нам нужно сделать, это проверить, находится ли сумма Xгде-то внутри этой матрицы.

• Который мы делаем с (+/X)∊matrix.

Брахилог , 6 байт

sj+~+?

Попробуйте онлайн!

Выводится через успех или неудачу, печать true.или false.запуск в качестве программы.

s         A contiguous sublist of the input
 j        with all of its items duplicated
  +       sums to
   ~+     the sum of the elements of
     ?    the input.

C 161 145 129 байт

• сэкономили несколько байтов благодаря @LeakyNun
• сэкономил несколько байтов благодаря @ceilingcat

i;j;k;t;r;s;f(x,n)int*x;{for(t=i=k=r=0;i<n;)t+=x[i++];for(;++k<n;i=n)for(;i--;r|=2*s==t)for(s=0,j=i;j<i+k;)s+=x[j++%n];return r;}

Ungolfed попробуйте онлайн

int f(int*x,int n)
{
    int t=0;

    for(int i=0;i<n;i++)
    {
        t += x[i];
    }

    for(int k=1;k<n;k++) // subset-size
    {
        for(int i=0,s;i<n;i++) // where to start
        {
            s=0;

            for(int j=i;j<i+k;j++) // sum the subset
            {
                s+=x[j%n];
            }

            if(2*s==t) return 1; // TRUE
        }
    }

    return 0; // FALSE
}

Haskell, 68 байт

f l|x<-[0..length l]=any(sum l==)[2*(sum$take a$drop b l)|a<-x,b<-x]

Функция fсначала создает список сумм всех возможных срезов данного списка. Затем он сравнивается с общей суммой элементов списка. Если мы получим в какой-то момент половину общей суммы, то мы знаем, что у нас есть пополам. Я также использую тот факт, что если вы takeили dropбольше элементов, чем есть в списке, Haskell не выдает ошибку.

Mathematica, 48 байтов

!FreeQ[Outer[Plus,#,-#],Last@#/2]&@Accumulate@#&

Анонимная функция, похожая в действии на многочисленные другие ответы.

Outer[Plus, #, -#]при действии Accumulate@#(которое, в свою очередь, воздействует на входной список, давая список последовательных итогов) генерирует по существу ту же таблицу, что и в нижней части ответа Лаки Нун.

!FreeQ[..., Last@#/2] проверяет, если (Last@#)/2 является не отсутствуют в результирующей таблице, и Last@#является последним из последовательных сумм, то есть сумма всех элементов списка ввода.

Если этот ответ несколько интересен, то это не из-за нового алгоритма, а скорее о хитростях, характерных для Mathematica; Например, !FreeQэто хорошо, по сравнению с тем MemberQ, что он не требует уплощения проверяемой таблицы и сохраняет байт.

APL (NARS), символы 95, байты 190

{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}

Рассмотрим один массив ввода из 4 элементов: 1 2 3 4. Как мы можем выбрать полезный для этого упражнения раздел этого набора? После того, как некоторые считают, что разделение этих четырех элементов, которые мы можем использовать, описывается двоичным числом слева:

0001,0010,0100,1000 2^(0..4) 1 2 4  8 
0011,0110,1100,                3 6 12
0111,1110,                       7 14
1111                               15

(1001 или 1011 ecc может быть в этом наборе, но у нас уже есть 0110 и 0100 ecc), поэтому одна шляпа просто написать одну функцию, которая из числа элементов входного массива строит эти двоичные числа ... это будет:

c←{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}

что из ввода 1 2 4 8 [2 ^ 0..lenBytesArgument-1] найдите 3 6 12, 7 14, 15; поэтому найдите двоичные числа из этих чисел и, используя их, найдите правильные разделы входного массива ... Я протестировал функцию c только для этих входных 4 элементов, но, похоже, это нормально для другого числа элементов ...

тест:

  f←{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}
  f¨(1 2 3 4)(6 6 12 12 12 11 1 12)(1000000 1000001 1)(1 2 3)(1 1)(42 42)
1 1 1 1 1 1 
  f¨(1 2 3 4 5)(2 1 3 4)(,10)(1000000 1000001)(,1)(1 2)(3 1 1)
0 0 0 0 0 0 0