title: Is it a semiprime?

text:
# Question
Title: Is it a semiprime?
Surprisingly, I don't think we have a question for determining if a number is semiprime.

> A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers.

Simple enough, but a remarkably important concept.

Given a positive integer, determine if it is a semiprime. Your output can be in any form so long as it gives the same output for any truthy or falsey value. You may also assume your input is reasonably small enough that performance or overflow aren't an issue.

Test cases:

```
input -> output
1     -> false
2     -> false
3     -> false
4     -> true
6     -> true
8     -> false
30    -> false   (5 * 3 * 2), note it must be EXACTLY 2 (non-distinct) primes
49    -> true    (7 * 7)      still technically 2 primes
95    -> true
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
      -> true, and go call someone, you just cracked RSA-2048

```

This is , so standard rules apply!

# Answer
# Brachylog, 2 bytes

Basically a port from Fatalize's answer to the Sphenic number challenge.

```
ḋĊ

```

**Try it online!**

### How?

```
ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple

```
> 20 votes

# Answer
# Husk, 4 bytes

Look ma no Unicode!

```
=2Lp

```

**Try it online!**

### How?

```
=2Lp - a one input function
   p - prime factorisation (with duplicates included)
  L  - length
=2   - equals 2?

```
> 16 votes

# Answer
# Pyth, 4 bytes

```
q2lP

```

**Test suite.**

---

# How?

```
q2lPQ     - Q is implicit input.

q2        - Is equal to 2?
    lPQ   - The length of the prime factors of the input.

```
> 8 votes

# Answer
# Python 3, 54 bytes

```
lambda n:0<sum((n%x<1)+(x**3==n)for x in range(2,n))<3

```

Try it online!

The previous verson had some rounding issues on large cube numbers (`125`,`343`,etc)
This calculates the amount of divisors (not only primes), if it has `1` or `2` it returns `True`.
The only exception is when a number has more than two prime factors but only two divisors. In this case it is a perfect cube of a prime (its divisors are its cube root and its cube root squared). `x**3==n` will cover this case, adding one to the cube root entry pushes the sum up to a count of 3 and stops the false-positive. thanks Jonathan Allan for writing with this beautiful explanation
> 8 votes

# Answer
# Mathematica, 16 bytes

```
PrimeOmega@#==2&

```

`PrimeOmega` counts the number of prime factors, counting multiplicity.
> 8 votes

# Answer
# Ruby, ~~56~~ 48 bytes

```
->x{r=c=2;0while x%r<1?(x/=r;c-=1):x>=r+=1;c==0}

```

Try it online!

### How it works:

```
->x{                    # Lambda function
    r=c=2;              # Starting from r=2, c=2
    0 while             # Repeat (0 counts as a nop)
        x%r<1? (        # If x mod r == 0
            x/=r:       # Divide x by r
            c-=1        # decrease c
        ):              # else
            x>=r+=1     # increase r, terminate if r>x
    );
    c==0                # True if we found 2 factors
}

```

Thanks Value Ink for the idea that saved 8 bytes.
> 6 votes

# Answer
# Mathematica, ~~31~~ 29 bytes

```
Tr[Last/@FactorInteger@#]==2&

```
> 5 votes

# Answer
# Python 2, 67 bytes

```
lambda k:f(k)==2
f=lambda n,k=2:n/k and(f(n,k+1),1+f(n/k,k))[n%k<1]

```

Try it online!

***-10 bytes thanks to @JonathanAllan!***

Credit for the Prime factorization algorithm goes to Dennis (in the initial version)
> 4 votes

# Answer
# Neim, 4 bytes

```
δ

```

Try it online!
> 4 votes

# Answer
# Mathematica 32 bytes

Thanks to ngenesis for 1 byte saved

```
Tr@FactorInteger[#][[;;,2]]==2&

```
> 4 votes

# Answer
## JavaScript (ES6), 47 bytes

Returns a boolean.

```
n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

```

### Demo

```
let f =

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

console.log(
  [...Array(200).keys()].filter(f).join`, `
)
```
> 4 votes

# Answer
# Regex (ECMAScript or better), ~~24~~ 23 bytes

```
(?=((x(x*))\2+)\1+$)\3^

```

*-1 byte thanks to Grimmy*

Try it online! \- ECMAScript
Try it online! \- Python
Try it online! \- Ruby

Takes its input in unary, as a string of `x` characters whose length represents the number.

This regex is based on the 18 byte "Is it prime?" regex `(?=(x(x*))\1+$)\2^`, which unlike its semiprime version above, is longer than the shortest known, the 16 byte `^(?!(xx+)\1+$)xx`. But like `^(?=(xx+?)\1*$)\1$` (also 18 bytes), it has the interesting attribute of implicitly rejecting 0 and 1 as prime numbers, whereas the 16 byte regex must explicitly reject them (the `xx` at the end).

```
                  # tail = N = input number; there's no need to anchor here,
                  # because a start anchor is used at the end of this regex
(?=
    (             # \1 = largest proper divisor of N that is >=2
        (x(x*))   # \2 = largest proper divisor of \1; \3 = \2 - 1
        \2+       # Assert that \2 is a proper divisor of \1
    )
    \1+$          # Assert that \1 is a proper divisor of N
)
\3^               # Assert that \3==0, and thus \2==1, meaning the largest proper
                  # divisor of the largest proper divisor of N is 1, meaning N is
                  # semiprime

```

# Regex (Perl / Java / PCRE / Python`regex` / .NET), 23 bytes

```
^(?>((x(x*))\2+)\1+$)\3

```

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE
Try it online! \- Python `import regex`
Try it online! \- .NET

This is a direct port of the "ECMAScript or better" regex above, using an atomic group instead of an atomic lookahead. It is much faster on most regex engines, as the `^` start-anchor test is done first instead of last.

# Regex (Perl / Java / PCRE / Python`regex`), 23 bytes

```
^((x+)\2*(?=\2$)){2}+x$

```

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE
Try it online! \- Python `import regex`

This is a port of the now-obsoleted 24 byte "ECMAScript or better" regex, using a possessive quantifier instead of an atomic lookahead to disable backtracking.

```
^                   # tail = input number
(
    (x+)            # \2 = largest strict divisor of tail
                    #    = tail / {smallest prime factor of tail}
    \2*(?=\2$)      # Assert that \2 is a strict divisor of tail; tail = \2
){2}+               # Execute the loop exactly 2 times, with backtracking disabled
x$                  # assert tail == 1

```

### \\$\large\textit{Expressions with interactive input}\\$

# , ~~59~~ ~~58~~ 54 bytes

```
grepl('^((.+)\\2*(?=\\2$)){2}+.$',strrep(1,scan()),,1)

```

Try it online! \- test cases only

### \\$\large\textit{Anonymous functions}\\$

# , ~~63~~ ~~62~~ ~~58~~ 53 bytes

```
\(n)grepl('^((.+)\\2*(?=\\2$)){2}+.$',strrep(1,n),,1)

```

Attempt This Online!

*-1 byte thanks to Giuseppe*
*-4 bytes by using `grepl()` instead of `sum(grep())` or `any(grep())`*
*-5 bytes by using a new anonymous function syntax introduced in R v4.1.0*

The old **58 byte** R v3.5.2 function: Try it online!

# Ruby, ~~37~~ 36 bytes

```
->n{?x*n=~/(?=((x(x*))\2+)\1+$)\3^/}

```

Try it online!
Try it online! \- test cases only

# PHP, 62 bytes

```
fn($n)=>preg_match('/^((.+)\2*(?=\2$)){2}+.$/',str_pad('',$n))

```

Try it online!

# JavaScript (ES6), ~~46~~ 45 bytes

```
n=>/(?=((.(.*))\2+)\1+$)\3^/.test(Array(n+1))

```

Try it online!

# Java 8, 61 bytes

```
n->new String(new char[n]).matches("((.+)\\2*(?=\\2$)){2}+.")

```

Try it online!
Try it online! \- test cases only

# Java 11, 51 bytes

```
n->"x".repeat(n).matches("((x+)\\2*(?=\\2$)){2}+x")

```

Try it online!

### \\$\large\textit{Full programs}\\$

# Retina, ~~30~~ 29 bytes

```
.+
$*
^(?>((1(1*))\2+)\1+$)\3

```

Try it online! \- test cases only

# PHP, 64 bytes

```
<?=preg_match('/^((.+)\2*(?=\2$)){2}+.$/',str_pad('',$argv[1]));

```

Try it online! \- tests one number at a time

# PHP `-F`, 61 bytes

```
<?=preg_match('/^((.+)\2*(?=\2$)){2}+.$/',str_pad('',$argn));

```

Try it online! \- tests ranges of numbers
Try it online! \- tests one number at a time
> 4 votes

# Answer
# J-uby \+ `prime`, 34 bytes

```
:prime_division|:*&:pop|:sum|:==&2

```

Try it online!
> 4 votes

# Answer
# Jelly, 5 bytes

```
ÆfL=2

```

Try it online!

# Explanation

```
ÆfL=2  Main link
Æf     Prime factors
  L    Length
   =   Equals
    2  2

```
> 3 votes

# Answer
# Actually, 4 bytes

```
ol2=

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 4 bytes

```
Òg2Q

```

Try it online!

**How?**

```
Ò       prime factors list (with duplicates)
 g      length
   Q    equal to
  2     2

```
> 3 votes

# Answer
# Dyalog APL, 18 bytes

```
⎕CY'dfns'
2=≢3pco⎕

```

Try it online!

**How?**

`⎕CY'dfns'` \- import `pco`

`3pco⎕` \- run `pco` on input with left argument 3 (prime factors)

`2=≢` \- length = 2?
> 3 votes

# Answer
# MATL, 5 bytes

```
Yfn2=

