A positive integer N is K-sparse if there are at least K 0s between any two consecutive 1s in its binary representation.
So, the number 1010101 is 1-sparse whereas 101101 is not.
Your task is to find the next 1-sparse number for the given input number. For example, if the input is 12 (0b1100) output should be 16 (0b10000) and if the input is 18 (0b10010) output should be 20 (0b10100).
Smallest program or function (in bytes) wins! Standard loopholes disallowed.
x & (x*2) != 0 algorithm from @alephalphaMy first attempt at Pyth:
f!.&TyThQ
implicit: Q = input()
f hQ find the first integer T >= Q + 1,
that satisfies the condition:
!.&TyT T & (T * 2) is 0
3 bytes saved thanks to DigitalTrauma.
l~{)___+&}g
l~ "Read and eval input.";
{ }g "Do while...";
)_ "Increment and duplicate (call this x).";
__+ "Get two more copies and add them to get x and 2x on the stack.";
& "Take their bitwise AND. This is non-zero is as long as x's base-2
representation contains '11'.";
This leaves the last number on the stack which is printed automatically at the end of the program.
This is a complete python program that reads in n, and prints the answer. I think it does quite well in the readability sub-competition.
n=input()+1
while'11'in bin(n):n+=1
print n
The test results:
$ echo 12 | python soln.py
16
$ echo 18 | python soln.py
20
f!}`11.BThQ
Try it online: Pyth Compiler/Executor.
implicit: Q = input()
f hQ find the first integer T >= Q + 1,
that satisfies the condition:
!}`11.BT "11" is not in the binary representation of T
"11" into `11.
\$\endgroup\$
Saved 11 bytes thanks to Martin Büttner.
#+1//.i_/;BitAnd[i,2i]>0:>i+1&
#!perl -p
sprintf("%b",++$_)=~/11/&&redo
Or from the command line:
perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"
1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}
This evaluates to a monadic function. Try it here. Usage:
1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16
1∘+ ⍝ Increment the input ⍺
⍣{ } ⍝ until
~∨/ ⍝ none of
2∧/ ⍝ the adjacent coordinates contain 1 1 in
⍺⊤⍨⍺⍴2 ⍝ the length-⍺ binary representation of ⍺.
A monadic verb. Fixed to obey the rules.
(+1 1+./@E.#:)^:_@>:
First, this is the verb with spaces and then a little bit less golfed:
(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:
Read:
] The argument
+ plus
[: +./ the or-reduction of
1 1 E. the 1 1 interval membership in
#: the base-2 representation of the argument,
[: ( )^:_ that to the power limit of
>: the incremented argument
The argument plus the or-reduction of the
1 1interval membership in the base-2 representation of the argument, that to the power limit applied to the incremented argument.
I basically compute if 1 1 occurs in the base-2 representation of the input. If it does, I increment the input. This is put under a power-limit, which means that it is applied until the result doesn't change any more.
{⍵+∨/2∧/⍵⊤⍨⍵⍴2}⍣=.
\$\endgroup\$
Using the fact that, for a 1-sparse binary number, x&2*x == 0:
f=x=>x++&2*x?f(x):x
No regexp, no strings, recursive:
R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n
Iterative version:
F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}
It's very simple, just using right shift to find a sequence of 11. When I find it, skip to next number. The recursive version is directly derived from the iterative one.
Ungolfed and more obvious. To golf, the trickiest part is merging the inner and outer loops (having to init x to 3 at start)
F = n=>{
do {
++n; // next number
for(x = n; x != 0; x >>= 1) {
// loop to find 11 in any position
if ((x & 3) == 3) { // least 2 bits == 11
break;
}
}
} while (x != 0) // if 11 was found,early exit from inner loop and x != 0
return n
}
%4>2 looks like some sorcery from Number Theory, can you please explain || provide a link?
\$\endgroup\$
f=input()+1
while f&2*f:f+=1
print f
Used the logic x & 2*x == 0 for 1-sparse number.
Thanks to @Nick and @CarpetPython.
Thanks to Martin Büttner for saving 9 bytes and Pietu1998 for 4 bytes!
function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}
How it works: it runs a for loop starting from a + 1 as long as the current number is not 1-sparse, and if it is, the loop is interrupted and it returns the current number. To check whether a number is 1-sparse, it converts it to binary and checks whether it does not contain 11.
Un-golfed code:
function nextOneSparseNumber(num) {
for (num++; /11/.test(num.toString(2)); num++);
return num;
}
n->(while contains(bin(n+=1),"11")end;n)
This creates an anonymous function that accepts a single integer as input and returns the next highest 1-sparse integer. To call it, give it a name, e.g. f=n->..., and do f(12).
Ungolfed + explanation:
function f(n)
# While the string representation of n+1 in binary contains "11",
# increment n. Once it doesn't, we've got the answer!
while contains(bin(n += 1), "11")
end
return(n)
end
Examples:
julia> f(12)
16
julia> f(16)
20
Suggestions and/or questions are welcome as always!
Try it here: http://repl.it/gpu/2
In lambda form (thanks to xnor for golfing):
f=lambda x:1+x&x/2and f(x+1)or-~x
Standard function syntax turned out to be shorter than a lambda for once!
def f(x):x+=1;return x*(x&x*2<1)or f(x)
f=lambda x:1+x&x/2and f(x+1)or-~x. It turns out that of you bit-shift right rather than left, you can use x/2 instead of (x+1)/2 because the difference is always in zero bits of x+1. The spec asks for a program though.
\$\endgroup\$
1+:>: 4%:3(?v~~
;n~^?-1:,2-%2<
Usage:
>python fish.py onesparse.fish -v 12
16
3 bytes added for the -v flag.
By recursion:
g=x=>/11/.test((++x).toString(2))?g(x):x
Same without arrow functions.
function f(x){return/11/.test((++x).toString(2))?f(x):x}
(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}
(if a named function is required, solution will be 69 bytes)
λd⋏[›x
λd⋏[›x
λ # Open a lambda for recursion
d # Double
⋏ # Bitwise AND the doubled input with the input
[ # If this is truthy (non-zero):
›x # Increment and recurse
->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}
Pretty basic. A lambda with an infinite loop and a regexp to test the binary representation. I wish that loop yielded and index number.
m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N
Notes:
m+1 to 2*m, where m is the input.~any(x) is true if x contains all zeros or if x is empty
C (32 bytes)
f(int x){return 2*++x&x?f(x):x;}
Recursive implementation of the same algorithm as so many other answers.
‘&Ḥ¬Ɗ1#
A full program accepting a single, non-negative integer which prints a positive integer (as a monadic link it yields a list containing a single positive integer).
Starting at v=n+1, and incrementing, double v to shift every bit up one place and bit-wise AND with v and then perform logical NOT to test if v is 1-sparse until one such number is found.
‘&Ḥ¬Ɗ1# - Main Link: n e.g. 12
‘ - increment 13
1# - 1-find (start with that as v and increment until 1 match is found) using:
Ɗ - last three links as a dyad:
Ḥ - double v
& - (v) bit-wise AND (with that)
¬ - logical NOT (0->1 else 1)
- implicit print (a single item list prints as just the item would)
