Fixed, will handle 1/4 and 3/4 correctly now.
i=...print((i=="11"or i=="01"or i=="0")and"1"or"0")
This version (64 characters) will handle irregular input (e.g. 000, 010, 11000), and will read from keyboard allowing any length (but still not unbounded).
i=io.read()print((i:find("^0+$")or i:find("^.10*$"))and"1"or"0")
ok, take #2 now that I've (hopefully) got my addition straight.
It looks like the key here is to do a translation from radix-2 math to radix-3 math with some kind of state machine.
Let's say the input after k bits is some binary decimal. We don't know whether the input has terminated yet or not. Therefore let's say the input number is some number x[k] + an unknown number between 0 and 2-k-1. This interval is either completely outside of the Cantor Set (in which case we return 0), or it is possibly inside the Cantor Set, in which case we continue. Now to figure out if that's codeable as a state machine....
...this seems fiendishly difficult, never mind the code golf aspects of it. I have a rough outline of how to approach, coding a pair of Cantor Set boundaries (e.g. [1/3,2/3] or [1/9,2/9]) as a pair of integers scaled by a number M = 2k3j, and the current input interval as a pair of integers scaled by M, but the numbers seem to be getting larger and larger, so it doesn't seem to lend itself to a finite state machine as far as I can tell. :/
very rough algorithm, in javascript-y pseudocode, no attempt at code size minimization:
var j = 0; // power of 3 we scale to
var k = 0; // power of 2 we scale to
var x0=0, x1=1; // ends of an interval within cantor-set after stage j
var i0=0, i1=1; // ends of the interval containing the input number
// These intervals are [x0,x1] (closed) and [i0,i1) (half-open)
while (1)
{
b = get_input_bit(); // (0 or 1), or -1 if input has terminated
if (b == -1)
break;
++k;
if (b == 0) // lower half of previous interval
{
i1 = i0+i1;
i0 <<= 1;
}
else // upper half of previous interval
{
i0 = i0+i1;
i1 <<= 1;
}
x0 <<= 1;
x1 <<= 1;
if (i1 <= x0 || i0 > x1)
{
// Possible Cantor interval and input interval are disjoint...
// the entire input interval is outside the Cantor set.
// Stop and return debugging info.
return {inSet: false, i0:i0,i1:i1,x0:x0,x1:x1,j:j,k:k};
}
// Now to compare input interval with Cantor interval.
if ((i1-i0)*3 < (x1-x0))
{ // If input interval is less than 1/3 size of Cantor interval,
// it can overlap at most 1 subinterval.
// Figure out which one.
//scale up by a factor of 3
++j;
i1 *= 3;
i0 *= 3;
yB = 2*x1+x0;
yA = 2*x0+x1;
// middle third of the cantor interval = [yA,yB]
if (i1 <= yB)
{
// input interval excludes right third of Cantor interval,
// so make the left third our new Cantor interval
x0 = 3*x0;
x1 = yA;
}
else if (i0 > yA)
{
// input interval excludes left third of Cantor interval,
// so make the right third our new Cantor interval
x0 = yB;
x1 = 3*x1;
}
else
{
throw("Algorithm error, I made a horrible mistake");
}
// now shift everything over (this algorithm uses relative integers,
// and does not rely on absolute integers)
x0 -= i0;
x1 -= i0;
i1 -= i0;
i0 = 0;
}
}
// OK, now the input has terminated, and we have to figure out whether
// the input can be expressed as an infinitely repeating series of 0's or 2's
// in ternary.
// Left as an exercise to the reader, it's late and I have to get to sleep.... 8/
return {inSet: true, i0:i0,i1:i1,x0:x0,x1:x1,j:j,k:k};
I think I have the "return false" case covered... sigh.
Haskell, 291 262 246 characters. Works for arbitrarily large finite input and for infinite input if the answer is 0.
import Ratio
f w a=elem a w||a<1%3&&f(a:w)(a*3)||a>2%3&&f(a:w)(a*3-2)
i a b c=let p=a*3;q=b*3;m=(a+b)/2 in q<1&&i p q c||p>2&&i(p-2)(q-2)c||(p<1&&q>1||p<2&&q>2)&&case c of('0':t)->i a m t;('1':t)->i m b t;_->f[]a
main=interact$show.fromEnum.i 0 1
Here's my previous answer which only worked for finite input:
import Data.Ratio
f w a = let b = a * 3 in
elem a w || b <= 1 && f (a:w) b || b >= 2 && f (a:w) (b-2)
c = f [0]
t d = sum $ zipWith (%) d $ iterate (* 2) 2
main = getLine >>= print . fromEnum . c . t . map (read . (:[]))
The function c takes a rational number and returns True if it's in the Cantor set. The rest is window dressing.
I concluded that I could safely change [0] to [] (that is, start with an empty set of "fractions we've already seen") and <=/>= to </> (because we will never see an exact 1/3 or 2/3 there).
Evaluates Cantor setness of the floating-point representation of 0.b1b2... from a finite-length command-line argument
$.=1;$./=2,$r+=$_*$.for pop=~/./g;for(0..99){$r-=2if($r*=3)>2;$r>1&&die"0
"}die"1
"
C, 142 141 characters
Should handle up to about 52 input characters.
#include <stdio.h>
double v,n=1;d,a=99;main(){for(;(d=getc(stdin))>47;v+=(d-48)*(n/=2))
;do{v=(v>0.5?1-v:v)*3;}while(v<1&&--a>0);return a<1;}
$ echo 0 | ./a.exe ; echo $?
1
$ echo 1 | ./a.exe ; echo $?
0
$ echo 11 | ./a.exe ; echo $?
1
$ echo 10101011 | ./a.exe ; echo $?
0
$ echo 10101010 | ./a.exe ; echo $?
0
Edited to not stop iterating when reaching the end of input...
SED - 41 characters
Props to gwell for the idea...
s/^\(0\|11\|01\)0*$/x/;s/[01]\+/0/;s/x/1/
echo "10011" | sed -e 's/^\(0\|11\|01\)0*$/x/;s/[01]\+/0/;s/x/1/'
0
echo "11000" | sed -e 's/^\(0\|11\|01\)0*$/x/;s/[01]\+/0/;s/x/1/'
1
My SED sucks - so this can probably be reduced further.
Python, 150 characters
Very naive solution for now (includes unnecessary conversion step to base 10), will focus on shortening it later. Only works for finite inputs.
j,s=0,0
for i in raw_input():
j-=1;s+=int(i)*(2**j)
d=[]
while 1:
n=s*3;m=int(n)
if m==1:print 0;break
if n in d:print 1;break
d.append(n);s=n-m