god....i'll be going to UTA in the fall for computer science, hopefully by the time i get out i know what the hell you guys are talking about in this thread
Printable View
god....i'll be going to UTA in the fall for computer science, hopefully by the time i get out i know what the hell you guys are talking about in this thread
Okay, I read this book "Archimede's Revenge" a couple weeks ago and it has a buttload of stuff like this, basically all this number and geometry thoery and stuff. Good reading. Here's one of the problems:
"Suppose there are 100 people in a group, and you want to find out if 50 of them know each other".
This can be done on paper by drawing 100 dots, connecting lines between people that know each other, and looking for all the people that know 49 others that all know the other 49.
Yeah, it's one of those problems that as the set of people gets larger, the amount of work that it would require to find the answer increases exponentially.
Find an algorithm that finds the answer in a manner such that the answer is found in an amount of work like n * number of people, rather than number of people ^ n.
I was working on a method where you make a table, with all the people in the columns and all the people in the rows. Mark an X in the appropriate spot where people know one another(including that person knowing themself). Then remove all people that have less than the needed number of associations. Then you are left with all the people knowing the amount of people needed to associate with. Then, if all the spaces are filled, the answer is 'yes', they all know each other. I belive this approach is not exponential, but I could be wrong.
duncanbojangles:
This problem is basically for a group of n people find out if n/2 people know each other.
The method you propose will only work in O(n^2) time. Or number of people ^ 2.
First: To find all of the people in the group who know at least (n/2 - 1) you will have to visit every person and at the least for every peson you will have to visit is (n/2 - 1) if they now the first (n/2-1) people. There fore just to find all the people who know more than (n/2 - 1) people requires a minimum time of: n * (n/2 - 1) or 1/2 n^2 - n which is on the order of n^2.
Edit
I just realized the the First part of your solution can be accomplished like the second part with an upper triangular adjacency matrix and would only require the following number of visits if you kept a count along the way for each person:
(n^2 - n) / 2 = 1/2 n^2 - 1/2 n which is less than 1/2 n^2 - n but it is still on the order of O(n^2).
Second: To check whether all the people who know n/2-1 people know all the others you have to check whether the resulting upper triangular adjacency matrix is full.
(example for n = 10 and n/2 = 5)
x x x x x
0 x x x x
0 0 x x x
0 0 0 x x
0 0 0 0 x
This matrix could be the result of removing rows from the original table / matrix, but since the lower triangle (everything under the diagonal) is the same as the upper triangle you only need to look at the upper triangle not including the diaganol and you must visite each one of those to see if they are x or not so we must visit
(5^2 - 5) / 2 or ((n/2)^2 - n) / 2 or 1/4 (n^2) - 1/2 n
which is of order O(n^2) as well
so your solution is exponential in nature.
Darn. Oh well. The problem applies to any amount of people knowing any number of people...it didn't necessarily have to be 50 out of 100, that was just the example they used in the book. Thanks for pointing that out to me, guess I'm just not MathGenius material :)
Edit!: After I thought about it, you may be able to reduce the amount of twork it requires to see who one person knows. If, for person A you find out they know B, C, D, and E, then B, C, D, and E will not have to check if they know A. This reduces a lot of work in theory, but in code you'd still have to check on the status of "knowingness of A". As long as the search is done in order, though, A, B, C, D, E, then you know that at E, they already know whether or not they know A, B, C, or D, so they don't have to check. This reduces a lot of overhead by only making E start looking at F.
This problem can be solved recursively but it is slow on the order of O(n^2) or greater. But I beleive you could use dynamic programming to solve the recursion from the bottom up. Basically you only do each calculation once. Not sure how to do it right now but I'm working on it.
here's a fun one for any computer/math nerd, how about a virtual enigma? no need for a plugboard, but 3 encoding disks plus the reflection disk.
FYI - for those who don't know the Enigma was a German encryption machine used in WWII. But it's relatively simple in construct.
It's been done ;)
http://homepages.tesco.net/~andycarl.../enigma_j.html
Hey now, is that yours or are you just showing someone else's final project? :D
A lot of these challenges have already been done, like the next perm one I did around the beginning of last year. But it gives people who want a challenge something to do....like myself.
Oops, sorry, I didn't mean to give the impression that that was mine. Never mind. I'll go away now. :D
;)
Random Quote program
#include <iostream>
#include <string>
#include <time>
#include <math>
#include <vector>
#include <fstream>
using namespace std;
void error(const char*p, const char *p2="")
{
cerr << p << " " << p2 << "\n";
exit(1);
}
int main(int argc, char *argv[])
{
vector<string> quotes(0);
int items=0;
string q;
if (argc < 2)
error("no filename given");
ifstream file(argv[1]);
if(!file)
error("can't open", argv[1]);
char ch;
while (file.get(ch)) {
if (ch=='\n'){
if(items % 100 == 0)
quotes.resize(quotes.size()+100); //increase the size of the vector
quotes[items++]=q;
q="";
}else
q+=ch;
}
int n;
srand(time(0));
n=rand()%items;
cout << quotes[n] <<endl;
return 0;
}
Quote:
Originally posted by Enlighted One
Random Quote program
Can it get any simpler than that?Code:#!/bin/bash
# pass the file with quotes as an argument
# range = the lenth of quote file
range=`cat $1 | wc -l`
# line = a random number between one and range
let "line=($RANDOM%$range)+1"
# output the random line
sed $line'!d' $1
I must admit that I'm pretty proud of myself. :D
Now somebody else will come along and make it simpler... heheh
:pCode:/usr/games/fortune
damn I love slackware.... making program challenges easier every day. :D
There's a theorem from graph theory that sums this um very nicely, no need to do brute search methods...
::goes to track down his graph theory book::
darn can't find it. Something to do with the degree of every vertex added together is 2 times the total number of edges. Therefore when doing person-person relationships, it's only possible for an even amount (it's impossible for there to be 7 people at a party and each one to know exactly 3 others).
Something like that :)
Quote:
Originally posted by duncanbojangles
Okay, I read this book "Archimede's Revenge" a couple weeks ago and it has a buttload of stuff like this, basically all this number and geometry thoery and stuff. Good reading. Here's one of the problems:
"Suppose there are 100 people in a group, and you want to find out if 50 of them know each other".
This can be done on paper by drawing 100 dots, connecting lines between people that know each other, and looking for all the people that know 49 others that all know the other 49.
Yeah, it's one of those problems that as the set of people gets larger, the amount of work that it would require to find the answer increases exponentially.
Find an algorithm that finds the answer in a manner such that the answer is found in an amount of work like n * number of people, rather than number of people ^ n.
I was working on a method where you make a table, with all the people in the columns and all the people in the rows. Mark an X in the appropriate spot where people know one another(including that person knowing themself). Then remove all people that have less than the needed number of associations. Then you are left with all the people knowing the amount of people needed to associate with. Then, if all the spaces are filled, the answer is 'yes', they all know each other. I belive this approach is not exponential, but I could be wrong.
Don't know if it has been said before, and I am really late on this thread...but anyway. Just learned how to do this in high school....Quote:
Originally posted by grady
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.
say z is what you are evaluating for
ax^3+bx^2+cx+d
a*z = m
m+b = n
n*z = o
o+c = p
p*z = q
q+d = r
and r is the answer.
example-
2x^3+x^3+4x+2
For 3
putting it in = 77
2 * 3 = 6
6 + 1 = 7
7 * 3 = 21
21 + 4 = 25
25 * 3 = 75
75 + 2 = 77
Anyway, it was probably already done, and I probably explained it way too much...but I'm bored anyway :D.
So in other words, you "factor" ax^3 + bx^2 + cx + d into:Quote:
Originally posted by gobeavers
say z is what you are evaluating for
ax^3+bx^2+cx+d
a*z = m
m+b = n
n*z = o
o+c = p
p*z = q
q+d = r
and r is the answer.
(((ax + b)x + c)x + d
It's not a true factorization, but it does reduce into n multiplications.
(FWIW: This question was asked so long ago that I don't remember if there was an answer to it posted already either! ;))
I don't konw...its something called "synthetic substitution" using some guys root theorem (or something like that)....we just learned it in pre-calc.Quote:
Originally posted by bwkaz
So in other words, you "factor" ax^3 + bx^2 + cx + d into:
(((ax + b)x + c)x + d
It's not a true factorization, but it does reduce into n multiplications.
(FWIW: This question was asked so long ago that I don't remember if there was an answer to it posted already either! ;))
Basically, you divide the polynomial by x-z, z being what you are evaluating for, and the remainder is the answer.
This piece of code is awesome! Compile it and run it!
Quote:
//The Beapanator!!!!!!!
#include <iostream>
using namespace std;
int main()
{
int w, n;
char y;
cout << "Would you like to annoy the people around you?";
cin >> y;
if(y=='y')
{
cout << "How many times?";
cin >> n;
for(n; n!=0; n--)
{
cout << "\a";
}
}
else
return 0;
}
bwkaz, don't you have anything to say about this? ;)Quote:
Enlighted One:
using namespace std;
If it makes it easier......Quote:
Originally posted by Sepero
bwkaz, don't you have anything to say about this? ;)
I really should.
It might make it "easier", but there's the minor detail of how it also makes it "wrong". :D (At least, "wrong" in terms of what I believe the C++ committees want. I could be wrong.)
<my standard rant on this subject: if you've already seen it, skip this bit>
The std:: namespace was added to the C++ standard library for a reason. If you pull that entire namespace into the default namespace, you eventually will trample on symbols that you've already defined in the default namespace. This will cause no end of compiler errors, until you figure out what the underlying issue is and start doing one of the following things.
</standard rant>
What you can do is only import the individual symbols you require, or (this is better, but takes more work) don't import anything, just use the std:: namespace qualifier everywhere.
And let me just say, beeps are ANNOYING. :p
I'm glad you like it:cool:Quote:
Originally posted by bwkaz
And let me just say, beeps are ANNOYING. :p
The Open Source Institute is offering a programming challenge for anybody interested. The winner of the contest will get an item worth up to $40 from Amazon.com. Second place winner can get an item worth up to $25.
If you are interested in trying out your skills with over 2500 other programmers for prizes. Check out http://www.osix.net
awww, reserected just to show some other places challenges. :( I was all excited that it was back up. Damn, anyone have any good challenges?
-I use mpg123 for playing mp3's
-It recognizes Winamp & xmms generated .m3u files.
-Those files can be stripped down to include just the paths to the mp3 files. i.e. /mnt/Music/Seether/Seether - Broken.mp3
So here's the challange:
-Write a script that pipes output similar to that of ls -RN to a file with a .m3u extension.
--each line in the file should be formatted as /directory/subdirectory/sub-subdirectory/file.mp3
--will need to handle different levels of subdirectories such as:
/mnt/Music/Seether/Seether - Broken.mp3
/mnt/Music/Liz Phair/Exile In Guyville/Liz Phair - Flower.mp3
Bonus:
-Have the script prompt the user for the mp3 directory, for example, mine would be /mnt/Music
-Have prompts for the user to add all subdirectories or individual ones for different artists, etc.
The end result would enable one to generate, manipulate, and play music playlists all from the command line. How cool!
psych-major:
find /path -name '*.mp3' >file.m3u
will work, as long as none of the filenames or directories have newlines in them. (Which is actually legal in filenames, but I doubt that the m3u format can handle it.)
That worked perfectly. I'm such a 'tard; I should of thought of it because I used to use an identical command for a batch file in DOS at my last job...Quote:
Originally posted by bwkaz
psych-major:
find /path -name '*.mp3' >file.m3u
will work, as long as none of the filenames or directories have newlines in them. (Which is actually legal in filenames, but I doubt that the m3u format can handle it.)
Thanks, for the quick response. I'll try to come up with something a little more challenging next time!
Challenge:
Write a script that prints only the first letter of each word that appears in a plaintext file. Only characters A-Z and a-z should be recognized. Carriage returns, punctionation, arabic numerals, etc. should all be ignored.
Demonstration:
Possible contents of the plaintext file:The result would be:Code:How much wood would a woodchuck chuck
If a woodchuck would chuck wood?
A woodchuck would chuck all the wood he could chuck
If a woodchuck would chuck wood.
Code:h
m
w
w
a
w
c
i
a
w
w
c
w
a
w
w
c
a
t
w
h
c
c
i
a
w
w
c
w
Nice one hop-frog. I thinking about trying it with a shell script, but when you mentioned no punctuation, that got my mind really wondering. :)
Hrmm, let's see...
perhaps?Code:sed -e 's/[[:space:]]/\n/g' file.txt | sed -e 's/[^A-Za-z]//g' | cut -c 1
bwkaz, you're like a regex guru or something. I don't know how you remember all that stuff!
:p
Maybe, but I don't think there's any way I'll ever be able to decipher this one:
http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.html
:p
I can't program perl and I can't really read the code well(though, I would imagine the "?" and ":" pairs are of "if" and "else").Quote:
Originally posted by bwkaz
Maybe, but I don't think there's any way I'll ever be able to decipher this one:
http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.html
:p
It looks VERY repetitive though. Is there absolutely no way they could've reduced the code with a function or two?
:confused:
Well... maybe, but it's not "code" per se. It's just one enormous regular expression that's meant to be applied to a string to determine whether the string is a valid RFC-822 address. AFAIK there is no such thing as a "function" when talking about regular expressions.
I believe the (?:) stuff isn't "if-else"; I think it introduces a "non-capturing group". It groups the characters in the string being tested, without assigning them to the Perl variables $1, $2, etc. ("capturing" them).
Using xwarppointer, one can easily write a shell script that moves the mouse around the screen in a sequence.
Challenge:
Write a program to accompany xwarppointer. When run, it simply sends a left-button click to the pointer.
Well, I won't do this, because I have a few other things going on at the moment, but it shouldn't be too hard to do. You should only need the Xtst libraries, and the <X11/Xtest.h> includes. Then you can open the display, and inject an X button-press, button-release event combination into the event list.
It's how I make sure numlock is on every time I start X -- I run a program that's linked against the Xtst library, which sends a key-press, key-release event pair pointing at the numlock key.
/me picks up jaw off the floor:DQuote:
Originally posted by bwkaz
Maybe, but I don't think there's any way I'll ever be able to decipher this one:
http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.html
:p
Take the sentence:
"She sells sea shells by the sea shore"
Reorder the words alphabetically, and do it in your favorite language.
;)
I found this thread again, thought it was lost..........
here is a challenge I did a few years ago while taking a C/C++ class and figured I'd put it out and see how many different ways it could be done (perl, VB, Bash script??, etc.).........have fun
Quote:
Find a six digit number that gives its digits reversed when multiplied by an integer between 2 and 9 inclusive.