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

(Вдохновение исходит от ЧР .)

Детали

• Треугольник может быть сформирован, если все перестановки трех сторон длины удовлетворяют строгому неравенству треугольника(Это означает, что a + b> c , a + c> b и b + c> a должны быть выполнены).$a,b,c$ $$a + b > c.$$ $a+b > c$$a+c>b$$b+c>a$
• Три длины сторон $a,b,c$ должны появляться в разных позициях в списке, но не обязательно должны быть попарно разными.
• Порядок трех чисел в списке ввода не имеет значения. Если мы рассмотрим список aи три числа a[i], a[j], a[k](где i,j,kони попарно различны), то (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])и т. Д. Все они рассматриваются как один и тот же треугольник.
• Предполагается, что входной список содержит не менее 3 записей.
• Можно предположить, что входной список отсортирован в порядке возрастания.

Примеры

Небольшая тестовая программа может быть найдена здесь на Попробуй онлайн!

Input, Output:
[1,2,3]  0
[1,1,1]  1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50

Для ввода [1,2,3,...,n-1,n]это A002623 .

Для ввода [1,1,...,1](длина n) это A000292 .

Для ввода первых nчисел Фибоначчи ( A000045 ) это A000004 .

R , 62 52 40 34 байт

sum(c(1,1,-1)%*%combn(scan(),3)>0)

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

Порт Луиса Мендо октавного решения

Поскольку a<=b<=cусловие треугольника эквивалентно a+b-c>0. Это a+b-cсжато захвачено матричным произведением [1,1,-1] * X, где X3-комбинации входного массива.

В комментариях было много предложений по улучшению, сделанных 3 разными людьми:

• Роберту С. за внушениеscan .

• Робину Райдеру за предложения по улучшению неравенства треугольника и этого странного, который требует, чтобы вход был в порядке убывания (который просто показывает, насколько важен гибкий формат ввода).

• и наконец Ник Кеннеди за следующее:

R , 40 байт

y=combn(scan(),3);sum(y[3,]<y[1,]+y[2,])

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

Stax , 8 7 байт

Спасибо за рекурсию за -1!

é═rê÷┐↨

Запустите и отладьте его на staxlang.xyz!

Распаковывается (8 байт) и пояснение:

r3SFE+<+
r           Reverse
 3S         All length-3 combinations
   F        For each combination:
    E         Explode: [5,4,3] -> 3 4 5, with 3 atop the stack
     +        Add the two shorter sides
      <       Long side is shorter? 0 or 1
       +      Add result to total

Это хитрый трюк. Если у вас есть последовательность инструкций, которая всегда будет приводить к 0 или 1, и вам нужно посчитать элементы из массива, которые дают достоверный результат в конце вашей программы, F..+это на байт меньше, чем {..f%.

Предполагается, что начальный список отсортирован по возрастанию. Без этого предположения вставьте oв начале 8 байтов.

Haskell , 49 байтов

([]%)
[c,b,a]%l|a+b>c=1
p%(h:l)=(h:p)%l+p%l
_%_=0

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

Рекурсивно генерирует все подпоследовательности l(обратные) и проверяет, какие из них длиной 3 образуют треугольники.

50 байтов

f l=sum[1|[a,b,c]<-filter(>0)<$>mapM(:[0])l,a+b>c]

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

Та же идея - генерировать подпоследовательности с mapMпомощью сопоставления каждого значения lлибо с самим собой (включить), либо 0(исключить).

50 байтов

([]%)
p%(b:t)=sum[1|c<-t,a<-p,a+b>c]+(b:p)%t
_%_=0

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

Пытается каждая точка разбиения взять средний элемент b.

51 байт

f(a:t)=f t+sum[1|b:r<-scanr(:)[]t,c<-r,a+b>c]
f _=0

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

Функция q=scanr(:)[]генерирует список суффиксов. Много проблем возникает из-за необходимости учитывать равные элементы нужное количество раз.

52 байта

q=scanr(:)[]
f l=sum[1|a:r<-q l,b:s<-q r,c<-s,a+b>c]

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

Вспомогательная функция q=scanr(:)[]генерирует список суффиксов.

57 байт

import Data.List
f l=sum[1|[a,b,c]<-subsequences l,a+b>c]

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

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

{⊇Ṫ.k+>~t}ᶜ

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

Возможно, я забыл воспользоваться отсортированным вводом в моем старом решении:

Брахилог , 18 17 15 байт

{⊇Ṫ¬{p.k+≤~t}}ᶜ

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

{            }ᶜ    The output is the number of ways in which
 ⊇                 a sublist of the input can be selected
  Ṫ                with three elements
   ¬{       }      such that it is not possible to show that
     p             for some permutation of the sublist
       k+          the sum of the first two elements
         ≤         is less than or equal to
      .   ~t}      the third element.

