Был ли мой пирог пополам?

43

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

1 2 3 4 5 пример

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

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

2 1 3 4 пример

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

10 пример

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

6 6 12 12 12 11 1 12 пример

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

1000000 1000001 пример

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

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 - более ранний ответ.

Кальвин Хобби
источник
30
Я полагаю, вы имеете в виду пирог секто?
Алекс А.
@HelkaHomba, можете ли вы переставить секторы, чтобы он заработал, и это то, что вы имели в виду, когда «расположение чисел по-разному может удалить биссектрисы»?
Соломон Уко
@SolomonUcko Вы не можете переставлять сектора.
Увлечения Кэлвина
1
Только [2 1 3 4] из ложных случаев должны быть действительно оценены. Другие ложные случаи легко отклоняются, потому что их сумма нечетна (или их длина <2).
Бенни Джобиган

Ответы:

12

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а также не будет обернуть вокруг.

Дрянная Монахиня
источник
3
После некоторой реструктуризации вы можете получить 13 байтов:+/e.&,2*+/\\.
Zgarb
10

Желе , 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.
Деннис
источник
7

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

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

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

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

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

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

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

Деннис
источник
15
Давайте посмотрим, как Деннис дает 5 ответов, прежде чем кто-то другой даст один.
Увлечения Кэлвина
6

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.

XNOR
источник
Странная альтернатива, которая дает списки:f=lambda l,s=0:l and(sum(l)==s)*l+f(l[1:],s+l[0])+f(l,s+l.pop())
xnor
5

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.

XNOR
источник
4

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.
Деннис
источник
4

На самом деле, 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
Мего
источник
4

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 . (большие тестовые случаи исключены)

Деннис
источник
Я понял, что вы можете сделать, n=sum(x)чтобы сделать n in ...; не больно использовать большее значение для n.
xnor
Ох, это умно. Спасибо!
Деннис
3

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 
Луис Мендо
источник
3

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

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

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

Ventero
источник
2

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 байта.)

Нил
источник
2

Дьялог АПЛ, 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.
Деннис
источник
2

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так сильно и выполняя битовую обработку &с оригиналом, чтобы увидеть результат, отличный от нуля (истинный).

XNOR
источник
1

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.
user2070206
источник
1

Брахилог , 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.
Несвязанная строка
источник
1

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
}
Khaled.K
источник
Возможно, вы можете сохранить несколько байтов, переместив объявления переменных на первый уровень и изменив i<n;i++на i++<n(хотя вам, возможно, придется иметь дело с некоторыми смещениями.
Leaky Nun
0

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 не выдает ошибку.

flawr
источник
0

Mathematica, 48 байтов

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

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

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

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

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

LLlAMnYP
источник
Я думаю, что !FreeQ[2Tr/@Subsequences@#,Tr@#]&должно работать, но у меня не будет 10.4 для тестирования в течение следующих 10 дней или около того.
Мартин Эндер
@MartinEnder Конечно, похоже, что это сработает, но я на 10.2, так что вот что у меня есть
LLlAMnYP
0

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 
RosLuP
источник