```

**Try it online!**

# Explanation

* `Yf` \- Prime factors.
* `n` \- Length.
* `2=` \- Is equal to 2?
> 3 votes

# Answer
# Python with SymPy 1.1.1,  ~~57~~  44 bytes

-13 bytes thanks to alephalpha (use 1.1.1's `primeomega`)

```
from sympy import*
lambda n:primeomega(n)==2

```

**Try it online!**
> 3 votes

# Answer
# Gaia, 4 bytes

```
ḍl2=

```

4 bytes seems to be a common length, I wonder why... :P

Try it online!

### Explanation

```
ḍ     Prime factors
 l    Length
  2=  Equals 2?

```
> 3 votes

# Answer
# , 67 bytes

```
c=0;n=scan();for(p in(1:n)[-1:-2]-1)while(n%%p<1){c=c+1;n=n/p};c==2

```

Try it online!
> 3 votes

# Answer
# Java 8, ~~69~~ 61 bytes

```
n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}

```

-8 bytes thanks to *@Nevay*.

Try it here.
> 3 votes

# Answer
# Ruby, 35+8 = 43 bytes

Uses the `-rprime` flag to unlock the `prime_division` function.

```
->n{n.prime_division.sum(&:pop)==2}

```

Try it online!
> 2 votes

# Answer
# Vyxal, 3 bytes

```
ǐḢ₃

```

Try it Online!
> 2 votes

# Answer
# Factor \+ `math.primes.factors`, 22 bytes

```
[ factors length 2 = ]

```

Try it online!
> 2 votes

# Answer
# Python 2, ~~75~~ 65 bytes

```
lambda n:g(n)==2
g=lambda n,i=2:n/i and[g(n,i+1),1+g(n/i)][n%i<1]

```

Try it online!

All credit to xnor's answer for the original prime factorization code.
> 1 votes

# Answer
# Japt, ~~6~~ 5 bytes

```
k Ê¥2

```

Test it online

---

## Explanation

Does pretty much the same as most of the other answers: `k` gets the array of prime factors, `Ê` gets its length and `¥` checks for equality with `2`.
> 1 votes

# Answer
# C#, 112 Bytes

```
n=>{var r=Enumerable.Range(2,n);var l=r.Where(i=>r.All(x=>r.All(y=>y*x!=i)));return l.Any(x=>l.Any(y=>y*x==n));}

```

With formatting applied:

```
n =>
{
    var r = Enumerable.Range (2, n);
    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
    return l.Any (x => l.Any (y => y * x == n));
}

```

And as test program:

```
using System;
using System.Linq;

namespace S
{
    class P
    {
        static void Main ()
        {
            var f = new Func<int, bool> (
                n =>
                {
                    var r = Enumerable.Range (2, n);
                    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
                    return l.Any (x => l.Any (y => y * x == n));
                }
            );

            for (var i = 0; i < 100; i++)
                Console.WriteLine ($"{i} -> {f (i)}");
            Console.ReadLine ();
        }
    }
}

```

Which has the output:

```
0 -> False
1 -> False
2 -> False
3 -> False
4 -> True
5 -> False
6 -> True
7 -> False
8 -> False
9 -> True
10 -> True
11 -> False
12 -> False
13 -> False
14 -> True
15 -> True
16 -> False
17 -> False
18 -> False
19 -> False
20 -> False
21 -> True
22 -> True
23 -> False
24 -> False
25 -> True
26 -> True
27 -> False
28 -> False
29 -> False
30 -> False
31 -> False
32 -> False
33 -> True
34 -> True
35 -> True
36 -> False
37 -> False
38 -> True
39 -> True
40 -> False
41 -> False
42 -> False
43 -> False
44 -> False
45 -> False
46 -> True
47 -> False
48 -> False
49 -> True
50 -> False
51 -> True
52 -> False
53 -> False
54 -> False
55 -> True
56 -> False
57 -> True
58 -> True
59 -> False
60 -> False
61 -> False
62 -> True
63 -> False
64 -> False
65 -> True
66 -> False
67 -> False
68 -> False
69 -> True
70 -> False
71 -> False
72 -> False
73 -> False
74 -> True
75 -> False
76 -> False
77 -> True
78 -> False
79 -> False
80 -> False
81 -> False
82 -> True
83 -> False
84 -> False
85 -> True
86 -> True
87 -> True
88 -> False
89 -> False
90 -> False
91 -> True
92 -> False
93 -> True
94 -> True
95 -> True
96 -> False
97 -> False
98 -> False
99 -> False

```
> 1 votes

# Answer
# Pari/GP, 17 bytes

```
n->bigomega(n)==2

```

Try it online!
> 1 votes

# Answer
# Python 2, 90 bytes

```
def g(x,i=2):
 while x%i:i+=1
 return i
def f(n,l=0):
 while 1%n:l+=1;n/=g(n)
 return l==2

```

`f` takes an integer `n` greater than or equal to `1`, returns boolean.

Try it online!

Test cases:

```
>>> f(1)
False
>>> f(2)
False
>>> f(3)
False
>>> f(4)
True
>>> f(6)
True
>>> f(8)
False
>>> f(30)
False
>>> f(49)
True
>>> f(95)
True

```
> 1 votes

# Answer
# Retina, 45 bytes

```
.+
$*
^(11+)(\1)+$
$1;1$#2$*
A`\b(11+)\1+\b
;

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
^(11+)(\1)+$
$1;1$#2$*

```

Try to find two factors.

```
A`\b(11+)\1+\b

```

Ensure both factors are prime.

```
;

```

Ensure two factors were found.
> 1 votes

# Answer
# , 6 bytes

5 bytes will work as a one-off:

```
   2=#q: 8
0
   2=#q: 9
1

```

I believe I need six when I define the function:

```
   semiprime =. 2=#@q:
   (,. semiprime) 1 + i. 20
 1 0
 2 0
 3 0
 4 1
 5 0
 6 1
 7 0
 8 0
 9 1
10 1
11 0
12 0
13 0
14 1
15 1
16 0
17 0
18 0
19 0
20 0

```
> 1 votes

# Answer
# Pyke, 5 bytes

```
Pl02q

```

Try it here!
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
fl2=

```

Attempt This Online! Link is to verbose version of code.

```
f      # prime factors
 l     # length
  2=   # equal to 2?

```
> 1 votes

# Answer
# Perl 6, 43 bytes

```
{my \f=first $_%%*,2..$_;?f&&is-prime $_/f}

```

Try it online!

`f` is the smallest factor greater than 1 of the input argument `$_`, or `Nil` if `$_` is 1. The return value of the function is true if `f` is true (ie, not `Nil`) AND the input argument divided by the factor is prime.

If `$_` itself is prime, then `f` will be equal to `$_`, and `$_ / f` is 1, which is not prime, so the formula works in that case as well.
> 0 votes

# Answer
# PHP, 75 bytes

```
<?php for($c=$t=2;$n=&$argv[1]>1;$t++)while($n%$t<1){$c--;$n/=$t;}echo+!$c;

```

Try it online!

This script is called from the command line with the number being tested as its parameter. It prints out a 1 if the number was a semi-prime, else a 0.

**Explanation**

```
<?php

```

Work through each integer, `$t`, from 2 up, to see if it's a factor. We need to keep going, dividing by the factors until `$n` (an alias for `$argv[1]`, the first CLI parameter) reaches 1. (And as there is a 2 to hand, we take the chance to initialize the counter, `$c`, to 2.)

```
for ($c = $t = 2; $n = &$argv[1] > 1; $t++)

```

When we find a factor, we keep using it for as long as we can…

```
    while ($n % $t < 1) {

```

…each time deccrementing the factor counter…

```
        $c--;

```

…and recalculating our number.

```
        $n /= $t;
    }

```

When we reach the end, the counter can only be 0 if there were 2 factors. We ‘not’ the number, but this converts it to a boolean, so we use `+` to make it into 1 (the number was a semi-prime) or 0 (it wasn’t).

```
echo +!$c;

```
> 0 votes

# Answer
# Braingolf, 8 bytes

```
pl2e1:0|

```

Try it online!
> 0 votes

# Answer
# APL(NARS), 7 chars, 14 bytes

```
{2=≢π⍵}

```

test:

```
  f←{2=≢π⍵}
  f¨1 2 3 4 6 8 30 49 95
0 0 0 1 1 0 0 1 1

```
> 0 votes

# Answer
# Alice, 15 bytes

```
/O\cdtv
@I/ nt<

```

Try it online!

## Flattened

```
IcdttnO   Full program
I         Read the input
 c        Get the prime factors in the stack
  dtt     Depth of the stack - 2
     n    Negate, becomes 1 if there was only 2 prime factors, 0 otherwise
      O   Print the result

```
> 0 votes

# Answer
# cQuents, 5 bytes

```
2=Lq$

```

Try it online!

1 for truthy, 0 for falsey.

## Explanation

```
       each term in the sequence is
2                                   2
 =                                    ==
  L                                      length (
   q                                              prime factors (
    $                                                             current index

```
> 0 votes

---
Tags: code-golf, number, sequence, decision-problem, primes
---


# Question
Title: Sort digits by their first occurrence in pi
Given a non-negative number `n`, sort the digits of `n` by their first occurrence in pi.

Input can be taken via function cli argument, or STDIN and as a string, char\[\] or integer. You may output via return value, exit status or STDOUT.

# Answer
# Pyth, ~~8~~ 6 bytes

```
ox+.n0

```

Try it here.

*-1 thanks to Leaky Nun: The input will provide the `0` if it's ever needed.*
*Trivial -1 thanks to Jakube: Backtick not needed (ah, how did I miss that, HOW?!?).*
> 14 votes

# Answer
# Python 3, ~~40~~ 39 bytes

1 byte thanks to Jonathan Allan.

```
lambda s:sorted(s,key="145926870".find)

```

Try it online!
> 21 votes

# Answer
# 05AB1E, ~~10~~ ~~9~~ 7 bytes