Perl 6 , 35 байт

+*.combinations(3).flat.grep(*+*>*)

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

объяснение

Это какой-то код, то есть краткая запись лямбда-функций (которая работает только в очень простых случаях). Каждый *является заполнителем для одного аргумента. Итак, мы берем список длин (который появляется в начале *), создаем все комбинации из 3 элементов (они всегда выходят в том же порядке, что и в исходном списке, что означает, что комбинации также сортируются), сглаживаем список, и затем возьмите список 3 на 3, и filter ( grep) только те триплеты, которые удовлетворяют *+*>*, то есть, что сумма первых двух аргументов больше, чем третий. Это дает все триплеты, и мы, наконец, посчитаем их с помощью числового контекста с помощью a +.

(Конечно, нам нужно проверить это только для случая «сумма двух меньших> самых больших». Если это так, то другой тривиально выполняется, если нет, триплет не обозначает правильные длины треугольника, и мы не надо смотреть дальше.)

Сетчатка , 55 байт

\d+
*
L$`_+
$<'
%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_
_

Попробуйте онлайн! Ссылка включает в себя тестовые случаи, но с значениями в 5-м случае уменьшены, чтобы позволить его завершить сегодня. Предполагает отсортированный ввод. Объяснение: Регулярные выражения на самом деле не любят сопоставлять более чем одно. Нормальное регулярное выражение сможет найти все значения, которые могут быть кратчайшим отрезком треугольника. Выбор Retina vздесь не помогает, за исключением того, чтобы избежать заглядывания. Однако wвариант Retina немного более полезен, так как он может найти как самую короткую, так и самую длинную ногу одновременно. Этого недостаточно для этой задачи, так как может быть несколько средних ног.

\d+
*

Преобразовать ввод в унарный.

L$`_+

Для каждого входного номера ...

$<'

... создайте строку, исходный массив которой будет обрезан, чтобы начать с этого числа. $'обычно означает строку после совпадения, но <модифицирует ее, чтобы обозначить строку после предыдущего разделителя, избегая траты 2 байтов на $&. Поэтому каждая строка представляет все потенциальные решения с использованием этого числа в качестве кратчайшего этапа.

%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_

Для каждой из этих линий найдите все возможные средние и самые длинные ноги, но убедитесь, что разница меньше, чем у первой ноги. Выведите a _для каждой соответствующей комбинации ног.

_

Подсчитайте общее количество найденных треугольников.

Python 3 , 73 байта

lambda l:sum(a+b>c for a,b,c in combinations(l,3))
from itertools import*

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

$(a,b,c)$$a+b>c$

Python 2 , 72 байта

f=lambda l,p=[]:l>[]and(p==p[:2]<[sum(p)]>l)+f(l[1:],p)+f(l[1:],p+l[:1])

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

73 байта

lambda l:sum(a+b>c for j,b in enumerate(l)for a in l[:j]for c in l[j+1:])

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

05AB1E , 12 10 9 байт

Мой первый раз с использованием 05AB1E! Спасибо Грими за -1!

