9
\$\begingroup\$

Given two strings containing only 0 and 1, decide the probability that first appears earlier as a consecutive substring in an infinite random 0/1 stream.

You can assume that neither string is suffix of the other string, so 01, 1, 00, 0 are invalid. (*)

IO format flexible. Your answer should be precise given ideal floating point numbers, so sampling is likely not a good idea.

Shortest code wins.

Note

  • I'd like to see how much longer code without assumption (*), allowing collision in a sequence but won't happen (due to fact that one string would appear earlier) or even just no extra rule(In which case f(a,b)+f(b,a)!=1). Therefore, you may also provide version(s) that do so, even if longer, if convenient.

Test cases

0, 1 => 50%
00, 1 => 25%
10, 00 => 75%
0, 01 => 100%
011, 001 => 1/3
00, 110 => 1/2 (Example with different length input but result half)
000, 101 => 5/12 (Examples provided by Bubbler)
000, 011 => 2/5
111, 1001 => 4/7
111, 0011 => 5/12 (Suggested by Neil, longer string would likely come earlier)
(Following not required)
11, 1 => 0%
1, 11 => 100%
10, 10 => 100% (0% if you choose strict early)
01, 1 => 50%   (0%)
1, 01 => 100%  (50%)

References

\$\endgroup\$
4
  • 1
    \$\begingroup\$ This answer may help. \$\endgroup\$
    – 138 Aspen
    Jan 6 at 5:46
  • \$\begingroup\$ Related (though probably not very useful) \$\endgroup\$
    – Tbw
    Jan 6 at 7:24
  • 2
    \$\begingroup\$ Can we express the answer as odds? \$\endgroup\$ Jan 6 at 19:27
  • 1
    \$\begingroup\$ @NickKennedy I guess so but what do other probably questions do \$\endgroup\$
    – l4m2
    Jan 7 at 2:19

3 Answers 3

8
\$\begingroup\$

Charcoal, 34 32 bytes

≔⮌E²SθIEθΣ⊞OυΣEθ×⊖⊗⁼κμ↨²Eι¬⌕λ✂ιξ

Try it online! Link is to verbose version of code. Outputs the ratio as a fraction but not necessarily in lowest terms. Technically works for all edge cases although two identical inputs outputs 0/0. Explanation: For the Cartesian product of the two inputs with itself, calculates which suffixes of one are prefixes of the other, then interprets that in base 2; this is negated when the strings are compared against each other. The final denominator is simply the sum of all four values; the numerator is the sum of two of them. Example for 111 and 0011:

Suffixes of 111: 111 11 1
Are they prefixes of 111? 1 1 1 = 7
Are they prefixes of 0011? 0 0 0 = -0
Suffixes of 0011: 0011 011 11 1
Are they prefixes of 111? 0 0 1 1 = -3
Are they prefixes of 0011? 1 0 0 0 = 8
Numerator = 8 - 3 = 5
Denominator = 8 - 3 + 7 - 0 = 12

Note that the values 7 and 8 are also half the indices at which you would expect to find 111 and 0011 respectively, which leads to the paradox that although you would expect to see 0011 first, the expected position of 111 is before that of 0011.

26 bytes by taking input in the form of a reversed list:

IEθΣ⊞OυΣEθ×⊖⊗⁼κμ↨²Eι¬⌕λ✂ιξ

Try it online! Link is to verbose version of code. Explanation:

  θ                         Input list
 E                          Map over elements
         θ                  Input list
        E                   Map over elements
              κ             Outer index
             ⁼              Equals
               μ            Inner index
            ⊗               Doubled
           ⊖                Decremented
          ×                 Times
                   ι        Outer string
                  E         Map over characters
                      λ     Inner string
                    ¬⌕      Begins with
                        ι   Outer string
                       ✂    Sliced from
                         ξ  Innermost index
                ↨           Convert from base
                 ²          Literal integer `2`
       Σ                    Take the sum
    ⊞Oυ                     Push to predefined empty list
   Σ                        Take the sum of that list
I                           Cast to string
                            Implicitly print
\$\endgroup\$
2
  • \$\begingroup\$ Seems your solution treats longer string win when collide, and it looks like that you thought so in sandbox \$\endgroup\$
    – l4m2
    Jan 6 at 10:44
  • \$\begingroup\$ @l4m2 That's how my source treats it: 01 precedes 1, unless the very first bit is 1. \$\endgroup\$
    – Neil
    Jan 6 at 10:48
2
\$\begingroup\$

Uiua 0.8.0, 35 bytes SBCS

+,∩(-:∩(°⋯⇌⊢⍉⊐≡⌕),:≡(□↘)⇡⧻♭..∩¤)⊙.,

Try on Uiua Pad!

Port of Neil's answer.

Explanation

⊙., # duplicate inputs in reverse order
∩(  # on both pairs,
  ∩¤    # add an axis to both inputs
  ⇡⧻♭.. # dup the first twice and range the length
  ≡(□↘) # for each in the range, 
        # drop that much from the front and box the result
  ,:    # dup top of stack to third
  ∩(    # on both pairs,
    ⊐≡⌕ # find suffixes in input
    ⊢⍉  # first column
    °⋯⇌ # reverse then un-bits, binary to number
  )
  -:    # subtract second from top
)
+,  # duplicate the second onto top then add
\$\endgroup\$
1
\$\begingroup\$

Jelly, 16 bytes

¹ÐƤ€eþ€¹Ƥ€Ḅạ/€UÄ

Try it online!

A Jelly port of Neil’s Charcoal answer, so be sure to upvote that one too!

If odds are allowable as output, one byte can be saved (by omitting the Ä). If it’s allowable to reverse the order of the inputs, then a further byte can be saved (omit the last U).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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