Saved 1 byte thanks to *Leaky Nun* noting that filtering out duplicates is unnecessary.
Saved 2 bytes thanks to *Adnan*.

```
žqRvy†J

```

Try it online!

**Explanation**

```
žq       # push pi to 15 decimals (contains all digits but 0)
  R      # reverse
   vy    # for each char in pi
     †J  # move it's occurrences in the input to the front

```
> 17 votes

# Answer
# Japt, ~~10~~ 9 bytes

8 bytes of code, +1 for the `-P` flag.

```
¬ñ!bMP+U

```

Try it online! Takes input as a string.

### Explanation

```
¬ñ!bMP+'0  // Implicit input

¬          // Split the input into chars.
 ñ         // Sort each char in the resulting list by
  !b       //   its index in
    MP+U   //     Math.PI + the input.
-P         // Join the result back into a single string.
           // Implicit: output result of last expression

```
> 8 votes

# Answer
# Jelly, 10 bytes

```
“ṀSṪw’ṾiµÞ

```

Try it online!

Takes input as a string of digits.

*-3 bytes thanks to @ETHproductions*

**Explanation**

```
“ṀSṪw’ṾiµÞ
        µ  - Separate chain into function “ṀSṪw’Ṿi and sort atom Þ.
         Þ - Sort the input by
       i   - Each digit's index in:
“ṀSṪw’     - the literal 3145926870 ...
      Ṿ    - transformed into the list 3,1,4,5,9,2,6,8,7,0

```
> 8 votes

# Answer
# CJam, ~~15~~ ~~12~~ ~~10~~ 8 bytes

```
r{P`#c}$

```

Try it online!

*-3: Use a string based on the `P` pi variable instead of a literal.*
*-2: Decided I don't need to uniquify at all, since finding an index takes the first occurrence anyways.* *-2: Thanks to jimmy23013 for an interesting approach using x mod 65536.*

Explanation:

```
r{P`#c}$ e# Takes an input token
r        e# Take the integer as a string
 {P`#c}  e# Sorting key:
  P      e#  Push P (defaults to 3.141592653589793)
   `     e#  Convert to string representation
    #    e#  Find char's index in the string we made
         e#  A '.' will never be found in an integer, but it doesn't matter, since the shifting preserves ideal sorting.
         e#  A '0' will be indexed as -1.
     c   e#  Convert index to char
         e#  This first calculates index % 65536, and then converts to char. We need this because otherwise 0 would be indexed as -1, i.e. smallest index.
         e#  We don't need to convert back to integer, since we can use lexicographical sorting.
       $ e# Sort with key
```
> 7 votes

# Answer
# Jelly,  ~~8~~  7 bytes

-1 byte thanks to Dennis (use any existing `0` in the input, clever.)

```
ØP;ṾiµÞ

```

**Try it online!**

### How?

```
ØP;ṾiµÞ - Main link: string s (char list)
     µÞ - sort the characters, c, of s by:
    i   -   first index of c in:
ØP      -     pi yield: 3.141592653589793
  ;     -     concatenate with left: [3.141592653589793, c]
   Ṿ    -     un-evaluate: "3.141592653589793,c" (a char list with the digit character c)
                                if any c is 0 ^ it will then be to the right of all others

```
> 7 votes

# Answer
## JavaScript (ES6), 54 bytes

```
f=
s=>[...s].sort((a,b)=>k[a]-k[b],k=`9150236874`).join``
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Uses strings for I/O.
> 7 votes

# Answer
# C (clang), ~~85~~ 73 bytes

```
*z=L"9150236874"-48;s(*a,*b){return z[*a]-z[*b];}f(*t,n){qsort(t,n,4,s);}

```

Try it online!
> 6 votes

# Answer
# PHP, 71 Bytes

The regex solution is shorter

```
for(;~$c=_3145926870[$i++];)echo str_repeat($c,substr_count($argn,$c));

```

or

```
for(;~$c=_3145926870[$i++];)echo str_pad("",substr_count($argn,$c),$c);

```

Online Versions

## PHP, 78 Bytes

```
for(;~$c=$argn[$i++];)$j[strpos("3145926870",$c)].=$c;ksort($j);echo join($j);

```

## PHP, 112 Bytes

```
$a=str_split($argn);usort($a,function($x,$y){return strpos($d="3145926870",$x)<=>strpos($d,$y);});echo join($a);

```

Online Version
> 5 votes

# Answer
# Ruby, 50 bytes

```
n=gets;"3145926870".each_char{|c|$><<c*n.count(c)}

```
> 4 votes

# Answer
# C (gcc), 78 bytes

```
f(char*s){for(char*d="3145926870",*p;*d;d++)for(p=s;*p;)*p++-*d||putchar(*d);}

```

Try it online!
> 4 votes

# Answer
# MATL, 14 bytes

```
YP99Y$uj!y=sY"

```

Try it online!

### Explanation with an example

The symbol `;` is used as row separator in matrices. So `[1 2 3]` is a row vector, `[1; 2; 3]` is a column vector, and `[1 2; 3 4]` is a square matrix. The latter can also be represented, for clarity, as

```
[1 2;
 3 4]

```

Consider input `2325` as an example.

```
YP     % Push approximation of pi as a double (predefined literal)
       % 3.14159265358979
99Y$   % Variable-precision arithmetic with 99 digits. Gives a string.
       % The input 3.14159265358979 is recognized as representing pi
       % STACK: '3.141592653589793238462 ··· 707'
u      % Unique entries, keeping order of their first appearance
       % STACK: '3.145926870'
j      % Input line as a string
       % STACK: '3.145926870', '2352'
!      % Transpose
       % STACK: '3.145926870', ['2'; '3';'5'; '2']
y      % Duplicate the second-top element in the stack
       % STACK: '3.145926870', ['2'; '3';'5'; '2'], '3.145926870'
=      % Test for equality, with broadcast. This gives a matrix with
       % all pairwise comparisons)
       % STACK: '3.145926870', [0 0 0 0 0 0 1 0 0 0 0;
       %                        1 0 0 0 0 0 0 0 0 0 0;
       %                        0 0 0 0 1 0 0 0 0 0 0;
       %                        0 0 0 0 0 0 1 0 0 0 0]
s      % Sum of each column
       % STACK: '3.145926870', [1 0 0 0 1 0 2 0 0 0 0]
Y"     % Run-length decoding. Implicitly display
       % STACK: '3522'

```
> 3 votes

# Answer
# PHP, 66 65 bytes

Saved 1 byte thanks to Titus.

```
while(~$d=_3145926870[++$i])echo preg_filter("/[^$d]/",'',$argn);

```
> 2 votes

# Answer
# C# Interactive, 37 36 Bytes

```
i.OrderBy(c=>"145926870".IndexOf(c))

```

Actually you have to execute this in the C# interactive for proper results, but I guess this is what you meant with *exit status*. The variable *i* actually is the input variable (it can be for example a string), so it's basically the method parameter.

I think the code itself is pretty straight forward.
> 2 votes

# Answer
# 05AB1E, ~~5~~ 6 bytes

Had to realise that `0` is not present in the standard length pi constant.

```
Σтžsyk

```

Try it online!

```
Σтžsyk
Σ      Sort by the result of code
 тžs   Push 100 digits of pi
   yk  Index of digit in pi

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 13 bytes

```
{⍵[⍵⍋⍨14⍕○1]}

```

Try it online!

`○1` Pi times 1.

`14⍕` convert to a string with 14 decimal digits. This includes all unique digits except 0.

`⍵⍋⍨` the indices that would sort the input string  according to order given by the previous string.

`⍵[...]` index with those indices into the input to sort it.
> 2 votes

# Answer
# Java 7, 110 bytes

```
String c(String s){String r="";for(char i:"3145926870".toCharArray())r+=s.replaceAll("[^"+i+"]","");return r;}

```

**Explanation:**

```
String c(String s){                       // Method with String parameter and String return-type
  String r="";                            //  Result String
  for(char i:"3145926870".toCharArray())  //  Loop over the characters of "3145926870"
    r+=s.replaceAll("[^"+i+"]","");       //   Append the result-String with all the occurrences of the current character
                                          //  End of loop (implicit / single-line body)
  return r;                               //  Return the result-String
}                                         // End of method

```

**Test code:**

Try it here.

```
class M{
  static String c(String s){String r="";for(char i:"3145926870".toCharArray())r+=s.replaceAll("[^"+i+"]","");return r;}

  public static void main(String[] a){
    System.out.println(c("12345678908395817288391"));
  }
}

```

**Output:**

```
33311145599922688888770

```
> 1 votes

# Answer
## Clojure, 38 bytes

```
#(sort-by(zipmap"3145926870"(range))%)

```

Input in string, returns a sequence of characters. `zipmap` creates a "dictionary" object, which can be used in a function context as well.

```
(f "1234")
(\3 \1 \4 \2)

```

If input digits were guaranteed to be unique then you could simply do `#(filter(set %)"3145926870")`.
> 1 votes

# Answer
# PHP, 69 68

```
for(;(~$d=$argn[$j++])||~$c=_3145926870[$i+++$j=0];)$c==$d&&print$d;

```

Still beaten by preg\_filter but I thought it was quite nice itself. Maybe someone can golf off some bytes.
> 1 votes

# Answer
# Husk, 4 bytes

```
Ö€İπ

```

Try it online!

Input as a list of digits.
> 1 votes

# Answer
# Pip, 10 bytes

```
PI.0@?_SKa

```

Try it online!

### Explanation

```
       SKa  Sort the command-line argument a by this key function:
    @?_      Index of first occurrence in
PI.0         Pi (3.141592653589793) concatenated with 0

```

If the `0` isn't added, `PI@?0` returns nil, which behaves... strangely... when used as a sorting key.
> 1 votes

# Answer
# Vyxal, 8 bytes

```
µ»×₍+=»ḟ

```

