title: GET your dubs together

text:
# Question
Title: GET your dubs together
On 4chan, a popular game is get. Every post on the site gets a sequential post ID. Since you can't influence or determine them, people try to guess (at least a part of) their own post number, usually the first few digits. Another version of the game is called dubs, and it's goal is to get repeating digits at the end of the number (i.e 1234555).

Your task, if you wish to accept it, is to write a program that takes a post id as input (standard integer, you can assume below 2^32), and returns how many repeating digits are on the end.

# Rules

* Standard loopholes are **disallowed**.
* The program can be a function, full program, REPL command, whatever works, really, as long as no external uncounted code/arguments are needed to run it.
* Input can come from STDIN, function arguments, command line argument, file, whatever suits you.

# Test Cases

```
Input: 14892093
Output: 1

Input: 12344444
Output: 5

Input: 112311
Output: 2

Input: 888888
Output: 6

Input: 135866667 //Post number I got on /pol/ few days ago, rip
Output: 1

```

# Answer
> 21 votes
## Mathematica, 29 bytes

How about an arithmetic solution?

```
IntegerExponent[9#+#~Mod~10]&

```

I'm very pleased to see that this beats the straight-forward Mathematica approach.

### Explanation

The code itself computes **9\*n + n%10** and then finds the largest power of **10** that divides the input, or in other words, counts the trailing zeros. We need to show if **n** ends in **k** repeated digits, that **9\*n + n%10** has **k** trailing zeros.

Rep-digits are most easily expressed mathematically by dividing a number like **99999** (which is **105-1**) by **9** and then multiplying by the repeated digit. So we can write **n = m\*10k \+ d\*(10k-1)/9**, where **m ≢ d (mod 10)**, to ensure that **n** doesn't end in *more* than **k** repeated digits. Note that **d = n%10**.

Let's plug that into our formula **9\*n + n%10**. We get **9\*m\*10k \+ d\*(10k-1) + d**. The **d** at the end is cancelled, so we're left with: **9\*m\*10k \+ d\*10k = (9\*m + d)\*10k**. But **9 ≡ -1 (mod 10)**, so **9\*m + d ≡ d - m (mod 10)**. But we've asserted that **m ≢ d (mod 10)** and hence **d - m ≢ 0 (mod 10)**.

In other words, we've shown that **9\*m + d** is not divisible by **10** and therefore, the largest power of **10** that divides **9\*n + n%10 = (9\*m + d)\*10k** is **k**, the number of trailing repeated digits.

As a bonus, this solution prints the correct result, , for input `0`.

# Answer
> 15 votes
## Retina, 9 bytes

```
&`(.)\1*$

```

Try it online!

Counts the number of overlapping matches of `(.)\1*$` which is a regex that matches a suffix of identical characters.

# Answer
> 9 votes
# Brachylog, 4 bytes

```
ẹḅtl

```

Try it online!

### Explanation

```
ẹ       Elements: split to a list of digits
 ḅ      Blocks: group consecutive equal digits into lists
  t     Tail: take the last list
   l    Length: Output is the length of that last list

```

If  worked directly on integers (and I'm not sure why I didn't implement it so that it does), this would only be 3 bytes as the  would not be needed.

# Answer
> 9 votes
# Python 2, ~~47~~ 41 bytes

```
lambda s:len(`s`)-len(`s`.rstrip(`s%10`))

```

Try it online!

### 36 bytes - For a more flexible input

```
lambda s:len(s)-len(s.rstrip(s[-1]))

```

Try it online!

# Answer
> 8 votes
## Javascript (ES6), ~~55~~ ~~52~~ ~~32~~ 30 bytes

```
a=>a.match`(.)\\1*$`[0].length

```
* Saved **19** bytes thanks to @MartinEnder by replacing the regex
* Saved **2** bytes thanks to @user81655 using tagged templates literals

---

Using a regex to match the last group of the last digit

*Note: First time posting. Do not hesitate to make remarks.*

```
f=a=>a.match`(.)\\1*$`[0].length

console.log(f("14892093"));//1
console.log(f("12344444"));//5
console.log(f("112311"));//2
console.log(f("888888"));//6
console.log(f("135866667 "));//1

```

# Answer
> 7 votes
# C, ~~62~~ ~~56~~ ~~48~~ 47 bytes

*Saved a byte thanks to @Steadybox!*

```
j,k;f(n){for(k=j=n%10;j==n%10;n/=10,k++);k-=j;}

```

Try it online!

# Answer
> 7 votes
# Perl 5, 22 bytes

21 bytes of code + `-p` flag.

```
/(.)\1*$/;$_=length$&

```

Try it online!

`/(.)\1*$/` gets the last identical numbers, and then `$_=length$&` assigns its length to `$_`, which is implicitly printed thanks to `-p` flag.

# Answer
> 7 votes
# PHP, 47 45 40 bytes

```
while($argn[-++$i]==$argn[-1]);echo$i-1;

```

Run with `echo <n> | php -nR '<code>`

seems a loop is still smaller than my first answer. simply count the chars that are equal to the last. This uses negative string offsets of *PHP 7.1*.

*-5 bytes* by Titus. Thanks !

---

Old answer:

```
<?=strlen($a=$argv[1])-strlen(chop($a,$a[-1]));

```

removes from the right every character matching the rightmost character and calculates the difference in the length.

# Answer
> 7 votes
# Python 2, ~~38~~ 32 bytes

```
f=lambda n:0<n%100%11or-~f(n/10)

```

*Thanks to @xnor for saving 6 bytes!*

Try it online!

# Answer
> 6 votes
# 05AB1E, 4 bytes

```
.¡¤g

```

Try it online! or as a Test suite

**Explanation**

```
.¡    # group consecutive equal elements in input
  ¤   # get the last group
   g  # push its length

```

# Answer
> 6 votes
## CJam, 7 bytes

```
re`W=0=

```

Try it online!

### Explanation

```
r   e# Read input.
e`  e# Run-length encode.
W=  e# Get last run.
0=  e# Get length.

```

# Answer
> 6 votes
# Jelly, 5 bytes

```
DŒgṪL

```

Try it online!

**Explanation**

```
D      # convert from integer to decimal
 Œg    # group runs of equal elements
   Ṫ   # tail
    L  # length

```

# Answer
> 6 votes
# Cubix, ~~24~~ 19 bytes

```
)uO)ABq-!wpUp)W.@;;

```

# Note

