Programming Challenges

[nullsquared]

Not sure if I should put this in back to basics, ideas?

Anyways, we can post & solve programming challenges here. If the solution is obvious to you, then you're probably not the one who should be answering, and more of the one who should be adding challenges

I'll start it off - write a program that parses the follow binary:
01001101 01100001 01100011 01101000 01101001 01101110 01100101 00100000 01000011 01101111 01100100 01100101 00100001
And writes out the characters that are represented by it.

You should have 2 solutions - a compile-time solution (yes, you can hard-code the binary in this case), and a run-time solution (best done from user input, though you can hard-code it here as well, just for simplicity).

Bonus Points
You'll receive bonus points (maybe a cookie ) if your solution is a numerical one. It's just a bit of added logic, since with characters you can test for '0' or '1'

Edit:
Well, compile-time solution is required only for languages that support such a solution. Feel free to use any language you wish to use for the run-time solution.

Edit:
Would be nice if we had [spoiler] tags. Because of this, post solutions at http://ogre.pastebin.com and link to them here, you don't want to ruin the challenge for others.

[jjp]

Not completly on topic but if you like programming challenges take a look at this page: www.spoj.pl

[nullsquared]

Not completly on topic but if you like programming challenges take a look at this page: www.spoj.pl

Definitely. I just thought we'd have our own little Ogre3D community version of the many challenges that are posted everywhere

[_tommo_]

This should do the trick:

SPOILER

Anyway there's no guarantee that the user will input meaningful data, and there isn't any check.
But it should work if the input is correct.
Anyway saturday 2:00 am coding isn't easy

[nullsquared]

1) put it on the pastebin I mentioned, don't spoil it for others

2) interesting solution! I didn't think of using characters to do the parsing, I was thinking of using direct numbers (for example, 101 as an unsigned long). I think I'll add bonus points if a numerical solution is used (and extra bonus points for the compile-time version, which can't use characters )

[syd]

not as easy as I thought
posted a solution that works well, i got "Machine Code!"

[nullsquared]

not as easy as I thought
posted a solution that works well, i got "Machine Code!"

Another interesting string-based solution! (this time based on a tokenizer )

I'm still waiting for someone to put up the numerical-based variant, which is a lot shorter . Like I said, extra points if you make a compile-time version in addition to a run-time version .

[ajs15822]

I had a few minutes to play around this evening, I wrote my solution in Javascript:

Code: Select all

/**
* Overview of algorithm:
* - split input up into tokens, delimited by a space (' ')
* - for each token: read in reverse, convert from binary to character, append to result
* - return decoded result as a string
**/

function decode(input)
{
	var result = "", tokens = input.split(' ');
	
	for(var i = 0, code = 0; i < tokens.length; i++, code = 0)
	{
		for(var j = 0; j < 8; j++)
			if(tokens[i][7 - j] == '1')
				code |= (1 << j);		
				
		result += String.fromCharCode(code);
	}
	
	return result;
}

[syd]

posted a compile time version
it basically use templates, and looks like:

Code: Select all

 cout << MetaParser<0,1,0,0,1,1,0,1>::MachineToChar();
	cout << MetaParser<0,1,1,0,0,0,0,1>::MachineToChar();
	cout << MetaParser<0,1,1,0,0,0,1,1>::MachineToChar();
	cout << MetaParser<0,1,1,0,1,0,0,0>::MachineToChar();
	cout << MetaParser<0,1,1,0,1,0,0,1>::MachineToChar();
     //  ...

I don't know if this was what you expected

[nullsquared]

That's certainly another way of doing it . There's a way to do it completely at compile-time, though (your method has a run-time evaluation function). I'll post it for anyone really curious - but it's really easy if you give it a good thought, so don't cheat if you want to solve it yourself

(again, guys, use the pastebin I posted - don't spoil it for others )

[Kojack]

Two solutions posted.
http://ogre.pastebin.com/m67e73c3 - using boost::spirit
http://ogre.pastebin.com/fede77ee - numeric/class based

[syedhs]

Kojack, your solutions make me wanna try out boost:spirit right away.

[Kojack]

Third solution.
http://ogre.pastebin.com/fd2d45ed - template metaprogramming
Calculating the string is still runtime, but calculating each byte is compile time.

Boost::spirit kicks ass.


Fourth solution.
http://ogre.pastebin.com/f4e6255ea - spirit again, but cheating by using spirit's built in binary number parser. That's what I'd use in a real life spirit situation, but the previous one (solution 1) was more fun.

[Kojack]

It beats doing actual work.

Fifth solution.
http://ogre.pastebin.com/f39c6c6c6 - macro

[nikki]

Woah! Spirit is more awesome than I thought (and I thought it was pretty awesome ).

[FrameFever]

2) interesting solution! I didn't think of using characters to do the parsing, I was thinking of using direct numbers (for example, 101 as an unsigned long). I think I'll add bonus points if a numerical solution is used (and extra bonus points for the compile-time version, which can't use characters )

you have to use characters, how can you else save a binary like 00010100 in a long data type ?

[Kojack]

you have to use characters, how can you else save a binary like 00010100 in a long data type ?

See my second, third and fifth solutions.

[_tommo_]

Edited my last post to avoid spoilers, and updated my solution: now the program removes the non-binary chars from the string...

EDIT: D'oh! I posted the new version as Anonymous...

[syd]

@kojack: man you've ruined my cookies ambitions !
very nice code

[nikki]

@kojack: man you've ruined my cookies ambitions !
very nice code

Yeah, I've gotta say: Kojack is one of 'em 'real' hackers.

Worth going to Australia just for Kangaroos and Kojack.

[nullsquared]

Yeah, I was a bit when I saw a thousand different solutions in a row.

[Kojack]

Just don't ask me to write anything useful.


A bit of a warning, all of my numeric versions require the numbers start with a 0, otherwise the answer is wrong (easy to fix, but then it doesn't work with numbers that start with 0). Sarcastic "Yay!" for the c++ parser doing fun stuff with numbers.

[syd]

A bit of a warning, all of my numeric versions require the numbers start with a 0, otherwise the answer is wrong (easy to fix, but then it doesn't work with numbers that start with 0). Sarcastic "Yay!" for the c++ parser doing fun stuff with numbers.

this means the cookie belongs to me!

[nullsquared]

A bit of a warning, all of my numeric versions require the numbers start with a 0, otherwise the answer is wrong (easy to fix, but then it doesn't work with numbers that start with 0). Sarcastic "Yay!" for the c++ parser doing fun stuff with numbers.

Mwahaha, well, mine DOES!

Code: Select all

int main()
{
    std::cout << decimal_t<10000001>::value << "\n"; // outputs 257
}

[syd]

Mwahaha, well, mine DOES!

Code: Select all

int main()
{
    std::cout << decimal_t<10000001>::value << "\n"; // outputs 257
}

how comes it outputs 257 ?? A byte has 256 possible values right?