Cool solution. You put it under the LGPL? There's a man with principles:p
Printable View
Cool solution. You put it under the LGPL? There's a man with principles:p
Thanks for the compliment.(Notice my signature) :D
I was gonna use GPL, but I figured it's a little extreme for something small as this.
Challenge: Write a function that reverses the bits of an integer, i.e. 100110 -> 011001. The shorter the function the better. This is an essential procedure when coding a fast fourier transform.
do you mean like this:
orCode:unsigned int x(1000);
return ~x;
Code:unsigned int reverseBits(unsigned int x) {
unsigned int res(0), cntr(0xFFFFFFFF);
while (cntr) {
cntr >>= 1;
res <<= 1;
res |= x & 1;
x >>= 1;
}
return res;
}
The latter, I didn't realize my example was an xor too.
sorry, stuck with the shifting counter, non-shifting is quicker, believe it or not
[/B][/QUOTE]Code:unsigned int reverseBits(unsigned int x) {
unsigned int res(0), cntr(32);
while (cntr--) {
res <<= 1;
res |= x & 1;
x >>= 1;
}
return res;
}
Nice job, techno.
Heh, that makes me think of one.. Come up with bitwise-shift and increment (or decrement) functions, using only the bitwise operations. (that doesn't include >> :))Quote:
sorry, stuck with the shifting counter, non-shifting is quicker, believe it or not
Why's everyone always got to spell my name wrong? :( Oh, right maybe cause I spelled it wrong in the first place. :DQuote:
Originally posted by Sepero
Nice job, techno.
I get that all the time as well, teckno:) I've had oozi, OOzi, Oozi, oozy...
Let's get it right people, it's an o, then a zero, then a z, then an i. But Rob will do fine:)
can it include << ? So you're looking for a counter?Quote:
Originally posted by Strogian
Heh, that makes me think of one.. Come up with bitwise-shift and increment (or decrement) functions, using only the bitwise operations. (that doesn't include >> :))
so we can use ~ ^ & | and what not, but no >>.
Just making sure I have this correct. I'll be spending the next 4 hours running long tests which need barely to no interaction. This'll give me something to do.
Well, I want functions that replace the ++ and >> operations, so naturally you shouldn't use ++ or >> in the function. :) (<< and -- are also no-good, but I don't think they'd help you anyway :))
Do you want replacments for both pre and post increments? (ie ++x and x++)
Oh, wow. I'd never thought of that. Hey, if you can do it, go ahead! :)
Looks like you have had some interesting theoretical/mathematical challenges, so far. Heres something practical:
Define a simple hangman program
It takes one word as its only parameter
The user has 2x as many guesses as there are letters in the word to guess the word. the user enters a letter on stdin, the program prints out the word, with that guess and any previous ones revealed as letters in the word, other letter are replaced by *. Also printed out is the number of guesses left before the user runs out of time. So a sample run may go as follows:
hangman sameple
e
***e**e
you have 13 guesses remaining
s
s**e**e
etc.
have fun, this is easy compared to some earlier challenges and will hopefully less able programmers a chance to test their skills.
mullet
I deciphered Sepero's first code. I mostly figured it out without a program but used it just to help. Anyway, I have attached the code to decipher the code in Perl. Did anyone else get it?
The python rot13 can be made way shorter:
:)Code:def rot13(s):
return s.encode('rot13')
I actually mention that in the original post... :pQuote:
Originally posted by Strike
The python rot13 can be made way shorter:
:)Code:def rot13(s):
return s.encode('rot13')
Heres a java solution for the add 2 numbers without +
Sorry for no indent, I did this in galeonCode:
public int add(int a, int b){
BigInteger bigA = new BigInteger(a);
BigInteger bigB = new BigInteger(b);
BigInteger ans = bigA.add(bigB);
return ans.intValue();
}
Design a binary code and write an encoder and decoder such that if as many as 3 bits of a codeword are encoded with errors, the decoder can correct the codeword. Obviously the only purpose of the encoder here is to take a codeword and mess it up in no more than three places. Your word length can be whatever you want, but the number of codewords needs to be at least 4. The shorter the word length and greater the number of codewords, the smarter your code is of course :).
Write a program that reads in an integer from the console and finds all positive prime numbers between 2 and the number. Challenge:Code the routine so that as your program progresses it becomes faster, i.e. it can test the numbers in [1000000, 1000100] faster that it can test the numbers in [1000,1100].
Mathmatically speaking, is that even possible? Doesn't the list of factors that you have to test get longer each time?Quote:
Originally posted by grady
Code the routine so that as your program progresses it becomes faster, i.e. it can test the numbers in [1000000, 1000100] faster that it can test the numbers in [1000,1100]. [/B]
The number of factors does increase, so I'm guessing that perhaps if you want it to speed up you make some way of actually hanging on to your results from the previous number rather than starting over, perhaps taking advantage of the fact that all non prime numbers (bigger than 2) can be expressed as a product of primes.:)
The phenomena with the speed is a result of a possible solution to this challenge: Find the primes without factoring any numbers.
Yep, there's a dynamic programming algorithm to do it.Quote:
Originally posted by grady
The phenomena with the speed is a result of a possible solution to this challenge: Find the primes without factoring any numbers.
I don't remember what that algorithm is, of course ( :eek: ), but I do remember that it exists...
Ummm.... can we turn this back into a "Programming Challenges" thread? For some reason it has become a "Mathematical Challenges" thread. :confused:
here's some sloppy code i had lieing around on prime numbers.
Code:#!/usr/bin/perl
@numbers[10];
$arrySize = $ARGV[0];
$printSize = $ARGV[1];
$primeCount = 1;
if($arrySize < $printSize){
print "The number of elements to print is larger than the number of elements we want to search through!\n\n";
exit;
}
for($i = 0; $i <= $arrySize; $i++){
$numbers[$i] = $i + 2;
}
for($j = 0; $j <= $arrySize; $j++){
if($numbers[$j] != 0){
for($y = 2; $numbers[$j] * $y <= $arrySize; $y++){
$zeroIndex = $numbers[$j] * $y - 2;
$numbers[$zeroIndex] = 0;
}
} # end if
} # end for
print "Here are the prime numbers from 2 through $printSize\n\n";
for($a = 0; $a <= $arrySize && $primeCount <= $printSize; $a++){
if($numbers[$a] != 0 && $numbers[$a] <= $arrySize){
$primeCount++;
print "$numbers[$a] ";
}
}
print "\n";
I'm doing a project for my compy sci class. I'll have three years to work on it. I am going to do it in PHP (so I can make it on my linux box and run it on my teacher's winblows 98 . . . also for the MySQL integration), and I need a good idea for my project. There are seven requirements, that I must show mastery in my program. Almost all of them I could do in my sleep, but I need a good idea.
1. Arrays || Records || Objects
2. Selection Constructs (branching)
3. Iteration Constructs (looping)
4. subprograms (built-in && user defined)
5. parameter passing (hah!)
6. Sorting || Searching Techniques
7. File Access
It looks like a job for MySQL. But what should I make? Any ideas?
Thanks,
TROGDOR!!!
Quote:
Originally posted by Trogdor
I'm doing a project for my compy sci class. I'll have three years to work on it. I am going to do it in PHP (so I can make it on my linux box and run it on my teacher's winblows 98 . . . also for the MySQL integration), and I need a good idea for my project. There are seven requirements, that I must show mastery in my program. Almost all of them I could do in my sleep, but I need a good idea.
1. Arrays || Records || Objects
2. Selection Constructs (branching)
3. Iteration Constructs (looping)
4. subprograms (built-in && user defined)
5. parameter passing (hah!)
6. Sorting || Searching Techniques
7. File Access
It looks like a job for MySQL. But what should I make? Any ideas?
Thanks,
TROGDOR!!!
three years for that?....hmmmmm......how about a software database program...you know...to keep track of all of the software you own, cd keys....etc....of course...this is probably much too simple for your project...i'm guessing the teacher wants a little more complexity if you're getting three years to write it.
I'm still in high school, so I'm not what you might call a "1337 h4x0r". I'm a year ahead of my compy sci class, so I get three, instead of a little less than two, years to work on this for IB.
I'm thinking something along the lines of web software, so I can upload it to my school's ftp server and access it from any compydore. Maybe something net-related, like some data-base access, take input from people, etc.
Here is what I'm thinking:
> SELECT * FROM teachers WHERE clue > 0
0 rows returned
EDIT: Anyone have any good ideas besides bogus SQL requests?
EASY one: (sorry another math one)
Print all the squares from 0-10000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!
How about no variables, no additions, and no while loop?Quote:
Originally posted by tecknophreak
EASY one: (sorry another math one)
Print all the squares from 0-10000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!
Code:>>> print [x**2 for x in range(int(math.sqrt(10000)))]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144,
169, 196, 225, 256, 289, 324, 361, 400, 441,
484, 529, 576, 625, 676, 729, 784, 841, 900,
961, 1024, 1089, 1156, 1225, 1296, 1369, 1444,
1521, 1600, 1681, 1764, 1849, 1936, 2025,
2116, 2209, 2304, 2401, 2500, 2601, 2704,
2809, 2916, 3025, 3136, 3249, 3364, 3481,
3600, 3721, 3844, 3969, 4096, 4225, 4356,
4489, 4624, 4761, 4900, 5041, 5184, 5329,
5476, 5625, 5776, 5929, 6084, 6241, 6400,
6561, 6724, 6889, 7056, 7225, 7396, 7569,
7744, 7921, 8100, 8281, 8464, 8649, 8836,
9025, 9216, 9409, 9604, 9801]
is x**2 the same as saying square x? if so, that's no good, cause then it's using multiplication.
and no using functions, i.e. math.sqrt, cheap.
My python attempt:
[code]
x=0
y=0
while y<10000:
y=0
for loop in range(x):
y+=x
print y
x+=1
[code]
tecknophreak: you underconstrained it ;)
mrBen, that works, here's a properly indented version:
Code:
>>> x = 0; y = 0
>>> while y < 10000:
... y = 0
... for loop in range(x):
... y += x
... print y
... x +=1
...
Quote:
Originally posted by kshim5
Write a short program that asks for your height in integer inches and then convert your height to feet and inches.
Sure did. :DQuote:
Originally posted by Strike
tecknophreak: you underconstrained it ;)
mrBen, that works, here's a properly indented version:
Code:
>>> x = 0; y = 0
>>> while y < 10000:
... y = 0
... for loop in range(x):
... y += x
... print y
... x +=1
...
how's the "for loop in range(x)" work? and how do you know a loop(while/for) is done? cause in C/C++, etc, you have the { } to tell ya.
P.S. you can do lose two lines from your code. ;)
You only have to place the code inside the loop in a block if there is more than one statment.Quote:
Originally posted by tecknophreak
Sure did. :D
how's the "for loop in range(x)" work? and how do you know a loop(while/for) is done? cause in C/C++, etc, you have the { } to tell ya.
P.S. you can do lose two lines from your code. ;)
If there is no block around the code then only the first statment applies.
C/C++ you only need the block (braces) if there is more than one statment.
Although I use a block (braces) even if there is only one statment as I think it keeps the code more consistent and readable.
want a cookie? :pQuote:
Originally posted by Sepero
teckno, do you program in anything besides C/C++? I don't know what language that guy wrote that in, but I can read/understand it perfectly... Then again, maybe that's what makes me an outcast. :rolleyes:
i should have just ran the program, i see you need indents to run the program.
Strike: you don't even need the range(int(math.sqrt(10000))). The square root of 10000 is 100, so you can just use range(100). :p
(Of course, this doesn't negate the fact that x**2 is "multiplication". However, the way that multiplication is done on the CPU does negate this fact -- multiplication is done on the CPU by a series of additions, IIRC from Architecture. So hah; any solution is valid. :p)
Sepero: the language would be Python.