Считайте последние истины

59

Вдохновленный и в память о моем дорогом друге и коллеге,

Дэн Баронет

Дэн Баронет , 1956 - 2016 гг. RIP

Он нашел кратчайшее возможное решение APL для этой задачи:

задача

Если задан логический список, подсчитайте количество конечных значений истинности.

Примеры случаев

{}0

{0}0

{1}1

{0, 1, 1, 0, 0}0

{1, 1, 1, 0, 1}1

{1, 1, 0, 1, 1}2

{0, 0, 1, 1, 1}3

{1, 1, 1, 1, 1, 1}6

Адам
источник
Можем ли мы принять список как строку нулей и единиц? например 01100?
Аднан
@Adnan, только если для вашего языка это самый обычный способ представления логических списков.
Адам
71
Сожалею о вашей потере.
Мартин Эндер
6
@MartinEnder Спасибо. Будет тяжело идти вперед. Дэн научил меня всему, что мне нужно было знать, чтобы работать на Дьялога.
Адам
5
Прощай, Дэн. RIP ...
Эрик Outgolfer

Ответы:

36

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

⊥⍨

Проверьте это на TryAPL .

Как это устроено

(uptack, dyadic: decode) выполняет базовое преобразование. Если левый операнд является вектором, он выполняет смешанное базовое преобразование, что идеально подходит для этой задачи.

Для базового вектора b = b n , ⋯, b 0 и цифрового вектора a = a n , ⋯, a 0 , b ⊥ a преобразует a в смешанную базу b , т. Е. Вычисляет b 0 ⋯ b n-1 a n + ⋯ + b 0 b 1 a 2 + b 0 a 1 + a 0 .

Теперь (тильда dieresis , commute ) изменяет оператор влево следующим образом. В монадическом контексте он вызывает оператор с равными левым и правым аргументами.

Например, ⊥⍨ a определяется как a ⊥ a , который вычисляет a 0 ⋯ a n + ⋯ + a 0 a 1 a 2 + a 0 a 1 + a 0 , сумму всех накопленных произведений справа налево ,

Для K завершающих единиц, то к крайнему правым продукты 1 , а все остальные являются 0 , поэтому их сумма равна K .

Деннис
источник
14
Подсказка: Дэн сделал это всего за два байта.
Адам
3
Смешанная базовая конверсия! Это умно.
Деннис
1
Ой. Смешанная базовая конверсия, как это ударить снова.
Конор О'Брайен
Браво! На самом деле, из-за Дэна мы работаем в особом режиме b⊥bи ⊥⍨bотказываемся от бесконечного ускорения.
Адам
19

JavaScript (ES6), 21 байт

f=l=>l.pop()?f(l)+1:0

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

Arnauld
источник
Как это работает? Как f(l)+1вернуть значение > 2?
Оливер
@Oliver Это рекурсивный процесс, оцениваемый как l.pop()?(l.pop()?(l.pop()?(...etc...)+1:0)+1:0)+1:0.
Арно
Понимаю. Спасибо за объяснение.
Оливер
11

Желе , 4 байта

ŒrṪP

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

Для случая, когда список пуст, есть несколько любопытных наблюдений. Во-первых, длина строки, кодирующая пустой список, []возвращает другой пустой список []. Затем извлечение последнего элемента из этого с использованием tail возвращает 0вместо пары, [value, count]которые являются регулярными элементами массива кодированной длины серии. Затем продукт Pвозвращается 0при вызове, 0что является ожидаемым результатом.

объяснение

ŒrṪP  Main link. Input: list M
Œr    Run-length encode
  Ṫ   Tail, get the last value
   P  Product, multiply the values together
