# Programming Challenges

Show 40 post(s) from this thread on one page
Page 1 of 7 12345 ... Last
• 08-19-2003, 09:59 AM
trashthing
Programming Challenges
hi. i have started this thread for people to post programming challenges for others to solve. the programming challenges are exercises for people to practice programming. once you have completed a challenge post your code. when you are posting your code, please quote the challenge that you are responding to.

happy coding! :D
• 08-19-2003, 03:18 PM
swap two integers without using a temporary variable.
• 08-19-2003, 04:57 PM
Sepero
Cool. That was fun. How 'bout another. :p

Written in C++. I deleted my previous post and included the file instead. This way it doesn't spoil the fun for others.

Edit:
• 08-19-2003, 06:59 PM
cfaun5
Solution attached.
• 08-19-2003, 08:13 PM
dchidelf
What if I'm allergic to carrots? ;)

Hmmm...lets see...the hard way.
Code:

```#include <stdio.h> #define flip_bit if(a&1){                  \     if(b&1) { a >>= 1; a |= 0x80000000; } \     else    { a >>= 1; a &= 0x7FFFFFFF; } \     b >>= 1; b |= 0x80000000;            \   }                                        \   else {                                  \     if(b&1) { a >>= 1; a |= 0x80000000; } \     else    { a >>= 1; a &= 0x7FFFFFFF; } \     b >>=1; b &= 0x7FFFFFFF;              \   } int main(){   int a = -343;   int b = 711;   fprintf(stdout,"a: %d  b: %d\n",a,b);   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   flip_bit flip_bit flip_bit flip_bit   fprintf(stdout,"a: %d  b: %d\n",a,b);   return 0; }```
This isn't really a legitimate solution, so I figured there would be no harm in posting it in the message.
• 08-19-2003, 08:39 PM
Suramya
Quote:

swap two integers without using a temporary variable.
This thread is a cool idea. Here is my solution.

- Suramya
• 08-19-2003, 09:55 PM
bwkaz
Here's another challenge. Write a Web server.

Oh, wait, that's way too hard. ;)

Better:

Write a rot13 implementation, those'd be cool to see. Take stdin, transform it according to rot13 (changing nothing if the symbol isn't a letter, but rotating both uppercase and lowercase letters, separately), and print it to stdout. This program makes a nifty tool when people start talking in threads like this:

Quote:

Ubj vf rirelbar gbqnl?

Bu, abg onq, ohg V jbaqre vs nalobql ryfr trgf guvf guernq?

V'z fher gurl qba'g, ohg bu jryy.
Of course, I doubt anybody would do that anymore (that was something that happened more in the old G:OT forum), but still... ;)
• 08-20-2003, 01:53 AM
tecknophreak
prolly not. :D

Code:

```#include <iostream> using std::cin; using std::cout; int main() {         char ch;                while (cin.get(ch)) {                 cout << (char)(isalpha(ch) ? ((isupper(ch) ? 'A': 'a')                                 + ((ch - (isupper(ch) ? 'A' : 'a') + 13) % 26))                                 : ch);         } }```
• 08-20-2003, 03:07 AM
o0zi
Here's my Perl solution to swapping two variables:

(\$a, \$b) = (\$b, \$a);
:D

Web server did you say? Hmm...

#!/usr/bin/perl -w
use HTTP::Daemon;
\$HTTPserver=HTTP::Daemon->new(Timeout =>600);
print "My url is: ",\$HTTPserver->url,".\n";
while (\$HTTPclient = \$HTTPserver->accept) {
\$HTTPclient->autoflush(1);
print \$HTTPclient
Welcome to my web server!
This web server was written in Perl.
</BODY></HTML>';
\$HTTPclient->close;
}
• 08-20-2003, 07:10 AM
x_Ray
rot13 in python

Code:

```#!/usr/bin/python def rot13(text):     new_text = []     for x in text[0:]:         up = False         if x.isupper():             x = x.lower()             up = True         byte = ord(x)         if byte >= ord('a') and byte <= ord('z'):             x = chr((byte - ord('a') + 13) % 26 + ord('a'))             if up:                 x = x.upper()         new_text.append(x)     return ''.join(new_text) text = raw_input('Enter some text: ') print rot13(text)```
Or the easy way; text.encode('rot13') :)
• 08-20-2003, 09:52 AM
Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
• 08-20-2003, 10:10 AM
joelc
Hmm, my school had an upper level CS course called Applied Algorithms. The course basically consisted of a list of 30 specific programs handed out at the beginning of the semester, of which you had to write any 20 of them before the end. Class time would be spent clarifying rules, discussing implementation problems, advice, etc. I never took the course, but I am good friends with the professor. I might be able to get and post these programs when I visit the school again in a couple of weeks, if anyone is interested.

 Several, but not all, of these programs had very simple implementations (less than a page in c++), but had speed requirments (terms of Bigo) that make them more complicated.
• 08-20-2003, 11:08 AM
sploo22
Sepero:

Code:

```int main(int argc, char **argv) {     char buf[100];     if (argc != 2) return 1;     if (argv[1][0] != '-') return 1;     if (argv[1][1] == "c")     {         fgets(buf, 100, stdin);         printf("x\n");         return 0;     } else {         fgets(buf, 100, stdin);         printf("She sells \$ea sheLLs, by tHe se@ shorE.\n");         return 0;     }     return 1; }```
program -c to compress, program -d to decompress.

I love cheating :p
• 08-20-2003, 08:18 PM
bwkaz
Quote:

Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
( a + ib ) * ( c + id ) = ac - bd + i ( ad + bc )

So, I don't think I can figure a way to do it in less than four multiplications...

Hmm, maybe this:

( a + ib ) c + ( a + ib ) id

But that's not a canonical-form complex number, not really...

I can't come up with a way to relate ad + bc and ac - bd, either... if I could, that might lower the number of multiplications needed...

Good question! Just wish I could figure an answer... ;)
• 08-21-2003, 12:42 AM
Strogian
Quote:

Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
What's a real multiplication? Can I use division? :D

EDIT: Oh, I'm close. I know it. ;)

EDIT: Ah nevermind, I got nothing. :D
• 08-21-2003, 03:29 AM
o0zi
Checking up the definition of (a+ib)(c+id), it's

which is what bwkaz found.

However, the question was:
Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications

We've only used 1 multiplication, and that's multiplying (ad+bc) by i.
The only further step I could find was:

but nothing else. Any other takers?

After I was so pleased with my web server:(
• 08-21-2003, 03:31 AM
o0zi
Strogian, you can effectively use division, because if you want to divide n by 7, just multiply it by 1/7.
• 08-21-2003, 09:30 AM
Quote:

Originally posted by o0zi
Checking up the definition of (a+ib)(c+id), it's

[snip]

We've only used 1 multiplication, and that's multiplying (ad+bc) by i.
The only further step I could find was:

No, it's not a trick like that. It would still take 4 real multiplications to compute (ac-bd) and (ad+bc). There is a way to do it so you really only have to compute 3 products; and though it takes 1 extra addition and 2 extra subtractions, you would still get savings from not having to do the more expensive multiplication.

Here's another challenge. You can waste alot of multiplications evaluating a polynomial such as a x^3+b x^2+ c x + d , but its possible to evaluate an n degree polynomial with only n multiplications. Can you figure it out? Don't forget that computing x^3 takes 3 multiplications in itself.
• 08-21-2003, 12:56 PM
Stuka
grady: computing x^3 only requires 2 multiplications last time I checked. However, getting it to n is tougher ;)
<edit> No, it's not, I just forgot how to do it. I'll hack together a solution now.</edit>
• 08-21-2003, 02:34 PM
Strogian
I could do it if there weren't any coefficients, does that count? :p
• 08-21-2003, 03:21 PM
Quote:

Originally posted by Stuka
grady: computing x^3 only requires 2 multiplications last time I checked.
The summer must be turning me into an imbicile. The n is correct. You can evaluate the polynomial with n products.

Here's another challenge: Write a function using only bit operations that can sum any two signed integers. No + or - is allowed anywhere in the function.
• 08-21-2003, 07:10 PM
bwkaz
Quote:

Here's another challenge. You can waste alot of multiplications evaluating a polynomial such as a x^3+b x^2+ c x + d , but its possible to evaluate an n degree polynomial with only n multiplications. Can you figure it out? Don't forget that computing x^3 takes 3 multiplications in itself.
Sure, just factor it.

Oh, wait... not all polynomials factor... :p

Quote:

Here's another challenge: Write a function using only bit operations that can sum any two signed integers. No + or - is allowed anywhere in the function.
Code:

```int sum(int num1, int num2) {     int result = 0;     int i, carry = 0;     for(i=0; i<31; i++) {  /* these +'s don't count, do they? */         result |= (num1 ^ num2) & (1<<i) | carry;         carry = ((num1 & num2) & (1<<i)) << 1;     }     if(carry) {         fprintf(stderr, "Overflow.\n");     }     return result; }```
I think. Haven't tested it, but from what I remember from Computer Architecture, the non-carry bits are just XOR, and carry is determined by ANDing and then shifting left one. Signed vs. unsigned matters not one bit, because signed integers are two's complement, they're equivalent.
• 08-21-2003, 07:27 PM
cfaun5
This function is limited, but for all practical purposes, it works.

Code:

```#include <iostream> using std::cout; int add(int a, int b) {     int c=0, carry=0;     for (int i=1;i<9999999;i*=2) {         int bit1 = a&i, bit2 = b&i;         if ((!(bit1|bit2)) && carry) {             carry--;             bit1 = 1;         }                 if (bit1&bit2) {             bit1 = bit2 = 0;             carry++;         }         if(bit1^bit2)             c |= i;         }     return c; }```
• 08-21-2003, 07:42 PM
kshim5
Programming challenge
Write a short program that asks for your height in integer inches and then convert your height to feet and inches. Have the program use the underscore character to indicate where to type the response. Also, use a const symbolic constant to represent the conversion factor.
• 08-22-2003, 12:39 AM
Quote:

bwkaz said

Sure, just factor it.

Oh, wait... not all polynomials factor...
They might not factor but you could do it this way by calculating all of the roots to the desired precision, however this isn't the best way to solve the problem

http://mathworld.wolfram.com/Fundame...ofAlgebra.html

bwakz, cfaun5, no arithmetic is allowed anywhere in the function, pretend your writing a multiprecision library and you want it to execute as fast as possible.
• 08-22-2003, 01:32 AM
Strogian
Ooh! Ooh! I got it! :D

Well, here's what I got. From here, the program is probably simple. :)

ax^2+bx+c -> x(ax+b) + c
ax^3+bx^2+cx+d -> x(x(ax+b) + c) + d
...and so on...
• 08-22-2003, 02:00 AM
Strogian
And here's the addition one: (I assumed unsigned numbers, but negatives are designed to work seamlessly with an adder, right?)

Code:

```int fastadd(unsigned int a, unsigned int b) {   int tmpa;   do {     tmpa = a ^ b;     b = (a & b) << 1;     a = tmpa;   } while (a && b);   return a|b; }```
I think that's right.. It might actually be more efficient, though, if I just let it go through the one extra add cycle instead of checking both a and b each cycle.
• 08-22-2003, 03:39 AM
o0zi
Here's another challenge: generate some random numbers without using any in-built random functions (like rand).
• 08-22-2003, 03:45 AM
Sepero
Ok, I've got some good decyphering challenges made especially for you guys. These are not impossible like some of the previous posts. They will all decypher into english text. Please Post Your Answer As An Attachment. Have fun guys. :)

Level - Easy:
J}hjqqjsy1~tzgwtpjymjhtij3Wfsp2st{nhjM9}tw