Try it Online!

`µ` Sort by

first index in

`»×₍+=»` compressed integer 145926870
> 1 votes

# Answer
# Perl 6, 34 bytes

```
*.comb.sort:{3145926870.index: $_}

```

Try it

```
*\       # WhateverCode lambda (this is the parameter)
.comb    # split into digits
.sort: { # sort by

  3145926870.index: $_ # its index in this number
}

```
> 0 votes

# Answer
# k, 19 bytes

```
{x@<"3145926870"?x}

```

Explanation:

```
{                 } /function(x)
    "3145926870"?x  /for each x: "3145926870".index(x)
   <                /get indices with which to sort
 x@                 /sort x by those indices

```
> 0 votes

# Answer
# Japt, 6 bytes

Input as a string, output as an array of digit strings

```
¬nUiMP

```

Try it
> 0 votes

# Answer
# TI-Basic, 100 bytes

```
Input Str1
seq(expr(sub(Str1,I,1)),I,1,length(Str1→A
seq(1+sum(not(cumSum(Ans(I)={3,1,4,5,9,2,6,8,7}))),I,1,dim(Ans→B
SortD(ʟB,ʟA
sum(seq(₁₀^(I-1)ʟA(I),I,1,dim(ʟA

```

Takes input as a string. Outputs a number that is stored in `Ans` and is displayed at the end.
> 0 votes

---
Tags: code-golf, number, sorting, pi
---


title: Delete some bits and count

text:
# Question
Title: Delete some bits and count
Consider all `2^n` different binary strings of length `n` and assume `n > 2`. You are allowed to delete exactly `b < n/2` bits from each of the binary strings, leaving strings of length `n-b` remaining. The number of distinct strings remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different strings as possible, this challenge is to write code to compute how few can you leave as a function of `n`.

Example, `n=3` and `b = 1`. You can leave only the two strings `11` and `00`.

For `n=9` and `b = 1,2,3,4` we have `70,18,6,2`

For `n=8` and `b = 1,2,3` we have `40,10,4`

For `n=7` and `b = 1,2,3` we have `20,6,2`

For `n=6` and `b = 1,2` we have `12,4`

For `n=5` and `b = 1,2` we have `6,2`

This question was originally posed by me in 2014 in a different form on MO.

**Input and output**

Your code should take in an integer`n` and output a single integer for each value of `b` starting at `b = 0` and increasing.

**Score**

Your score is the largest `n` for which your code completes for all `b < n/2` in under a minute on my Linux based PC. In case of tie breaks, the largest `b` your code gets to for the joint largest `n` wins. In case of tie breaks on that criterion too, the fastest code for the largest values of `n` and `b` decides. If the times are within a second or two of each other, the first posted answer wins.

**Languages and libraries**

You can use any language of library you like. Because I have to run your code, it would help if it was free (as in beer) and worked in Linux.

# Answer
**Python 2.7 / Gurobi** n=9

This solution is very straight usage of Gurobi's ILP solver for the boolean Mixed-Integer Problems (MIP).

The only trick is to take out symmetry in 1's complement to halve the problem sizes.

Using Gurobi LLC's limited time "free" licence we are restricted to 2000 constraints, but solving 10 del 1 is well outside the 60 second time-limit anyway on my laptop.

```
from gurobipy import *
from itertools import combinations

def mincover(n,d):
    bs = pow(2,n-1-d)
    m = Model()
    m.Params.outputFlag = 0
    b = {}
    for i in range(bs):
      b[i] = m.addVar(vtype=GRB.BINARY, name="b%d" % i)
    m.update()
    for row in range(pow(2,n-1)):
      x = {}
      for i in combinations(range(n), n-d):
        v = 0
        for j in range(n-d):
          if row & pow(2,i[j]):
            v += pow(2,j)
        if v >= bs:
          v = 2*bs-1-v
        x[v] = 1
      m.addConstr(quicksum(b[i] for i in x.keys()) >= 1)
    m.setObjective(quicksum(b[i] for i in range(bs) ), GRB.MINIMIZE)
    m.optimize()
    return int(round(2*m.objVal,0))

for n in range(4,10):
    for d in range((n//2)+1):
        print n, d, mincover(n,d)

```

UPDATE+CORR: 10,2 has optimal solution size 31 (see e.g.) Gurobi shows no symmetric solution of size 30 exists (returns problem infeasible) .. \[my attempt to show asymmetric feasibility at 30 remained inconclusive after 9.5hrs runtime\] e.g. bit patterns of integers `0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255` or `0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255`
> 6 votes

# Answer
# C++, n=6

Brute force with some small optimizations.

```
#include<cassert>
#include<iostream>
#include<vector>

// ===========
/** Helper struct to print binary representation.
`std::cout<<bin(str,len)` prints (str:len) == the bitstring
represented by last (len) bits of (str).
*/
struct bin{
    int str,len;
    bin(int str,int len):str(str),len(len){}
};
std::ostream& operator<<(std::ostream& str,bin a){
    if(a.len)
        return str<<bin(a.str>>1,a.len-1)<<char('0'+(a.str&1));
    else if(a.str)
        return str<<"...";
    else
        return str;
}
// ===========

/// A patten of (len) bits of ones.
int constexpr pat1(int len){
    return (1<<len)-1;
}

// TODO benchmark: make (res) global variable?

/**Append all distinct (subseqs+(sfx:sfxlen)) of (str:len)
with length (sublen) to (res).
*/
void subseqs_(
    int str,int len,int sublen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    // std::cout<<"subseqs_ : str = "<<bin(str,len)<<", "
    // "sublen = "<<sublen<<", sfx = "<<bin(sfx,sfxlen)<<'\n';

    assert(len>=0);

    if(sublen==0){ // todo remove some branches can improve perf?
        res.push_back(sfx);
        return;
    }else if(sublen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }else if(sublen>len){
        return;
    }

    if(str==0){
        res.push_back(sfx);
        return;
    }

    int nTrail0=0;
    for(int ncut;str&&nTrail0<sublen;

        ++nTrail0,
        ncut=__builtin_ctz(~str)+1, // cut away a bit'0' of str
        // plus some '1' bits
        str>>=ncut,
        len-=ncut
    ){
        ncut=__builtin_ctz(str)+1; // cut away a bit'1' of str
        subseqs_(str>>ncut,len-ncut,sublen-nTrail0-1,
            sfx|1<<(sfxlen+nTrail0),sfxlen+nTrail0+1,
            res
        ); // (sublen+sfxlen) is const. TODO global var?
    }

    if(nTrail0+len>=sublen) // this cannot happen if len<0
        res.push_back(sfx);
}

std::vector<int> subseqs(int str,int len,int sublen){
    assert(sublen<=len);
    std::vector<int> res;
    if(__builtin_popcount(str)*2>len){ // too many '1's, flip [todo benchmark]
        subseqs_(pat1(len)^str,len,sublen,0,0,res);
        int const p1sublen=pat1(sublen);
        for(int& r:res)r^=p1sublen;
    }else{
        subseqs_(str,len,sublen,0,0,res);
    }
    return res;
}

// ==========

/** Append all distinct (supersequences+(sfx:sfxlen)) of (str:len)
with length (suplen) to (res).
Define (a) to be a "supersequence" of (b) iff (b) is a subsequence of (a).
*/
void supseqs_(
    int str,int len,int suplen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    assert(suplen>=len);

    if(suplen==0){
        res.push_back(sfx);
        return;
    }else if(suplen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }

    int nTrail0; // of (str)
    if(str==0){
        res.push_back(sfx);
        // it's possible that the supersequence is '0000..00'
        nTrail0=len;
    }else{
        // str != 0 -> str contains a '1' bit ->
        // supersequence cannot be '0000..00'
        nTrail0=__builtin_ctz(str);
    }
    // todo try `nTrail0=__builtin_ctz(str|1<<len)`, eliminates a branch
    // and conditional statement

    for(int nsupTrail0=0;nsupTrail0<nTrail0;++nsupTrail0){
        // (nsupTrail0+1) last bits of supersequence matches with
        // nsupTrail0 last bits of str.
        supseqs_(str>>nsupTrail0,len-nsupTrail0,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    int const strMatch=str?nTrail0+1:len;
    // either '1000..00' or (in case str is '0000..00') the whole (str)

    for(int nsupTrail0=suplen+strMatch-len;nsupTrail0-->nTrail0;){
        // because (len-strMatch)<=(suplen-1-nsupTrail0),
        // (nsupTrail0<suplen+strMatch-len).

        // (nsupTrail0+1) last bits of supersequence matches with
        // (strMatch) last bits of str.
        supseqs_(str>>strMatch,len-strMatch,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    // todo try pulling constants out of loops
}

// ==========

int n,b;
std::vector<char> done;
unsigned min_undone=0;

int result;
void backtrack(int nchoice){
    assert(!done[min_undone]);
    ++nchoice;
    std::vector<int> supers_s;
    for(int s:subseqs(min_undone,n,n-b)){
        // obviously (s) is not chosen. Try choosing (s)
        supers_s.clear();
        supseqs_(s,n-b,n,0,0,supers_s);
        for(unsigned i=0;i<supers_s.size();){
            int& x=supers_s[i];
            if(!done[x]){
                done[x]=true;
                ++i;
            }else{
                x=supers_s.back();
                supers_s.pop_back();
            }
        }

        unsigned old_min_undone=min_undone;
        while(true){
            if(min_undone==done.size()){
                // found !!!!
                result=std::min(result,nchoice);
                goto label1;
            }
            if(not done[min_undone])
                break;
            ++min_undone;
        }
        if(nchoice==result){
            // backtrack more will only give worse result
            goto label1;
        }

        // note that nchoice is already incremented
        backtrack(nchoice);

        label1: // undoes the effect of (above)
        for(int x:supers_s)
            done[x]=false;
        min_undone=old_min_undone;
    }
}

int main(){
    std::cin>>n>>b;

    done.resize(1<<n,0);
    result=1<<(n-b); // the actual result must be less than that

    backtrack(0);
    std::cout<<result<<'\n';
}

```

