23
\$\begingroup\$

Let's start by defining a Two Bit Number™️:

  • It is a positive integer
  • When expressed as a binary string it has exactly 2 true bits OR
  • When expressed as a decimal number, it has exactly 2 of the numeral one, and all other numerals are zero.

Or as a sentence

A Two Bit Number™️ is a number which contains exactly 2 of the numeral 1 and no other numerals besides 0, when expressed as a decimal string or a binary number.

So here area all the Two Bit Numbers™️ between 0 and 256

Dec  Bin       Type
3    00000011  Binary
5    00000101  Binary
6    00000110  Binary
9    00001001  Binary
10   00001010  Binary
11   00001011  Decimal
12   00001100  Binary
17   00010001  Binary
18   00010010  Binary
20   00010100  Binary
24   00011000  Binary
33   00100001  Binary
34   00100010  Binary
36   00100100  Binary
40   00101000  Binary
48   00110000  Binary
65   01000001  Binary
66   01000010  Binary
68   01000100  Binary
72   01001000  Binary
80   01010000  Binary
96   01100000  Binary
101  01100101  Decimal
110  01101110  Decimal
129  10000001  Binary
130  10000010  Binary
132  10000100  Binary
136  10001000  Binary
144  10010000  Binary
160  10100000  Binary
192  11000000  Binary

The challenge:

  • Write some code which accepts a number and outputs true or false (or some indicator of true or false) if it is a Two Bit Number™️.
  • Input will always be an integer, but it may not always be positive.
  • It can be in any language you like.
  • It's code golf, so the fewest bytes wins.
  • Please include links to an online interpreter for your code (such as tio.run).

Test Cases

Binary Two Bit Numbers™️:

  • 3
  • 9
  • 18
  • 192
  • 288
  • 520
  • 524304

Decimal Two Bit Numbers™️:

  • 11
  • 101
  • 1001
  • 1010
  • 1100
  • 1000001
  • 1100000000
  • 1000000010