миль
источник
Как вариант ŒgṪS, тоже работает!
Линн
Это дает правильный вывод для пустого списка в качестве входных данных, но я удивлен, учитывая рассечение. Не могли бы вы пройти через этот особый случай?
Питер Тейлор
@PeterTaylor Я тоже удивлен, что это сработало. Кроме того, я только что заметил, что первая ссылка имеет неправильный код.
миль
@PeterTaylor в желе реализован в виде: lambda z: iterable(z).pop() if iterable(z) else 0. iterableпри вызове из списка просто возвращает список, и пустой список, конечно, ложный.
FryAmTheEggman
10

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

@]#=+

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

объяснение

@]        A suffix of the Input...
  #=      ...whose elements are all equal
    +     Sum its elements

Так как @] - Suffixначинается с самого большого суффикса до самого маленького, сначала он найдет самый длинный.

Fatalize
источник
10

CJam (8 байт)

{W%0+0#}

Набор онлайн-тестов

рассечение

{    e# begin a block
  W%  e# reverse the array
  0+  e# append 0 so there's something to find
  0#  e# find index of first 0, which is number of nonzeros before it
}
Питер Тейлор
источник
10

Haskell, 26 25 байт

a%b|b=1+a|0<3=0
foldl(%)0

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

Prelude> foldl(%)0 [True,False,True,True]
2

Версия Pointfree (26 байт):

length.fst.span id.reverse

Использование целочисленного списка вместо списка bool (21 байт, благодаря Christian Sievers):

a%b=b*(a+1)
foldl(%)0

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

Prelude> foldl(%)0 [1,0,1,1]
2

Pointfree версия (25 байт)

sum.fst.span(==1).reverse
Laikoni
источник
Для целочисленных списков foldlидея работает сa%b=b*(a+1)
Кристиан Сиверс
9

Сетчатка , 7 5 байт

r`1\G

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

Определение формата ввода для Retina не совсем однозначно. Поскольку Retina не имеет понятия о каком-либо типе, кроме строк (и также не имеет значения, которое можно использовать для нашего обычного определения истинности и фальши), я обычно использую 0и 1(или что-то позитивное в целом), чтобы соответствовать истине и фальши, как они представляют ноль или несколько совпадений соответственно.

С односимвольными представлениями нам также не нужен разделитель для списка (что, в некотором смысле, является более естественным представлением списка для языка, который имеет только строки). Адам подтвердил, что это приемлемый формат ввода.

Что касается самого регулярного выражения, оно совпадает rсправа налево и \Gпривязывает каждое совпадение к предыдущему. Следовательно, это подсчитывает, сколько 1s мы можем сопоставить с конца строки.

Мартин Эндер
источник
«Да, для Retina, поскольку он обрабатывает только строки, я думаю, что строка« 01 »или« FT »в порядке.
Adám
9

05AB1E , 12 10 6 5 байт

Сохранено 1 байт благодаря carusocomputing .

Î0¡¤g

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

объяснение

Î      # push 0 and input
 0¡    # split on 0
   ¤   # take last item in list
    g  # get length
Emigna
источник
0¡¤gэто четыре байта.
Волшебная Осьминог Урна
@carusocomputing: Отлично! Когда я это написал, еще не было ясно, был ли ввод строки
верным
J0¡¤gтоже еще короче;).
Волшебная Осьминог Урна
@carusocomputing: К сожалению, нам нужно Îобработать пустой ввод, но это все еще сохраненный байт, спасибо :)
Emigna
8

Python, 31 байт

lambda a:(a[::-1]+[0]).index(0)
Митч Шварц
источник
7

Mathematica, 25 24 байта

Fold[If[#2,#+1,0]&,0,#]&
alephalpha
источник
3
Просто записываю порт крутого смешанного базового решения Дэна: FromDigits[b=Boole@#,MixedRadix@b]&(35 байт).
Грег Мартин
5

Pyth, 6 байт

x_+0Q0

Попробуй это здесь!

Добавляет 0, переворачивает и находит индекс первого 0

синий
источник
@Jakube исправлено - другой алгоритм
Blue
5

C90 (gcc), 46 байтов

r;main(c,v)int**v;{while(0<--c&*v[c])r++;c=r;}

Ввод осуществляется через аргументы командной строки (одно целое число на аргумент), вывод через код завершения .

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

Как это устроено

r является глобальной переменной. Его тип по умолчанию равен int и, будучи глобальным, значение по умолчанию равно 0 .

Аргумент функции c по умолчанию также имеет значение int . Он будет содержать целое число n + 1 для массивов из n логических значений ; первым аргументом main всегда является путь к исполняемому файлу.

Аргумент функции v объявлен как int**. Фактический тип v будет таким char**, но поскольку мы будем проверять только младший значащий бит каждого аргумента, чтобы разделить символы 0 (кодовая точка 48 ) и 1 (кодовая точка 49 ), это не будет иметь значения для little-endian машины.

Цикл while уменьшает значение c и сравнивает его с 0 . Как только c достигнет 0 , мы вырвемся из цикла. Это необходимо только в том случае, если массив не содержит 0 .

Пока 0<--cвозвращается 1 , мы берем c- й аргумент командной строки ( v[c]) и извлекаем его первый символ с помощью разыменования указателя ( *). Мы берем побитовое AND логического 0<--cи кодовую точку символа (и три мусорных байта, которые следуют за ним), поэтому условие вернет 0, как только встретится 0 , выходя из цикла.

В оставшемся случае, в то время как аргументы командной строки 1 , r++приращения г на 1 , таким образом , подсчет количества завершающих 1 «с.

Наконец, c=rсохраняет вычисленное значение r в c . С настройками по умолчанию компилятор оптимизирует и удаляет назначение; это фактически генерирует movl %eax, -4(%rbp)инструкцию. Так как retвозвращает значение регистра EAX, это генерирует желаемый результат.

Обратите внимание, что этот код не работает с C99, который возвращает 0 из основного, если достигнут конец основного .

Деннис
источник
По argcкрайней мере 1(с указанием argv[0]имени файла)? Вы можете сохранить один байт --c&&вместо 0<--c&. Код выхода gcc взят из argc? Ухоженная.
Тит
@ Titus Это не сработает. *v[c]это кодовая точка 1 или 0 , так что это либо 49, либо 48 и, следовательно, всегда верно.
Деннис
С C89 и C90, gcc возвращает все, что находится в RAX на данный момент. C99 всегда возвращает 0 из основного, если достигнут конец.
Деннис
4

k, 6 байтов

+/&\|:

Эта композиция функций переводится в sum mins reversein q, более читабельный брат языка, где mins - это скользящий минимум.

skeevey
источник
Может ли: быть отброшен?
Стритстер
4

J, 9 3 байта

#.~

Это рефлексивное смешанное базовое преобразование. Потому что это то же самое, что и смешанное базовое преобразование. Очередной раз.

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

   v =: #.~
   ]t =: '';0;1;0 1 1 0 0;1 1 1 0 1;1 1 0 1 1;0 0 1 1 1;1 1 1 1 1 1
++-+-+---------+---------+---------+---------+-----------+
||0|1|0 1 1 0 0|1 1 1 0 1|1 1 0 1 1|0 0 1 1 1|1 1 1 1 1 1|
++-+-+---------+---------+---------+---------+-----------+
   v&.> t
+-+-+-+-+-+-+-+-+
|0|0|1|0|1|2|3|6|
+-+-+-+-+-+-+-+-+
   (,. v&.>) t
+-----------+-+
|           |0|
+-----------+-+
|0          |0|
+-----------+-+
|1          |1|
+-----------+-+
|0 1 1 0 0  |0|
+-----------+-+
|1 1 1 0 1  |1|
+-----------+-+
|1 1 0 1 1  |2|
+-----------+-+
|0 0 1 1 1  |3|
+-----------+-+
|1 1 1 1 1 1|6|
+-----------+-+
Конор О'Брайен
источник
2
Подсказка: это можно сделать всего за 3 байта, используя J-перевод решения Дэна.
Адам
1
@ Adám Я пытался найти решение. Не думал о конверсии базы. Это действительно очень умно с его стороны!
Конор О'Брайен
1
Да. Это был Дэн. :-(
Адам
4

R, 40 39 25 байт

Полностью переработанное решение благодаря @Dason

sum(cumprod(rev(scan())))

Чтение входных данных из stdin, обратный вектор, и, если первым элементом является, !=0то вывод первой длины кодировки длин серий ( rle), иначе 0.

Billywob
источник
1
Вы можете сохранить байт, изменив вторую строку на ifelse(r$v,r$l,0)[1]. (Если векторизовано, а затем взять первый элемент.)
rturnbull
1
нет необходимости в iflelse - просто умножьте r $ v и r $ l.
Dason
Но маршрут sum (cumprod (rev (.))) Должен в любом случае сэкономить много байтов
Dason
3

Haskell, 24 байта

foldl(\a b->sum[a+1|b])0

Итерирует по списку, добавляя по одному для каждого элемента, сбрасывая до 0того, как он попадет в False.

16 байтов с входом 0/1:

foldl((*).(+1))0

Если бы список был гарантированно непустым, мы могли бы получить 14 байтов:

sum.scanr1(*)1

Это вычисляет совокупный продукт от спины, затем суммирует их. Совокупный продукт остается 1, пока не достигнет 0, а затем станет 0. Таким образом, 1 соответствуют конечным 1.

XNOR
источник
3

C # 6, 103 72 байта

using System.Linq;
int a(bool[] l)=>l.Reverse().TakeWhile(x=>x).Count();

Использование неуниверсального списка превосходит общий список на 1 байт

-31 байт благодаря Скотту

Ссылка Ng
источник
Если вы используете массив ints, вы можете сойти с рукint a(int[] l)=>l.Reverse().TakeWhile(i=>i>0).Sum();
Скотт
@ Скотт Конечно, о чем я думал ... Я буду придерживаться bool, хотя. Вопрос определяет логический список, и это не C.
Ссылка Ng
Компилировать в a Func<bool[], int>для 57 байтов, т.е.using System.Linq;l=>l.Reverse().TakeWhile(x=>x).Count();
TheLethalCoder
2

Python, 37 байт

f=lambda l:len(l)and-~f(l[:-1])*l[-1]
orlp
источник
2

DASH , 16 байт

@len mstr"1+$"#0

Это не самое короткое из возможных DASH-решений, но самое короткое из возможных DASH-решений вызывает у меня проблемы. Я публикую этот новый подход на своем месте.

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

(@len mstr"1+$"#0)"100111"

объяснение

@(                 #. Lambda
  len (            #. Get the length of the array after...
    mstr "1+$" #0  #. ... matching the argument with regex /1+$/
  )                #. * mstr returns an empty array for no matches
)
Mama Fun Roll
источник
2

Скала, 25 байт

l=>l.reverse:+0 indexOf 0

Ungolfed:

l=>(l.reverse :+ 0).indexOf(0)

Переворачивает список, добавляет 0 и находит первый индекс 0, который является числом элементов перед первым 0

corvus_192
источник
2

Пакетный, 57 байт

@set n=0
@for %%n in (%*)do @set/an=n*%%n+%%n
@echo %n%

Принимает ввод как параметры командной строки. Работает путем умножения аккумулятора на текущее значение перед его добавлением, так что любые нули в командной строке сбрасывают счет. Обратите внимание, что %%nэто не то же самое, что переменная nили %n%.

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

Java 7, 62 байта

int c(boolean[]a){int r=0;for(boolean b:a)r=b?r+1:0;return r;}

Ungolfed & тестовый код:

Попробуй это здесь.

class M{
  static int c(boolean[] a){
    int r = 0;
    for (boolean b : a){
      r = b ? r+1 : 0;
    }
    return r;
  }

  public static void main(String[] a){
    System.out.print(c(new boolean[]{}) + ", ");
    System.out.print(c(new boolean[]{ false }) + ", ");
    System.out.print(c(new boolean[]{ true }) + ", ");
    System.out.print(c(new boolean[]{ false, true, true, false, false }) + ", ");
    System.out.print(c(new boolean[]{ true, true, true, false, true }) + ", ");
    System.out.print(c(new boolean[]{ true, true, false, true, true }) + ", ");
    System.out.print(c(new boolean[]{ false, false, true, true, true }) + ", ");
    System.out.print(c(new boolean[]{ true, true, true, true, true, true }));
  }
}

Выход:

0, 0, 1, 0, 1, 2, 3, 6
Кевин Круйссен
источник
2

Perl 5,10, 22 байта

21 байт + 1 байт для -aфлага. Поскольку выражение на основе регулярных выражений было сделано ...: p

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

$n++while pop@F;say$n

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

Пол Пикард
источник
1
Немного короче, если вы принимаете аргументы через командную строку: perl -E '$_++while pop;say' 0 1 1 0 1 1 1но это ничего не выводит для 0(хотя я не уверен, что это проблема!)
Dom Hastings
2

Perl, 22 байта

21 байт кода + 1 байт для -pфлага.

s/.(?=.*0)//g;$_=y;1;

Чтобы запустить это:

perl -pE 's/.(?=.*0)//g;$_=y;1;' <<< "0 1 1 0 1 1 1"

( На самом деле, формат ввода не имеет значения , много: 0110111, 0 1 1 0 1 1 1, и [0,1,1,0,1,1,1]т.д. бы все работы)


18- байтовая версия от @Dom Hastings, но она требует ввода в виде строки 0 и 1, что недопустимо:

perl -pE '/1*$/;$_=length$&' <<< '0110111'
папа
источник
Люблю этот ;трюк :) Если формат - это одна непрерывная строка: perl -pE '/1*$/;$_=length$&' <<< '0110111'для 18, не уверен, что это нарушает правила или нет ...
Dom Hastings
@DomHastings, да, я тоже! (Спасибо, Тон, за то, что показал мне это!) Первый и второй комментарии вопроса вроде бы запрещают формат ввода, необходимый для вашего решения ... Но я отредактирую свой пост, чтобы предложить вашу версию, если формат ввода был более свободно.
Дада
2

PHP, 50 байт

<?=strlen(preg_filter('/.*[^1]/','',join($argv)));

Жутко моя первая попытка с регулярным выражением оказалось короче , чем мои попытки с массивами ...
Использование как:

php tt.php 1 1 0 1 1
user59178
источник
2

Ruby 37 32 байта

->n{n.size-1-(n.rindex(!0)||-1)}

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

Используется !0как false, так как 0 являются истинными значениями в Ruby. rindexнаходит последний индекс значения в массиве.

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

boolean_list = [true, false, false, true]
->n{n.size-1-(n.rindex(!0)||-1)}[boolean_list]

Возвращает 1


Если бы мне было разрешено передать строку 0 и 1 в качестве параметров командной строки (что не так, как ruby ​​представляет списки логических значений), я мог бы получить значение 24:

$*[0]=~/(1*)\z/;p$1.size

При этом используются регулярные выражения и выводится длина строки, возвращаемой регулярным выражением /(1*)\z/, где \zнаходится конец строки. $*[0]является первым переданным аргументом и является строкой 0 и 1.

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

trailing_truths.rb 011101

Возвращает 1.

IMP1
источник
1
Когда у вас есть индекс последнего ложного значения, зачем вам снова извлекать элементы из массива?
Lee W
Ты прав, а я нет. Благодарю. 5 байт!
IMP1