Run locally:

```
[user202729@archlinux golf]$ g++ -std=c++17 -O2 delbits.cpp -o delbits
[user202729@archlinux golf]$ time for i in $(seq 1 3); do ./delbits <<< "6 $i"; done
12
4
2

real    0m0.567s
user    0m0.562s
sys     0m0.003s
[user202729@archlinux golf]$ time ./delbits <<< '7 1'
^C

real    4m7.928s
user    4m7.388s
sys     0m0.173s
[user202729@archlinux golf]$ time for i in $(seq 2 3); do ./delbits <<< "7 $i"; done
6
2

real    0m0.040s
user    0m0.031s
sys     0m0.009s

```
> 3 votes

# Answer
# MATLAB, n=9

Mixed-integer linear programming (MILP)

Use the `intlinprog` function of the optim package

```
% mincover.m

function result = mincover(n, d)
    bs = 2^(n - 1 - d);

    % define problem
    f = ones(bs, 1);
    intcon = 1:bs;
    lb = zeros(bs, 1);
    ub = ones(bs, 1);
    A = [];
    b = [];

    for row = 0:(2^(n-1) - 1)
        x = zeros(bs, 1);
        combs = nchoosek(1:n, n-d);
        for i = 1:size(combs, 1)
            v = 0;
            for j = 1:(n-d)
                if bitand(row, 2^(combs(i, j) - 1))
                    v = v + 2^(j - 1);
                end
            end
            if v >= bs
                v = 2*bs - 1 - v;
            end
            x(v + 1) = 1;
        end
        A = [A; x'];
        b = [b; 1];
    end

    options = optimoptions('intlinprog','Display','off');
    [x, fval] = intlinprog(f, intcon, -A, -b, [], [], lb, ub, options);
    result = round(2 * fval);
end

```

```
% run_mincover.m

for n = 3:9
    for d = 0:floor(n/2)
        fprintf('n=%d, d=%d, mincover=%d\n', n, d, mincover(n, d))
    end
end

```

```
n=3, d=0, mincover=8
n=3, d=1, mincover=2
n=4, d=0, mincover=16
n=4, d=1, mincover=4
n=4, d=2, mincover=2
n=5, d=0, mincover=32
n=5, d=1, mincover=6
n=5, d=2, mincover=2
n=6, d=0, mincover=64
n=6, d=1, mincover=12
n=6, d=2, mincover=4
n=6, d=3, mincover=2
n=7, d=0, mincover=128
n=7, d=1, mincover=20
n=7, d=2, mincover=6
n=7, d=3, mincover=2
n=8, d=0, mincover=256
n=8, d=1, mincover=40
n=8, d=2, mincover=10
n=8, d=3, mincover=4
n=8, d=4, mincover=2
n=9, d=0, mincover=512
n=9, d=1, mincover=70
n=9, d=2, mincover=18
n=9, d=3, mincover=6
n=9, d=4, mincover=2

```
> 1 votes

---
Tags: fastest-code
---


title: Swap encoding iteration count

text:
# Question
Title: Swap encoding iteration count
# Introduction

In this challenge, I asked you to implement swap encoding.

Swap encoding is an encoding method where you iterate through the string, reversing substrings between identical characters. The basic algorithm is:

For each character in the string:

Check: Does the string contain the character again, after the instance you found?

If so, then modify the string by reversing the section between the character and the next instance, inclusive.

Otherwise do nothing.

# Example

Start with the string 'eat potatoes'.

e is found again, so reverse that section: `eotatop taes`
o is found again, so reverse that section (doing nothing as it is palindromic)
t is found again, so reverse that section (doing nothing as it is palindromic)
a is found again, so reverse that section: `eotat potaes`
t is found again, so reverse that section: `eotatop taes`
None of 'op taes' are found again, so `eotatop taes` is our final string!

Anyway, in this chat, @okie and I discussed what would happen if you repeatedly ran the swap algorithm on something until it returned to the original string. We managed to prove that it will always return.

Okay, that's a lot of preamble. Here's your challenge:

Write a program or function that takes a string as input, and returns the number of times it has to be swapped before it will return to itself.

# Scoring

Answers will be timed on their combined score on all the scored testcases, so please append a snippet to your program that runs all the testcases one after another.

I will time all answers on all on my computer (2018 Macbook Air), although please link to a downloadable interpreter/compiler for less mainstream languages.

Here is my reference implementation.

# Testcases

# Simple testcases (Just to check it works):

```
1231 => 2
1234512345 => 6
123142523
Sandbox for Proposed Challenges => 1090
Collatz, Sort, Repeat => 51
Rob the King: Hexagonal Mazes => 144
Decompress a Sparse Matrix => 8610
14126453467324231 => 1412
12435114151241 - 288
Closest Binary Fraction => 242
Quote a rational number => 282
Solve the Alien Probe puzzle => 5598

```

# Scored testcases (The ones I'm timing you on)

```
124351141512412435325 => 244129
Write a fast-growing assembly function => 1395376
And I'm now heading to the elevator => 207478
I'm in the now infamous elevator => 348112
1549827632458914598012734 => 1025264
i was always mediocre at golfing => 1232480
tho, i like some code challenges => 2759404
I am once again in an elevator => 1606256
A person with mannerism of cat => 867594

```

# IMPORTANT

To make it fair, I have to time all programs under the same load on my computer. So if one person requests a retime, I have to retime them all. This means your time may fluctate.

# Answer
# C, 1.972 seconds

In 2021 we don't have faster CPUs, we just have more cores. Let's use them! Naive implementation using POSIX threads to parallelize. A simple but fast hash is used to save some string compares.

Update: unrolled loop for short distances to shave off 9% percent.

Update 2: flag unique characters to prevent unnecessary searching for duplicate character (saves additional 12%, now saved 19% over original code).

```
// To compile:
//    $ gcc -Wall -O3 JasonSmith.c -lpthread -o JasonSmith
//
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define UNIQUE_MASK  (0x80)

/**
 * Test Vectors with expected answers.
 */
typedef struct {
   const char *text;
   int         expected;
} test_vector_t;

test_vector_t test_vectors[] = {
   {  "124351141512412435325",                  244129   },
   {  "Write a fast-growing assembly function", 1395376  },
   {  "And I'm now heading to the elevator",    207478   },
   {  "I'm in the now infamous elevator",       348112   },
   {  "1549827632458914598012734",              1025264  },
   {  "i was always mediocre at golfing",       1232480  },
   {  "tho, i like some code challenges",       2759404  },
   {  "I am once again in an elevator",         1606256  },
   {  "A person with mannerism of cat",         867594   },
};
int nr_test_vectors = sizeof(test_vectors)/sizeof(test_vectors[0]);

/**
 * Worker thread
 * @param test vector to process
 */
void process(test_vector_t *test_vector) {

   // swap encoding is destructive, so first make copy
   // of challenge text in separate buffer
   char text[strlen(test_vector->text) + 1 + 5];
   memset(text, 0, sizeof(text));
   strcpy(text, test_vector->text);

   // flag unique characters by setting high bit
   for (char *p = text; *p; p++) {
      assert((*p & UNIQUE_MASK) == 0);  // assume no "weird" UTF-8 chars
      int is_unique = 1;
      for (char *q = text; *q; q++) {
          if (p == q) continue;
          if (*p == *q) {
            is_unique = 0;
            break;
          }
      }
      if (is_unique) *p |= UNIQUE_MASK;
   }

   // flagged text no longer matches original text, so we must
   // save flagged text as the new "original" for comparison later.
   char orig[strlen(text) + 1];
   strcpy(orig, text);

   // calculcate hash of original text
   unsigned long original_hash = 0;
   for (char *p = text; *p; p++) {
      original_hash = original_hash*31 + *p;
   }

   // repeatedly swap encode until original text is back
   unsigned long hash;
   unsigned int count = 0;
   do {
      hash = 0;
      for (char *p = text; *p; p++) {
         hash = hash*31 + *p;

         // no need to search for duplicate of unique character
         if ((*p & UNIQUE_MASK) != 0) continue;

         // unrolled loop for short distances
         if (p[0] == p[1]) continue;
         if (p[0] == p[2]) continue;
         if (p[0] == p[3]) {
            char temp = p[1];
            p[1] = p[2];
            p[2] = temp;
            continue;
         }
         if (p[0] == p[4]) {
            char temp = p[1];
            p[1] = p[3];
            p[3] = temp;
            continue;
         }
         if (p[0] == p[5]) {
            char temp = p[1];
            p[1] = p[4];
            p[4] = temp;

            temp = p[2];
            p[2] = p[3];
            p[3] = temp;
            continue;
         }

         // scan for larger distances
         char *last = p+6;
         while (*last && *last != *p) last++;
         if (*last) {
            char *start = p;
            while (++start < --last) {
               char temp = *start;
               *start = *last;
               *last = temp;
            }
         }
      }
      count++;
   } while (hash != original_hash || strcmp(orig, text));

   // show result to user
   printf("%-40s -> %8d (%s)\n", test_vector->text, count,
      (count == test_vector->expected ? "Ok" : "FAIL"));
}

/**
 * Main
 */
int main() {
   pthread_t threads[nr_test_vectors];
   for (int i = 0; i < nr_test_vectors; i++) {
      pthread_create(&threads[i], NULL, (void (*))process, test_vectors+i);
   }
   for (int i = 0; i < nr_test_vectors; i++) {
      pthread_join(threads[i], NULL);
   }
   return 0;
}

```
> 2 votes

# Answer
# C++ (gcc), 3.809 seconds

Compile with `g++ -O3 -std=c++14`.

As requested by the OP, the testcases were included in the source.

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

