Should we have a small programming challenge?

[andrzej]

No offense but I hate computer programs that are polite. I can't stand it when my computer says please and thank you. Well thank you isn't so bad but please is. I can just picture Dos saying, "Please don't format your drive unless you really want to lose all your data." It didn't really say that but follow with me here. If I had programmed it, it would say, "Don't type Y here unless you know what you're about to mess up." And these signs in restaurants that say, "Thank you for not smoking," how do they know you didn't smoke anyway? If I had a restaurant, the signs would say, "No smoking in here maggot." As you can tell, I'm not much of a people person. But I'm tired of all this extra politeness. When it comes to computer programs, it needs to tell a user what to do and if the user doesn't do it, then the user can deal with it when things screw up. The computer shouldn't have to beg the user to insert the next disc. I guess I'm gonna wrap it up with that.

You misread my program's comments. He's behaving like someone not allowed to be impolite, but really willing to. See how ONE and CORRECT are pronounced ? One can almost hear "you fscking idiot". Didn't you notice that sarcasm and disdain pouring out of the word "please" ?

[kenshi]

No, keep kenshi (I almost typed kenshin there ). Prince anything sounds too...pretty boy. Well whatever floats your boat!

Hey, I'm no pretty boy. I'm as ugly as they come. Kenshi was the dragon prince though, so I don't think that makes him a pretty boy.

You misread my program's comments. He's behaving like someone not allowed to be impolite, but really willing to. See how ONE and CORRECT are pronounced ? One can almost hear "you fscking idiot". Didn't you notice that sarcasm and disdain pouring out of the word "please" ?

My mistake. I got to the please and thank you part and quit reading. I guess it's cool then.

[ndogg]

'k, I read through all the posts, and I'm just sick of coming up with "yet another factoring program." I want to do something more interesting. For example, given a graph, find the shortest path. Let's assume the input for a graph looks like this:

7
1 2 2
1 3 4
1 4 7
2 4 3
2 5 10
3 4 2
4 5 7
3 6 5
4 6 8
4 7 10
5 7 6
6 7 1

Where the first number represents the number of vertices. Let's go to the next line, '1' represents vertex 1 and the first '2' represents vertex 2 and the last '2' represents the weight to go from vertex 1 to vertex 2. The graph is assumed to be directed, so, unless it's specified, you can't go from vertex 2 to vertex 1.

We'll assume that vertices are number from 1 to n, where n is the number of vertices, and all weights are positive. If there is no path between two vertices, then the weight is infinite. The purpose of your program should be to find all the shortest distances from vertex 1 to all other vertices.

Since I'm just interested in the running time for the algorithm that you use, you can use something like the time() function around that part of your algorithm. If the algorithm is too quick for time() (or what ever timing function you use), then try repeating it a large number of times (say, 100000 times.)

I already have a sample implementation of one of the many forms of Dijkstra'
s algorithm in C++ already. To get any interesting timings out of it, though, change MAX to 100000 (this will repeat the algorithm 100000 times).

[kenshi]

I'm really unsure of what you mean with the graph challenge. What do you mean by weight? At first, I thought you meant calculate the distance to go from the origin of the grid to a certain point. That's simple trigonometry. But from the example you showed, apparently this isn't what you're looking for. Can you explain it a bit more because I haven't had many math class.

[ndogg]

I'm really unsure of what you mean with the graph challenge. What do you mean by weight? At first, I thought you meant calculate the distance to go from the origin of the grid to a certain point. That's simple trigonometry. But from the example you showed, apparently this isn't what you're looking for. Can you explain it a bit more because I haven't had many math class.

s/weight/distance/g
Sorry, I should have used better language. *The numbers in the last column are the distances. *What I'm looking for is the shortest distance using the given paths to go from vertex 1 to all other vertices.

[elo]

It's a bit late, but here's my C++ version:

www.thmleo.f2s.com/main.cc
www.thmleo.f2s.com/factor.h
www.thmleo.f2s.com/factor.cc

and to compile,

g++ main.cc

Using 10^15 takes around 8 seconds, whereas kenshi's is ~5s.

edit: it doesn't read the number from the command line, but after you start it

[kenshi]

s/weight/distance/g
Sorry, I should have used better language. The numbers in the last column are the distances. What I'm looking for is the shortest distance using the given paths to go from vertex 1 to all other vertices.

I may sound unintelligent by asking, but what do you mean by vertex? I haven't dealt with graphs since Algebra 2 in 9th grade. I remember the distance from the origin being the same formula for the length of a hypotenus, and the distance between two points being quite close, but I don't remember vertices.

[ndogg]

I may sound unintelligent by asking, but what do you mean by vertex? I haven't dealt with graphs since Algebra 2 in 9th grade. I remember the distance from the origin being the same formula for the length of a hypotenus, and the distance between two points being quite close, but I don't remember vertices.

This isn't a coordinate graph that I'm talking about here. Think more along the lines of the Traveling Salesman problem, but not quite that. Here's a good Java animation of it all. Plot some points on it, make some lines in between the points, change the distances, and run it.

[kenshi]

Ok, I think I get it now. That seems like a lot more than just a simple program though. Figuring out the algorithm would take a while. I think this is more than a week project.

[ndogg]

Ok, I think I get it now. That seems like a lot more than just a simple program though. Figuring out the algorithm would take a while. I think this is more than a week project.

Dijkstra's algorithm makes it super simple. Once you figure that out, it doesn't take much.