Non Two Bit Numbers™️:

  • 0
  • 1
  • 112 (any numerals over 1 prevent it being a binary
  • 200
  • 649
  • -1
  • -3

Fun fact: I was not able to find any DecimalBinary Two Bit Numbers™️ checking up to about 14 billion, and I have a hypothesis that such a number does not exist, but I have no mathematical proof. I'd be interested to hear if you can think of one.

\$\endgroup\$
19
  • 5
    \$\begingroup\$ I've sketched out a somewhat clumsy proof that no DB2B number exists. Not sure if it makes sense though \$\endgroup\$ – Jo King Sep 30 '20 at 14:07
  • 5
    \$\begingroup\$ @JoKing How do you get from 10^x+10^y = 2^x+2^b to 5^x = 2^b/10^y? It looks like you may have incorrectly treated the former expression as though it said * instead of +, and then divided both sides by 2^x*10^y. \$\endgroup\$ – Lynn Sep 30 '20 at 14:43
  • 4
    \$\begingroup\$ Input will always be an integer, but it may not always be positive. How are negative numbers encoded? With a minus in front? With a 1 in front? Using two's complement? \$\endgroup\$ – Stef Sep 30 '20 at 15:35
  • 5
    \$\begingroup\$ The existence of DecimalBinary Two Bit Numbers™️ is a fascinating nerd-snipe problem! \$\endgroup\$ – Sisyphus Oct 1 '20 at 0:38
  • 5
    \$\begingroup\$ You have -1 as not a Two Bit number (it would be in 2-s complement), you have -3 as not a Two Bit number (it would be with a minus sign character prepended). You do not have -11 as an example (again would be with a minus sign). I can only imagine that your rule is to convert to a base representation using digits in \$[-b+1..0]\$ e.g. -123 base 10 is [-1,-2,-3] \$= -1 \times 10^2 + -2 \times 10^1 + -1 \times 10^0\$. Without a spec it seems we can say all negative numbers are not Two Bit Numbers, so why, are there example ones and why do we even need to handle them? \$\endgroup\$ – Jonathan Allan Oct 1 '20 at 2:39

40 Answers 40

18
\$\begingroup\$

Python 3, 68 62 48 bytes

-6 bytes thanks to xnor!
-14 bytes thanks to Jitse!

lambda n:' 11 'in f' {n:b} {n} '.replace('0','')

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ @user your 51 bytes returns false for all valid binaries entries \$\endgroup\$ – Kaddath Sep 30 '20 at 13:47
  • \$\begingroup\$ Its looks like you can cut the (n>0)* because any negative values will fail the test due to their minus sign. \$\endgroup\$ – xnor Sep 30 '20 at 21:18
  • \$\begingroup\$ you can replace s.replace('0','')=='11' with s.count('1')==2 \$\endgroup\$ – Turksarama Oct 1 '20 at 5:39
  • \$\begingroup\$ @Turksarama this would fail for inputs like 121. The s.replace('0','')=='11' makes sure there are no other digits. \$\endgroup\$ – ovs Oct 1 '20 at 6:50
  • 1
    \$\begingroup\$ 52 bytes \$\endgroup\$ – Jitse Oct 1 '20 at 7:22
11
\$\begingroup\$

Haskell, 50 bytes

f n=or[b^x+b^y==n|b<-[2,10],x<-[0..n],y<-[x+1..n]]

Try it online!

Brute force search.

Alternative 50 bytes

b!0=0
b!x=rem x b^3+b!quot x b
f n=2!n==2||10!n==2

b!x computes a base-b “cubed digit sum” of x. For example, 10!123 = \$1^3+2^3+3^3\$ = 36.

We check if either of 2!n or 10!n equals 2.

quot is necessary to support negative input. It rounds toward zero, whereas div rounds down, meaning div (-1) 10 == (-1), causing an infinite loop.

\$\endgroup\$
0
10
\$\begingroup\$

JavaScript (ES6), 38 bytes

Returns 0 for true, or a non-zero integer for false.

n=>(g=n=>!(n&=n-1)|n&n-1)(n)*g('0b'+n)

Try it online!

How?

The helper function g removes the two least significant bits set in n by computing n & (n - 1) twice. If we get 0 the first time, it means that n has at most one bit set, which is not enough. If we don't get 0 the second time, it means that n has more than 2 bits set, which is too much.

For the decimal test, we invoke g with '0b' + n to parse it as a binary value. If n is negative, this gives something such as '0b-10100', which is NaN'ish and fails as expected.


JavaScript (ES6),  40  39 bytes

Returns a Boolean value telling whether the input is not a Two Bit Number.

n=>[n,'0b'+n].every(n=>!(n&=n-1)|n&n-1)

Try it online!

\$\endgroup\$
8
\$\begingroup\$

APL (Dyalog Extended), 18 bytes

2∊+/↑(*3)2 10⊤¨0⌈⎕

Try it online!

Jo King's 18 byte solution.

APL (Dyalog Extended), 20 21 20 26 25 bytes

{<⍵:2∊+/↑(⊂×⍨⍎¨⍕⍵)⍪⊂⊤⍵⋄0}

Try it online!

+1 byte after correcting the answer(ovs).

-1 byte after ovs's suggestion.(yay!)

+7 bytes after properly accepting negative test cases.

-1 byte from Adám.

Inspired from the J solution.

Explanation

{⍵>0:2∊+/↑(⊂2*⍨⍎¨⍕⍵)⍪⊂⊤⍵⋄0}
 ⍵>0:                       If number is positive
                      ⊤⍵    Decode number to binary
            ×⍨⍎¨⍕⍵          square each digit
         ↑ ⊂        ⍪⊂      join into two rows
       +/                   sum each row
     2∊                     is two present in it?
                         ⋄0 otherwise return 0
\$\endgroup\$
9
  • \$\begingroup\$ I think there might be another problem. For some reason I couldn't test it, but I think this returns 1 for negative inputs like ¯5, so you need an ⍵>0 check (like the J solution). \$\endgroup\$ – ovs Sep 30 '20 at 14:37
  • \$\begingroup\$ it errors on negative inputs like ¯5 due to and getting the digits. just needs a conditional. \$\endgroup\$ – Razetime Sep 30 '20 at 16:27
  • \$\begingroup\$ Doesn't this fail to output 0 on negative numbers? \$\endgroup\$ – Adám Sep 30 '20 at 19:58
  • \$\begingroup\$ now it does. @Adám \$\endgroup\$ – Razetime Oct 1 '20 at 3:13
  • 1
    \$\begingroup\$ Your score is a mountain range series. \$\endgroup\$ – Dominic van Essen Oct 1 '20 at 6:24
6
\$\begingroup\$

05AB1E, 8 7 bytes

b‚€{11å

Try it online or verify all test cases.

Explanation:

b        # Convert the (implicit) input-integer to a binary string
 ‚       # Pair it together with the (implicit) input-integer
  €{     # Sort the digits in each string
    11å  # And check if this pair contains an 11 (which is truthy for "011","0011",etc.)
         # (after which the result is output implicitly)
\$\endgroup\$
6
\$\begingroup\$

R, 50 49 48 46 bytes

Edit: -1 byte, and then -1 more byte, and then -2 more bytes, thanks to Robin Ryder

gsub(0,'',n<-scan())!=11&sum(n%/%2^(0:n)%%2)-2

Try it online!

Tests for decimal 2bit numbers using text manipulation to remove '0' digits and check whether the result is not '11', and then tests for binary 2bit numbers by calculating the binary digits and checking if they do not sum to 2. Returns FALSE for 2bit numbers and TRUE for non-2bit numbers.
It seems a bit clunky to do two different kinds of tests for essentially the same feature, but somehow comes-out quite short...

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Nice! You can save a byte by putting n<-scan() in the gsub call. \$\endgroup\$ – Robin Ryder Oct 1 '20 at 13:33
  • \$\begingroup\$ Thanks a lot! How did I not realize that? \$\endgroup\$ – Dominic van Essen Oct 1 '20 at 13:57
  • \$\begingroup\$ 48 bytes by inverting the output. \$\endgroup\$ – Robin Ryder Oct 1 '20 at 16:28
  • \$\begingroup\$ @RobinRyder that's neat. I suppose we can always use - instead of != for numeric comparisons, and so probably instead of == if (like here) there's a way to 'flip' the output. Nice trick! \$\endgroup\$ – Dominic van Essen Oct 1 '20 at 16:38
  • \$\begingroup\$ Precisely. That also works e.g. in if statements. \$\endgroup\$ – Robin Ryder Oct 1 '20 at 19:14
5
\$\begingroup\$

J, 25 bytes

0&<*10&#.inv+&(2=1#.*~)#:

Try it online!

How it works

0&<*10&#.inv+&(2=1#.*.~)#:
0&<*                       input is a positive number
    10&#.inv               list of digits base 10
                        #: list of digits base 2
            +&(        )   OR the result of both …
                    *.~    square each digit (x>=2 will be larger than 2)
                 1#.       sum
               2=          is equal to two

If there is a DecimalBinary number, the + as OR could result in 2, thus needing one byte more for +..

\$\endgroup\$
5
\$\begingroup\$

Brachylog, 9 bytes

ℕ{ḃc|}o11

Try it online!

Somewhat embarrassed I didn't think to translate other solutions' sort-based approaches earlier...

A more fun solution:

Brachylog, 10 bytes

ℕ{|ẹ~ḃ}ḃ+2

Try it online!

ℕ             The input is a whole number (necessary to exclude -3 etc.),
 {|   }       which either unchanged or
   ẹ          with its decimal digits
    ~ḃ        interpreted as binary (impossible if any ≥ 2),
       ḃ      has binary digits
        +2    that sum to 2.

Brachylog, 12 11 bytes

ℕ{ḃ|ẹ}<ᵛ²+2

Try it online!

-1 byte thanks to xash

ℕ              The input is a whole number,
 { | }         and either
  ḃ            its binary digits
    ẹ          or its decimal digits
      <ᵛ²      are all less than 2
         +2    and sum to 2.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 11 bytes \$\endgroup\$ – xash Sep 30 '20 at 13:27
  • \$\begingroup\$ Was sort of considering something like that, but never thought to superscript --thanks! \$\endgroup\$ – Unrelated String Sep 30 '20 at 13:34
  • \$\begingroup\$ Why does + not work on numbers and requires ? \$\endgroup\$ – Kroppeb Sep 30 '20 at 17:05
5
\$\begingroup\$

Japt, 9 bytes

There's gotta be a way to shave at least one more byte off this.

ìͶBªB¥¢ñ

Try it or run all test cases

ìͶBªB¥¢ñ     :Implicit input of integer U
ì             :Convert to digit array
 Í            :Sort (and implicitly convert back to integer)
  ¶           :Test for strict equality with
   B          :11
    ª         :Logical OR with
     B¥       :Test 11 for equality with
       ¢      :Convert U to binary string
        ñ     :Sort
\$\endgroup\$
5
\$\begingroup\$

Raku, 25 bytes

{$_|.base(2)~~/^10*10*$/}

Try it online!

Checks if the input or the base 2 of the input matches the regex ^10*10*$

\$\endgroup\$
5
\$\begingroup\$

Regex (ECMAScript), 70 68 56 52 bytes

-4 bytes by successfully combining base \$2\$ and \$10\$ into a single expression, as was already accomplished in the other versions

^((x)|(x))((((\2*)\3*)(\2\7){8}x(?=\6$))*x){2}\2{8}$

Try it online!

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

Here are some examples of how this 52 byte version works:

Example input: 1001000
Choose base 10 and subtract 1 from tail
1000999
Iteration 1 of the outer loop:
1000999
100099
10009
1000
tail -= 1
999
Iteration 2 of the outer loop:
999
99
9
tail -= 1
8
Assert tail == 10 - 2

Example input: 11
Choose base 10 and subtract 1 from tail  
10
Iteration 1 of the outer loop:
10
tail -= 1
9
Iteration 2 of the outer loop:
9
tail -= 1
8
Assert tail == 10 - 2

The regex, pretty-printed and commented:

^                # tail = N = input number
# Pick which base to operate in, and tail -= 1
(
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=2
)
# Assert tail is the sum of two powers of B
(
    (
        # tail = (tail + 1) / B - 1
        ((\2*)\3*)   # if \2=1, then \6 = \7 = (tail + 1) / 10 - 1;
                     # if \3=1, then \6 =      (tail + 1) /  2 - 1, and \7 = 0
        (\2\7){8}
        x
        (?=\6$)
    )*               # Loop the above zero or more times
    x                # tail -= 1
){2}                 # Loop the above exactly twice
\2{8}$               # Assert tail == B - 2

The following text applies to the earlier 56 byte version:

This turned out to be very similar to Neil's 58 byte regex. I looked at the byte count, but not at the regex itself, in that answer's heading before working on the problem myself. It took me a while to figure out how to make a non-ECMAScript-specific regex shorter than 70 bytes. The hangup for me was, that I was doing it like this:

^((((x+)\4{8}(?=\4$))*x(?=(xx)*$)){2}|(((x+)(?=\8$))*x(?=(xx)*$)){2})$

In order to prevent the loop from subtracting the same power of 2 or 10 twice (and matching, for example, 512 and 200) I had to use (?=(xx)*$) to assert that tail is even after subtracting 1 (this works for both 2 and 10, as they are both even). Finally I figured out that I could just use two alternatives inside the (...){2} loop, one that must do at least one division before subtracting 1, and one that can only subtract 1 if it's the first thing done, and this saved 7 bytes per base, giving 70 - 2×7 = 56 bytes:

^((((x+)\4{8}(?=\4$))+x|^x){2}|(((x+)(?=\7$))+x|^x){2})$

Regex (ECMAScript / Perl / Java / Python / PCRE / .NET), 54 bytes

^(x?)(^x|\B)((((\1*)\2*)(\1\6){8}x(?=\5$))*x){2}\1{8}$

This is a port of the 52 byte ECMAScript version to be NPCG-behavior-independent and compatible with a wide variety of regex engines including ECMAScript (i.e., "generic"). This is done by changing ((x)|(x)) (where \2 and \3 are differently 1 or unset) to (x?)(^x|\B) (where \1 and \2 are differently 1 or 0).

Try it online! - ECMAScript
Try it online! - Perl
Try it online! - Java
Try it online! - Python
Try it online! - PCRE
Try it online! - .NET

It exposes a bug in the Ruby regex engine. The 56 byte regex works in Ruby: Try it online!
But the 54 byte regex does not: Try it online! Boiling this down, it appears that ^((x*)(){4}(?=\2$))*x$ matches powers of 2 just fine, but ^((x*)(){5}(?=\2$))*x$ does not.

Similarly, while it works with Python's re module (see above), it exposed a bug in the the more powerful regex module: Try it online!    [This bug has now been fixed!]

Regex (ECMAScript+(?*)), 54 47 bytes

^(?*(x)|(x))((((\1*)\2*)\6{8}(?=\5$))+x|^x){2}$

In this version, the two bases \$10\$ and \$2\$ are combined, by choosing between them using the initial (x)|(x). Thanks to molecular lookbehind (?*), this can be done without subtracting 1 from the number being tested:

^
(?*
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 - \2; B=2
)
# Assert tail is the sum of two powers of B
(
    # Alternative #1: Divide evenly by B as many times as possible, at least once
    # (meaning tail has to be initially divisible by B), then subtract 1.
    (
        ((\1*)\2*)\6{8}(?=\5$)   # assert tail % B == 0; tail /= B
    )+
    x                            # tail -= 1
|
    # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
    # the first thing we do. If this path is taken, only alternative #1 can next.
    ^x                           # assert tail == N; tail -= 1
){2}             # Loop the above exactly twice
$                # Assert tail == 0

When \1=1 and \2=0, ((\1*)\2*)\6{8}(?=\5$) behaves like (x*)\5{8}(?=\5$), dividing by \$10\$.
When \1=0 and \2=1, ((\1*)\2*)\6{8}(?=\5$) behaves like (x*)(?=\5$), dividing by \$2\$.

Regex (ECMAScript 2018), 51 bytes

((x)|(x))$(?<=^(x((?<=^\6)\7{8}(\3*(\2*)))+|x$){2})

Try it online!

This is a port of the ECMAScript+(?*) version to variable-length right-to-left-evaluated positive lookbehind (?<=). It starts 1 off from the end, reaches the end by capturing a determination of whether to work in base \$10\$ or \$2\$, then does the rest of its work going backwards.

It exposes a bug present in the ECMAScript 2018 regex engine of both SpiderMonkey (Firefox) and V8 (Chrome / Node). To make this regex work, the multiline flag must be enabled. It fails to work without the flag. pxeger has reported the bug.

(
    (x)          # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
    (x)          # \3 = 1 - \2; B=2
)
$                # head = N = input number
# Assert head is the sum of two powers of B
(?<=             # Lookbehind - evaluated right-to-left
    ^            # Assert head == 0
    (
        # Alternative #1: Divide evenly by B as many times as possible, at least once
        # (meaning head has to be initially divisible by B), then subtract 1.
        x                             # head -= 1
        (
            (?<=^\6)\7{8}(\3*(\2*))   # assert head % B == 0; head /= B
        )+
    |
        # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
        # the first thing we do. If this path is taken, only alternative #1 can next.
        x$                            # assert head == N; head -= 1
    ){2}     # Loop the above exactly twice
)

Regex (Perl / Python / Ruby / PCRE / .NET), 51 39 bytes

^()?(((x*)(?(1)\4{8})(?=\4$))+x|^x){2}$

Try it online! - Perl
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE
Try it online! - .NET

This version takes advantage of a conditional group (?(1)\4{8}) to determine whether to work in base \$10\$ or \$2\$.

^
()?              # \1 = choose between B=10 (if set) or B=2 (if unset)
# Assert tail is the sum of two powers of B
(
    # Alternative #1: Divide evenly by B as many times as possible, at least once
    # (meaning tail has to be initially divisible by B), then subtract 1.
    (
        (x*)(?(1)\4{8})(?=\4$)   # assert tail % B == 0; tail /= B
    )+
    x                            # tail -= 1
|
    # Alternative #2: Don't divide at all, and just subtract 1, but only if this is
    # the first thing we do. If this path is taken, only alternative #1 can next.
    ^x                           # assert tail == N; tail -= 1
){2}             # Loop the above exactly twice
$                # Assert tail == 0

Regex (Java), 44 bytes

^()?(((x*)(\1\4{8}|(?!\1))(?=\4$))+x|^x){2}$

Try it online!

^(()|())(((x*)(\2\6{8}|\3)(?=\6$))+x|^x){2}$

Try it online!

These are ports of the 39 byte version, to a regex flavor that has no conditionals. In the first one, the (?(1)\4{8}) conditional is replaced with (\1\4{8}|(?!\1)) which behaves equivalently at a cost of 5 extra bytes. In the second the expression (()|()) instead of ()? is used to determine the mode (which either sets \2 or \3 leaving the other one unset), and the conditional is replaced with (\2\6{8}|\3). The regex is otherwise changed (except for shifting the capture group numbering).

\$\endgroup\$
4
  • \$\begingroup\$ As a pure .NET regex, I could do it in 46 bytes, if I could be bothered to golf down the last few bytes from (?<=(?=((((1+)(?(5)\4{8})(?=\4$))+|^)1){2}$)^(1)?) (it's just tedious which is why I haven't bothered.) \$\endgroup\$ – Neil Apr 2 at 23:50
  • \$\begingroup\$ @Neil That regex doesn't work and it's 50 bytes, so 46 is an oddly specific byte count to conjecture on. But yeah, I hadn't tried with conditionals yet, I was too much in the ECMAScript mindset at the time. \$\endgroup\$ – Deadcode Apr 3 at 0:25
  • \$\begingroup\$ The regex works fine when I try it, but I was imaging that it would be 46 bytes as I could reverse the entire regex which would leave me with a lookahead which I could then remove, but I may have got that byte count wrong. Anyway, your ^()? capture is the superior way of implementing the conditional, so that's a moot point now. \$\endgroup\$ – Neil Apr 3 at 1:06
  • \$\begingroup\$ My bad, 50 byte regex actually does work it's the x/1 difference \$\endgroup\$ – Deadcode Apr 3 at 1:36
4
\$\begingroup\$

Charcoal, 21 13 bytes

№⟦⁻θ0⁻⍘N²0⟧11

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a two bit number, nothing if not. Port of @Kaddath's PHP answer. Explanation:

   θ            Input as a string
  ⁻ 0           Remove zeros
       N        Input as a number
      ⍘ ²       Convert to base 2
     ⁻   0      Remove zeros
 ⟦        ⟧     Make into a list
№          11   Count occurances of literal string `11`
\$\endgroup\$
4
\$\begingroup\$

Python 3, 67 bytes

lambda n:n>2in{g(n,2),g(n,10)}
g=lambda x,b:x and(x%b)**2+g(x//b,b)

Try it online!

Port of my Haskell answer. (I took the test harness from ovs's Python answer. Thanks!)

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

R, 71 64 bytes

-7 bytes thanks to Dominic van Essen

`+`=function(n,k)sum((n%/%k^(0:n)%%k)^2)-2
n=scan();n<0|n+2&n+10

Try it online!

Output is reversed: gives FALSE if the input is a Two Bit Number, and TRUE if it is not.

The helper function + converts an integer to a vector of digits in base k (we need k=2 and k=10). Then sum the square of these digits. This sum is equal to 2 exactly for a Two Bit Number.

Will fail due to memory limits for large input, in which case you can use 0:log2(n) instead of 0:n and || instead of |: Try it online!.

\$\endgroup\$
9
  • \$\begingroup\$ This seems to invert true and false... Not sure if that's usually allowed with IO rules. \$\endgroup\$ – AJFaraday Sep 30 '20 at 14:13
  • \$\begingroup\$ @AJFaraday Yes, that is what I meant by "output is reversed". I took the challenge spec of "some indicator of true or false" as meaning that any 2 consistent values (here false and true) would be OK, but if that doesn't suit you I can correct it at the cost of 1 or 2 bytes. \$\endgroup\$ – Robin Ryder Sep 30 '20 at 14:29
  • 1
    \$\begingroup\$ I've checked, this is typically allowed. Upvoted :) \$\endgroup\$ – AJFaraday Sep 30 '20 at 14:35
  • 2
    \$\begingroup\$ @AJFaraday This is explicitly allowed by your own rules anyway, as some indicator of true or false can definitely be false and true. \$\endgroup\$ – Arnauld Sep 30 '20 at 14:53
  • 1
    \$\begingroup\$ Actually | works now that the log2 is out! \$\endgroup\$ – Robin Ryder Sep 30 '20 at 19:05
4
\$\begingroup\$

Factor, 79 74 70 bytes

-4 bytes thanks to chunes

: n ( n -- ? ) dup present swap >bin [ 48 swap remove "11"= ] bi@ or ;

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a byte with present instead of 10 >base, save 2 bytes with dup present swap >bin instead of [ present ] [ >bin ] bi, and save another byte by removing the space after the string. \$\endgroup\$ – chunes Apr 4 at 5:14
  • \$\begingroup\$ @chunes Thank you! I wasn't aware of present. \$\endgroup\$ – Galen Ivanov Apr 4 at 8:21
3
\$\begingroup\$

Jelly, 8 bytes

,BṢ€Ḍ11e

Try it online!

Explanation

,BṢ€Ḍ11e  Main Link
,         Pair the integer with
 B        Convert the integer to binary
  Ṣ€      Sort Each (sorts the digits of the integer implicitly)
    Ḍ     Convert from decimal to integer
     11e  Is 11 in this list?
\$\endgroup\$
3
\$\begingroup\$

Perl 5 -lp, 35 bytes

$_=grep/^10*10*$/,$_,sprintf"%b",$_

Try it online!

returns 1 or 2 (if a number can be decimal and binary Two Bit number) for true, 0 for false.

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

Wolfram Language (Mathematica), 46 bytes

!FreeQ[Tr/@(#~IntegerDigits~{10,2}^2),2]&&#>0&

Try it online!

-1 byte from @att

\$\endgroup\$
1
  • \$\begingroup\$ -1 byte since infix has higher precedence than Power \$\endgroup\$ – att Sep 30 '20 at 16:55
3
\$\begingroup\$

PCRE Regex, 100 95 bytes

^(((?(2)\2\2|.))*.)(?!\1)((?(3)\3\3|.))*.$|^(((?(5)\5{10}|.{9}))*.)(?!\4)((?(6)\6{10}|.{9}))*.$

Assume unary input (no support for negative numbers).

Should work in flavors with support for conditional regex and forward-declared back-reference.

The regex consists of 2 similar portions, one check for binary and the other for decimal.

  • The code makes use of sum of geometric series to match 2n and 10n.
    1 + (1 + 2 + 22 + ... + 2n) = 2n+1
    1 + 9 * (1 + 10 + 102 + ... + 10n) = 10n+1

  • Then it try to decompose the number into sum of 2n + 2k (or 10n + 10k for decimal), and check that 2n != 2k

Update:

  • Drops unused capturing group
  • Drops $ in (?!\1$) since it's fine if we reject 2n < 2k

regex101

\$\endgroup\$
8
  • \$\begingroup\$ I really did not expect a regex answer to this :) \$\endgroup\$ – AJFaraday Oct 1 '20 at 12:51
  • 1
    \$\begingroup\$ This inelegant regex works in ecma: ^((x)+|(x)+)(((\2+)\3+)\6{8}(?=\5$))+(?=(((\2+)\3+)\9{8}(?=\8$))*x$)\1$. Ideally the choice distinction 2 and 10 would be more subtle. \$\endgroup\$ – H.PWiz Oct 1 '20 at 15:00
  • \$\begingroup\$ @H.PWiz Post your own answer :) \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oct 1 '20 at 15:41
  • \$\begingroup\$ Took me a while to figure out what the regex is about - it decomposes number n into a * (1 + 2^b) then check a = 2^k. And the capturing group 2 and 3 switches between base 2 and base 10. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oct 1 '20 at 16:29
  • 1
    \$\begingroup\$ Is there any reason not to do this? \$\endgroup\$ – Neil Oct 3 '20 at 1:08
3
\$\begingroup\$

Julia, 61 bytes

using a regex on the binary and decimal representation of the number

x->any(match.([r"^0*10*10*$"],["$x",bitstring(x)]).!=nothing)

Try it online!

Julia, 69 bytes

by sorting the caracters

x->any(endswith.(join.(sort.(collect.(["0$x",bitstring(x)]))),"011"))

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Nice first post! \$\endgroup\$ – Redwolf Programs Oct 2 '20 at 16:20
3
\$\begingroup\$

Ruby 2.7, 44 bytes

->n{[2,10].any?{n.to_s(_1).tr(?0,'')=='11'}}

Explanation:

->n{                      # a lambda with one argument
    [2,10].any?{          # Return true if for either of 2 or 10...
      n.to_s(_1)          # input in that base
      .tr(?0,'')          # after removing all 0-s
      =='11'              # is exactly '11'
    }
}

Equivalent in ruby < 2.7, 46 bytes

->n{[2,10].any?{|b|n.to_s(b).tr(?0,'')=='11'}}

Try it out

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

Retina 0.8.2, 36 bytes

^\d+
$*1¶$&
+`^(1+)\1
$+0
m`^10*10*$

Try it online! Link includes most test cases (the larger ones cause Retina to run out of memory). Explanation:

^\d+
$*1¶$&

If the input is non-negative, prefix it with a unary copy.

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

Begin converting the unary copy to binary. At this point there are too many zeros in the result, but fortunately they are irrelevant.

m`^10*10*$

Match either number as being a two bit number.

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

K (ngn/k), 25 24 bytes

-1 byte thanks to ngn

{("11"~($x)^$0)+2=+/2\x}

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ "0" ---> $0 \$\endgroup\$ – ngn Oct 6 '20 at 22:07
  • \$\begingroup\$ @ngn Thank you! \$\endgroup\$ – Galen Ivanov Oct 7 '20 at 0:08
3
\$\begingroup\$

Husk, 11 10 bytes

#2§¤eṁ^3ḋd

Try it online!

Explanation

  §            Apply to input the two functions
         d       Convert to list of digits
        ḋ        And convert to list of binary digits
   ¤e          Then apply to both values
     ṁ^3         Cube each and sum
#2             How many 2s are there in the list?
\$\endgroup\$
3
\$\begingroup\$

Scala, 73 63 54 52 bytes

n=>Seq(n+"",n.toBinaryString)find(_ matches "10*"*2)

Try it online!

Edit:

  • Thanks to @Tomer Shetah for pointing out that lamdbas do not require their type definition (see comments), which reduces the length from 73 to 63 bytes
  • Thanks to @user for adding some nice syntax tricks that further reduce the length from 63 to 54 bytes
  • Again thanks to @user for the comment on using find instead of exists, which saves another 2 bytes and is valid for this challenge, since it is stated that a valid solution should "output true or false (or some indicator of true or false)"
\$\endgroup\$
5
  • \$\begingroup\$ You can do it in -10 bytes. Try it online! \$\endgroup\$ – Tomer Shetah Oct 20 '20 at 9:08
  • \$\begingroup\$ I am unsure about whether it is accepted for a Scala solution to provide an anonymous expression that cannot be called without binding it to some function name and signature to make it actually callable. You exclude the val f: Int => Boolean = from your byte-counts, although it is required to call the expression. I include the binding via the (shorter) def a(n:Int)= alternative. So my question in a nutshell: is for example _.length a valid solution, or only one of val a: String => Int = _.length or def a(s: String)=s.length ? Perhaps this is a topic for a meta discussion. \$\endgroup\$ – cubic lettuce Oct 21 '20 at 15:07
  • 2
    \$\begingroup\$ It has already been discussed. Please read this post \$\endgroup\$ – Tomer Shetah Oct 22 '20 at 5:16
  • \$\begingroup\$ You can get 54 bytes. In fact, if you use find instead of exists, you can save 2 bytes more, but you'll have to change your test cases to use !=None instead. \$\endgroup\$ – user Nov 19 '20 at 23:26
  • 1
    \$\begingroup\$ -1 for being spherical lettuce and calling yourself cubic lettuce \$\endgroup\$ – Razetime Nov 20 '20 at 15:36
3
\$\begingroup\$

Generic regex, 58 56 bytes

^(((1+)(?=\3$))+1|^1){2}$|^(((1+)\6{8}(?=\6$))+1|^1){2}$

Try it online! Link includes test harness written in Retina 0.8.2 although the regex itself should work in most engines. Takes input in signed unary i.e. ^-?1*$. Explanation: Given k and m we can write a specific test for a number being the sum of k distinct powers of m by repeatedly dividing by m and subtracting 1 k distinct times along the way, before we eventually reach zero:

^(((1+)\3{<m-2>}(?=\3$))+1|^1){<k>}$

where <m-2> and <k> represent substitutions for the specific values being tested (subject to trivial reductions such as \3{0} being a no-op). This works as follows:

   (1+)                                 Find `i` such that
       \4{<m-2>}                        `i+(m-2)i=(m-1)i` is equal to
                (?=\4$)                 `n-i`, therefore `i=n/m`.
  (                    )+               Divide `n` by `m` at least once
                         1              Then decrement
 (                        |^1)          Or on the first loop just decrement
                              {<k>}     Decrement `k` distinct times
^                                  $    Consume entire input

The problem then reduces to an alternation of two such tests. Edit: Saved 2 bytes by noticing from @Deadcode's answer that (((...)+|^)1) is the same as ((...)+1|^1).

\$\endgroup\$
1
  • \$\begingroup\$ I'm very impressed by your generic regex's shortness! Here is a ECMAScript test harness for it. I have been trying to construct a similarly short generic or ECMAScript regex without reading yours, and so far have not been able to do better than 70 generic, 68 ECMAScript, or 54 with molecular lookahead. I'm finding it extremely hard to combine the binary and decimal tests compactly without molecular lookahead or variable-length lookbehind, but I'll keep trying. \$\endgroup\$ – Deadcode Mar 12 at 18:33
2
\$\begingroup\$

PHP, 69 67 bytes

echo($f=fn($s)=>str_replace(0,'',$s)==11)($argn)|$f(decbin($argn));

Try it online!

Pretty straightforward: treats each input as a string, replaces all zeroes by '' and tests if it (loosely) equals 11, or if the binary does

EDIT: saved 2 bytes by using 0 instead of '0'

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

APL (Dyalog Extended), 19 bytes

2∊2 10(+.×⍨⊤)¨⊢×0<⊢

Try it online!

Commented:

                0<⊢  ⍝ Is the (right) argument greater than 0
              ⊢×     ⍝ Multiply this with the argument
                     ⍝   results in 0 for negative inputs
  2 10(     )¨       ⍝ Call the next function with each of the bases 2 and 10
                     ⍝   and the non-negative number as a right argument
           ⊤         ⍝ Convert number to base digits
       +.×⍨          ⍝ The sum of squares of the digits
2∊                   ⍝ Does this contain 2?
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 75 \$\cdots\$ 76 80 bytes

Added 6 bytes to fix a bug.

d;r;c;f(n){for(c=2,r=__builtin_popcount(n)!=2|n<0;n>0;n/=10)d=n%10,c-=d*d;r*=c;}

Try it online!

Returns a falsy value if \$n\$ is a Two Bit Number™️ or a truthy one otherwise.

\$\endgroup\$
3
  • \$\begingroup\$ strictly speaking __builtin_popcount is a built-in function that only exists in some compilers and not a standard function \$\endgroup\$ – phuclv Oct 2 '20 at 4:15
  • 1
    \$\begingroup\$ @phuclv true, but, "For the purposes of PPCG, a programming language is defined by its implementation." codegolf.meta.stackexchange.com/a/7833/43195 \$\endgroup\$ – Phoenix Oct 2 '20 at 4:40
  • \$\begingroup\$ @phuclv As it clearly states my answer is for GCC, __builtin_popcount is a GCC builtin. \$\endgroup\$ – Noodle9 Oct 2 '20 at 10:12
2
\$\begingroup\$

Java 8, 67 bytes

n->(" "+n+" "+n.toString(n,2)+" ").replace("0","").contains(" 11 ")

Try it online.

Explanation:

n->                       // Method with Integer parameter and boolean return-type
  (" "                    //  Have a leading space
   +n                     //  Appended with the input
   +" "                   //  Appended with another space
   +n.toString(n,2)       //  Appended with the input as binary-String
   +" ")                  //  Appended with a trailing space
        .replace("0","")  //  Then remove all "0"s from this string
        .contains(" 11 ") //  Check if what remains contains 11 surrounded with spaces
\$\endgroup\$
3
  • \$\begingroup\$ Surely n.toString(2) suffices? \$\endgroup\$ – Neil Oct 3 '20 at 0:27
  • \$\begingroup\$ @Neil No, I'm afraid not. The first n is used as a static call. Non-golfed, it would be Integer.toString(n,2), which is a shorter variant of Integer.toBinaryString(n). What you suggest is short for Integer.toString(2), which would result in "2", since the Integer.toString(int) method will use base-10 by default. \$\endgroup\$ – Kevin Cruijssen Oct 3 '20 at 11:38
  • \$\begingroup\$ Ah, I thought there would be a non-static toString(radix) method for some reason. \$\endgroup\$ – Neil Oct 3 '20 at 15:51

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.