3.Æʒ`α›}g

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

Прямой порт моего ответа Stax. Получить все комбинации из трех записей и подсчитать те, которые могут образовывать треугольники. Это та часть счета, которая действительно получила меня. Я трачу кучу байтов там. Там должно быть какая-то ошибка новичка.

3.Æʒ`α›}g
3.Æ          List of length-3 combinations
   ʒ   }g    Count truthy results under operation:
    `          Push the two shorter sides, then the long one
     α         Absolute difference (negated subtraction in this case)
      ›        Remaining short side is longer?

JavaScript (ES6), 63 байта

f=([v,...a],p=[])=>v?(!p[2]&p[0]+p[1]>v)+f(a,p)+f(a,[...p,v]):0

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

Октава / MATLAB, 33 байта

@(x)sum(nchoosek(x,3)*[1;1;-1]>0)

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

Zsh , 66 байт

for a;z=$y&&for b (${@:2+y++})for c (${@:3+z++})((t+=c<a+b))
<<<$t

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

Относительно просто, используя преимущества отсортированного ввода и увеличивая forзаголовок (увеличение происходит один раз за родительский цикл).

for a;{
  z=$y
  for b (${@:2+y++});{   # subarray starting at element after $a
    for c (${@:3+z++})   # subarray starting at element after $b
      ((t+=c<a+b))
  }
}

Excel VBA, 171 164 152 байта

^{-26 байт благодаря TaylorScott}

Sub z
t=[A:A]
u=UBound(t)
For i=1To u-2
For j=i+1To u-1
For k=j+1To u
a=t(i,1):b=t(j,1):c=t(k,1)
r=r-(a+b>c)*(b+c>a)*(c+a>b)
Next k,j,i
Debug.?r
End Sub

Вход находится в диапазоне A:Aактивного листа. Вывод в ближайшее окно.

Так как он рассматривает каждую комбинацию каждой ячейки в столбце высотой 2 ²⁰ ячеек (что составляет почти 2 ⁶⁰ комбинаций), этот код ... не быстрый. Вы можете сделать это намного быстрее, но за счет байтов.

Древесный уголь , 17 байт

ＩΣ⭆θ⭆…θκ⭆…θμ›⁺νλι

Попробуйте онлайн! Ссылка на подробную версию кода. Предполагает отсортированный ввод. Объяснение:

   θ                Input array
  ⭆                 Map over elements and join
      θ             Input array
     …              Truncated to length
       κ            Outer index
    ⭆               Map over elements and join
          θ         Input array
         …          Truncated to length
           μ        Inner index
        ⭆           Map over elements and join
              ν     Innermost value
             ⁺      Plus
               λ    Inner value
            ›       Is greater than
                ι   Outer value
 Σ                  Take the digital sum
Ｉ                   Cast to string for implicit print

Japt -x , 9 байт

à3 ËÌÑ<Dx

Попытайся

à3 ®o <Zx

Попытайся

Wolfram Language (Mathematica) , 37 35 байт

Tr@Boole[2#3<+##&@@@#~Subsets~{3}]&

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

Рубин , 41 байт

->l{l.combination(3).count{|a,b,c|c<a+b}}

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

Pyth , 14 байт

*1sm>sPded.cQ3

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

          .cQ3  # All combinations of length 3 from Q (input), sorted in ascending order
   m            # map over that lambda d:
     sPd        #   sum(d[:-1])
    >   ed      #     > d[-1]
  s             # sum all of those (uses the fact that True = 1)
*1              # multiply by 1 so it doesn't output True if there's only one triangle

Альтернатива (также 14 байтов):

lfTm>sPded.cQ3

Perl 5 ( -p), 55 52 байта

с помощью обратного отслеживания регулярных выражений, -3 байта благодаря использованию кряка @Cows ^вместо (?!)сбоя и возврата.

$d='(\d++)';$_=/$d.* $d.* $d(?{$n++if$1+$2>$3})^/+$n

или

$_=/(\d++).* (\d++).* (\d++)(?{$n++if$1+$2>$3})^/+$n

TIO

Желе , 9 байт

œc3+>ƭ/€S

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

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

объяснение

œc3       | Combinations of length 3
     ƭ/€  | Reduce each using each of the following in turn:
   +      | - Add
    >     | - Greater than
        S | Sum (counts the 1s)

Альтернатива 9:

œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S

J , 40 байт

1#.](+/*/@(->])])@#~2(#~3=1&#.)@#:@i.@^#

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

Баш , 123 байта

for a;do for((i=2;i<=$#;i++)){ b=${!i};for((j=$[i+1];j<=$#;j++)){ c=${!j};T=$[T+(a<b+c&b<a+c&c<a+b)];};};shift;done;echo $T

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

Весёлый.

SNOBOL4 (CSNOBOL4) , 181 байт

	S =TABLE()
R	X =X + 1
	S<X> =INPUT	:S(R)
I	I =J =K =I + 1	LT(I,X)	:F(O)
J	J =K =J + 1	LT(J,X)	:F(I)
K	K =K + 1	LT(K,X - 1)	:F(J)
	T =T + 1 GT(S<I> + S<J>,S<K>)	:(K)
O	OUTPUT =T
END

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

$O(n^3)$00

C (лязг) , 83 байта

x,y,q;f(*a,z){for(x=y=q=0;z;q+=z>1&a[x-=x?1:2-y--]+a[y]>a[z])y=y>1?y:--z;return q;}

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

Сохранено 1 благодаря @ceilingcat