21
\$\begingroup\$

This is a cross-post of a problem I posted to anarchy golf: http://golf.shinh.org/p.rb?tails

Given two integers \$ n \$ and \$ k \$ \$ (0 \le k \le n) \$, count the number of combinations of \$ n \$ coin tosses with at least \$ k \$ tails in a row.

For example, if \$ n = 3 \$ and \$ k = 2 \$, the answer is \$ 3 \$:

HHH ❌
HHT ❌
HTH ❌
HTT ✔️
THH ❌
THT ❌
TTH ✔️
TTT ✔️

For convenience sake, you do not need to handle the case where \$ n = k = 0 \$.

Rules

  • The input must take in two integers \$ n \$ and \$ k \$, and output the answer as a single integer
  • Inaccuracies due to integer overflow are acceptable, but floating point errors are prohibited
  • As usual for , the shortest code in bytes wins

Test Cases

 n,  k  ->  ans
---------------
 1,  0  ->  2
 1,  1  ->  1
 2,  0  ->  4
 2,  1  ->  3
 2,  2  ->  1
 3,  1  ->  7
 3,  2  ->  3
 3,  3  ->  1
 5,  2  ->  19
 6,  4  ->  8
 9,  2  ->  423
12,  0  ->  4096
13,  5  ->  1262
14,  8  ->  256
16,  7  ->  2811

More terms are listed under OEIS A109435.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ "For example, if n=3 and k=2, the answer is 2:" but you then go on to quote the correct value of 3 in your test cases. \$\endgroup\$
    – Neil
    Jun 12 at 6:49
  • \$\begingroup\$ @Neil Fixed, thanks. I changed the example case last minute and forgot to update the answer as well.. \$\endgroup\$ Jun 12 at 7:01

24 Answers 24

12
\$\begingroup\$

Python, 50 bytes

lambda n,k:sum(k*"1"in bin(i)for i in range(2**n))

Attempt This Online!

Brute-force solution seems to be the shortest.


Python, 67 bytes

lambda n,k:2**n-(g:=lambda a:a*k>0and(a<3or g(a-1)*2-g(a+~k)))(n+2)

Attempt This Online!

-11 bytes thanks to Neil.

More mathematical answer.

$$ f(n, k) = 2^n - k \operatorname{-bonacci}(n+k) \\ k \operatorname{-bonacci}(n) = \begin{cases} 0 & n < k-1 \\ 1 & n = k-1 \\ \sum^k_{i=1} k \operatorname{-bonacci}(n-i) & n > k-1 \end{cases} $$

\$\endgroup\$
1
  • \$\begingroup\$ lambda n,k:2**n-(g:=lambda a:a*k>0and(a<3or g(a-1)*2-g(a+~k)))(n+2) saves 11 bytes and should be much faster. \$\endgroup\$
    – Neil
    Jun 12 at 17:39
8
\$\begingroup\$

x86-64 machine code, 28 bytes

31 C0 99 52 89 F1 FF C9 78 07 D1 EA 72 F8 75 F4 41 FF C0 5A FF C2 0F A3 FA 73 E8 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes n in EDI and k in ESI and returns the answer in EAX.

In assembly:

f:  xor eax, eax
    cdq
a:  push rdx
b:  mov ecx, esi
c:  dec ecx
    js d
    shr edx, 1
    jc c
    jnz b
    .byte 0x41
d:  inc eax
    pop rdx
    inc edx
    bt edx, edi
    jnc a
    ret
\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1 for skipping inc with 0x41. \$\endgroup\$
    – xiver77
    Jun 12 at 18:20
7
\$\begingroup\$

Vyxal s, 13 9 8 bytes

EƛbĠṠ⁰≥a

Try it Online!

A very neat little answer I'm very happy with.

Explained

EƛbĠṠ⁰≥a
Eƛ       # to each item in the range [1, 2 ** N)
  bĠṠ    #   get the sums of consecutive digits of the binary representation of that number
     ⁰≥a #   are any of those greater than K? This is essentially getting all consecutive runs of flips and getting there length. Works because there's only 1s and 0s
# the s flag sums that list. 
\$\endgroup\$
7
\$\begingroup\$

Python, 55 bytes

f=lambda n,k:n>=k and 2*f(n-1,k)-(-1<<n>>-~k)-f(n+~k,k)

Attempt This Online!

Slightly longer than @pxeger's Python answer but more efficient.

How?

Uses the recurrence

\$f(n,k)=2f(n-1,k)+2^{n-k-1}-f(n-k-1,k)\qquad(n>k)\$

which is obtained by counting words that have k consecutive 1's somewhere in the first n-1 places, words that end in a 0 followed by k 1's and the overlap of these two groups.

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES7), 59 bytes

Expects (n)(k).

