65
\$\begingroup\$

Task:

Given an integer input, figure out whether or not it is a Cyclops Number.

What is a Cyclops number, you may ask? Well, it's a number whose binary representation only has one 0 in the center!

Test Cases:

Input | Output | Binary  | Explanation
--------------------------------------
0     | truthy | 0       | only one zero at "center"
1     | falsy  | 1       | contains no zeroes
5     | truthy | 101     | only one zero at center
9     | falsy  | 1001    | contains two zeroes (even though both are at the center)
10    | falsy  | 1010    | contains two zeroes
27    | truthy | 11011   | only one zero at center
85    | falsy  | 1010101 | contains three zeroes
101   | falsy  | 1100101 | contains three zeroes
111   | falsy  | 1101111 | only one zero, not at center
119   | truthy | 1110111 | only one zero at center

Input:

  • An integer or equivalent types. (int, long, decimal, etc.)

  • Assume that if evaluating the input results in an integer overflow or other undesirable problems, then that input doesn't have to be evaluated.

Output:

  • Truthy or falsy.

  • Truthy/falsy output must meet the used language's specifications for truthy/falsy. (e.g. C has 0 as false, non-zero as true)

Challenge Rules:

  • Input that is less than 0 is assumed to be falsy and thus does not have to be evaluated.

  • If the length of the binary representation of the number is even, then the number cannot be a Cyclops number.

General Rules:


This is my first Programming Puzzles & Code Golf challenge, so any feedback on how I should improve would be much appreciated!

\$\endgroup\$
  • 24
    \$\begingroup\$ Note: This is A129868 \$\endgroup\$ – tsh Mar 8 at 2:40
  • 35
    \$\begingroup\$ +1 for the 2800 year late pop culture reference in the title \$\endgroup\$ – Sanchises Mar 8 at 9:21
  • \$\begingroup\$ what is the maximum number that is be tested? \$\endgroup\$ – Serverfrog Mar 8 at 13:06
  • \$\begingroup\$ @Serverfrog since I did not specify a limit, assume that any positive integer can be tested. \$\endgroup\$ – Tau Mar 8 at 14:09
  • \$\begingroup\$ Is binary input allowed? \$\endgroup\$ – Qwertiy May 25 at 8:22

46 Answers 46

1
\$\begingroup\$

Stax, 9 7 bytes

ç8┤-½Θ■

Run and debug it

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

K (ngn/k), 19 bytes

{1=(~x)+/~a&|a:2\x}

Try it online!

{ } function with argument x

2\x the bits of x

a: assign to a

a&|a and between a and its reverse (|a)

~ not

+/ sum

(~x) use "not x" as the initial value for the sum. this is to correct for 2\x returning an empty list of bits when x is 0

1= compare with 1

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

dc, 62 60 bytes

[2~rd0<B]dsBx1kz2/szsi[1r-si]sC[zlz=Cli*siz0<M]sMz1=Cz1<Mlip

Try it online!

