🔒 Locked

Fastest Code

Started by Merge2 Jan 5, 2001 at 2:10 AM 18 replies 650+ views

Original Post

Jan 5, 2001 at 2:10 AM

Hey guys, What are some examples of "classic" problems people use to test how fast their code is? For example, I think the 8 queens problem (positioning 8 queens on a chess board so that no queen is attacking any other queen) is this kind of problem (maybe not, but I think it is). I was thinking, maybe GameDev could actually update their Contests section with a contest to see who could solve -insert problem name here- the fastest, as in number of seconds it takes your program to solve the given problem. Aside from that, does anyone know of any problems similar in nature to the 8 queens problem? merge http://merge.to

acraig

Jan 5, 2001 at 2:21 AM

The Towers of Hanoi is another good one. Or navigating a simple maze. This would be a cool contest.

-------
Andrew

nes8bit

PRO

612

nes8bit

Jan 5, 2001 at 3:08 AM

Damn it! No more puzzle contests!

---------------------------
"the only thing I ask, is that if my games get pirated, people must do a good job of it." - Erick

Merge2

Author

Merge2

Jan 5, 2001 at 3:23 AM

I''m not talking about a "puzzle" contest as in tetris type games. I''m talking about see who can write a program that solves the given problem(s) the fastest. Like a contest to see who can write a program to solve all solutions of the 8 queens problem or navigating a maze or the towers of hanoi in the least amount of time. Like if your program solves the given problem in 3 seconds and my program solves it in 4, then you win. That kind of deal. I''d definetly put some significant effort into a contest like that, because it''s not subjective. The winner isn''t who the judges liked the best, it''s plain and simple. Whoever writes the fastest code wins. If GameDev doesn''t start this contest, I''m gonna get me a sponsor and run this contest on my website.

http://merge.to

morfe

Jan 5, 2001 at 3:28 AM

- Fastest real-time mandelbrot zoom

"NPCs will be inherited from the basic Entity class. They will be fully independent, and carry out their own lives oblivious to the world around them ... that is, until you set them on fire ..."
"When you are willing to do that which others are ashamed to do, therein lies an advantage."

Merge2

Author

Merge2

Jan 5, 2001 at 3:33 AM

Fastest real-time what?

http://merge.to

morfe

Jan 5, 2001 at 3:39 AM

Mandelbrot fractals. You can zoom in forever.

Merge2

Author

Merge2

Jan 5, 2001 at 3:53 AM

Ok, I did a quick search for Mandelbrot fractals and found a lot of stuff on them, but I''m not sure I understand the "problem" part that you''d be trying to solve.

Here''s how I''m seeing it. You can zoom in on any vector type image infinitely (or a bitmap for that matter, of course it''ll just be one pixel blown up to the size of the screen after a while, but you could still do it). So I guess I''m just not understanding the specifics of what we''d be trying to solve in the Mandelbrot zoom contest.

Also, if you can zoom in forever, how does the program ever reach a "solution"?

Thanks,

merge

http://merge.to

morfe

Jan 5, 2001 at 6:40 AM

It's not really a problem solving type situation. It's a fastest code situation.

Zooming mandelbrots is not just about blowing up pixels, but rather dynamic resampling and calculation of fractals. It uses a basic formula to generate an image, not usually a standard vector image or bitmap. It's real-time generation of images.

The whole idea is efficient code, and algorithm optimisation. The graphics side is important, but not overly complicated.

The basic Mandelbrot fractal

Edited by - morfe on January 5, 2001 7:45:27 AM

Sandman

209

Sandman

Jan 5, 2001 at 8:40 AM

We did the chinese sliding tile puzzle at uni, and there was a massive difference in the execution times. Most took around 1-2 hrs to solve a single puzzle (and would hang if there was no solution) the best ones (including my own

) took < 10 s and could identify unsolvable configurations.

Merge2

Author

Merge2

Jan 5, 2001 at 1:12 PM

Ok, so we have the 8 queens problem, the tower of hanoi, navigating through a maze, and the sliding tile puzzle. Sorry but the fractals thing doesn''t really seem like a good contest since there isn''t a clear-cut solution. If gamedev doesn''t do one of these contests, I''m deffinetly going to hold this contest.

BTW, is Gamedev ever going to update their contests page? They need to move the contest that "ends in December" from the Current Contests section.

merge

http://merge.to

Arch@on

Jan 5, 2001 at 1:52 PM

How about ''Fastest solver for Fastest puzzle solving quest''

I think making program that uses A-algorithm for puzzle solving is the best woth 32x32 tiles and with 100x100 map. This needs all the programming skills you got.

Time comes, time goes and I only am.

Nebob

Jan 5, 2001 at 3:21 PM

Calculate n accurate digits of PI

SHilbert

122

SHilbert

Jan 5, 2001 at 3:34 PM

I''m with nessy, no more puzzle contests for god''s sake!

SHilbert

122

SHilbert

Jan 5, 2001 at 4:20 PM

Although I do happen to know how to generate the Mandelbrot Set... hmm

acraig

Jan 5, 2001 at 5:10 PM

It''s not so much as a puzzle but an algorithm test. What is the best way to solve a maze? Can you developer a faster way to do the Towers? It would be a good test on programming. Could have different language divisions to see how each compare.

-------
Andrew

Lamtd

Jan 5, 2001 at 6:04 PM

Yeah, a programming contest, that would definitively be cool... but we already know that the winner will be the first nerd who will write a 100% hand-optimized assembly code that takes advantage of MMX, SSE and 3DNow at the same time (yes, I *know* that''s impossible lol). We don''t necessarily need to make it a real contest with prizes and stuff, but maybe something so that people can see what real optimization is (too many people here are assuming they know how to optimize code efficiently lol).

harrys

Jan 5, 2001 at 6:31 PM

quote:
Original post by Lamtd

Yeah, a programming contest, that would definitively be cool... but we already know that the winner will be the first nerd who will write a 100% hand-optimized assembly code that takes advantage of MMX, SSE and 3DNow at the same time (yes, I *know* that''s impossible lol). We don''t necessarily need to make it a real contest with prizes and stuff, but maybe something so that people can see what real optimization is (too many people here are assuming they know how to optimize code efficiently lol).

If you really want to know who''s the coolest guy in town - make them a 200K Lines Fortan77 program speed up by the factor 2...

Just kidding, but a good solution is to present some proven code and make a contest of speeding it up _without_ changeing the compiler or moving to assembly. This would require good knowlege of the language and how todays processors work.

acraig

Jan 5, 2001 at 7:31 PM

quote:
Original post by Lamtd

Yeah, a programming contest, that would definitively be cool... but we already know that the winner will be the first nerd who will write a 100% hand-optimized assembly code ...

Have assembly code as a seperate division. If you want to use assembly then use only assembly.

Edited by - acraig on January 5, 2001 8:31:56 PM

SHilbert

122

SHilbert

Jan 5, 2001 at 8:36 PM

quote:
Original post by harrys
If you really want to know who''s the coolest guy in town - make them a 200K Lines Fortan77 program speed up by the factor 2...

My mom might be able to do that

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.