Page 1 of 2
Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 11:28 am
by avansc
this one is a bit tricky. you will find lots of answers online, but try and figure this one out on your own.
you are to write a function that takes one argument, of type string. which will have a domain of {0,1}
thus a binary representation ex. char *data = "101101010001010101000101010110010101001010001000101101"
of any length. your function will return a boolean value. true if the binary string is divisible by 3, false if not.
note: you are not allowed to convert the binary string to a number. you are only allowed to work with 1's and 0's
Code: Select all
bool function(char *data)
{
// computation
return true/fase;
}
a huge help on this will be any knowladge of finite state machines. FSM, pumping lemmas.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 1:43 pm
by dandymcgee
I'm looking forward to seeing solutions, because I don't have the slightest clue how to even begin doing any of these challenges. I guess I'm not as good at programming as I thought I was.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 2:10 pm
by avansc
dandymcgee wrote:I'm looking forward to seeing solutions, because I don't have the slightest clue how to even begin doing any of these challenges. I guess I'm not as good at programming as I thought I was.
dont be so hard on yourself. im sure you can do it.
here is a FSM that i whipped together that is for binary numbers that are divisible by 2
not that when you are done with proccessing the string you have to be in state 3 inorder for the sequence to be divisible by 2. if it is in any other state its false.
implimenting it in code is fairly easy.
Code: Select all
switch(state)
{
case 1:
case 2:
case 3:
}
here is a big bonus that will help.
if your divisor is n you will at least have to have n+1 states.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 5:26 pm
by avansc
do you guys need more hints? or are you just not interested?
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 5:40 pm
by Kleithap
Dude, I'm really busy right now with all kinds of other stuff, sorry. Maybe send Falco pm and ask if he wants to post this on the news again?
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 5:43 pm
by Falco Girgis
I'm doing a huge assembly project due at midnight. I keep having homework assignments, so I haven't been able to keep up with these.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 5:57 pm
by avansc
oh yeah, sorry i forgot lots of people are college age. sorries friends.
ps: falco, what is the assembly project about?
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 8:02 pm
by XianForce
dandymcgee wrote:I'm looking forward to seeing solutions, because I don't have the slightest clue how to even begin doing any of these challenges. I guess I'm not as good at programming as I thought I was.
Well that's why they are "challenges" just think on them a bit and you'll think of something. I think these challenges are great. It gets creative juices flowing to do things you normally might not even think to try. Funny thing about this challenge, I was just thinking of doing something with binary numbers, and thought about your challenges, then I got on and you had a binary challenge xD
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 9:05 pm
by sparda
Yeah, lots and lots of homework assignments in this end as well. I glanced at the challenge: I'm curious though, when you say that you can't convert the string to numbers, that means that something like this is not valid, correct?:
Code: Select all
std::string str = "101";
printf("%d", atoi(str.c_str()));
just checking.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 9:27 pm
by avansc
sparda wrote:Yeah, lots and lots of homework assignments in this end as well. I glanced at the challenge: I'm curious though, when you say that you can't convert the string to numbers, that means that something like this is not valid, correct?:
Code: Select all
std::string str = "101";
printf("%d", atoi(str.c_str()));
just checking.
no thats not valid, and even if it was it wouldent help. thats 101 decimal, 101 bin = 5 dec.
here is a funtion that tells you if it is divisible by 2. this should give you a very clear idea behind the concept, and making it divisible by 3 wont be that had.
PS: jot a couple of scenarios down on paper, that helps.
Code: Select all
bool divBy2(char *data)
{
int state = 1;
int count = 0;
while(true)
{
switch(state)
{
case 1:
{
if(data[count] == NULL)
return false;
if(data[count] == '1')
state = 2;
break;
}
case 2:
{
if(data[count] == NULL)
return false;
if(data[count] == '1')
state = 2;
if(data[count] == '0')
state = 3;
break;
}
case 3:
{
if(data[count] == NULL)
return true;
if(data[count] == '0')
state = 3;
if(data[count] == '1')
state = 2;
break;
}
}
count++;
}
}
note that this is not the best FSM, it van be simplified. but i just made it like this to illustrate the basic concept.
Re: Challenge 3 - Binary.
Posted: Tue Nov 04, 2008 10:05 pm
by MarauderIIC
avansc wrote:do you guys need more hints? or are you just not interested?
Most of us are EST and noon to 6pm isn't a whole lot of time to actually read this topic d:
Re: Challenge 3 - Binary.
Posted: Wed Nov 05, 2008 8:12 am
by cypher1554R
avansc wrote:note: you are not allowed to convert the binary string to a number. you are only allowed to work with 1's and 0's
I was smiling until you said this.. :s
Re: Challenge 3 - Binary.
Posted: Wed Nov 05, 2008 8:33 am
by avansc
i could post a solution for numbers divisible by 3, then change the challenge to divisible by 5.
note: making it divisible by 5 takes a bit more brainpower to keep track of thinks, but you can get there if you follow what divisible by 3 does.
also, drawing a finite state machine helps alot. having a picture is a lot easier than trying to code it all in your head.
Re: Challenge 3 - Binary.
Posted: Wed Nov 05, 2008 7:35 pm
by avansc
well i guess this one alluded some. if you had thought about ho a computer does modulus, you might have gotten it.
FSM
and code for that FSM
Code: Select all
bool func(char *data)
{
int state = 3;
while(true)
{
switch(state)
{
case 0:
{
if(*data == NULL)
return true;
if(*data == '1')
state = 1;
break;
}
case 1:
{
if(*data == NULL)
return false;
if(*data == '1')
state = 0;
if(*data == '0')
state = 2;
break;
}
case 2:
{
if(*data == NULL)
return false;
if(*data == '0')
state = 1;
break;
}
case 3:
{
if(*data == NULL)
return false;
state = 1;
break;
}
}
*data++;
}
}
if it finishes in state 0 the modulus = 0, in state 1 mod = 1 and state 2 mod = 2.. nifty hey.
hope you saw that this is actually not that hard.
Re: Challenge 3 - Binary.
Posted: Wed Nov 05, 2008 10:33 pm
by Arce
Aw, fuck. This is the second competition I missed...>.<
Usually I don't have time to enter these as I read them. However, these challenges are pretty freaking great.
I'm confident I can solve this one, though I confess I haven't looked too closely at the specifics and/or hints...Though the competition is over, I still refuse to check out the solution--I'll write my own sometime. ;P
Again, keep up the challenges. May I recommend giving them more time? Though I do know that leaves room for outside sources and/or other means of cheating...Aw, well. Regardless of winner, I like the fuckers. ;P