dc has no native truthy/falsy values (conditionals either execute a macro or they don't); using 1 for truthy and 0 for falsy, I hope that's ok.

[2~rd0<B]dsBx          # Basic breakdown into binary. Every digit is a stack entry. Luckily this
                       # also leaves an extra 0 on the stack.
1k                     # Set precision to one - needed it at 0 for the binary-ifier.
z2/sz                  # Divide the stack depth by 2 and store it in 'z'. This is why we're lucky
                       # that the binary-ifier leaves an extra bit on the stack! Numbers with even 
                       # numbers of binary digits will now have an odd number & this value will be
                       # (whatever).5 which... isn't a valid stack depth.
si                     # Seed 'i' which is our truthiness register w/ that extra 0
[1r-si]sC              # Macro 'C' toggles the top of stack between 0 and 1 by subtracting it from 1.
                       # It stores this in 'i'. This is the only way 'i' ever becomes 1.
[zlz=Cli*siz0<M]sM     # First we test if we're at the position of the stack that matches up with 
                       # 'z', and run 'C' if so. Thus, if we're in the 'Cyclops' position (the
                       # middle), we'll flip that from a 0 to a 1 or vice versa. Next we load 'i'
                       # and multiply it by top of stack, putting that back in 'i'. For the first half
                       # this whole thing does nothing but multiply stuff by zero. In the middle
                       # position (if there is one) it sets 'i' to 1 if it's a zero. For the rest of
                       # the digits, it multiplies by '1' if things are ok, and '0' if there's another
                       # (Cyclops-invalidating) zero.
z1=Cz1<M               # 1 and 0 don't work w/o special treatment. Run 'C' if it's one of these, 
                       # otherwise start 'M'
lip                    # Print 'i'

Golfed off two bytes because my brain was fried and I was using a wasteful, convoluted method of toggling between 1 and 0.

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

C++, 142 138 107 106 104 88 85 82 72 bytes

-10 bytes thanks to ceilingcat

int f(int n){int c=1;for(;n&1;n/=2)++c;while(n/=2,--c,n&1);return!n&!c;}

Ungolfed:

bool is_cyclops(int n)
{
    int ones = 1;
    while ((n & 1) == 1)
    {
        ++ones;
        n /= 2;
    }
    while (--ones, n /= 2, (n & 1) == 1)
    {
        // nothing to do
    }
    return n == 0 && ones == 0;
}
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 135 130 bytes

Uses the Formula described here: A129868

(n)->java.util.stream.IntStream.range(0,16).map(r->((Double)(Math.pow(2,2*r+1)-(Math.pow(2,r)-1)-2)).intValue()).anyMatch(c->c==n)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Why do you say it doesn't work with all positive integers? It works fine up to a million, and I see no reason why it'd stop working. \$\endgroup\$ – Grimy Mar 8 at 16:02
  • \$\begingroup\$ codegolf.stackexchange.com/questions/181128/… "...any positive integer can be tested". Example where it wont work anymore: 2096127. This is due to that i only test the first 11 of the OEIS A129868 Numbers. could do more maybe, but it will not work vor ANY positive integer i think \$\endgroup\$ – Serverfrog Mar 8 at 16:09
  • 2
    \$\begingroup\$ Okay, so this doesn't actually answer the problem, you should edit it to make it work or delete it. Marking an answer as non-competing isn't a free pass, it should still be valid. \$\endgroup\$ – Grimy Mar 8 at 16:13
  • \$\begingroup\$ It's funny how you first say everything is fine, and after i point you where the OP post that limit (that wasn't really defined before this answer was posted) you aggressively force to make it work now or deleting it without seemingly to know the timeline between answer and the point it was invalid :P \$\endgroup\$ – Serverfrog Mar 8 at 16:21
  • 1
    \$\begingroup\$ Currently it is unkown if this or any other answer is valid because OP don't really defined what he meant with any positive integer as a integer could be 2 things, one has a maximum value the other not. And after my last change it is working with the 32-bit signed Integer \$\endgroup\$ – Serverfrog Mar 8 at 16:41
0
\$\begingroup\$

C++ (clang), 72 68 67 bytes

As with Neil's and Grimy's solutions, this works by asserting that the input is of the form \$(2^k-1)(2^{k+1}+1)\$.

5 bytes were dropped thanks to Arnauld, by changing ((x)+1) to -~(x) and ((x)-1) to ~-(x), and then changing n-a*-b to n+a*b.

int f(int n){int z,k=0;while((z=n+~-(1<<k)*~(1<<++k))>0);return!z;}

Try it online!

Ungolfed:

bool is_cyclops_number(int n)
{
    for (int k=0;; k++)
    {
        int z = n - ((1<<k)-1) * ((1<<(k+1))+1);
        if (z == 0)
            return true;
        if (z < 0)
            return false;
    }
}

C (gcc), 41 bytes

Returns zero for true and nonzero for false.

k;f(n){for(k=0;n+~-(1<<k)*~(1<<++k)>0;);}

Try it online!

This demonstrates why I hate the implicit accumulator return value exploit that is commonly used in C submissions and less often in C++ submissions. It's fragile and very much platform dependent. Here, it depends upon the comparison operator > not changing the value of the accumulator.