constexpr int TESTCASES_NUM = 9;
constexpr char *TESTCASES[TESTCASES_NUM] = {"124351141512412435325", "Write a fast-growing assembly function", "And I'm now heading to the elevator", "I'm in the now infamous elevator", "1549827632458914598012734", "i was always mediocre at golfing", "tho, i like some code challenges", "I am once again in an elevator", "A person with mannerism of cat"};

int solve(char *s, int n) {
    int ans = 0;
    int i, j;
    char *p, *q, b;
    char s0[n];
    memcpy(s0, s, n);
    do {
        for(i = 0; i < n; ++i) {
            for(j = i + 1; j < n; ++j) {
                if(s[i] == s[j]) {
                    for(p = s + i + 1, q = s + j - 1; p < q; ++p, --q) {
                        b = *p;
                        *p = *q;
                        *q = b;
                    }
                    break;
                }
            }
        }
        ++ans;
    } while (memcmp(s0, s, n));
    return ans;
}

int main(int argc, char **argv) {
    for(int t = 0; t < TESTCASES_NUM; ++t) {
        char* s = TESTCASES[t];
        int  n = strlen(s);

        int count[300];
        memset(count, 0, sizeof(count));
        for(int i = 0; i < n; ++i) {
            ++count[s[i]];
        }
        char z[n];
        int m = 0;
        for(int i = 0; i < n; ++i) {
            if(count[s[i]] == 1) {
                if(i > 1 and count[s[i - 1]] == 1 and count[s[i - 2]] == 1) {
                    continue;
                }
            }
            if(i > 1 and s[i] == s[i - 2] and count[s[i - 1]] == 1) {
                --m;
                continue;
            }
            if(m == 0 and count[s[i]] == 0) {
                continue;
            }
            z[m++] = s[i];
        }
        while(m > 1 and count[z[m - 1]] == 1) {
            --m;
        }

        printf("%d\n", solve(z, m));
    }
}

```

Try it online!

The naive implementation, with a couple of preprocessing optimizations.

Say that a character is *unique* if it occurs exactly once in the input string.

* If there are more than 2 consecutive unique characters, we can remove some of them until there are exactly 2 consecutive ones.
* We can remove every prefix or suffix consisting entirely of unique characters.
* We can make substitutions `aba -> a` whenever `b` is unique (thanks to kops for the suggestion!).
> 3 votes

# Answer
# C (clang), 5.383 seconds

```
#include <strings.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

unsigned int f(char* str)
{
    unsigned int count = 0;

    char original[strlen(str) + 1];
    strcpy(original, str);

    do {
        for (char* current = str; *current; ++current)
        {
            for (
                    char* last = index(current + 1, *current),
                    *start = current;
                    last > start;
                )
            {
                char temp = *start;
                *start++ = *last;
                *last-- = temp;
            }
        }
        ++count;
    } while (strcmp(original, str));

    return count;
}

int main(int argc, char** argv)
{
#ifdef SIMPLE
    char* tests[] = {"1231", "1234512345", "123142523", "Sandbox for Proposed Challenges", "Collatz, Sort, Repeat", "Rob the King: Hexagonal Mazes", "Decompress a Sparse Matrix", "14126453467324231", "12435114151241", "Closest Binary Fraction", "Quote a rational number", "Solve the Alien Probe puzzle"};
    int expected[] = {2, 6, 4, 1090, 51, 144, 8610, 1412, 288, 242, 282, 5598};
#else
    char* tests[] = {"124351141512412435325", "Write a fast-growing assembly function", "And I'm now heading to the elevator", "I'm in the now infamous elevator", "1549827632458914598012734", "i was always mediocre at golfing", "tho, i like some code challenges", "I am once again in an elevator", "A person with mannerism of cat"};
    int expected[] = {244129, 1395376, 207478, 348112, 1025264, 1232480, 2759404, 1606256, 867594};
#endif

    char* checker[]   = {"\xE2\x9C\x95", "\xE2\x9C\x93"};
    for (int index = 0; index < sizeof(expected)/sizeof(*expected); ++index) {
        char* t = tests[index];
        char buff[strlen(t) + 1];
        strcpy(buff, t);
        int s = f(buff);
        int e = expected[index];
        printf("\"%s\" -> %d %s\n", t, s, checker[e==s]);
    }
}

```

Try it online!

Compile with `-O3`.
> 2 votes

# Answer
# Rust, 9.659 seconds

Port of @Delfad0r's C++ answer in Rust.

Try it online!

```
static TESTCASES: &[&str] = &[
    "124351141512412435325",
    "Write a fast-growing assembly function",
    "And I'm now heading to the elevator",
    "I'm in the now infamous elevator",
    "1549827632458914598012734",
    "i was always mediocre at golfing",
    "tho, i like some code challenges",
    "I am once again in an elevator",
    "A person with mannerism of cat",
];

fn solve(mut s: Vec<char>) -> i32 {
    let mut ans = 0;
    let original_s = s.clone();
    loop {
        for i in 0..s.len() {
            if let Some(j) = (i + 1..s.len()).find(|&j| s[i] == s[j]) {
                s[i + 1..j].reverse();
            }
        }
        ans += 1;
        if s == original_s { break; }
    }
    ans
}

fn main() {
    for &testcase in TESTCASES {
        let s: Vec<char> = testcase.chars().collect();
        let n = s.len();

        let mut count = vec![0; 300];
        for &ch in &s {
            count[ch as usize] += 1;
        }

        let mut z = vec![];
        for i in 0..n {
            if count[s[i] as usize] == 1 {
                if i > 1 && count[s[i - 1] as usize] == 1 && count[s[i - 2] as usize] == 1 {
                    continue;
                }
            }
            if i > 1 && s[i] == s[i - 2] && count[s[i - 1] as usize] == 1 {
                if let Some(_) = z.pop() { continue; }
            }
            if z.is_empty() && count[s[i] as usize] == 0 {
                continue;
            }
            z.push(s[i]);
        }
        while let Some(&last) = z.last() {
            if count[last as usize] == 1 { z.pop(); }
            else { break; }
        }
        println!("{}", solve(z));
    }
}

```
> 1 votes

---
Tags: fastest-code
---


# Question
Title: Compute the size of intersections of sets
## Input

A positive integer N representing the size of the problem and four positive integers v, x, y, z.

## Output

This is what your code should compute. Consider a set of N distinct integers and consider all ways of choosing 3 subsets (which can overlap) from the set. There are \\$2^{3N}\\$ different possible ways of choosing the three subsets. Call the three subsets A, B and C.

Your code must count the number of possible choices of subsets A, B, C such that |A∩B∩C| = v, |A∩B| = x, |B∩C| = y, |C∩A| = z for non-negative integers v, x,y, z.

## Scoring

I will generate a set of 5 valid inputs for each N and the time for your code will be the longest running time for a given problem size for any of the 5 inputs. Each answer will be tested on the same set of inputs, and your score is the highest N your code reaches on my PC in 60 seconds (spec details below). This means you need to give me simple and complete instructions on how to compile and run your code in Linux.

## Examples

Answers for different values of N, v, x, y, z.

* 2, 0, 1, 1, 1 gives 0
* 2, 1, 1, 1, 1 gives 8
* 2, 2, 1, 1, 1 gives 0
* 8, 0, 2, 3, 3 gives 560
* 8, 1, 2, 3, 3 gives 80640
* 8, 2, 2, 3, 3 gives 215040
* 8, 3, 2, 3, 3 gives 0

## My PC

I have an AMD Ryzen 5 3400G running Ubuntu 20.04.

## Notes

This challenge is run *per* language so the fastest in Python is not competing with the fastest in C directly. I will maintain a league table per language once the first answer is given.

# Answer
# Python 3.8 (pre-release)

```
from math import comb
C=lambda n,k:comb(n,k) if n>=0 and k>=0 else 0
f=lambda n,v,x,y,z:C(n,v)*C(n-v,x-v)*C(n-x,y-v)*C(n-x-y+v,z-v)*4**(n-x-y-z+2*v)

```

Try it online!

We fill the Venn diagram's compartments one by one, and we multiply the numbers of options we have at each step:

`C(v,n)` \- to fill the common intersection `A∩B∩C`, we need to choose `v` elements out of a total of `n`. After making that choice, we are left with `n-v` elements.

`C(n-v,x-v)` \- we fill the `x-v` compartment from those `n-v`, and we're left with `n-v-(x-v) = n-x` elements

`C(n-x,y-v)` \- we fill `y-v`, with `n-x-y+v` left

`C(n-x-y+v,z-v)` \- we fill `z-v`

For each of the remaining `n-x-y-z+2*v` elements, there are four possibilities - either belong to exactly one of `A`, `B`, or `C`, or to none of them. Those choices are independent, so we multiply by `4**(n-x-y-z+2*v)`.
> 11 votes

# Answer
# Mathematica

Try it online!

```
B[n_, k_] := If[n >= 0 && k >= 0, Binomial[n, k], 0]
f[n_, v_, x_, y_, z_] := B[n, v]*B[n - v, x - v]*B[n - x, y - v]*B[n - x - y + v, z - v]*4^(n - x - y - z + 2*v)

(* Unit tests *)
Print[f[2, 0, 1, 1, 1] == 0]
Print[f[2, 1, 1, 1, 1] == 8]
Print[f[2, 2, 1, 1, 1] == 0]
Print[f[8, 0, 2, 3, 3] == 560]
Print[f[8, 1, 2, 3, 3] == 80640]
Print[f[8, 2, 2, 3, 3] == 215040]
Print[f[8, 3, 2, 3, 3] == 0]

```
> 0 votes

---
Tags: math, combinatorics, fastest-code
---


title: Count trailing truths

text:
# Question
Title: Count trailing truths
# Inspired by, and in memory of, my dear friend and colleague,

# 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`

# Answer
> 42 votes
# 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**.

