20
\$\begingroup\$

Background

My user ID is 78410, or \$1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0_2\$. One interesting property of this number is that, in binary,

  • it doesn't have three consecutive identical digits, and yet
  • it has a substring \$100100100\$ which is three copies of \$100\$.

So, I define a Bubbler number as a positive integer whose binary representation satisfies the following:

  • it doesn't have three consecutive identical digits (so it is a member of A063037), and
  • it contains a substring which is three consecutive copies of some nonempty string (so it is NOT a member of A286262).

Task

Given a positive integer as input, determine if it is a Bubbler number.

You can use truthy/falsy values in your language or two distinct values to indicate true/false respectively.

There are 55 Bubbler numbers under 1000:

42 84 85 106 149 169 170 171 212 213 292 298 299 338 339 340 341 342 362 365
405 425 426 427 438 585 596 597 598 618 658 661 676 677 678 681 682 683 684 685
724 725 730 731 804 810 811 850 851 852 853 854 874 876 877

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
  • 9
    \$\begingroup\$ Ugh. User ids all over again. \$\endgroup\$ – user92069 May 29 at 8:13
  • 10
    \$\begingroup\$ A tribute to yourself!? That's hilarous. \$\endgroup\$ – user92069 May 29 at 13:42

17 Answers 17

7
\$\begingroup\$

Brachylog, 10 bytes

ḃsᶠ~j₃ˢlⁿ1

Try it online!

This was meant to only be a partial solution, but it turns out that fails on empty inputs.

  ᶠ           Find every
 s            substring of
ḃ             the input's binary digits,
      ˢ       then for each substring
   ~j₃        map it to the string which it is three copies of
      ˢ       (ignoring and discarding it if there is no such string).
        ⁿ     For none of those strings (of which there is at least one)
       l      is its length
         1    1.
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Python 2, 64 63 61 58 bytes

f=lambda n,i=2:[n>i>0<f(n,i+1),i>3][3*bin(i)[3:]in bin(n)]

Try it online!

A recursive function that returns True if the number is a Bubbler number, and False otherwise.

Generates all possible binary string, then for each binary string checks if n contains 3 consecutive copies of that string.

The binary strings are generated by evaluating bin(i)[3:] for \$i\$ from \$2\$ to \$n-1\$. The slice [3:] gets rid of the first 3 characters in the binary representation of \$i\$, which are always 0b1. This allows us to generate binary strings that has leading 0.

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6),  54  49 bytes

Saved 5 bytes thanks to @l4m2!

n=>/^(?!.*(.)\1\1).*(.+)\2\2/.test(n.toString(2))

Try it online!

Regular expression

/^(?!.*(.)\1\1).*(.+)\2\2/
 ^                         // match the beginning of the string
  (?!         )            // must NOT be followed by:
       (.)                 //   a single character
     .*                    //   appearing anywhere
          \1\1             //   immediately followed by 2 copies of itself
                           // must also match:
                 (.+)      //   a string
               .*          //   appearing anywhere
                     \2\2  //   immediately followed by 2 copies of itself

JavaScript (ES6), 55 bytes

This version uses a helper function to test /(.+.)\1{2}/ and /(.)\1{2}/ separately.

n=>(g=p=>n.toString(2).match(p+".)\\1{2}"))`(.+`&&!g`(`

Try it online!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 49 \$\endgroup\$ – l4m2 May 29 at 12:49
6
\$\begingroup\$

05AB1E, 15 12 bytes