\$\endgroup\$
  • \$\begingroup\$ Suggest for(k=1;n+~-k*~(k*=2)>0;); instead of for(k=0;n+~-(1<<k)*~(1<<++k)>0;); \$\endgroup\$ – ceilingcat May 24 at 22:43
0
\$\begingroup\$

Swift, 161 bytes

func c(a:Int)->Int{
    let b=String(a,radix:2)
    let f=b.firstIndex(of:"0")
    return a>=0 && f==b.lastIndex(of:"0") && f?.encodedOffset==b.count/2 ? 1 : 0
}

Try it online!

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

PHP, 74 bytes

function($x){return($c=strlen($a=decbin($x)))&1&&trim($a,1)===$a[$c/2|0];}

Try it online!

Totally naïve non-mathematical approach, just strings.

function cyclops( $x ) {
    $b = decbin( $x );     // convert to binary string (non-zero left padded)
    $l = strlen( $b );     // length of binary string
    $t = trim( $b, 1 );    // remove all 1's on either side
    $m = $b[ $l / 2 |0 ];  // get the middle "bit" of the binary string
    return 
        $l & 1 &&          // is binary string an odd length?
        $t === $m;         // is the middle char of the binary string the same as
                           // the string with left and right 1's removed? (can only be '0')
}

Or 60 bytes based on @Chronocidal's algorithm above.

function($x){return decbin($x)==str_pad(0,log($x,2)|1,1,2);}

Try it online!

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

Perl 5 -p, 32 bytes

$_=(sprintf'%b',$_)=~/^(1*)0\1$/

Try it online!

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

Java, 201 bytes (compilable)

Hmm, a different approach in java, runnable on commandline (so there is much to cut out).

class Z{public static void main(String[]a{a=Integer.toBinaryString(Integer.valueOf(a[0])).split("0");System.out.println(a.length==0?1:(a.length!=2?1:a[0].length()-a[1].length()+a.length-2)==0?1:0);}}

prints 0 for non cyclops and 1 for cyclops numbers.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! I think you can remove public . Is there a ) missing after String[]a? a.length==0 -> a.length < 1, again later (maybe?). \$\endgroup\$ – Stephen Mar 11 at 18:54
0
\$\begingroup\$

Factor, 69 bytes

: f ( n -- ? ) >bin [ dup reverse = ] [ [ 48 = ] count 1 = ] bi and ;

Try it online!

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

PHP

The shortest code should be this:

preg_match('`^(?<l>1*)0\k{l}$`', decbin($n));

Here the script to test it:

$inputs = [
    0,
    1,
    5,
    9,
    10,
    27,
    85,
    101,
    111,
    119,
];


function isCyclop($n) {
    return preg_match('`^(?<l>1*)0\k{l}$`', decbin($n));
}

foreach ($inputs as $input) {
    echo "$input : ".(isCyclop($input)?'truthy':'falsy').PHP_EOL;
}
\$\endgroup\$
0
\$\begingroup\$

Java, 96 bytes

n->{String[]a=Integer.toBinaryString(n).split("0");return n==0||a.length==2&&a[0].equals(a[1]);}

Try it online!

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

Perl 6 (26 bytes)

{so .base(2)~~/^(1*)0$0$/}
\$\endgroup\$
  • \$\begingroup\$ You can remove the so, since the output can just be truthy/falsey, but it ends up the same as my answer \$\endgroup\$ – Jo King Mar 19 at 2:17
0
\$\begingroup\$

Pip, 87 bytes

a:qTa<=1{((a%2)=0)?(x:"0".x)(x:"1".x)a//:2}1=a?x:"1".xsc:x^"0"x=0|#x%2=1&(c0)=(c1)&#c=2

Try it online!

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

Gaia, 10 9 bytes

b:ṭ¤0C1=∧

Try it online!

Verify All Test Cases

b:		% convert to binary and dup
  ṭ		% is it a palindrome?
        ∧	% and
   ¤0C		% is the count of zeros
      1=	% equal to 1?
		% implicit print top of stack
\$\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.