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

  • Can we take the list as a string of zeros and ones? e.g. 01100? – Adnan Nov 6 '16 at 12:57
  • @Adnan only if that is the most normal way for your language to represent boolean lists. – Adám Nov 6 '16 at 15:42
  • 70
    Sorry for your loss. – Martin Ender Nov 6 '16 at 17:03
  • 5
    @MartinEnder Thank you. It will be tough going forward. Dan taught me all I needed to know to work for Dyalog. – Adám Nov 6 '16 at 17:32
  • 4
    Farewell to Dan. RIP... – Erik the Outgolfer Nov 7 '16 at 12:46

54 Answers 54

up vote 36 down vote accepted

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 = bn, ⋯, b0 and a digit vector a = an, ⋯, a0, b ⊥ a converts a to the mixed base b, i.e., it computes b0⋯bn-1an + ⋯ + b0b1a2 + b0a1 + a0.

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 a0⋯an + ⋯ + a0a1a2 + a0a1 + a0, 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.

  • 14
    Hint: Dan did it in only two bytes. – Adám Nov 6 '16 at 17:27
  • 3
    Mixed base conversion! That's clever. – Dennis Nov 6 '16 at 18:03
  • 1
    Oh. Mixed base conversion, how it strikes again. – Conor O'Brien Nov 6 '16 at 18:39
  • Bravo! In fact, because of Dan, we special-cased b⊥b and ⊥⍨b giving up to infinite speed-up. – Adám Nov 6 '16 at 19:18

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

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

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
  • Alternatively, ŒgṪS works, too! – Lynn Nov 6 '16 at 13:20
  • 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? – Peter Taylor Nov 6 '16 at 13:25
  • @PeterTaylor I'm surprised too that it worked. Also, I just noticed that the first link has the wrong code. – miles Nov 6 '16 at 13:32
  • @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. – FryAmTheEggman Nov 6 '16 at 13:36

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.

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
}

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
  • For integer lists the foldl idea works with a%b=b*(a+1) – Christian Sievers Dec 7 '16 at 16:09

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.

  • "Yes, for Retina, being that it handles only strings, I think a "01" or "FT" string is in order. – Adám Nov 6 '16 at 17:23

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
  • 0¡¤g is four bytes. – Magic Octopus Urn Nov 7 '16 at 15:44
  • @carusocomputing: Nice! It wasn't yet clarified if string input was okay when I wrote this, but I see now that it is :) – Emigna Nov 7 '16 at 15:49
  • J0¡¤g is also still shorter ;). – Magic Octopus Urn Nov 7 '16 at 15:54
  • @carusocomputing: Unfortunately we need Î to handle the empty input, but it's still a byte saved thanks :) – Emigna Nov 7 '16 at 15:54

Python, 31 bytes

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

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

MATL, 4 bytes

PYps

Try it online!

P       % Flip
 Yp     % Cumulative product
   s    % Sum

Mathematica, 25 24 bytes

Fold[If[#2,#+1,0]&,0,#]&
  • 3
    Just recording a port of Dan's cool mixed-base solution: FromDigits[b=Boole@#,MixedRadix@b]& (35 bytes). – Greg Martin Nov 7 '16 at 7:31

Pyth, 6 bytes

x_+0Q0

Try it here!

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

  • @Jakube fixed now - different algorithm – Blue Nov 7 '16 at 9:54

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 cth 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.

  • 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. – Titus Dec 7 '16 at 17:50
  • @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 Dec 7 '16 at 18:19
  • With C89 and C90, gcc returns whatever is in RAX at that moment. C99 always returns 0 from main if the end is reached. – Dennis Dec 7 '16 at 18:22

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.

  • 1
    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.) – rturnbull Nov 6 '16 at 15:10
  • 1
    no need for the iflelse - just multiply r$v and r$l. – Dason Nov 8 '16 at 15:22
  • But the sum(cumprod(rev(.))) route should save a lot of bytes anyways – Dason Nov 8 '16 at 15:23

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.

  • Can the : be dropped? – streetster Oct 5 at 6:33

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|
+-----------+-+
  • 2
    Hint: This can be done in only 3 bytes, using the J translation of Dan's solution. – Adám Nov 6 '16 at 17:25
  • 1
    @Adám I tried looking for a solution. Didn't think of base conversion. That's really quite clever of him! – Conor O'Brien Nov 6 '16 at 18:44
  • 1
    Yes. That was Dan. :-( – Adám Nov 6 '16 at 19:20

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.

Pyke, 10 6 bytes

_0+0R@

Try it here!

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

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

Python, 37 bytes

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

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
)

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

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.

GolfSharp, 14 bytes

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

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

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!

  • 1
    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!) – Dom Hastings Nov 7 '16 at 12:43

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'
  • 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... – Dom Hastings Nov 7 '16 at 12:42
  • @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. – Dada Nov 7 '16 at 13:39

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

Ruby 37 32 bytes

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

Creates an anonymous function that finds the right-most instance of a false value, and counts the size of the subarray starting at that value.

It uses !0 as false, as 0 are truthy values in Ruby. rindex finds the last index of a value in an array.

Usage:

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

Returns 1


If I was allowed to be passed a string of 0s and 1s as command line parameters (which is not how ruby represents lists of booleans), I could get it down to 24:

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

This uses regular expressions and prints the length of the string returned by the regular expression /(1*)\z/, where \z is the end of the string. $*[0] is the first argument passed and is a string of 0s and 1s.

Usage:

trailing_truths.rb 011101

Returns 1.

  • 1
    Once you have the index of the last false value, why do you need to retrieve elements from the array again? – Lee W Nov 7 '16 at 16:14
  • You're right, I don't. Thanks. 5 bytes off! – IMP1 Nov 8 '16 at 8:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.