Count trailing truths

Question

Inspired by, and in memory of, my dear friend and colleague,

Dan Baronet

Dan Baronet, 1956 – 2016. R.I.P.

He found the shortest possible APL solution to this task:

Task

Given a Boolean list, count the number of trailing truth values.

Example cases

{} → 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

• Adnan: Can we take the list as a string of zeros and ones? e.g. 01100?
• Adám: @Adnan only if that is the most normal way for your language to represent boolean lists.
• Martin Ender: Sorry for your loss.
• Adám: @MartinEnder Thank you. It will be tough going forward. Dan taught me all I needed to know to work for Dyalog.
• Erik the Outgolfer: Farewell to Dan. RIP...

Answer 1

Dyalog APL, (削除) 6 (削除ここまで) 2 bytes

⊥⍨

Test it on TryAPL.

How it works

⊥ (uptack, dyadic: decode) performs base conversion. If the left operand is a vector, it performs mixed base conversion, which is perfect for this task.

For a base vector b = b_n, ⋯, b₀ and a digit vector a = a_n, ⋯, a₀, b ⊥ a converts a to the mixed base b, i.e., it computes b₀⋯b_n-1a_n + ⋯ + b₀b₁a₂ + b₀a₁ + a₀.

Now, ⍨ (tilde dieresis, commute) modifies the operator to the left as follows. In a monadic context, it calls the operator with equal left and right arguments.

For example, ⊥⍨ a is defined as a ⊥ a, which computes a₀⋯a_n + ⋯ + a₀a₁a₂ + a₀a₁ + a₀, the sum of all cumulative products from the right to the left.

For k trailing ones, the k rightmost products are 1 and all others are 0, so their sum is equal to k.

• Adám: Hint: Dan did it in only two bytes.
• Dennis: Mixed base conversion! That's clever.
• Conor O'Brien: Oh. Mixed base conversion, how it strikes again.
• Adám: Bravo! In fact, because of Dan, we special-cased b⊥b and ⊥⍨b giving up to infinite speed-up.

Answer 2

JavaScript (ES6), 21 bytes

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

Test cases

f=l=>l.pop()?f(l)+1:0
console.log(f([])); // → 0
console.log(f([0])); // → 0
console.log(f([1])); // → 1
console.log(f([0, 1, 1, 0, 0])); // → 0
console.log(f([1, 1, 1, 0, 1])); // → 1
console.log(f([1, 1, 0, 1, 1])); // → 2
console.log(f([0, 0, 1, 1, 1])); // → 3
console.log(f([1, 1, 1, 1, 1, 1])); // → 6

• Oliver: How does this work? How does f(l)+1 return a value > 2?
• Arnauld: @Oliver This is a recursive process, evaluated as l.pop()?(l.pop()?(l.pop()?(...etc...)+1:0)+1:0)+1:0.
• Oliver: I see. Thanks for the explanation.

Answer 3

Brachylog, (削除) 7 (削除ここまで) (削除) 6 (削除ここまで) 5 bytes

@]#=+

Try it online!

Explanation

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

Since @] - Suffix starts from the biggest suffix all the way up to the smallest one, it will find the longest run first.

Answer 4

Jelly, 4 bytes

ŒrṪP

Try it online! or Verify all test cases.

For the case where the list is empty, there are some curious observations. First, run-length encoding the empty list [] returns another empty list []. Then retreiving the last element from that using tail Ṫ returns 0 instead of a pair [value, count] which are the regular elements of a run-length encoded array. Then product P returns 0 when called on 0 which is the expected result.

Explanation

ŒrṪP Main link. Input: list M
Œr Run-length encode
 Ṫ Tail, get the last value
 P Product, multiply the values together

• lynn: Alternatively, ŒgṪS works, too!
• Peter Taylor: It gives the right output for the empty list as input, but I'm surprised given the dissection. Would you mind walking through that special case?
• miles: @PeterTaylor I'm surprised too that it worked. Also, I just noticed that the first link has the wrong code.
• FryAmTheEggman: @PeterTaylor Ṫ in Jelly is implemented as: lambda z: iterable(z).pop() if iterable(z) else 0. iterable when called on a list just returns the list, and the empty list is of course falsy.

Answer 5

Haskell, (削除) 26 (削除ここまで) 25 bytes

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

Usage:

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

Pointfree version (26 bytes):

length.fst.span id.reverse

---

Using an integer list instead of a bool list (21 bytes, thanks to Christian Sievers):

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

Usage:

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

Pointfree version (25 bytes)

sum.fst.span(==1).reverse

• Christian Sievers: For integer lists the foldl idea works with a%b=b*(a+1)

Answer 6

CJam (8 bytes)

