Challenge 3 - Binary.

[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.

[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.

[avansc]

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.

[avansc]

do you guys need more hints? or are you just not interested?

[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?

[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.

[avansc]

oh yeah, sorry i forgot lots of people are college age. sorries friends.
ps: falco, what is the assembly project about?

[XianForce]

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

[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.

[avansc]

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.

[MarauderIIC]

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:

[cypher1554R]

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

[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.

[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.

[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