bŒʒ3ä1ìË}{нË

Outputs 0 for truthy and 1 for falsey.

Try it online or verify some more test cases.

Explanation:

b         # Convert the (implicit) input to a binary-string
 Π       # Take all substrings of the binary-string
  ʒ       # Filter it by:
   3ä     #  Split the substring into 3 equal-sized parts
     1ì   #  Prepend a 1 to each part
       Ë  #  Check that the three parts are equal
          #  (the prepend 1 is necessary, because ["01","01","1"] would be truthy,
          #   since strings and integers are interchangeable in 05AB1E)
  }{      # After the filter: sort all remaining substrings
          # (this causes any "000" and/or "111" to be leading)
    н     # Pop and push the first substring (or "" if none are left)
     Ë    # Check if all characters in this string are equal (also truthy for "")
          # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Bash + Unix utilities, 44 bytes

dc -e2o?n|egrep -v 000\|111|egrep '(.+)\1\1'

Try it online!

Input is on stdin, and the output is the exit code (0 for truthy, 1 for falsey, as usual with shell scripts).

Or verify the Bubbler numbers under 1000.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

perl -M5.010 -n, 45 bytes

$_=sprintf"%b",$_;say!/(.)\1\1/&&!!/(.+)\1\1/

Try it online!

Turns the input into a string with the binary representation of the number, applies regexes to test the requirements, then prints 1 or an empty string accordingly. Two bytes (the !!) could be saved if there wasn't a restriction for two distinct values -- without them, for bubbly numbers, it prints the thrice repeated string.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What about "truthy/falsy values in your language"? I know Perl can be weird, but if you're using !! it ought to already be truthy or falsy, right? ...That is an honest question. \$\endgroup\$ – Unrelated String May 29 at 10:46
  • \$\begingroup\$ @UnrelatedString Sure, and anything which isn't 0, the empty string, the string "0" or undefined is true. Without the !!, you'll get true values, but you'll get different values for different inputs (and returning two distinct values is a requirement -- I take that 1 specific value for false, and 1 specific value for true). In Perl && returns the value of the left operand if it's false, and value of the right operand if the left operand is true. And the value of /(.+)\1\1/ will be what is matched by the (.+) (because it is in list context, due to the say). \$\endgroup\$ – Abigail May 29 at 10:56
  • 2
    \$\begingroup\$ If you accept 0 and 1 as output you could swap the matches and use & instead for -3. Try it online! \$\endgroup\$ – Dom Hastings May 29 at 12:12
3
\$\begingroup\$

Jelly, 10 bytes

BẆẋ3ẇɗƇ$ḢḊ

A monadic Link accepting a positive integer which yields a list - in Jelly an empty list (non-Bubbler) is falsey while a non-empty list is truthy (Bubbler).

Try it online! Or see the test-suite (identifying all Bubbler numbers in \$[1..1000]\$).

How?

BẆẋ3ẇɗƇ$ḢḊ - Link: positive integer, n
B          - convert n to binary (say b)
       $   - last two links as a monad - f(b):
 Ẇ         -   all sublists (say s) - Note these are sorted from shortest to longest
      Ƈ    -   filter keep those x of s which are truthy under:
     ɗ     -     last three links as a dyad - f(x, b):
   3       -       three
  ẋ        -       repeat (e.g. [1,0] -> [1,0,1,0,1,0])
    ẇ      -       is a sublist of (b)?
        Ḣ  - head (given an empty list this yields 0)
         Ḋ - dequeue
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 45 bytes

{(*/0<3!+/+3'x)>*/^a?,/'3#','a:,/,\'|',\x}@2\

Try it online!

2\ binary encode

{ }@ apply function

first condition:

  • ,/,\'|',\x all substrings of the argument, i.e. prefixes (,\), reverse each (|'), prefixes each (,\'), raze (,/)

  • a: assign to a

  • ,/'3#',' triplicate each, i.e. enlist each (,'), 3-reshape each (3#'), raze each (,/')

  • a? find - indices in a, or nulls (0N) for not found

  • ^ is null?

  • */ all

second condition:

  • 3' sliding window of size 3

  • + transpose

  • +/ sum

  • 3! mod 3

  • 0< positive?

  • */ all

> and not (between the two conditions)

| improve this answer | |
\$\endgroup\$
3
+200
\$\begingroup\$

[APL (Dyalog 18.0)], 34 33 bytes

⊃1<∘⍸⊢{∨/⍺⍷⍨∊3/⊂1↓⍵}Ö(2∘⊥⍣¯1)¨2↓⍳

Try it online!

This uses ⎕IO←0 and the Over operator (, which was added in 18.0). The current version on TIO is 17.1, so it's been implemented manually (thanks Bubbler!). I think this does well for a non-regex answer.

Explanation

                              2↓⍳     ⍝ The range 2 to n-1
     ⊢               (2∘⊥⍣¯1)         ⍝ Convert this range and the input to base 2
      {∨/⍺⍷⍨∊3/⊂1↓⍵}Ö        ¨        ⍝ Before applying the function to each
                1↓⍵                   ⍝ Drop the first 1 of the binary number
           ∊3/⊂                      ⍝ Repeat the list 3 times and flatten
       ∨/⍺⍷⍨                          ⍝ Is this sublist in the binary input?
⊃   ⍸                                 ⍝ Is the index of the first element
 1<∘                                  ⍝ Greater than one?

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Something like this would be more helpful to test the code and check the score. \$\endgroup\$ – Bubbler Sep 11 at 3:54
  • \$\begingroup\$ @Bubbler Thanks! I always forget how to declare the function outside the code section \$\endgroup\$ – Jo King Sep 11 at 4:34
  • \$\begingroup\$ I'd love to see an explanation of this answer. \$\endgroup\$ – Razetime Oct 15 at 12:30
  • \$\begingroup\$ @Razetime Added explanation \$\endgroup\$ – Jo King Oct 16 at 7:51
2
\$\begingroup\$

Jelly, 14 13 12 11 10 bytes

BẆẋ3eɗƇ`ḢṖ

Try it online!

The third -1 takes some inspiration from Kevin Cruijssen's 05AB1E solution.

Fourth -1 thanks to Jonathan Allan reminding me of Jelly's truthiness semantics.

Outputs truthy or falsy.

 Ẇ            Every substring of
B             the input's binary digits.
      Ƈ       Filter them by
  ẋ3 ɗ        repeated three times
    e         membership in
BẆ     `      every substring of the input's binary digits.
         Ṗ    Is there more than one element to remove from
        Ḣ     the first (i.e., shortest) of the filtered substrings?
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Oh, just saw how similar mine is to yours - I hadn't even noticed an existing Jelly answer. \$\endgroup\$ – Jonathan Allan May 29 at 12:34
  • 2
    \$\begingroup\$ Using the empty-list being falsey and the fact that taking the head of an empty list yields 0 you can replace LỊ with (as I did in mine) or which gets your one down to 10 bytes too. \$\endgroup\$ – Jonathan Allan May 29 at 12:38
2
\$\begingroup\$

Husk, 9 bytes

tṠḟ·€*3Qḋ

Returns a list, which is nonempty iff the input is a Bubbler number. In Husk, empty lists are falsy and nonempty lists are truthy.

Try it online!

Explanation

tṠḟ·€*3Qḋ   Implicit input: a number, say n=84.
        ḋ   Binary representation: [1,0,1,0,1,0,0]
       Q    Sublists: [[1],[0],[1,0], …, [1,0,1,0,1,0,0]]
  ḟ         Find the first one that satisfies this (or an empty list if none do):
              Example list: [1,0]
     *3       Repeat three times: [1,0,1,0,1,0]
 Ṡ ·€         It occurs in the list of sublists: yes.
            Result: [1,0]
t           Remove the first element: [0], truthy.

The correctness of this program relies on the fact that Q enumerates the sublists in a "good" order (all sub-sublists of a sublist occur in the result before the sublist itself) and returns the first match it finds. If 000 occurs in the binary representation, then [0] is listed before any longer triply repeated sublist (unless that sublist consists of only 1s, in which case [1] is listed before it).

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 44 bytes

.+
$*
+`(1+)\1
$+0
01
1
A`000|111
1`(.+)\1\1

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary

+`(1+)\1
$+0
01
1

Convert to binary.

A`000|111

Delete the string if it contains 000 or 111 (A`(.)\1\1 also works for the same byte count).

1`(.+)\1\1

Check whether there are three consecutive substrings.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 28 bytes

≔⍘N²θ¿⬤01¬№θ×ι³⊙θΦκ№θ׳✂θλ⊕κ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for true, nothing for false. Explanation:

≔⍘N²θ

Input the number and convert it to base 2 as a string.

¿⬤01¬№θ×ι³

Test whether neither digit 0 nor 1 appears triplicated in the string.

⊙θΦκ№θ׳✂θλ⊕κ

Check whether any nontrivial substring appears triplicated. (I use Φ instead of a second since Charcoal doesn't currently accept an implicit range there, but the effect is the same.)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

T-SQL, 258 bytes

Added some line changes to make it readable

DECLARE @ char(99)=''
WHILE @i>0
SELECT @=left(@i%2,1)+@,@i/=2;
WITH C as(SELECT number+1n FROM spt_values WHERE'P'=type)
SELECT count(*)FROM C,C D
WHERE not(@ like'%000%'or @ like'%111%'or len(@)<D.n*3+C.n+2)
and @ like'%'+replicate(substring(@,C.n,D.n+1),3)+'%'

Returns 1 or more for true, 0 for false

Try it online

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 124 120 114 113 bytes

b,c,i,j;f(a){for(b=c=1;a;a/=2)for(b&=a&7^7&&a&7,i=~3,j=1;++j<11;i*=2)c&=~i&(a>>j^a|a>>j*2^a)||!(a>>j*3-1);b&=!c;}

Try it online!

-4 -5 bytes: ceilingcat

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Raku, 37 bytes

{.base(2)~~/(.+)$0$0/&none /(.)$0$0/}

Try it online!

This matches the base-2 representation of the input number against the junction

/(.+)$0$0/ & none /(.)$0$0/

...which succeeds if it matches the first pattern, but not the second one.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Can't you just replace none with !? \$\endgroup\$ – Jo King Sep 10 at 6:24
  • \$\begingroup\$ @JoKing That seems to work, but I have no idea why. I would expect /foo/ & ! /bar/ to be a junction of a regex and a boolean. \$\endgroup\$ – Sean Sep 10 at 16:19
  • \$\begingroup\$ Well, the whole thing is boolified by the ~~, and when a regex is boolified, it evaluates with $_. \$\endgroup\$ – Jo King Sep 11 at 3:22
0
\$\begingroup\$

Ruby, 42 bytes

->n{n.to_s(2)=~/^(?!.*(.)\1\1).*(.+)\2\2/}

Try it online!

How it works:

->n{
  n.to_s(2)      # convert to binary representation string
  =~ /           # check if it matches regex
  ^(?!.*(.)\1\1) # (from the start) assert that there are no 3
                 # repeated characters anywhere in the string
  .*             # skip any number of characters
  (.+)\2\2/      # check that there is a sequence of 1 or more
                 # characters repeated 3 times (note that there
                 # are no 3 repetitions of a single character so
                 # the 1 case is irrelevant (equivalent to ..+))
}

squints eyes
"regex..."

| improve this answer | |
\$\endgroup\$

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.