Level - Medium
144 192 208 58 202 178 164 202 48 200 194 198 172 202 202 212 176 192 192 170 36 116 48 188 180 188 194 198 172 200 200 172 170 60 180 190 202 172 198 188 172 170 180 164 202 172 168 198 164 168 184 172 198

Level - Hard
GTSP0@RRTPTRVTNBPYVNY3=>

• 08-22-2003, 08:11 AM
tecknophreak
Quote:

Originally posted by bwkaz
Sure, just factor it.

for(i=0; i<31; i++) { /* these +'s don't count, do they? */

Easy way out:

unsigned int i;

for (i = 4294967295; i; i >>= 1)

You'll get 32 shifts until i = 0, or 31 until i = 1, there's your counter.
• 08-22-2003, 10:41 AM
o0zi
Did any of you ever read "The Code Book" by Simon Singh? He did what Sepero's just done, and had 10 levels of difficulty. If I remember rightly, there was a cash prize, but that was several years ago. Great read.
• 08-22-2003, 11:37 AM
tecknophreak
Quote:

Originally posted by o0zi
Did any of you ever read "The Code Book" by Simon Singh? He did what Sepero's just done, and had 10 levels of difficulty. If I remember rightly, there was a cash prize, but that was several years ago. Great read.
I'm actually in the process of reading that. Singh writes some damn good math books. I also read his Fermat's Theorem book(can't remember exactly what it was)...maybe Fermat's Enigma, or was that by someone else, ramble, ramble...
• 08-22-2003, 01:18 PM
Strogian
Quote:

Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
You have no idea how much pain this problem gave me. :D

x = (a+b)(c+d)
y = ac
z = bd

• 08-22-2003, 02:33 PM
o0zi
(claps Strogian) Ingenious, absolutely ingenious...:)
• 08-22-2003, 04:00 PM
Hey strogian g/j, you got all my challenges. :)

Here's another challenge:
rand( ) in C generates a flat distribution of numbers; you are equally likely to get any given number the generator is capable of returning. If you histogram these numbers the histogram is relatively flat. Looking at the histogram ( sideways ) it might look like this:

x =0
xxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxx
x = 2^32 - 1

Write a function such that the numbers are distributed as x^2. In other words if you histogrammed many numbers from your function it would look like this ( sideways ):

x = -1
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxx
xx
x
xx
xxxx
xxxxxxxxxx
xxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x = 1

only produce numbers on the interval [-1,1] instead of [0,2^32-1]. Put your function in a small program that outputs to the console a 20 bin ( line ) histogram similar to the one's I've shown above to prove ( by eyeball method ) that your function works correctly. If you really want to show off the function's legitimacy compute the chi-squared. You are allowed to use your language's native flat-distribution random number generator in your program.
• 08-22-2003, 04:23 PM
trashthing
i have a challenge. write a program that reads a text file and prints out how many characters, numbers, letters, words, and lines there are.
• 08-22-2003, 06:44 PM
bwkaz
Quote:

Originally posted by trashthing
i have a challenge. write a program that reads a text file and prints out how many characters, numbers, letters, words, and lines there are.
Code:

```#!/bin/bash /usr/bin/wc "\$@"```
You just have to give it the right options... ;)
• 08-23-2003, 11:21 AM
o0zi
Another challenge: write a program that converts any decimal number to any base up to base 36, where numbers after 0-9 are represented by A-Z.
• 08-23-2003, 09:36 PM
Sepero
Quote:

Originally posted by o0zi
Convert decimal numbers to a base up to base 36, where numbers after 0-9 are represented by A-Z.
Cool. I only thought I had to do 36base, but after re-reading it, I see he wanted "up to base 36". After a few modifications, it does binary, octal, hex, up to base36 and everything inbetween!!! :D
• 08-23-2003, 09:40 PM
Sepero
I'm attaching the binary for any non-C++ programmers. I might actually use this program sometime, so I thought you guys might too. :)
Show 40 post(s) from this thread on one page
Page 1 of 7 12345 ... Last