* Actually counts how many of the same characters are at the end of the input, so this works for really big integers and really long strings as well (as long as the amount of same characters at the end is smaller than the maximum precision of JavaScript (around 15 digits in base-10).
* Input goes in the input field, output is printed to the output field

Try it here

# Explanation

First, let's expand the cube

```
    ) u
    O )
A B q - ! w p U
p ) W . @ ; ; .
    . .
    . .

```

The steps in the execution can be split up in three phases:

1. Parse input
2. Compare characters
3. Print result

## Phase 1: Input

The first two characters that are executed are `A` and `B`. `A` reads all input and pushes it as character codes to the stack. Note that this is done in reverse, the first character ends up on top of the stack, the last character almost at the bottom. At the very bottom, `-1` (`EOF`) is placed, which will be used as a counter for the amount of consecutive characters at the end of the string. Since we need the top of the stack to contain the last two characters, we reverse the stack, before entering the loop. Note that the top part of the stack now looks like: `..., C[n-1], C[n], -1`.

The IP's place on the cube is where the `E` is, and it's pointing right. All instructions that have not yet been executed, were replaced by no-ops (full stops).

```
    . .
    . .
A B E . . . . .
. . . . . . . .
    . .
    . .

```

## Phase 2: Character comparison

The stack is `..., C[a-1], C[a], counter`, where `counter` is the counter to increment when the two characters to check (`C[a]` and `C[a-1]`) are equal. The IP first enters this loop at the `S` character, moving right. The `E` character is the position where the IP will end up (pointing right) when `C[a]` and `C[a-1]` do not have the same value, which means that subtracting `C[a]` from `C[a-1]` does not yield `0`, in which case the instruction following the `!` will be skipped (which is a `w`).

```
    . .
    . .
. S q - ! w E .
p ) W . . ; ; .
    . .
    . .

```

Here are the instructions that are executed during a full loop:

```
q-!;;p) # Explanation
q       # Push counter to the bottom of the stack
        #     Stack (counter, ..., C[a-1], C[a])
 -      # Subtract C[a] from C[a-1], which is 0 if both are equal
        #     Stack (counter, ..., C[a-1], C[a], C[a-1]-C[a])
  !     # Leave the loop if C[a-1]-C[a] does not equal 0
   ;;   # Remove result of subtraction and C[a] from stack
        #     Stack (counter, ..., C[a-1])
     p  # Move the bottom of the stack to the top
        #     Stack (..., C[a-1], counter)
      ) # Increment the counter
        #     Stack (..., C[a-1], counter + 1)

```

And then it loops around.

## Phase 3: Print result

Since we left the loop early, the stack looks like this: `counter, ..., C[a-1]-C[a]`. It's easy to print the counter, but we have to increment the counter once because we didn't do it in the last iteration of the loop, and once more because we started counting at `-1` instead of `0`. The path on the cube looks like this, starting at `S`, pointing right. The two no-ops that are executed by the IP are replaced by arrows that point in the direction of the IP.

```
    ) u
    O )
. B . . . S p U
. ) . . @ . . .
    > >
    . .

```

The instructions are executed in the following order. Note that the `B)` instructions at the end change the stack, but don't affect the program, since we are about to terminate it, and we do not use the stack anymore.

```
p))OB)@ # Explanation
p       # Pull the counter to the top
        #     Stack: (..., counter)
 ))     # Add two
        #     Stack: (..., counter + 2)
   O    # Output as number
    B)  # Reverse the stack and increment the top
      @ # End the program

```

# Answer
> 6 votes
# C (gcc), ~~32~~ 29 bytes

```
f(x){x=x%100%11?1:-~f(x/10);}

```

This is a port of my Python answer.

This work with gcc, but the lack of a `return` statement is undefined behavior.

Try it online!

# Answer
> 5 votes
## Python 2, 51 bytes

Takes integer as input. Try it online

```
lambda S:[x==`S`[-1]for x in`S`[::-1]+'~'].index(0)

```

48 bytes for string as input. Try it online

```
lambda S:[x==S[-1]for x in S[::-1]+'~'].index(0)

```

# Answer
> 5 votes
## C#, ~~63~~ 62 bytes

---

**Golfed**

```
i=>{int a=i.Length-1,b=a;while(a-->0&&i[a]==i[b]);return b-a;}

```

---

**Ungolfed**

```
i => {
    int a = i.Length - 1,
        b = a;

    while( a-- > 0 && i[ a ] == i[ b ] );

    return b - a;
}

```

---

**Ungolfed readable**

```
i => {
    int a = i.Length - 1, // Store the length of the input
        b = a ;           // Get the position of the last char

    // Cycle through the string from the right to the left
    //   while the current char is equal to the last char
    while( a-- > 0 && i[ a ] == i[ b ] );

    // Return the difference between the last position
    //   and the last occurrence of the same char
    return b - a;
}

```

---

**Full code**

```
using System;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
         Func<String, Int32> f = i => {
            int a = i.Length - 1, b = a;
            while( a-- > 0 && i[ a ] == i[ b ] );
            return b - a;
         };

         List<String>
            testCases = new List<String>() {
               "14892093",
               "12344444",
               "112311",
               "888888",
               "135866667"
            };

         foreach( String testCase in testCases ) {
            Console.WriteLine( $" Input: {testCase}\nOutput: {f( testCase )}\n" );
         }

         Console.ReadLine();
      }
   }
}

```

---

**Releases**

* **v1.1** \- `- 1 byte` \- Thanks to Kevin's comment.
* **v1.0** \- `63 bytes` \- Initial solution.

---

**Notes**

Nothing to add

# Answer
> 5 votes
# MATL, ~~6~~ 5 bytes

*1 byte saved thanks to @Luis*

```
&Y'O)

```

Try it at **MATL Online**

**Explanation**

```
        % Implicitly grab input as a string
&Y'     % Perform run-length encoding on the string but keep only the second output
        % Which is the number of successive times an element appeared
O)      % Grab the last element from this array
        % Implicitly display

```

# Answer
> 3 votes
## Batch, 91 bytes

```
@set s=-%1
@set n=1
:l
@if %s:~-2,1%==%s:~-1% set s=%s:~,-1%&set/an+=1&goto l
@echo %n%

```

The `-` prevents the test from running off the start of the string.

# Answer
> 3 votes
# Powershell, 41 Bytes

```
for($n="$args";$n[-1]-eq$n[-++$a]){};$a-1

```

straightforward loop backwards until a char doesn't match the last char in the string, return the index of that char -1.

-3 thanks to @AdmBorkBork - using a for loop instead of a while.

# Answer
> 3 votes
# JavaScript (ES6), 34 bytes

```
f=(n,p)=>n%10-p?0:1+f(n/10|0,n%10)

```

Not shorter than the regex solution.

Recursive function which evaluates the digits from right-to-left, stopping when a different digit is encountered. The result is the number of iterations. `p` is `undefined` on the first iteration, which means `n%10-p` returns `NaN` (falsy). After that, `p` equals the previous digit with `n%10`. When the current digit (`n%10`) and the previous (`p`) are different, the loop ends.

# Answer
> 3 votes
# Röda, 12 bytes

```
{count|tail}

```

Try it online!

This is an anonymous function that expects that each character of the input string is pushed to the stream (I think this is valid in spirit of a recent meta question).

It uses two builtins: `count` and `tail`:

1. `count` reads values from the stream and pushes the number of consecutive elements to the stream.
2. `tail` returns the last value in the stream.

# Answer
> 3 votes
## T-SQL, 238 214 Bytes

```
declare @ varchar(max) = '' declare @i int=0, @e int=0, @n int=right(@,1), @m int while (@i<=len(@)) begin set @m=(substring(@,len(@)-@i,1)) if (@n=@m) set @e=@e+1 else if (@i=0) set @e=1 set @i=@i+1 end select @e

```

Or:

```
declare @ varchar(max) = '12345678999999'
declare
    @i int = 0,
    @e int = 0,
    @n int = right(@,1),
    @m int

while (@i <= len(@))
begin
    set @m = (substring(@,len(@)-@i,1))
    if (@n = @m) set @e = @e + 1
    else
    if (@i) = 0 set @e = 1
    set @i = @i + 1
end
select @e

```

# Answer
> 2 votes
## Mathematica, ~~33~~ 30 bytes

*Thanks to Greg Martin for saving 3 bytes.*

```
Tr[1^Last@Split@Characters@#]&

```

Takes input as a string.

Gets the decimal digits (in the form of characters), splits them into runs of identical elements, gets the last run and computes the length with the standard trick of taking the sum of the vector `1^list`.

# Answer
> 2 votes
# Java 7, 78 bytes

```
int c(int n){return(""+n).length()-(""+n).replaceAll("(.)\\1*$","").length();}

```

Try it here.

I tried some things using recursion or a loop, but both ended up above 100 bytes..

# Answer
> 2 votes
# JavaScript (ES6), ~~39~~ ~~38~~ ~~37~~ 27 bytes

```
f=n=>n%100%11?1:1+f(n/10|0)

```

Maybe not shorter than the regex-based solution, but I couldn't resist writing a solution entirely based on arithmetic. The technique is to repeatedly take `n % 100 % 11` and divide by 10 until the result is non-zero, then count the iterations. This works because if the last two digits are the same, `n % 100 % 11` will be `0`.

# Answer
> 2 votes
# Python 3 - ~~50~~ 44 bytes

Full program (in Python 3, `input()` returns a string, no matter the input):

```
g=input();print(len(g)-len(g.rstrip(g[-1])))

```

# Answer
> 2 votes
# Bash \+ Unix utilities, 34 bytes

```
sed s/.*[^${1: -1}].//<<<x$1|wc -c

```

Try it online!

# Answer
> 2 votes
# C (clang), 41 bytes

```
f(x){return x&&x%10-x/10%10?1:f(x/10)+1;}

```

There are already 2 other C solutions, but they both depend on loops. This uses recursion. If the last 2 digits are different then it's 1, otherwise you do 1+ the number of consecutive digits of the number with the last digit removed.

Try it online!

# Answer
> 2 votes
# Haskell, 33 bytes

```
f(h:t)=sum[1|all(==h)t]+f t
f _=0

```

Try it online!

Takes string input. Repeatedly cuts off the first character, and adds 1 if all characters in the suffix are equal to the first one.

# Answer
> 2 votes
# R, 35 bytes

```
rle(rev(charToRaw(scan(,''))))$l[1]

```

Brief explanation

```
                  scan(,'')         # get input as a string
        charToRaw(         )        # convert to a vector of raws (splits the string)
    rev(                    )       # reverse the vector
rle(                         )$l[1] # the first length from run length encoding

```

# Answer
> 2 votes
# Befunge-98, 19 bytes

```
01g3j@.$~:01p-!j$1+

```

Try it online!

This could be made shorter if I managed to only use the stack.

How it works:

```
01g3j@.$~:01p-!j$1+
01g                 ; Get the stored value (default: 32)                 ;
   3j               ; Skip to the ~                                      ;
        ~           ; Get the next character of input                    ;
         :01p       ; Overwrite the stored value with the new char       ;
             -!     ; Compare the old value and the new                  ;
               j$   ; Skip the $ when equal, else pop the counter        ;
                 1+ ; Increment the counter                              ;

; When the input runs out, ~ reflects the IP and we run: ;
   @.$
     $              ; Pop the extraneous value (the stored value) ;
   @.               ; Print the number and exit                   ;

```

# Answer
> 2 votes
# Jelly, 4 bytes

```
ŒrṪṪ

```

Takes input as a string, returns a number.

Try it online!

Relatively simply, `Œr` Run-length encodes the input,  pushes the last pair, then  pushes its second item. Which thus gives us the length of consecutive digits at the end of the string.

# Answer
> 2 votes
# Clojure, 48 bytes

`#(-> (partition-by identity (str %)) last count)`

Usage: `(#(-> (partition-by identity (str %)) last count) 123455)`

`=> 2`

Ungolfed:

```
(defn count-digits [n]
                  (-> (partition-by identity (str n))
                      last
                      count))

```

# Common Lisp, 82 bytes

`(defun c (n) (if (eq (mod n 10) (floor (mod n 100) 10)) (+ 1 (c (floor n 10))) 1))`

Ungolfed:

```
(defun c (n)
  (if (eq (mod n 10)
          (floor (mod n 100) 10))
      (+ 1 (c (floor n 10))) 1))

```

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

```
Ġt

```

Try it Online!

> need to get this to 2 bytes somehow – Razetime

## Explained

```
Ġt
Ġ    # Group the integer into consecutive chunks
 t   # Take the tail of that list
     # The `-l` flag prints the length of TOS

```

# Answer
> 2 votes
## ARM Thumb-2 (no divide instruction/libgcc), 38 bytes

Raw machine code:

```
b530 2400 250a 3401 2200 280a d302 3201
380a e7fa 0001 0010 2d0a bf08 460d 428d
d0f1 1e60 bd30

```

Uncommented asm:

```
        .text
        .arch armv6t2
        .globl dubs
        .thumb
        .thumb_func
dubs:
        push    {r4, r5, lr}
        movs    r4, #0
        movs    r5, #10
.Lloop:
        adds    r4, #1
        movs    r2, #0
.Ldivloop:
        cmp     r0, #10
        blo     .Ldivloop_end
        adds    r2, #1
        subs    r0, #10
        b       .Ldivloop
.Ldivloop_end:
        movs    r1, r0
        movs    r0, r2
        cmp     r5, #10
        it      eq
        moveq   r5, r1
        cmp     r5, r1
        beq     .Lloop
        subs    r0, r4, #1
        pop     {r4, r5, pc}

```

### Explanation

C function signature:

```
// Assume: post_id != 0
uint32_t dubs(uint32_t post_id);

```

First, push registers and set up our dubs counter in r4:

```
dubs:
        push    {r4, r5, lr}
        movs    r4, #0

```

Now, in order to reuse the loop, we use a "magic" value of 10 for the last digit in r5, and set it at the end of the loop.

```
        movs    r5, #10

```

Begin the count by incrementing the dubs counter:

```
.Lloop:
        adds    r4, #1

```

Now, we start our divmod loop to divide the ID by 10 and get the remainder.

The divided ID will be in `r2` and the remainder will be in `r0`.

```
        movs    r2, #0
.Ldivloop:
        cmp     r0, #10
        blo     .Ldivloop_end
        adds    r2, #1
        subs    r0, #10
        b       .Ldivloop

```

That is basically this in C:

```
uint32_t quotient = 0;
while (dividend >= 10) {
    ++quotient;
    dividend -= 10;
}
uint32_t remainder = dividend;

```

This could probably be optimized. We ended up with the registers in the wrong spot, so we have to move things around. Specifically, we want the remainder in `r1` and the divided ID in `r0`.

The biggest problem is dealing with `movs` either clobbering the flags or requiring hi registers. If it didn't do that, I would put it after the `cmp`.

```
.Ldivloop_end:
        movs    r1, r0
        movs    r0, r2

```

Now, we check for that magic number and set the lowest digit to that.

```
        cmp     r5, #10
        it      eq
        moveq   r5, r1

```

Now, check if the new remainder in r1 and loop if it is the same as the last digit.

```
        cmp     r5, r1
        beq     .Lloop

```

Move the dubs count into the return register and return. We are actually one too high so we have to correct it.

```
        subs    r0, r4, #1
        pop     {r4, r5, pc}

```

# Answer
> 1 votes
# C, ~~62~~ 55 bytes

```
i,j;f(n){for(i=0,j=n%10;++i;n/=10)if(j-n%10)return--i;}

```

Try it online!

# Answer
> 1 votes
## REXX, 50 bytes

```
arg ''-1 # 1 n
say length(n)-length(strip(n,T,#))

```

Parse argument with empty string, causing parsing cursor to move to end of argument, then left one step, put remainder (one character) of argument in `#` variable, move to first character and put first word of argument in `n` variable.

Strip trailing characters equivalent to `#` from `n` and compare length to `n`.

# Answer
> 1 votes
# Ruby, ~~28~~ 22 bytes

```
->s{s[/(.)\1*$/].size}

```

Anonymous function that takes the number as a string.

# Answer
> 1 votes
# Octave, 30 bytes

```
@(s)find(flip(diff([0 +s])),1)

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), 53 bytes

```
f=(n,i=1)=>(a=[...n]).pop()==a[a.length-1]?f(a,i+1):i

```

# Answer
> 1 votes
# Japt, 23 bytes

```
¬â l ¥1?Ul :Uw ¬b@X¦UgJ

```

Try it online!

### Explanation:

```
¬â l ¥1?Ul :Uw ¬b@X¦UgJ
¬                         // Split the input into an array of chars
 â                        // Return all unique permutations
   l ¥1                   // Check if the length is equal to 1
       ?                  // If yes, return:
        Ul                //   The length of the input
            :             // Else, return:
             Uw           //   The input, reversed
                ¬         //   Split into an array of chars
                  @       //   Iterate through, where X is the iterative item
                 b        //   Return the first index where:
                   X¦     //     X !=
                     UgJ  //     The last char in the input

```

# Answer
> 1 votes
# Haskell, 36 bytes

## Without import solution (39 bytes)

```
f n=length.takeWhile(==last n)$reverse n

```

~~Note that a pointfree solution is longer (and less understandable):~~ EDIT: since anonymous functions are allowed, let's shave off two bytes which brings us to 39 (still longer than 36):

```
(length.).takeWhile.(==).last<*>reverse

```

## With import solution (36 bytes, 19 without import)

```
import Data.List
f=length.last.group

```

Run like `f "2394398222222"` either way

# Answer
> 1 votes
# Befunge-93, 45 bytes

```
<_v#`0:~
pv>$00p110
p>00g-#v_10g1+10
  @.g01<

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 3 bytes

```
Åγθ

```

Try it online or verify all test cases.

Or alternatively:

```
γθg

```

Try it online or verify all test cases.

**Explanation:**

```
Åγ   # Run-length decode the (implicit) input-integer
     #  i.e. 1333822 → [1,3,1,2]
  θ  # Pop and push the last item
     #  → 2
     # (which is output implicitly as result)

γ    # Split the (implicit) input-integer into parts of subsequent equal digits
     #  i.e. 1333822 → [1,333,8,22]
 θ   # Pop and push the last item
     #  → 22
  g  # Pop and push its length
     #  → 2
     # (which is output implicitly as result)

```

# Answer
> 1 votes
# Pyth, 4 bytes

```
her9

```

Kinda surprised this hasn't been posted yet.

Try it online!

# Answer
> 1 votes
# Ruby `-nl`, 16 bytes

Input is STDIN. Subtracts the position of the start of the dubs sequence from the length of the string (technically, the position of the end of the string).

```
p~/$/-~/(.)\1*$/

```

Try it online!

# Answer
> 1 votes
# Japt, 6 bytes

```
ì òÎÌÊ

```

Try it or run all test cases

```
ì òÎÌÊ     :Implicit input of integer
ì          :To digit array
  ò        :Partition between truthy pairs
   Î       :   Sign of difference
    Ì      :Last element
     Ê     :Length

```

# Answer
> 1 votes
# APL (Dyalog Extended), 9 bytes

```
⊃⍸⌽1,2≠/⍞

```

input as a string

`1,2≠/` 1 concatenated with n-wise reduction with ≠, boolean mask of the starts of sections

reverse

`⊃⍸` index of the first 1

Try it online!

# Answer
> 1 votes
# K (oK), ~~15~~ 12 bytes

```
{+/&\|x=*|x}

```

Try it online!

Takes input as a string.

* `x=*|x` compare each digit to the last digit of the input
* `&\|` "turn off" `1b`s occurring after first `0b`, e.g. `&\|110011b` =\> `110000b`
* `+/` take sum

# Answer
> 1 votes
# Stax, 4 bytes

```
E:GH

```

Run and debug it

# Answer
> 1 votes
## x86\_64 machine code, 24 bytes

Could probably be golfed a bit further.

Input and output is through rax as integers.

```
00000000  6a 0a 5d 31 f6 31 d2 f7  f5 89 d3 ff c6 31 d2 f7  |j.]1.1.......1..|
00000010  f5 39 d3 74 f6 89 f0 c3                           |.9.t....|

```

Disassembly (with explanation):

```
dubs:
  6a 0a                 push   0xa
  5d                    pop    rbp      ; set rbp to 10 (for divison)
  31 f6                 xor    esi,esi  ; zero counter
  31 d2                 xor    edx,edx  ; zero upper dividend
  f7 f5                 div    ebp      ; initial divide (can this be golfed into the other divide?)
  89 d3                 mov    ebx,edx  ; set ebx (repeating digit)
loop:
  ff c6                 inc    esi      ; inc counter
  31 d2                 xor    edx,edx  ; zero upper dividend (gets filled with remainder)
  f7 f5                 div    ebp      ; divide
  39 d3                 cmp    ebx,edx  ; compare repeating digit with digit 'popped'
  74 f6                 jz     loop     ; if equal keep looping
  89 f0                 mov    eax,esi  ; move counter to eax for output
  c3                    ret

```

Full program source to run subroutine:

```
; nasm -felf64 -odubs.o dubs.asm
; ld -odubs dubs.o
; ./dubs; echo $?

bits 64

section .text
    global _start

_start:
    mov rax, 12344444
    call dubs

    mov rdi, rax
    mov rax, 60
    syscall ; exit with return val as exit code

dubs:
    push 10
    pop rbp
    xor esi, esi
    xor edx, edx
    div ebp ; eax quot edx rem
    mov ebx, edx
loop:
    inc esi
    xor edx, edx
    div ebp ; eax quot edx rem
    cmp ebx, edx
    jz loop
    mov eax, esi
    ret

```

# Answer
> 1 votes
# Jelly, 3 bytes

```
ŒɠṪ

```

Try it online!

Well, there’s a 5 byte and a 4 byte Jelly answer, so might as well go for 3 bytes

## How it works

```
ŒɠṪ - Main link. Takes l on the left as a list of digits
Œɠ  - Group adjacent equal values in l and get the lengths of each
  Ṫ - Get the last one

```

# Answer
> 1 votes
# AWK, 44 bytes

```
{for(d=$1%10;$1%10~d;k++)$1=($1-d)/10;$1=k}1

```

This piece of code uses math, so should work only with numbers.

```
{
for(             # $1 is the input, but will be modified during the code.
    d=$1%10;     # before the loop, records the last digit of $1 to _d_,
    $1%10~d;     # and stops if the last digit of $1 is different from _d_.
    k++          # increments 1 to _k_ after each loop.
   )
   $1=($1-d)/10; # removes the last digit of $1 and divides by 10.
                 # this uses less bytes than int($1/10).

$1=k             # after the end of the looping, assigns the count variable _k_
                 # to $1, which will become the output.
}
1                # prints $1

```

Try it online!

---

# AWK, 44 bytes

```
{for(i=n=split($1,a,e);a[i--]~a[n];)$1=n-i}1

```

This code treats the input as string. Works with all kinds of characters.

```
{
for(
    i=n=split($1,a,e); # splits the input to the _a_ array,
                       # using the _e_ empty variable as flag (i.e, a null character)
                       # also sets the number of elements of the array
                       # to the _i_ and _n_ variables

    a[i--]~a[n];       # loops while the _i_ and _n_ elements are equal
                       # this also decrements _i_ by 1 after the evaluation
   )
     $1=n-i            # during each loop, sets the output to n-i
}
1                      # prints $1

```

Try it online!

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

```
ġ

```

Attempt This Online!

## Thunno 2, 3 bytes

```
ġtl

```

Attempt This Online!

#### Explanation

```
     # Implicit input
ġ    # Group consecutive digits together
 t   # Get the last item (also done by t flag)
  l  # And push the length (also done by L flag)
     # Implicit output

```

# Answer
> 1 votes
# Raku, 18 bytes

```
{m/(.)$0*$/.chars}

```

Try it online!

`m/(.)$0*$/` applies a regex to the input argument that matches any number of the same trailing characters. (In Raku, applying a regex to a number implicitly matches against its string representation.) Then `.chars` counts how many characters there are in the match.

# Answer
> 1 votes
# Lua, 36 bytes

```
s=...print(#s:match(~~(s%10)..'+$'))

```

Try it online!

# Answer
> 0 votes
# **PHP 40chars**

(Does not take into account php tags)

```
strlen(preg_match('/(.)\1*$/',$argv[1]))

```

# Answer
> 0 votes
# C#, 49 bytes

```
i=>i.Reverse().TakeWhile(x=>x==i.Last()).Count();

```

Try it here

**Full code**

```
  using System;
  using System.Linq;

  class Program
  {
      static void Main()
      {
          Func<string, int> func = i=>i.Reverse().TakeWhile(x=>x==i.Last()).Count();

          Console.WriteLine(func("14892093"));
          Console.WriteLine(func("12344444"));
          Console.WriteLine(func("112311"));
          Console.WriteLine(func("888888"));
          Console.WriteLine(func("135866667"));
          Console.ReadLine();
      }
  }

```

# Answer
> 0 votes
# Java 7, ~~64~~ 62 bytes

Golfed:

```
int w(int x){int r=1,d=x%10;while((x/=10)%10==d)r++;return r;}

```

Ungolfed:

```
int w(int x)
{
    int r = 1, d = x % 10;
    while ((x /= 10) % 10 == d)
        r++;
    return r;
}

```

Try it online

# Answer
> 0 votes
# Vim - 39

```
ix^[Y$d?[^^R=@@[len(@@)-2]^M]^Mcc^R=len(@2)^M

```

(*^\[*, *^M*s and *^R*s are one char each)

* insert non-number (for *88888* input), copy line, move to the end
* delete searching backwards for a char other then the last char
* replace line with length of deleted text

# Answer
> 0 votes
# , 14 bytes

```
>:i.&1}.~:|.":

```

Try it online!

It's fortunate that the challenge allows a REPL command. As a verb (function) it's 20 bytes:

```
3 :'>:i.&1}.~:|.":y'

```

For arbitrarily large integers, the literal must be suffixed by `x`.

### Explained

Applied right to left, all monadic verbs:

* `":` Format - Stringifies its argument
* `|.` Reverse
* `~:` Nub sieve - Produces a boolean array of 1's each time a new item is introduced, 0 otherwise
* `}.` Behead - Removes first item of array
* `i.&1` Index of - Gets index of first `1`. `i.` is actually a dyadic verb, but `&1` ties right argument to `1`.
* `>:` Increment

# Answer
> 0 votes
# Common Lisp, 72 chars

```
(lambda(i)(do((n i(floor n 10))(c 1(1+ c)))((/= 0(mod(mod n 100)11))c)))

```

Unoglfed

```
(lambda (i)
  (do ((n i (floor n 10))
       (c 1 (1+ c)))
      ((/= 0 (mod (mod n 100) 11)) c)))

```

Explanation

`(/= 0 (mod (mod n 100) 11))`

This checks to see if the last two digits of n are different- if n%100 is not divisible by 11.

```
(do ((n i (floor n 10))
     (c 1 (1+ c)))
    (... c))

```

`do` is a powerful generic looping construct in lisp. Its first argument is a list describing the looping variables. Each element is a list of (variable initial-value step-form) where step-form is evaluated each time through the loop to update that variable. The second argument is a test to perform to end the loop (the test I covered above) and a list of values to return after looping (in this case just `c`, which has been incrementing each time though the loop).

`(lambda (i) ...)` Wraps the operation in an anonymous function that takes the number as an integer.

# Answer
> 0 votes
# x86-16 machine code, IBM PC DOS, ~~22~~ ~~21~~ 20 bytes

**Binary:**

```
00000000: d1ee 8a1c 8d38 8a05 fdf3 aef6 d191 052f  .....8........./
00000010: 0ecd 10c3                                ....

```

Build and test `DUBS.COM` with `xxd -R`.

**Unassembled listing:**

```
D1 EE       SHR  SI, 1              ; SI to command line tail (80H)
8A 1C       MOV  BL, BYTE PTR[SI]   ; BX = input string length
8D 38       LEA  DI, [BX][SI]       ; DI to end of string
8A 05       MOV  AL, BYTE PTR[DI]   ; AL = last char
FD          STD                     ; set LODS to decrement
F3 AE       REPZ SCASB              ; scan [DI] backwards until AL doesn't match
F6 D1       NOT  CL                 ; negate CL to get number of matches + 1
91          XCHG AX, CX             ; AL = CL
05 2F0E     ADD  AX, 0E2FH          ; ASCII convert and adjust, BIOS tty function
CD 10       INT  10H                ; write number to console
C3          RET                     ; return to DOS

```

A standalone PC DOS executable program. Input via command line, output number to console.

**Notes:**

This takes advantage of a few "features" of PC DOS register startup values; specifically `BH = 0`, `CX = 00FFH` and `SI = 100H`. `REPZ` decrements `CX` on every compare operation, so starting at `00FFH` will yield a negative count of reps. It is off-by-one because `REPZ` decrements before comparison, so the first non-match still gets counted. That number is ones-complimented and adjusted by 1 to get the count of matched digits.

Also, since `CH = 0` it's possible to combine `ADD AL, '0'-1` and `MOV AH, 0EH` into a single instruction `ADD AX, 0E2FH` to save 1 byte, since `AH` will be `0`. Old-school SIMD for you!

**I/O:**

---
Tags: code-golf, number, number-theory, counting
---


# Question
Title: How high can you go? (A coding+algorithms challenge)
Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for a challenge which will also stretch your ability to improve an algorithm.

The following code computes a list of length 9. Position `i` in the list counts the number of times at least `i` consecutive zeros were found when computing the inner products between `F` and `S`. To do this exactly, it iterates over all possible lists `F` of length `n` and lists `S` of length `n+m-1`.

```
#!/usr/bin/python
import itertools
import operator

n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
            leadingzerocounts[i] +=1
            i+=1
print leadingzerocounts

```

The output is

> \[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064\]

If you increase n to 10,12,14,16,18,20 using this code it very rapidly becomes far too slow.

**Rules**

* The challenge is to give the correct output for as large an n as possible. Only even values of n are relevant.
* If there is a tie, the win goes to the fastest code on my machine for the largest n.
* I reserve the right not to test code that takes more than 10 minutes.
* You may change the algorithm in any way you like as long as it gives the correct output. In fact **you will have to** change the algorithm to make any decent progress toward winning.
* The winner will be awarded one week from when the question was set.
* The bounty will be awarded when it is due which is a little after when the winner will be awarded.

**My Machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

**Status**.

* **C**. n = 12 in 49 seconds by @Fors
* **Java**. n = 16 in 3:07 by @PeterTaylor
* **C++**. n = 16 in 2:21 by @ilmale
* **Rpython**. n = 22 in 3:11 by @primo
* **Java**. n = 22 in 6:56 by @PeterTaylor
* **Nimrod**. n = 24 in 9:28 seconds by @ReimerBehrends

## **The winner was Reimer Behrends with an entry in Nimrod!**

As a check, the output for n = 22 should be `[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]`.

---

The competition is now over but... I will offer **200 points** for every submission that increases n by 2 (within 10 minutes on my computer) until I run out of points. This offer is open **forever**.

# Answer
# Nimrod (N=22)

```
import math, locks

const
  N = 20
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, int]
  ComputeThread = TThread[int]

var
  leadingZeros: ZeroCounter
  lock: TLock
  innerProductTable: array[0..FMax, int8]

proc initInnerProductTable =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)

initInnerProductTable()

proc zeroInnerProduct(i: int): bool =
  innerProductTable[i] == 0

proc search2(lz: var ZeroCounter, s, f, i: int) =
  if zeroInnerProduct(s xor f) and i < M:
    lz[i] += 1 shl (M - i - 1)
    search2(lz, (s shr 1) + 0, f, i+1)
    search2(lz, (s shr 1) + SStep, f, i+1)

when defined(gcc):
  const
    unrollDepth = 1
else:
  const
    unrollDepth = 4

template search(lz: var ZeroCounter, s, f, i: int) =
  when i < unrollDepth:
    if zeroInnerProduct(s xor f) and i < M:
      lz[i] += 1 shl (M - i - 1)
      search(lz, (s shr 1) + 0, f, i+1)
      search(lz, (s shr 1) + SStep, f, i+1)
  else:
    search2(lz, s, f, i)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for f in countup(base, FMax div 2, numThreads):
    for s in 0..FMax:
      search(lz, s, f, 0)
  acquire(lock)
  for i in 0..M-1:
    leadingZeros[i] += lz[i]*2
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

```

Compile with

```
nimrod cc --threads:on -d:release count.nim

```

(Nimrod can be downloaded here.)

This runs in the allotted time for n=20 (and for n=18 when only using a single thread, taking about 2 minutes in the latter case).

The algorithm uses a recursive search, pruning the search tree whenever a non-zero inner product is encountered. We also cut the search space in half by observing that for any pair of vectors `(F, -F)` we only need to consider one because the other produces the exact same sets of inner products (by negating `S` also).

The implementation uses Nimrod's metaprogramming facilities to unroll/inline the first few levels of the recursive search. This saves a little time when using gcc 4.8 and 4.9 as the backend of Nimrod and a fair amount for clang.

The search space could be further pruned by observing that we only need to consider values of S that differ in an even number of the first N positions from our choice of F. However, the complexity or memory needs of that do not scale for large values of N, given that the loop body is completely skipped in those cases.

Tabulating where the inner product is zero appears to be faster than using any bit counting functionality in the loop. Apparently accessing the table has pretty good locality.

It looks as though the problem should be amenable to dynamic programming, considering how the recursive search works, but there is no apparent way to do that with a reasonable amount of memory.

Example outputs:

N=16:

```
@[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]

```

N=18:

```
@[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

```

N=20:

```
@[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

```

For purposes of comparing the algorithm with other implementations, N=16 takes about 7.9 seconds on my machine when using a single thread and 2.3 seconds when using four cores.

N=22 takes about 15 minutes on a 64-core machine with gcc 4.4.6 as Nimrod's backend and overflows 64-bit integers in `leadingZeros[0]` (possibly not unsigned ones, haven't looked at it).

---

Update: I've found room for a couple more improvements. First, for a given value of `F`, we can enumerate the first 16 entries of the corresponding `S` vectors precisely, because they must differ in exactly `N/2` places. So we precompute a list of bit vectors of size `N` that have `N/2` bits set and use these to derive the initial part of `S` from `F`.

Second, we can improve upon the recursive search by observing that we always know the value of `F[N]` (as the MSB is zero in the bit representation). This allows us to predict precisely which branch we recurse into from the inner product. While that would actually allow us to turn the entire search into a recursive loop, that actually happens to screw up branch prediction quite a bit, so we keep the top levels in its original form. We still save some time, primarily by reducing the amount of branching we are doing.

For some cleanup, the code is now using unsigned integers and fix them at 64-bit (just in case someone wants to run this on a 32-bit architecture).

Overall speedup is between a factor of x3 and x4. N = 22 still needs more than eight cores to run in under 10 minutes, but on a 64-core machine it's now down to about four minutes (with `numThreads` bumped up accordingly). I don't think there's much more room for improvement without a different algorithm, though.

N=22:

```
@[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

```

Updated again, making use of further possible reductions in search space. Runs in about 9:49 minutes for N=22 on my quadcore machine.

Final update (I think). Better equivalence classes for choices of F, cutting runtime for N=22 down to ~~3:19 minutes~~ 57 seconds (edit: I had accidentally run that with only one thread) on my machine.

This change makes use of the fact that a pair of vectors produces the same leading zeros if one can be transformed into the other by rotating it. Unfortunately, a fairly critical low-level optimization requires that the top bit of F in the bit representation is always the same, and while using this equivalence slashed the search space quite a bit and reduced runtime by about one quarter over using a different state space reduction on F, the overhead from eliminating the low-level optimization more than offset it. However, it turns out that this problem can be eliminated by also considering the fact that F that are inverses of one another are also equivalent. While this added to the complexity of the calculation of the equivalence classes a bit, it also allowed me to retain the aforementioned low-level optimization, leading to a speedup of about x3.

One more update to support 128-bit integers for the accumulated data. To compile with 128 bit integers, you'll need `longint.nim` from here and to compile with `-d:use128bit`. N=24 still takes more than 10 minutes, but I've included the result below for those interested.

N=24:

```
@[761152247121980686336, 122682715414070296576, 19793870419291799552, 3193295704340561920, 515628872377565184, 83289931274780672, 13484616786640896, 2191103969198080, 359662314586112, 60521536552960, 10893677035520, 2293940617216, 631498735616, 230983794688, 102068682752, 48748969984, 23993655296, 11932487680, 5955725312, 2975736832, 1487591936, 743737600, 371864192, 185931328, 92965664]

```

---

```
import math, locks, unsigned

when defined(use128bit):
  import longint
else:
  type int128 = uint64 # Fallback on unsupported architectures
  template toInt128(x: expr): expr = uint64(x)

const
  N = 22
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, uint64]
  ZeroCounterLong = array[0..M-1, int128]
  ComputeThread = TThread[int]
  Pair = tuple[value, weight: int32]

var
  leadingZeros: ZeroCounterLong
  lock: TLock
  innerProductTable: array[0..FMax, int8]
  zeroInnerProductList = newSeq[int32]()
  equiv: array[0..FMax, int32]
  fTable = newSeq[Pair]()

proc initInnerProductTables =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)
    if innerProductTable[i] == 0:
      if (i and 1) == 0:
        add(zeroInnerProductList, int32(i))

initInnerProductTables()

proc ror1(x: int): int {.inline.} =
  ((x shr 1) or (x shl (N-1))) and FMax

proc initEquivClasses =
  add(fTable, (0'i32, 1'i32))
  for i in 1..FMax:
    var r = i
    var found = false
    block loop:
      for j in 0..N-1:
        for m in [0, FMax]:
          if equiv[r xor m] != 0:
            fTable[equiv[r xor m]-1].weight += 1
            found = true
            break loop
        r = ror1(r)
    if not found:
      equiv[i] = int32(len(fTable)+1)
      add(fTable, (int32(i), 1'i32))

initEquivClasses()

when defined(gcc):
  const unrollDepth = 4
else:
  const unrollDepth = 4

proc search2(lz: var ZeroCounter, s0, f, w: int) =
  var s = s0
  for i in unrollDepth..M-1:
    lz[i] = lz[i] + uint64(w)
    s = s shr 1
    case innerProductTable[s xor f]
    of 0:
      # s = s + 0
    of -1:
      s = s + SStep
    else:
      return

template search(lz: var ZeroCounter, s, f, w, i: int) =
  when i < unrollDepth:
    lz[i] = lz[i] + uint64(w)
    if i < M-1:
      let s2 = s shr 1
      case innerProductTable[s2 xor f]
      of 0:
        search(lz, s2 + 0, f, w, i+1)
      of -1:
        search(lz, s2 + SStep, f, w, i+1)
      else:
        discard
  else:
    search2(lz, s, f, w)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for fi in countup(base, len(fTable)-1, numThreads):
    let (fp, w) = fTable[fi]
    let f = if (fp and (FSize div 2)) == 0: fp else: fp xor FMax
    for sp in zeroInnerProductList:
      let s = f xor sp
      search(lz, s, f, w, 0)
  acquire(lock)
  for i in 0..M-1:
    let t = lz[i].toInt128 shl (M-i).toInt128
    leadingZeros[i] = leadingZeros[i] + t
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

```
> 20 votes

# Answer
## Java (`n=22`?)

I think most of the answers which do better than `n=16` use a similar approach to this, although they differ in the symmetries they exploit and the way they divide the task between threads.

The vectors defined in the question can be replaced with bit strings, and the inner product with XORing the overlapping window and checking that there are exactly `n/2` bits set (and hence `n/2` bits cleared). There are `n! / ((n/2)!)` (central binomial coefficient) strings of `n` bits with `n/2` bits set (which I call *balanced* strings), so for any given `F` there are that many windows of `S` which give a zero inner product. Moreover, the action of sliding `S` along one and checking whether we can still find an incoming bit which gives a zero inner product corresponds to looking for an edge in a graph whose nodes are the windows and whose edges link a node `u` to a node `v` whose first `n-1` bits are the last `n-1` bits of `u`.

For example, with `n=6` and `F=001001` we get this graph:

and for `F=001011` we get this graph:

Then we need to count for each `i` from `0` to `n` how many paths of length `i` there are, summing over the graphs for every `F`. I think most of us are using depth-first search.

Note that the graphs are sparse: it's easy to prove that each node has in-degree of at most 1 and out-degree of at most one. That also means that the only structures possible are simple chains and simple loops. This simplifies the DFS a bit.

I exploit a couple of symmetries: the balanced strings are closed under bit inverse (the `~` operation in many languages from the ALGOL family), and under bit rotation, so we can group together values of `F` which are related by these operations and only do the DFS once.

```
public class CodeGolf26459v8D implements Runnable {
    private static final int NUM_THREADS = 8;

    public static void main(String[] args) {
        v8D(22);
    }

    private static void v8D(int n) {
        int[] bk = new int[1 << n];
        int off = 0;
        for (int i = 0; i < bk.length; i++) {
            bk[i] = Integer.bitCount(i) == n/2 ? off++ : -1;
        }

        int[] fwd = new int[off];
        for (int i = 0; i < bk.length; i++) {
            if (bk[i] >= 0) fwd[bk[i]] = i;
        }

        CodeGolf26459v8D[] runners = new CodeGolf26459v8D[NUM_THREADS];
        Thread[] threads = new Thread[runners.length];
        for (int i = 0; i < runners.length; i++) {
            runners[i] = new CodeGolf26459v8D(n, i, runners.length, bk, fwd);
            threads[i] = new Thread(runners[i]);
            threads[i].start();
        }

        try {
            for (int i = 0; i < threads.length; i++) threads[i].join();
        }
        catch (InterruptedException ie) {
            throw new RuntimeException("This shouldn't be reachable", ie);
        }

        long surviving = ((long)fwd.length) << (n - 1);
        for (int i = 0; i <= n; i++) {
            for (CodeGolf26459v8D runner : runners) surviving -= runner.survival[i];
            System.out.print(i == 0 ? "[" : ", ");
            java.math.BigInteger result = new java.math.BigInteger(Long.toString(surviving));
            System.out.print(result.shiftLeft(n + 1 - i));
        }
        System.out.println("]");
    }

    public final int n;
    protected final int id;
    protected final int numRunners;
    private final int[] bk;
    private final int[] fwd;

    public long[] survival;

    public CodeGolf26459v8D(int n, int id, int numRunners, int[] bk, int[] fwd) {
        this.n = n;
        this.id = id;
        this.numRunners = numRunners;

        this.bk = bk;
        this.fwd = fwd;
    }

    private int dfs2(int[] graphShape, int flip, int i) {
        if (graphShape[i] != 0) return graphShape[i];

        int succ = flip ^ (fwd[i] << 1);
        if (succ >= bk.length) succ ^= bk.length + 1;

        int j = bk[succ];
        if (j == -1) return graphShape[i] = 1;

        graphShape[i] = n + 1; // To detect cycles
        return graphShape[i] = dfs2(graphShape, flip, j) + 1;
    }

    @Override
    public void run() {
        int n = this.n;
        int[] bk = this.bk;
        int[] fwd = this.fwd;

        // NB The initial count is approx 2^(2n - 1.33 - 0.5 lg n)
        // For n=18 we overflow 32-bit
        // 64-bit is good up to n=32.
        long[] survival = new long[n + 1];
        boolean[] visited = new boolean[1 << (n - 1)];
        int th = 0;
        for (int f = 0; f < visited.length; f++) {
            if (visited[f]) continue;

            int m = 1, g = f;
            while (true) {
                visited[g] = true;
                int ng = g << 1;
                if ((ng >> (n - 1)) != 0) ng ^= (1 << n) - 1;
                if (ng == f) break;
                m++;
                g = ng;
            }

            if (th++ % numRunners != id) continue;

            int[] graphShape = new int[fwd.length];
            int flip = (f << 1) ^ f;
            for (int i = 0; i < graphShape.length; i++) {
                int life = dfs2(graphShape, flip, i);
                if (life <= n) survival[life] += m;
            }
        }

        this.survival = survival;
    }
}

```

On my 2.5GHz Core 2 I get

```
# n=18
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

real    0m3.131s
user    0m10.133s
sys     0m0.380s

# n=20
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

real    1m8.706s
user    4m20.980s
sys     0m0.564s

# n=22
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

real    20m10.654s
user    76m53.880s
sys     0m6.852s

```

Since Lembik's computer has 8 cores and executed my earlier single-threaded program twice as fast as mine, I'm optimistic that it will execute `n=22` in less than 8 minutes.
> 11 votes

# Answer
# C

It is basically just a slightly optimised implementation of the algorithm in the question. It can manage `n=12` within the time limit.

```
#include <stdio.h>
#include <inttypes.h>

#define n 12
#define m (n + 1)

int main() {
    int i;
    uint64_t S, F, o[m] = {0};
    for (S = 0; S < (1LLU << (n + m - 1)); S += 2)
        for (F = 0; F < (1 << (n - 1)); F++)
            for (i = 0; i < m; i++)
                if (__builtin_popcount(((S >> i) & ((1 << n) - 1)) ^ F) == n >> 1)
                    o[i] += 4;
                else
                    break;
    for (i = 0; i < m; i++)
        printf("%" PRIu64 " ", o[i]);
    return 0;
}

```

Test run for `n=12`, including compilation:

```
$ clang -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall fast.c
$ time ./a.out
15502147584 3497066496 792854528 179535872 41181184 9826304 2603008 883712 381952 177920 85504 42560 21280
real    0m53.266s
user    0m53.042s
sys     0m0.068s
$

```

Comment: I just turned my brain on and used some simple combinatorics to calculate that the first value will always be `n! / ((n / 2)!)^2 * 2^(n + m - 1)`. It seems to me that there must be a completely algebraic solution to this problem.
> 6 votes

# Answer
## Java, `n=16`

For any given value of `F` there are `\binom{n}{n/2}` vectors which have a zero inner product with it. So we can build a graph whose vertices are those matching vectors and whose edges correspond to the shifting of `S`, and then we just need to count paths of length up to `n` in the graph.

I haven't tried microoptimising this by replacing conditionals with bitwise operations, but each double-increment of `n` increases running time about 16-fold, so that's not going to make enough of a difference unless I'm pretty close to the threshold. On my machine, I'm not.

```
public class CodeGolf26459 {

    public static void main(String[] args) {
        v3(16);
    }

    // Order of 2^(2n-1) * n ops
    private static void v3(int n) {
        long[] counts = new long[n+1];
        int mask = (1 << n) - 1;
        for (int f = 0; f < (1 << (n-1)); f++) {
            // Find adjacencies
            long[] subcounts = new long[1 << n];
            for (int g = 0; g < (1 << n); g++) {
                subcounts[g] = Integer.bitCount(f ^ g) == n/2 ? 2 : -1;
            }

            for (int round = 0; round <= n; round++) {
                long count = 0;
                // Extend one bit.
                long[] next = new long[1 << n];
                for (int i = 0; i < (1 << n); i++) {
                    long s = subcounts[i];
                    if (s == -1) next[i] = -1;
                    else {
                        count += s;
                        int j = (i << 1) & mask;
                        if (subcounts[j] >= 0) next[j] += s;
                        if (subcounts[j + 1] >= 0) next[j + 1] += s;
                    }
                }
                counts[round] += count << (n - round);
                subcounts = next;
            }
        }

        System.out.print("[");
        for (long count : counts) System.out.print(count+", ");
        System.out.println("]");
    }
}

```

On my 2.5GHz Core 2 I get

```
$ javac CodeGolf26459.java && time java -server CodeGolf26459
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600, ]

real    6m2.663s
user    6m4.631s
sys     0m1.580s

```
> 5 votes

# Answer
## RPython, N=22 ~3:23

Multi-threaded, using a stackless recursive descent. The program accepts two command line arguments: N, and the number of worker threads.

```
from time import sleep

from rpython.rlib.rthread import start_new_thread, allocate_lock
from rpython.rlib.rarithmetic import r_int64, build_int, widen
from rpython.rlib.rbigint import rbigint

r_int8 = build_int('r_char', True, 8)

class ThreadEnv:
  __slots__ = ['n', 'counts', 'num_threads',
               'v_range', 'v_num', 'running', 'lock']

  def __init__(self):
    self.n = 0
    self.counts = [rbigint.fromint(0)]
    self.num_threads = 0
    self.v_range = [0]
    self.v_num = 0
    self.running = 0
    self.lock = None

env = ThreadEnv()

bt_bits = 12
bt_mask = (1<<bt_bits)-1
# computed compile time
bit_table = [r_int8(0)]
for i in xrange(1,1<<bt_bits):
  bit_table += [((i&1)<<1) + bit_table[i>>1]]

def main(argv):
  argc = len(argv)
  if argc < 2 or argc > 3:
    print 'Usage: %s N [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 3:
    env.num_threads = int(argv[2])
  else:
    env.num_threads = 2

  env.n = int(argv[1])
  env.counts = [rbigint.fromint(0)]*env.n
  env.lock = allocate_lock()

  v_range = []
  v_max = 1<<(env.n-1)
  v_num = 0
  v = (1<<(env.n>>1))-1
  while v < v_max:
    v_num += 1
    v_range += [v]
    if v&1:
      # special case odd v
      s = (v+1)&-v
      v ^= s|(s>>1)
    else:
      s = v&-v
      r = v+s
      # s is at least 2, skip two iterations
      i = 3
      s >>= 2
      while s:
        i += 1
        s >>= 1
      v = r|((v^r)>>i)
  env.v_range = v_range
  env.v_num = v_num

  for i in xrange(env.num_threads-1):
    start_new_thread(run,())

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.05)

  result = []
  for i in range(env.n):
    result += [env.counts[i].lshift(env.n-i+3).str()]
  result += [env.counts[env.n-1].lshift(3).str()]
  print result
  return 0

def run():
  with env.lock:
    v_start = env.running
    env.running += 1

  n = env.n
  counts = [r_int64(0)]*n
  mask = (1<<n)-1
  v_range = env.v_range
  v_num = env.v_num
  z_count = 1<<(n-2)

  for i in xrange(v_start, v_num, env.num_threads):
    v = v_range[i]
    counts[0] += z_count
    counts[1] += v_num
    r = v^(v<<1)
    for w in v_range:
      # unroll counts[2] for speed
      # ideally, we could loop over x directly,
      # rather than over all v, only to throw the majority away
      # there's a 2x-3x speed improvement to be had here...
      x = w^r
      if widen(bit_table[x>>bt_bits]) + widen(bit_table[x&bt_mask]) == n:
        counts[2] += 1
        x, y = v, x
        o, k = 2, 3
        while k < n:
          # x = F ^ S
          # y = F ^ (S<<1)
          o = k
          z = (((x^y)<<1)^y)&mask
          # z is now F ^ (S<<2), possibly xor 1
          # what S and F actually are is of no consequence

          # the compiler hint `widen` let's the translator know
          # to store the result as a native int, rather than a signed char
          bt_high = widen(bit_table[z>>bt_bits])
          if bt_high + widen(bit_table[z&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z
            k += 1
          elif bt_high + widen(bit_table[(z^1)&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z^1
            k += 1
          else: k = n

  with env.lock:
    for i in xrange(n):
      env.counts[i] = env.counts[i].add(rbigint.fromrarith_int(counts[i]))
    env.running -= 1

def target(*args):
  return main, None

```

---

**To Compile**

Make a local clone of the PyPy repository using mercurial, git, or whatever you prefer. Type the following incantation (assuming the above script is named `convolution-high.py`):

```
$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution-high.py

```

where `%PYPY_REPO%` represents an environment variable pointing to the repository you just cloned. Compilation takes about one minute.

---

**Sample Timings**

N=16, 4 threads:

```
$ timeit convolution-high-c 16 4
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]
Elapsed Time:     0:00:00.109
Process Time:     0:00:00.390

```

N=18, 4 threads:

```
$ timeit convolution-high-c 18 4
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]
Elapsed Time:     0:00:01.250
Process Time:     0:00:04.937

```

N=20, 4 threads:

```
$ timeit convolution-high-c 20 4
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]
Elapsed Time:     0:00:15.531
Process Time:     0:01:01.328

```

N=22, 4 threads:

```
$ timeit convolution-high-c 22 4
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
Elapsed Time:     0:03:23.156
Process Time:     0:13:25.437

```
> 5 votes

# Answer
# Python 3.3, N = 20, 3.5min

Disclaimer: my intention is **NOT** to post this as my own answer, since the algorithm I'm using is only a shameless port from primo's RPython solution. My purpose here is only to show what you can do in Python if you combine the magic of **Numpy** and **Numba** modules.

Numba explained in short:

> Numba is an just-in-time specializing compiler which compiles annotated Python and NumPy code to LLVM (through decorators). http://numba.pydata.org/

**Update 1**: I noticed after tossing the numbers around that we can simply skip some of the numbers completely. So now **maxf** becomes **(1 \<\< n) // 2** and **maxs** becomes **maxf**2\**. This will speed up the process quite a bit. n = 16 now takes only ~48s (down from 4,5min). I also have another idea which I'm going to try and see if I can make it go a little faster.

**Update 2:** Changed algorithm (primo's solution). While my port does not yet support multithreading it is pretty trivial to add. It is even possible to release CPython GIL using Numba and ctypes. This solution, however, runs very fast on single core too!

```
import numpy as np
import numba as nb

bt_bits = 11
bt_mask = (1 << bt_bits) - 1
bit_table = np.zeros(1 << bt_bits, np.int32)

for i in range(0, 1 << bt_bits):
    bit_table[i] = ((i & 1) << 1) + bit_table[i >> 1]

@nb.njit("void(int32, int32, int32, int32, int64[:], int64[:])")
def run(n, m, start, re, counts, result):
    mask = (1 << n) - 1

    v_max = (1 << n) // 2
    rr = v_max // 2

    v = (1 << (n >> 1)) - 1
    while v < v_max:
        s = start

        while s < rr:
            f = v ^ s
            counts[0] += 8
            t = s << 1
            o, j = 0, 1

            while o < j and j < m:
                o = j
                w = (t ^ f) & mask
                bt_high = bit_table[w >> bt_bits]

                if bt_high + bit_table[w & bt_mask] == n:
                    counts[j] += 8
                    t <<= 1
                    j += 1
                elif bt_high + bit_table[(w ^ 1) & bt_mask] == n:
                    counts[j] += 8
                    t = (t | 1) << 1
                    j += 1
                    s += re

            s = v & -v
            r = v + s
            o = v ^ r
            o = (o >> 2) // s
            v = r | o

    for e in range(m):
        result[e] += counts[e] << (n - e)

```

And finally:

```
if __name__ == "__main__":
    n = 20
    m = n + 1

    result = np.zeros(m, np.int64)
    counts = np.zeros(m, np.int64)

    s1 = time.time() * 1000
    run(n, m, 0, 1, counts, result)
    s2 = time.time() * 1000

    print(result)
    print("{0}ms".format(s2 - s1))

```

This runs on my machine in 212688ms or ~3.5min.
> 3 votes

# Answer
# C++ N=16

I'm testing on a EEEPC with an atom.. my time don't make a lot of sense. :D
The atom solve n=14 in 34 seconds. And n=16 in 20 minutes. I want to test n = 16 on OP pc. I'm optimistic.

The ideas is that every time we find a solution for a given F we have found 2^i solution because we can change the lower part of S leading to the same result.

```
#include <stdio.h>
#include <cinttypes>
#include <cstring>

int main()
{
   const int n = 16;
   const int m = n + 1;
   const uint64_t maxS = 1ULL << (2*n);
   const uint64_t maxF = 1ULL << n;
   const uint64_t mask = (1ULL << n)-1;
   uint64_t out[m]={0};
   uint64_t temp[m] = {0};
   for( uint64_t F = 0; F < maxF; ++F )
   {
      for( uint64_t S = 0; S < maxS; ++S )
      {
         int numSolution = 1;
         for( int i = n; i >= 0; --i )
         {
            const uint64_t window = S >> i;
            if( __builtin_popcount( mask & (window ^ F) ) == (n / 2) )
            {
               temp[i] += 1;
            } else {
               numSolution = 1 << i;
               S += numSolution - 1;
               break;
            }
         }
         for( int i = n; i >= 0; --i )
         {
            out[i] += temp[i]*numSolution;
            temp[i] = 0;
         }
      }
   }
   for( int i = n; i >= 0; --i )
   {
      uint64_t x = out[i];
      printf( "%lu ", x );
   }
   return 0;
}

```

to compile:

gcc 26459.cpp -std=c++11 -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459
> 2 votes

# Answer
### JAVASCRIPT n:12

In my computer it took 231.242 seconds. In the Demo I'm using webworkers to prevent freezing the browser. This sure can be further improved with parallel workers. I know JS don't stand a chance in this challenge but I did it for fun!

**Click to run the online Demo**

```
var n = 8;
var m = n + 1;
var o = [];
var popCount = function(bits) {
  var SK5  = 0x55555555,
      SK3  = 0x33333333,
      SKF0 = 0x0f0f0f0f,
      SKFF = 0xff00ff;

  bits -= (bits >> 1) & SK5;
  bits  = (bits & SK3) + ((bits >> 2) & SK3);
  bits  = (bits & SKF0) + ((bits >> 4) & SKF0);
  bits += bits >> 8;

  return (bits + (bits >> 15)) & 63;
};
for(var S = 0; S < (1 << n + m - 1); S += 2){
  for(var F = 0; F < (1 << n - 1); F += 1){
    for (var i = 0; i < m; i++){
      var c = popCount(((S >> i) & ((1 << n) - 1)) ^ F);
      if(c == n >> 1){
        if(!o[i]) o[i] = 0;
        o[i] += 4;
      } else break;
    }
  }
}
return o;

```
> 2 votes

# Answer
# Rust

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

Try it online!

### `src/main.rs`

```
fn main() {
    const N: u64 = 8;
    const M: usize = (N + 1) as usize;
    const MAX_S: u64 = 1 << (2 * N);
    const MAX_F: u64 = 1 << N;
    const MASK: u64 = (1 << N) - 1;

    let mut out = [0; M];
    let mut temp = [0; M];

    for f in 0..MAX_F {
        let mut s = 0;
        while s < MAX_S {
            let mut num_solution = 1;
            for i in (0..=N).rev() {
                let window = s >> i;
                if (MASK & (window ^ f)).count_ones() == (N / 2) as u32 {
                    temp[i as usize] += 1;
                } else {
                    num_solution = 1 << i;
                    s += num_solution - 1;
                    break;
                }
            }
            for i in (0..=N).rev() {
                out[i as usize] += temp[i as usize] * num_solution;
                temp[i as usize] = 0;
            }
            s += 1;
        }
    }

    for i in (0..=N).rev() {
        let x = out[i as usize];
        print!("{} ", x);
    }
}

```

### Build and running

```
# win10 environment

$ set Copt-level=3
$ set Clto=fat
$ set Ctarget-cpu=native
$ cargo build --release
$ cargo run --release

```
> 2 votes

# Answer
# Fortran: n=12

I just made a quick'n'dirty version in Fortran, no optimizations except OpenMP. It should squeeze in at just below 10 minutes for n=12 on the OPs machine, it takes 10:39 on my machine which is sligthly slower.

64-bit integers have a negative performance impact indeed; guess I would have to rethink the whole algorithm for this to be much faster. Don't know if I'm going to bother, I think I'll rather spend some time thinking up a good challenge that's more to my own tastes. If anyone else wants to take this and run with it, go ahead :)

```
program golf
use iso_fortran_env
implicit none
integer, parameter ::  n=12
integer :: F(n), S(2*n)
integer(int64) :: leadingzerocounts(n+1)
integer :: k
integer(int64) :: i,j,bindec,enc

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,2**(2*n)-1
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=2*n,1,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j)=1
      enc=enc-bindec
    else
      S(j)=-1
    endif
  end do
  do j=0,2**(n)-1
    ! Convert j into the array F with -1s and 1s
    enc=j
    do k=n,1,-1
      bindec=2**(k-1)
      if (enc-bindec .ge. 0) then
        F(k)=1
        enc=enc-bindec
      else
        F(k)=-1
      endif
    end do
    ! Compute dot product
    do k=1,n+1
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end

```
> 1 votes

# Answer
# Lua: n = 16

Disclaimer: my intention is NOT to post this as my own answer, since the algorithm I'm using is shamelessly stolen from Anna Jokela's clever answer. which was shamelessly stolen from ilmale's clever answer.

Besides, it's not even valid - it has inaccuracies caused by floating point numbers (it would be better if Lua would support 64-bit integers). However, I'm still uploading it, just to show how fast this solution is. It's a dynamic programming language, and yet I can calculate n = 16 in reasonable time (1 minute on 800MHz CPU).

Run with LuaJIT, standard interpreter is too slow.

```
local bit = require "bit"
local band = bit.band
local bor = bit.bor
local bxor = bit.bxor
local lshift = bit.lshift
local rshift = bit.rshift

-- http://stackoverflow.com/a/11283689/736054
local function pop_count(w)
    local b1 = 1431655765
    local b2 = 858993459
    local b3 = 252645135
    local b7 = 63

    w = band(rshift(w, 1), b1) + band(w, b1)
    w = band(rshift(w, 2), b2) + band(w, b2)
    w = band(w + rshift(w, 4), b3)
    return band(rshift(w, 24) + rshift(w, 16) + rshift(w, 8) + w, b7)
end

local function gen_array(n, value)
    value = value or 0
    array = {}
    for i = 1, n do
        array[i] = value
    end
    return array
end

local n = 16
local u = math.floor(n / 2)
local m = n + 1
local maxf = math.floor(lshift(1, n) / 2)
local maxs = maxf ^ 2
local mask = lshift(1, n) - 1

local out = gen_array(m, 0)
local temp = gen_array(m, 0)

for f = 0, maxf do
    local s = 0
    while s <= maxs do
        local num_solution = 1

        for i = n, 0, -1 do
            if pop_count(band(mask, bxor(rshift(s, i), f))) == u then
                temp[i + 1] = temp[i + 1] + 8
            else
                num_solution = lshift(1, i)
                s = s + num_solution - 1
                break
            end
        end

        for i = 1, m do
            out[i] = out[i] + temp[i] * num_solution
            temp[i] = 0
        end

        s = s + 1
    end
end

for i = m, 1, -1 do
    print(out[i])
end

```
> 1 votes

---
Tags: code-challenge, fastest-code
---