# Answer
> 19 votes
## 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
```

# Answer
> 12 votes
# 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

```

# Answer
> 12 votes
# 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
> 11 votes
# 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

```

# Answer
> 10 votes
# 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

```

# Answer
> 10 votes
## 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
> 9 votes
## Python, 31 bytes

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

```

# Answer
> 9 votes
## 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 `r`ight to left and `\G` anchors each match to the previous one. Hence, this counts how many `1`s we can match from the end of the string.

# Answer
> 8 votes
# MATL, 4 bytes

```
PYps

```

Try it online!

```
P       % Flip
 Yp     % Cumulative product
   s    % Sum

```

# Answer
> 7 votes
# Mathematica, ~~25~~ 24 bytes

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

```

# Answer
> 7 votes
# 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
> 6 votes
## Pyth, 6 bytes

```
x_+0Q0

```

Try it here!

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

# Answer
> 6 votes
# 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|
+-----------+-+

```

# Answer
> 5 votes
# 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.

# Answer
> 4 votes
# 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`.

# Answer
> 4 votes
# 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.

# Answer
> 3 votes
## Pyke, ~~10~~ 6 bytes

```
_0+0R@

```

Try it here!

# Answer
> 3 votes
## 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
> 3 votes
# 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

# Answer
> 3 votes
# 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.

# Answer
> 2 votes
## 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'

```

# Answer
> 2 votes
# Python, 37 bytes

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

```

# Answer
> 2 votes
# 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
> 2 votes
# 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
> 2 votes
## 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
> 2 votes
## GolfSharp, 14 bytes

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

```

# Answer
> 2 votes
# 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
> 2 votes
# 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!

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# C++17, ~~82~~ 66 bytes

```
int f(){return 0;}int f(int H,auto... L){return(H*...*L)+f(L...);}

```

Uses the C++17 template parameter fold expression and essentially the same idea as Dennis. Saving 16 bytes by using Generic Variadic Lambda.

Explanation:

```
int f(){return 0;} //base case for empty list

int f(int H, auto... L) { //first element, variadic arguments
    return (H*...*L)      //a_0*a_1*a_2*...
         + f(L...);       //+ f(a_1,a_2,...)
}

```

Usage:

```
f(1,1,0,1,1,0,1,1,1,1,1) -> 5
f() -> 0
f(1,0,1,0) -> 0

```

## Non competing

Albeit longer, this also works with template constants:

```
template <int...L> int C=0;
template <int H, int...L> int C<H,L...> = (H*...*L)+C<L...>;

```

Usage:

```
std::cout << C<1,0,1,1>  << std::endl;
std::cout << C<1,0,1,0,1>  << std::endl;
std::cout << C<1,1,1,0,1,0,1,1>  << std::endl;
std::cout << C<1,1,1,0,1,0,1,1,1,1,1,1>  << std::endl;
std::cout << C<> << std::endl;

```

# Answer
> 2 votes
# 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

```

# Answer
> 2 votes
## Pip, 8 bytes

```
WDQg++ii

```

Takes input as command-line arguments of `0` and `1` (or any truthy value). Try it online!

### Explanation

```
          g is cmdline args, i is 0
 DQg      Dequeue item from end of g
W   ++i   While this is truthy, increment i
       i  Print i

```

(Dequeueing from an empty list gives nil, which is falsey.)

# Answer
> 2 votes
# PHP, ~~40~~ 34 bytes

Along with `$argv` comes `$argc` ... and both are variable.
Either one of the arguments or `+$argv[0]`==`+"-"` is `0`.

```
while(+$argv[--$argc])$i++;echo$i;

```

takes input from command line arguments. Empty output for `0`.
Run with `php -nr '<code>' <space separated values>`

**unary output, ~~35~~ 29 bytes**

```
while(+$argv[--$argc])echo 1;

```

# Answer
> 2 votes
# brainfuck, 99 bytes

Takes input like `11011`. Output is a single byte/character value.

```
-[>+<-----]>---[>>,]<-[>+<-----]>---[-<+>>>+<<]<[->+<]>+>>+[<+[-<<+>>]<<<[-<+>>>-<<]<[->+<]>>>-]<-.

```

**Try it online** \- Run with input, then click "view memory" to see the value under the pointer that was printed.

**Explanation:**

```
-[>+<-----]>---             put constant 48 (ASCII '0') at start of list
[>>,]                       receive all input, with an empty cell between each
<-[>+<-----]>---            constant 48 near end of list
[-<+>>>+<<]<[->+<]>+>>      move to right and copy right, add one to make 49 (ASCII '1')
                            TAPE: 48 _ i0 _ i1 _ ... in _ 49 _ 48< (pointer)

+[<+[-<<+>>]<<              LOOP. Put counter+=1 in empty cell. Move it left 2 cells.
<[-<+>>>-<<]<[->+<]>        Subtract value from value 2 cells right.
>>-]<-.                     Subtract one more. If zero, print counter-1, Else loop again.

```

---

Close, but must contain a zero, and it doesn't handle trailing zeros or an empty list. (49 bytes)

```
,[>>,]>>+[<+[-<<+>>]<<<[-<+>>>-<<]<[->+<]>>>-]<-.

```

# Answer
> 2 votes
# Pushy, 6 bytes

```
$v;FL#

```

Arguments given a list on command line: `$ pushy truths.pshy 0,1,1,0,0.` Like my binary conversion program, this takes advantage of the second stack in an interesting way. Here's how it works:

```
         \ Implicit: Input on stack
$        \ While last item is not 0:
 v;      \   Move last item to auxiliary stack
   FL#   \ Output length of auxiliary stack.

```

Note that the loop will not run if the list is empty, so the output will be `0`.

# Answer
> 2 votes
# PHP, 38 bytes

a totally different approach

```
<?=strpos(strrev(join([0]+$argv)),48);

```

takes input from command line arguments. Save to file.

`[0]+$argv` sets the first element (script name) to `0`.
Join that without a delimiter, reverse and find the first occurence of the `0` character.

While my first solution works with any truthy and falsy values, this one obviously depends on single characters: `0` is falsy, every other character (apart from maybe the `0` byte) truthy.

# Answer
> 2 votes
# Pari/GP, 30 bytes

```
p->valuation(Pol(p)*(x-1)+1,x)

```

Converts the list to a polynomial, say \\$p\\$, then finds the valuation of \\$(x-1)p+1\\$ with respect to \\$x\\$, i.e., the minimal degree of its nonzero terms.

For example, if we take `[1, 0, 1, 1, 1]` as input, then the polynomial \\$p\\$ is \\$x^4 + x^2 + x + 1\\$, and \\$(x-1)p+1\\$ is \\$x^5 - x^4 + x^3\\$, whose valuation is \\$3\\$.

Try it online!

# Answer
> 2 votes
# Taxi, ~~1580~~ ~~1576~~ 1564 bytes

*-4 bytes because of a less complex route to the Crime Lab (string equality checker). Also, you don't run out of gas for a sufficiently large number of truthy values anymore!*

*-12 bytes by getting rid of the quotes.*

```
Go to the Post Office:w 1 l 1 r 1 l.
Pickup a passenger going to Chop Suey.
Go to Chop Suey:n 1 r 1 l 4 r 1 l.
[B]
Switch to plan C if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone:n 1 l 3 l.
Pickup a passenger going to Narrow Path Park.
Pickup a passenger going to Joyless Park.
Go to Zoom Zoom:n.
Go to Narrow Path Park:w 1 l 1 l 1 r.
Go to Joyless Park:e 1 r 3 l.
Go to Chop Suey:w 1 r 1 r 1 l.
Switch to plan B.
[C]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 l 3 l 3 l 2 r.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park:w 1 r.
Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.
[D]
Switch to plan F if no one is waiting.
Pickup a passenger going to Crime Lab.
1 is waiting at Writer's Depot.
Go to Writer's Depot:w 1 l 1 r 2 l.
Pickup a passenger going to Crime Lab.
Go to Zoom Zoom:n.
Go to Crime Lab:w 1 l 2 r.
Switch to plan E if no one is waiting.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:s.
Pickup a passenger going to Addition Alley.
Go to Sunny Skies Park:n 1 l 1 l 1 r.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:n 1 r 1 r 1 r.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park:n 1 l 1 l 1 l.
Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.
Switch to plan D.
[E]
Go to Narrow Path Park:n 5 l.
[F]
Go to Sunny Skies Park:w 1 l 1 r 2 l 1 l.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:s 1 l 1 r 1 r.
Pickup a passenger going to Post Office.
Go to Post Office:n 1 l 1 r.
Go to Taxi Garage:n 1 r 1 l 1 r.

```

Input is in the form of a string of 0's and 1's (for example: `11101`).

Try it online!

Taxi is an esolang in which all programming is done by picking up and dropping off passengers at various stops in the fictional town of Townsburg. Of course, your taxicab will sometimes run out of gas, so you also need to visit gas stations every so often, and pay using the credits you receive as fare.

I had to do some strange management of fuel in this program. Specifically, I have a loop at the beginning (between plans `B` and `C`) which pushes each character of the input to `Narrow Path Park` (which is a LIFO queue, or a stack) by going back and forth between `Narrow Path Park` and `Chop Suey` (which split the input string into characters in the first place). However, for sufficiently large inputs, this can cause me to run out of gas. Simply going to a gas station every iteration is insufficient, because I'm not earning enough money from actually bringing passengers to their destinations. The best way I've figured out to earn enough money to make going to a gas station every iteration "worth it" is bringing each new passenger to `Cyclone` (which clones them), and taking one of those clones to `Narrow Path Park` while leaving one forever trapped at `Joyless Park` (which is a FIFO queue, but for the purposes of this program is a dumping ground).

(Note: Bringing passengers to `Riverview Bridge` is a good way to get rid of them, but they don't pay you - because they always seem to fall off the bridge into the river before they can pay - so I couldn't do this either.)