Fully bitwise because binary string manipulation in JS is too verbose.

(n,i=1<<n)=>g=k=>i--&&(h=m=>i&m^m?h(m*2):m<=i)(2**k-1)+g(k)

Try it online!


JavaScript (ES7), 38 bytes

Saved 2 bytes thanks to @Neil

Expects (k)(n). Returns true for 1.

Uses loopy walt's recursion formula.

k=>g=n=>n>k?2*g(--n)-g(n-=k)+2**n:n==k

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Having only just finished golfing @pxeger's Python answer it would have been 53 bytes in ES7: k=>n=>2**n-(g=a=>a*k>0&&(a<3||g(a-1)*2-g(a+~k)))(n+2) \$\endgroup\$
    – Neil
    Jun 12 at 17:44
  • 1
    \$\begingroup\$ k=>g=n=>n-k?n>k&&2*g(--n)-g(n-=k)+2**n:1 saves 2 bytes, although it requires ES7. \$\endgroup\$
    – Neil
    Jun 12 at 18:07
6
\$\begingroup\$

PARI/GP, 40 bytes

k->g(n,r=k)=if(!r,2^n,n,g(n--,r--)+g(n))

Attempt This Online!

A port of @tsh's JavaScript answer.


PARI/GP, 42 bytes

k->n->(y=1-x)/(y-=x)/(x+y/x^k)%x^(n+1)\x^n

Attempt This Online!

According to OEIS, the generating function for column \$k\$ is \$\frac{x^k}{(1-\sum_{i=1}^k x^i)(1-2x)}\$, which could be simplified to \$\frac{(1-x)}{(1-2x)(x+(1-2x)/x^k)}\$.

\$\endgroup\$
1
  • \$\begingroup\$ nice use of generating functions \$\endgroup\$
    – qwr
    Jun 13 at 3:11
5
\$\begingroup\$

C (standard compliant), 78 bytes

int f(int n,int k,int c){return n?n+c-k?k-c?f(n-1,k,0)+f(n-1,k,c+1):1<<n:1:0;}

For the readable version:

int f(int n,int k,int c){
    if(n==0)return 0; // no more coin flip left => no possible path
    if(n==(k-c))return 1; // last coin flip and 1 tail is lacking
    if(k==c)return 1<<n; // we have done k tails in a row, any path is a good path, and there are 2^n
    return f(n-1,k,0) // possible paths if we get a head
    +f(n-1,k,c+1); // possible paths if we get a tail
}
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in C page for ways you can golf your program. You might also want to link an online interprter like Try It Online so people can test your code. \$\endgroup\$
    – emanresu A
    Jun 14 at 9:41
  • \$\begingroup\$ Welcome also from me. You can sometimes (usually) save some bytes by dropping the return keyword and relying on the hacky property of C functions to return the last assignment, and save some more by skipping declaring ints (which is default) like this... (although both of these would probably counteract the 'standard compliant' aspect...) \$\endgroup\$ Jun 14 at 12:58
5
\$\begingroup\$

K (ngn/k), 21 19 bytes

-2 bytes saved thanks to a suggestion by coltim on another answer.

Enumerates all binary length-n sequences and counts the ones with runs of at least k 1s.