{W%0+0#}

Online test suite

Dissection

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

Answer 7

05AB1E, (削除) 12 (削除ここまで) (削除) 10 (削除ここまで) (削除) 6 (削除ここまで) 5 bytes

Saved 1 byte thanks to carusocomputing.

Î0¡¤g

Try it online!

Explanation

Î # push 0 and input
 0¡ # split on 0
 ¤ # take last item in list
 g # get length

• Magic Octopus Urn: 0¡¤g is four bytes.
• Emigna: @carusocomputing: Nice! It wasn't yet clarified if string input was okay when I wrote this, but I see now that it is :)
• Magic Octopus Urn: J0¡¤g is also still shorter ;).
• Emigna: @carusocomputing: Unfortunately we need Î to handle the empty input, but it's still a byte saved thanks :)

Answer 8

Python, 31 bytes

lambda a:(a[::-1]+[0]).index(0)

Answer 9

Retina, (削除) 7 (削除ここまで) 5 bytes

r`1\G

Try it online! (The first line enables a linefeed-separated test suite.)

Defining the input format for Retina isn't entirely unambiguous. Since Retina has no concept of any type except strings (and also no value that can be used for our usual definition of truthy and falsy), I usually use 0 and 1 (or something positive in general) to correspond to truthy and falsy, as they represent zero or some matches, respectively.

With single-character representations, we also don't need a separator for the list (which in a way, is more the more natural list representation for a language that only has strings). Adám confirmed that this is an acceptable input format.

As for the regex itself, it matches from right to left and \G anchors each match to the previous one. Hence, this counts how many 1s we can match from the end of the string.

• Adám: "Yes, for Retina, being that it handles only strings, I think a "01" or "FT" string is in order.

Answer 10

MATL, 4 bytes

PYps

Try it online!

P % Flip
 Yp % Cumulative product
 s % Sum

Answer 11

Jelly, 4 bytes

ṣ0ṪL

TryItOnline! , or all tests

How?

ṣ0ṪL - Main link: booleanList
ṣ0 - split on occurrences of 0 ([] -> [[]]; [0] -> [[],[]]; [1] -> [[1]]; ...)
 Ṫ - tail (rightmost entry)
 L - length

Answer 12

Mathematica, (削除) 25 (削除ここまで) 24 bytes

Fold[If[#2,#+1,0]&,0,#]&

• Greg Martin: Just recording a port of Dan's cool mixed-base solution: FromDigits[b=Boole@#,MixedRadix@b]& (35 bytes).

Answer 13

J, (削除) 9 (削除ここまで) 3 bytes

#.~

This is reflexive mixed base conversion. Because this is the same as mixed base conversion. Again.

Test cases

 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|
+-----------+-+

• Adám: Hint: This can be done in only 3 bytes, using the J translation of Dan's solution.
• Conor O'Brien: @Adám I tried looking for a solution. Didn't think of base conversion. That's really quite clever of him!
• Adám: Yes. That was Dan. :-(

Answer 14

Pyth, 6 bytes

x_+0Q0

Try it here!

Appends a 0, reverses and finds the index of the first 0

• Blue: @Jakube fixed now - different algorithm

Answer 15

C90 (gcc), 46 bytes

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

Input is via command-line arguments (one integer per argument), output via exit code.

Try it online!

How it works

r is a global variable. Its type defaults to int and, being global, it value defaults to 0.

The function argument c defaults to int as well. It will hold the integer n + 1 for arrays of n Booleans; the first argument of main is always the path of the executable.

The function argument v is declared as int**. The actual type of v will be char**, but since we'll only examine the least significant bit of each argument to tell the characters 0 (code point 48) and 1 (code point 49) apart, this won't matter on little-endian machines.

The while loop decrements c and compares it to 0. Once c reaches 0, we'll break out of the loop. This is needed only if the array contains no 0's.

As long as 0<--c returns 1, we takes the c^th command-line argument (v[c]) and extract its first character with by dereferencing the pointer (*). We take the bitwise AND of the Boolean 0<--c and the code point of the character (and three garbage bytes that follow it), so the condition will return 0 once a 0 is encountered, breaking out of the loop.

In the remaining case, while the command-line arguments are 1, r++ increments r by 1, thus counting the number of trailing 1's.

Finally, c=r stores the computed value of r in c. With default settings, the compiler optimize and remove the assignment; it actually generates the movl %eax, -4(%rbp) instruction. Since ret returns the value of the EAX register, this generates the desired output.

Note that this code does not work with C99, which returns 0 from main if the end of main is reached.

• Titus: Isn´t argc at least 1 (with argv[0] containing the file name)? You could save one byte with --c&& instead of 0<--c&. gcc´s exit code is taken from argc? Neat.
• Dennis: @Titus That won't work. *v[c] is the code point of 1 or 0, so it's either 49 or 48 and thus always truthy.
• Dennis: With C89 and C90, gcc returns whatever is in RAX at that moment. C99 always returns 0 from main if the end is reached.

Answer 16

k, 6 bytes

+/&\|:

This function composition translates to sum mins reverse in q, the language's more readable sibling, where mins is a rolling minimum.

• mkst: Can the : be dropped?
• coltim: A port of APL version is possible in ngn/k for 5 bytes.

Answer 17

R, (削除) 40 39 (削除ここまで) 25 bytes

Completely reworked solution thanks to @Dason

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

Read input from stdin, reverse the vector and if the first element of is !=0 then output the the first length of the run-length encoding (rle), else 0.

• rturnbull: You can save a byte by changing the second line to ifelse(r$v,r$l,0)[1]. (Vectorized if, and then take the first element.)
• Dason: no need for the iflelse - just multiply r$v and r$l.
• Dason: But the sum(cumprod(rev(.))) route should save a lot of bytes anyways

Answer 18

Haskell, 24 bytes

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

Iterates over the list, adding one for each element, resetting to 0 after it hits a False.

16 bytes with 0/1 input:

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

If the list were guaranteed non-empty, we could get 14 bytes:

sum.scanr1(*)1

This computes the cumulative product from the back, then sums them. The cumulative product remains 1 until a 0 is hit, and then becomes 0. So, the 1's correspond to trailing 1's.

Answer 19

Pyke, (削除) 10 (削除ここまで) 6 bytes

_0+0R@

Try it here!

Answer 20

C#6, (削除) 103 (削除ここまで) 72 bytes

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

Using non-generic list beats generic list by 1 byte lol

-31 bytes thanks to Scott

• Scott: If you use an array of ints, you can get away with int a(int[] l)=>l.Reverse().TakeWhile(i=>i>0).Sum();
• Link Ng: @Scott Of course what was I thinking... I will stick with bool though. Question specifies boolean list and it's not C.
• TheLethalCoder: Compile to a Func<bool[], int> for 57 bytes i.e. using System.Linq;l=>l.Reverse().TakeWhile(x=>x).Count();

Answer 21

Japt -hx, 3 bytes

i ô

Try it online!

Japt's flag combinations rock.

How it works

Ui ô
Ui Insert `undefined` at index 0
ô Split at falsy items
-h Take last element
-x Sum

If we didn't have to handle the special case [], we could get away with 1 byte ô, winning over APL.

• Adám: Half the job is done by flags‽

Answer 22

Python, 37 bytes

f=lambda l:len(l)and-~f(l[:-1])*l[-1]

Answer 23

DASH, 16 bytes

@len mstr"1+$"#0

It's not the shortest possible DASH solution, but the shortest possible DASH solution is bugging out on me. I'm posting this novel approach in its place.

Usage:

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

Explanation

@( #. 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
)

Answer 24

Scala, 25 bytes

l=>l.reverse:+0 indexOf 0

Ungolfed:

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

Reverses the list, appends a 0 and find the first index of 0, which is the number of elements before the first 0

Answer 25

Batch, 57 bytes

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

Takes input as command-line parameters. Works by multiplying the accumulator by the current value before adding it on, so that any zeros in the command line reset the count. Note that %%n is not the same as the n or %n% variable.

Answer 26

GolfSharp, 14 bytes

n=>n.V().O(F);

Answer 27

Java 7, 62 bytes

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

Ungolfed & test code:

Try it here.

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

Output:

0, 0, 1, 0, 1, 2, 3, 6

Answer 28

Perl 5.10, 22 bytes

21 bytes + 1 byte for -a flag. Since the regex-based expression was done... :p

The input values for the array must be separated by a space.

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

Try it online!

• Dom Hastings: Slightly shorter if you take arguments via command line: perl -E '$_++while pop;say' 0 1 1 0 1 1 1 but this doesn't output anything for 0 (not sure if that's a problem though!)

Answer 29

Perl, 22 bytes

21 bytes of code + 1 byte for -p flag.

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

To run it :

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

(Actually, the format of the input doesn't matter a lot : 0110111, 0 1 1 0 1 1 1, [0,1,1,0,1,1,1] etc. would all work)

---

18 bytes version from @Dom Hastings but it requires to supply the input as a string of 0 and 1, which isn't allowed :

perl -pE '/1*$/;$_=length$&' <<< '0110111'

• Dom Hastings: Loving that ; trick :) If format is one continuous string: perl -pE '/1*$/;$_=length$&' <<< '0110111' for 18, not sure if that's bending the rules or not though...
• Dada: @DomHastings yea, me too! (Thanks Ton for showing me that!) The first and second comments of the question kinda disallow the format of input you need for your solution... But I'll edit my post to suggest your version if the format of the input was more free.

Answer 30

PHP, 50 bytes

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

Weirdly my first try with a regex turned out shorter than my try with arrays...
Use like:

php tt.php 1 1 0 1 1