# Answer
> 2 votes
# Brain-Flak, 30 bytes

```
(()){{}({}{{}}<><{}>)<>([])}<>

```

Try it online!

## Explanation

```
(()) #{ Start Loop.  Used instead of ([]) so that the loop will run at least once on empty input. }
{{}  #{Remove the stack height. }
 (
  {}{{}}  #{ Add the TOS with any 1s below it (until a zero). }
  <><{}>  #{ Remove a value on the other stack if there. }
 )     #{ Push the result (# of 1s just removed) to the other stack. }
 <>    #{ Switch stacks back. }
 ([])  #{ Push stack height for the loop. }
}  #{ Once the loop is done (stack is empty)... }
<> #{ Switch stacks to the most recent # of 1s removed. }

```

# Answer
> 2 votes
# Vyxal `s`, 2 bytes

```
Ġt

```

Try it Online!

Tied with first!

### Explained

```
Ġt∑
Ġ   # group by consecutive
 t  # tail

```

`s` flag does sum.

# Answer
> 2 votes
# Raku, 17 bytes

```
{sum [\R*] 0,|@_}

```

Try it online!

* `0, |@_` is the input list of boolean values with a zero prepended to the front.
* `R*` is the `R`eversed multiplication operator. It's the same as the regular multiplication operator `*`, except that it's right-associative.
* `[\R*]` is the "triangular reduction" of the list to the right, using the `R*` operator. Given a list \\$x\_0, x\_1, ... x\_n\\$, it produces \\$x\_n, x\_n \cdot x\_{n-1}, x\_n \cdot x\_{n-1} \cdot x\_{n-2}, ..., x\_n \cdot x\_{n-1} \cdot x\_{n-2} \cdot ... \cdot x\_0\\$. Raku's arithmetic operators treat boolean true values as 1 and false values as 0, so this produces a list that starts with as many ones as there are true values at the end of the list, followed by as many zeroes as there are remaining values in the list.
* `sum` adds up those values.

It's necessary to paste a leading zero onto the front of the input list, or else an empty list would produce the multiplicative identity element 1.

# Answer
> 1 votes
# Python2, ~~42~~ 41 Byes

```
t=input()[::-1];print len(t[:t.index(0)])

```

takes input as \[1, 1, 0, 1, 1\]

# Answer
> 1 votes
# ABCR, 14 bytes

```
c7iA)7a!xcx!Bp

```

Accepts the formatting `[0,1,0,1,0`, where any non-numeric character can be replaced with any other non-numeric character. Empty input is the empty list.

Explanation: Every `7` input number `i` is queued up `A`; every "0" input number (or rather, non-"1") `)7` will pop from the queue until it's empty `7a!x`; before another input number is queued, a delimiter character is grabbed `cx` to check for the end of queue. After all the integers are grabbed, `!Bp` prints the length of the queue of input numbers (which will be all the trailing "1" values.)

# Answer
> 1 votes
## PHP, ~~58~~ ~~54~~ 53 bytes

```
function f($a){while(array_pop($a))$i++;return+$i;}

```

Since PHP has no list I use an array instead

-4 bytes thanks to user59178

All tests

# Answer
> 1 votes
# Swift 3, 49 bytes

```
func a(b:[Bool]){print(b.reduce(0,{$1 ?$0+1:0}))}

```

# Answer
> 1 votes
# Minkolang, 32 bytes

```
0$nI1-[1=?v0g1+1R]N.
      .Ng0<

```

Try it online!

### Explanation

```
0                             pushes 0 (this is the number that will keep track of the number of 1s)
 $n                           pushes all of input as numbers (pushes -1 if there is no input)
   I1-                        pushes stack minus 1 (to exclude the 0)
      [          ]            for loop with the previous number as the number of iterations
       1=?                     check equality with 1 (this is for the empty input testcase)
                               where -1 will be pushed by the interpreter

```

If number is not `1` (ie `0` or `-1`\[`-1` will be pushed if there is no input\]):

```
         <                     start going left
       g0                      gets the first element in stack
     .N                       output it as number and stop program

```

If number is `1`:

```
          v                    gets jumped over by ? since true has been evaluated
           0g1+                gets the first element and adds 1 to it
               1R              rotates stack once clockwise
                  N.          outputs as number and stops program

```

# Answer
> 1 votes
**Clojure, ~~39~~ 36 bytes**

```
#(count(take-while{1 1}(reverse %)))

```

Input as integers `[1 0 1 1 0 1 1 1]`, anything other than `1` is falsy. `{1 1}` is a hash-map with key `1` and value `1` which can also used as a function. For example `({1 999} 1)` is `999` (truthy) whereas `({1 999} 0)` is `nil` (falsy).

*Original*, based on booleans:

```
#(count(take-while(fn[i]i)(reverse %)))

```

Amazing how `(fn[i]i)` is shorter than `identity` and also doesn't force you to put a space after `take-while`. Must take a list or vector of booleans, integers can be converted like this: `(map #(= 1 %) [1 0 1 1 0 1 1 1])`

# Answer
> 1 votes
# PHP, 33 Bytes

```
<?=strspn(strrev(join($_GET)),1);

```

Online Version

strspn

# Answer
> 1 votes
# Mathematica, 36 bytes

```
Length[#/.({___,0,x___/;x==1}:>{x})]&

```

Not the shortest, but short enough where I was proud to submit it :)

# Answer
> 1 votes
# brainfuck, 33 bytes

```
,[+++>-[<->-----],]<[>[-<+>]<<]>.

```

Try it online!

Takes input via a string like `101011`, and then outputs via byte value. I've added some code in the footer to add 48 to the value to output a digit.

```
 ,[  Loop over input
   +++>-[<->-----]  Subtract 48 from each value to form a tape of 0s and 1s
 ,]
 <[>[-<+>]<<]   Add up all the trailing ones
 >.             And print the value

```

# Answer
> 1 votes
# Rust, 44 bytes

```
|a|a.iter().rev().take_while(|&&i|i).count()

```

Try it online!

explanation:

```
|a|a.iter().rev().take_while(|&&i|i).count() //anonymous function
|a|a.iter()                                  //iterate over the input
           .rev()                            //reverse the iterator
                 .take_while(|&&i|i)         //take while **self is true
                                    .count() //Count the elements in the iterator

```

# Answer
> 1 votes
# Factor, 18 bytes

```
[ [ ] count-tail ]

```

Attempt This Online!

# Answer
> 1 votes
# Fig, \\$5\log\_{256}(96)\approx\\$ 4.116 bytes

```
Lt@x$

```

Try it online!

No "group consecutive," unlike most other golfing languages.

```
Lt@x$
    $ # Reverse the list
 t    # Take while
  @x  # The identity function
L     # Return the length

```

# Answer
> 1 votes
# Nekomata \+ `-1`, 3 bytes

```
sP∑

```

Attempt This Online!

```
s       Find a suffix of the input
 P      that contains only positive integers
  ∑     and sum them.

```

`-1` prints the first solution.

# Answer
> 1 votes
# Thunno 2 `tS`, 1 byte

```
ġ

```

Attempt This Online!

Or, if you want it flagless:

## Thunno 2, 3 bytes

```
ġtS

```

Attempt This Online!

#### Explanation

```
ġtS  # Implicit input
ġ    # Group consecutive
 t   # Last item
  S  # Sum
     # Implicit output

```

# Answer
> 0 votes
# Braingolf, 7 bytes

```
!?&gGL|

```

Try it online!

## Explanation

```
!?&gGL|  Implicit input from commandline args
!?       If last item on stack is > 0..
  &g     ..Combine all items into single number (1, 1, 0, 1 becomes 1101)
    G    ..Split into digit runs (1101 becomes 11, 0, 1)
     L   ..Pop last item and push length of item (111 becomes 3)
      |  Endif
         Implicit output of last item on stack, either number of trailing ones, or zero

```

# Answer
> 0 votes
# Backhand, 17 bytes

```
v I^: ]|{]1$|{O @

```

Try it online!

### Explanation:

```
v I^: ]|{]1$|{O @
v                  Decrease step value to 2
  I                Get input as a number
    : ]|{          Reflect if not EOF
   ^               Increase step value to 3
v                  Decrease to 2 and repeat the loop
         ]         The leftover EOF (-1) is now our counter. Increment it to 0
           $|{     Reflect if the top value is truthy
       |{ 1        Reflect and repeat
         ]         Increment the counter for every truthy value
              O @  Output the final state of the counter

```

# Answer
> 0 votes
# Ohm v2, 5 bytes

```
Ö⁾ì]*

```

RLE encodes the string, takes the last element, flattens, and multiplies

Try it online!

# Answer
> 0 votes
# , 7 bytes

```
Ó1*0
ø1

```

Try it online! Takes input as a string of `0` and `1`.

## Explanation

```
Ó1*0     Remove all occurences of any number of ones followed by a zero
ø1       Count the number of remaining ones

```

# Answer
> 0 votes
# MBASIC, 112 bytes

```
1 INPUT B$:T=0:FOR I=LEN(B$) TO 1 STEP -1:C$=MID$(B$,I,1):IF C$="0" THEN 4
2 IF C$="1" THEN T=T+1
3 NEXT
4 PRINT T

```

Just wanted to see if I could do it.

**Explanation**

Input is a string of 1's and 0's. String is traversed from right to left. If the current digit is a 0, bail out and print the total. If the digit is a 1, increment the total and continue to loop.

**Output**

```
? 01100
 0

? 11011
 2

? 11101
 1

? 111111
 6

```

# Answer
> 0 votes
# 05AB1E, 3 bytes

```
γθO

```

Try it online!

```
γθO  # full program
  O  # sum of...
 θ   # last...
γ    # group of consecutive equal elements in...
     # implicit input
     # implicit output

```

---
Tags: code-golf, number, array, counting, logic
---