{+/y<|/1(1+*)\!x#2}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 8 bytes

1xẇⱮSɓ2ṗ

Try it online!

\$k\$ on the left, \$n\$ on the right.

   Ɱ        For each
     ɓ2ṗ    sequence of n 1s and 2s,
  ẇ         does it contain as a sublist
1x          k 1s?
    S       Sum.
\$\endgroup\$
4
\$\begingroup\$

Factor + sequences.repeating, 58 bytes

[ "1"swap cycle swap 2^ iota [ >bin subseq? ] with count ]

Try it online!


Longer but much cooler:

Factor, 67 bytes

[| n k | n 2^ ""n [ dup k short tail* sum suffix ] times last - ]

Try it online!

\$2^n\$ minus the \$(n+k-1)\$th k-bonacci number.

Example:

\$n=6, k=4\$

The tetranacci sequence begins: \$0, 1, 1, 2, 4, 8, 15, 29, \color{red}{56}\$

\$2^6-56=8\$

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 89 88 bytes

m;r;a;b;c;f(n,k){for(c=b=1<<n;b--;c-=m<k)for(a=b,m=r=0;a;m=r>m?r:m)r+=a&1?:-r,a/=2;m=c;}

Try it online!

Saved a byte thanks to ceilingcat!!!

\$\endgroup\$
0
3
\$\begingroup\$

APL(Dyalog Unicode), 28 bytes SBCS

{1⊥⍵≤⌈/∘(≢¨⊆⍨)⍤1⍉(⍺⍴2)⊤⍳2*⍺}

Try it on APLgolf!

Alternatively (same length): {1⊥(∨/(⍵⍴1)⍷⊢)⍤1⍉(⍺⍴2)⊤⍳2*⍺}

\$\endgroup\$
3
\$\begingroup\$

Retina, 39 bytes

.+,(.+)
<$1*1>
"$+"+%`$
0$"1
<(.*)>.*\1

Try it online! No test suite due to the way the program uses history. Explanation:

.+,(.+)
<$1*1>

Replace the input with a string of k 1s wrapped in <>s.

"$+"+

Repeat n times.

%`$
0$"1

Duplicate each row, appending 0 and 1 to each copy respectively.

<(.*)>.*\1

Count the number of rows where the binary portion contains k 1s.

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 8 bytes

TIã$×δåO

Try it online or verify all test cases or try it step-by-step.

Explanation:

T        # Push 10
 I       # Push the first input `n`
  ã      # Take the cartesian product of the two, to create all possible n-sized strings
         # containing 0s and 1s
   $     # Push 1 and the second input `k`
    ×    # Repeat the 1 `k` amount of times as string
     δ   # Map over the list we created earlier, using this "1"-string as argument:
      å  #  Check if the "1"-string is a substring of the string we're mapping over
       O # Sum to get the amount of truthy values
         # (which is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 94 bytes

.+,(.+)
1$&$*0;$&$*11;$1$*,1,
+`1;1*,(((1)|,)*)
;$1$#3$*1,
+`^(1+)0
$1$1
r`\2;;(1*,)*(1*),$

1

Try it online! Link includes test cases. Explanation:

.+,(.+)
1$&$*0;$&$*11;$1$*,1,

Create 2ⁿ in binary, n+1 in unary, then a list of k 0s and a 1.

+`1;1*,(((1)|,)*)
;$1$#3$*1,

Repeat n+1 times, drop the first element of the list, and append the sum of the remaining elements. This calculates the n+1th k-bonacci number.

+`^(1+)0
$1$1

Convert the 2ⁿ from binary into unary.

   r`\2;;(1*,)*(1*),$

Subtract the n+1th k-bonacci number from 2ⁿ.

1

Convert to decimal.

Rather than trying to count the number of n coin tosses with at least k tails in a row, it's easier to consider the number of n coin tosses that do not have k tails in a row. By considering them grouped by the number of tails that they end with, it's possible to determine a recurrence relation for the number of rows. For example, with k=3:

  • For 0 coin tosses, 1 ends in 0 tails, 0 end in 1 tails, and 0 end in 2 tails. Total 1 matching row.
  • For 1 coin toss, 1 ends in 0 tails, 1 ends in 1 tails, and 0 end in 2 tails. Total 2 matching rows.
  • For 2 coin tosses, 2 end in 0 tails, 1 ends in 1 tails, and 1 ends in 2 tails. Total 4 matching rows.
  • For 3 coin tosses, 4 end in 0 tails, 2 end in 1 tails, and 1 ends in 2 tails. Total 7 matching rows.
  • For 4 coin tosses, 7 end in 0 tails, 4 end in 1 tails, and 2 end in 2 tails. Total 13 matching rows.
  • For n coin tosses:
    • The number that end in 0 tails is the total for n-1 coin tosses, since the value is simply that plus an extra toss of heads.
    • The number that end in 1 tails is the number that end in 0 tails for n-1 coin tosses, with each row having an extra toss of tails. However, this is also the total for n-2 coin tosses.
    • The number that end in 2 tails is the number that end in 1 tails for n-1 coin tosses, with each row having an extra toss of tails. Recursively, we see that this is also the total for n-3 coin tosses.
    • The total is the sum of these which is also the total of the previous three totals. Thus, this forms a 3-binacci sequence.

In general, the number of n coin tosses that do not have k tails in a row is a k-binacci sequence.

The number of n coin tosses with at least k tails in a row plus the number of n coin tosses that do not have k tails in a row is of course the total possible number of rows, 2ⁿ.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 39 bytes

k=>g=(n,r=k)=>r?n&&g(--n,--r)+g(n):2**n

Try it online!

k=>    // Number of tails required in a row
g=(
  n,   // Number of coins we will flip
  r=k  // Number of tails still required in a row
)=>
  r?   // Do we still require tails?
   n&& // And we have more coins can flip?
    g(--n,--r)+ // Luckily, tail this time
    g(n):       // Nope, head this time
  2**n // We don't care what we get from remaining coins
\$\endgroup\$
3
\$\begingroup\$

R, 72 68 bytes

Edit: -4 bytes thanks to @Dominic van Essen.

\(n,k)sum(sapply(1:2^n-1,\(x,r=rle(intToBits(x)>0))any(r$l*r$v>=k)))

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ 68 bytes... \$\endgroup\$ Jun 13 at 12:12
  • \$\begingroup\$ Ah, that's the fix for k=1 I was looking for. Thanks, @DominicvanEssen! \$\endgroup\$
    – pajonk
    Jun 13 at 13:43
3
\$\begingroup\$

Pip, 14 bytes

0<1XbNTB_MS,Ea

Attempt This Online!

Brute force, same concept as pxeger's Python answer.

-5 bytes thanks to DLosc

\$\endgroup\$
1
  • \$\begingroup\$ Since you're using a lambda expression for your function, you can use b directly rather than yanking it first. That, combined with a couple other golfs, gets you down to 14 bytes. \$\endgroup\$
    – DLosc
    Jun 15 at 18:46
2
\$\begingroup\$

Burlesque, 36 bytes

s11rzjCBg1{{gw:pd{-]g1>=}fl}fl}qL[IE

Try it online!

s1     # Save k
1rz    # [0, 1]
jCB    # Combinations up to n
g1     # Get k
{      # Catch k == 0
 {gw   # Group with length ([1, 1, 0] -> [[2, 1], [1, 0]])
  :pd  # Filter for tails
  {    # Filter
   -]  # Head
   g1  # k
   >=  # Greater than or equal
  }
  fl   # Count matches
 }
 fl    # Count matches
}
qL[    # Length of combinations (when k == 0)
IE     # If else
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 15 bytes

NθILΦX²N№⍘ι²×θ1

Try it online! Link is to verbose version of code. Takes k as the first input and n as the second input. Explanation: Uses brute force, so takes exponential time in n.

Nθ              Input `k` as an integer
      ²         Literal integer `2`
     X          Raised to power
       N        Input `n` as an integer
    Φ           Filtered where
          ι     Current value
         ⍘      Converted to base
           ²    Literal integer `2`
        №       Count i.e. contains
              1 Literal string `1`
            ×   Repeated by
             θ  Input `k`
   L            Take the length
  I             Cast to string
                Implicitly print

27 bytes for an efficient version (approximately linear time):

NθNη⊞υ¹F⊕θ⊞υ↨¹✂⮌υ⁰η¹I⁻X²θ⊟υ

Try it online! Link is to verbose version of code. Takes n as the first input and k as the second input. Explanation:

NθNη

Input n and k.

⊞υ¹

Start with the zeroth term of the k-bonacci sequence.

F⊕θ⊞υ↨¹✂⮌υ⁰η¹

Calculate n+1 additional terms.

I⁻X²θ⊟υ

Subtract the n+1th term from 2ⁿ.

\$\endgroup\$
2
\$\begingroup\$

Perl 5 -pl, 35 bytes

$b=<>;$_=grep/T{$b}/,glob"{H,T}"x$_

Try it online!

\$\endgroup\$
1
2
\$\begingroup\$

MATLAB, 71 bytes

function f(n,k),sum(contains(string(dec2bin(0:2^n-1)),repmat('1',1,k)))

The binary representation of all numbers from 0-2^n-1 will give each combination of coin flips. From that, I can search the resulting string vector for repeated instances of 1 ( my choice for tails) that are at least k long and sum the logical array for the result.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Not sure if '1'(1+~(1:k)) works in MATLAB (it does in Octave). Also can this be an anonymous function, I think? \$\endgroup\$
    – Giuseppe
    Jun 20 at 14:18
2
\$\begingroup\$

Excel, 49 bytes

=COUNT(FIND(REPT(1,B2),BASE(SEQUENCE(2^A2)-1,2)))

Input for n is in A2 and k is in B2.

  • SEQUENCE(2^A2)-1 creates an array from 0 to (2^n)-1.
  • BASE(~,2)) converts that array to binary.
  • REPT(1,B2) creates a string of k 1s.
  • FIND(REPT(~),BASE(~)) tries to find that repeated string in each binary element in the array. This returns an array of integers (if it's found in that element) and errors (if it's not).
  • COUNT(FIND(~)) counts the numbers in that array.

Screenshot

\$\endgroup\$
2
\$\begingroup\$

BQN, 20 bytes

{+´⥊∨´¨∧´˘¨𝕩⊸↕¨↕𝕨⥊2}

-1 byte thanks to @Razetime!

Try it here!

Explanation

  • ↕𝕨⥊2 generate binary sequences of length n
  • 𝕩⊸↕¨ convert each binary sequence to subsequences of length k
    • example: 1010 with k=3 becomes 101, 010
  • ∨´¨∧´˘¨ AND each subsequence, then OR each result
  • +´⥊ sum to get total number of 1s
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 2¨↕𝕨𝕨⥊2 \$\endgroup\$
    – Razetime
    Jun 19 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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