Last visit was: It is currently Thu Mar 28, 2024 7:38 am


All times are UTC-05:00




Post new topic Reply to topic  [64 posts ] 
Author Message
 Post subject:
PostPosted:Thu Aug 09, 2007 6:12 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
Hmm I could just be stupid but I can't seem to find Onlink's source anywhere. If you give me access to the source I can have a rudimentery multi threaded build out by tommorow.
Onlink's source isn't public, since it's based on Uplink, and Introversion has kept it closed source.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 6:26 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
If I buy a Dev CD could I be given a chance to create a multi-threaded build?


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 6:45 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
If I buy a Dev CD could I be given a chance to create a multi-threaded build?
We'd consider it, certainly, but Onlink is already multithreaded a bit. You really have to know what to parallelize in order to actually do it.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 9:10 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
Hmm I haven't seen the code to Uplink so I can't say to much however, I'm guessing that dividing everything time related (emails,passive trace, missions, story line) could be one thread. Tell you what I just ordered a Dev CD and I'll get back to you with a multithreaded version of vanilla Uplink when I get back from vacation.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 10:47 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Meanwhile... Anyone want to take a stab at Challenge Two?

*stab*

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Fri Aug 10, 2007 12:07 pm 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
At Tycho request, remixed wikipedia code:
Quote:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

const int nMax = 14;
int row[nMax];
int n;
int s;

void putBoard()
{
printf( "\nSolution #%d:\n---------------------------------\n", s );
for ( int y = 0; y < n; printf("|\n---------------------------------\n" ), y++ )
for ( int x = 0; x < n; printf( x++ == row[y] ? "| Q " : "| " ) );
}

bool safe( int x, int y )
{
for ( int i = 1; i <= y; i++ )
if ( row[y - i] == x || row[y - i] == x - i || row[y - i] == x + i )
return false;
return true;
}

void nQueens( int y )
{
for ( int x = 0; x < n; x++ )
if ( safe( row[y - 1] = x, y - 1 ) )
if ( y < n )
nQueens( y + 1 );
else
{
s++;
//putBoard();
}
}

int main()
{
for ( n = 2; n <= nMax; n++ )
{
clock_t init = clock();

s = 0;
nQueens( 1 );

clock_t final = clock();

printf( "%10d # of solutions for %d x %d = %d\n", (int)( (final - init) * 1000 / CLOCKS_PER_SEC ), n, n, s );
}

printf( "\nEnd\n" );
getchar();

return 0;
}


Last edited by frenchfrog on Mon Aug 13, 2007 9:10 am, edited 1 time in total.

Top
Offline  
 Post subject:
PostPosted:Fri Aug 10, 2007 5:50 pm 
User avatar
 

Joined:Sun Feb 12, 2006 8:56 pm
Posts:1019
Website:http://eddieringle.com
Location:Detroit, MI
I'm waiting for a challenge more at my level, (my very low level :D ). Plus I want to learn a little more C++... speaking of which did anyone take a look at my post in General?

_________________
-- Eddie Ringle

Check out Elysian Shadows and consider backing us on Kickstarter!

====================================

Image


Top
Offline  
 Post subject:
PostPosted:Fri Aug 10, 2007 11:21 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
I'm waiting for a challenge more at my level, (my very low level :D ). Plus I want to learn a little more C++... speaking of which did anyone take a look at my post in General?
I suppose N queens is a bit too complex a problem for a game forum. I will keep N queens up for now, because anyone who can solve it and write a fast solution deserves to (or at least should be) to be a developer on Onlink.

I will also work on finding simpler problems that have large potential for optimization and improvement. The isPrime optimization challenge was fairly straightforward I think. Was it too challenging?

And I saw your post. Even replied. Just haven't been home all day.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Sat Aug 11, 2007 10:58 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
cpu5594, feel free to optimize the code I posted above and make it yours :)

I can explain it line by line if you wish.


Top
Offline  
 Post subject:
PostPosted:Sat Aug 11, 2007 2:57 pm 
User avatar
 

Joined:Sun Feb 12, 2006 8:56 pm
Posts:1019
Website:http://eddieringle.com
Location:Detroit, MI
Tycho: Yeah, it was a bit challenging, but this is coming from a newbie C++ coder.

frenchfrog: Thank you for the offer, and it would be nice if you could explain the code, I am looking at it and I think I get half of it, the other half is like a foriegn language.

_________________
-- Eddie Ringle

Check out Elysian Shadows and consider backing us on Kickstarter!

====================================

Image


Top
Offline  
 Post subject:
PostPosted:Sun Aug 12, 2007 12:32 am 
 

Joined:Sun Aug 05, 2007 11:51 pm
Posts:25
Location:Orange County, California
I initially found this task quite daunting, but it is actually somewhat straightforward once you find a good technique and get down to it. Today I hammered out a technique that will find distinct solutions correctly in a kind-of-reasonable timeframe. It did take some effort and some wrong techniques to figure it out, though.


Top
Offline  
 Post subject:
PostPosted:Sun Aug 12, 2007 10:59 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Code:
#include <stdlib.h> #include <stdio.h> // Needed for clock() (and related stuff), help in the calculation of the elapsed function time #include <time.h> // Maximum number of the Queens to test const int nMax = 14; // This array represent the rows of the N-Queens grid // Since there can only be one queen per row, it's in fact representing the queens positions // ex: If there is a queen in the 2nd row at the 5th position: row[1] == 4 (both rows and positions start at zero) int row[nMax]; // Current number of the Queens to test int n; // Number of solutions int s; void putBoard() { printf( "\nSolution #%d:\n---------------------------------\n", s ); for ( int y = 0; y < n; printf("|\n---------------------------------\n" ), y++ ) for ( int x = 0; x < n; printf( x++ == row[y] ? "| Q " : "| " ) ); } // Check if the added queen is in a safe location (not in vertical or diagonal line with an already placed queen) // int y == row of the new queen (y goes from 1 to n) // int x == position of the new queen on the y row (x goes from 0 to n - 1) bool safe( int x, int y ) { // Test the queens (rows) already placed for ( int i = 1; i <= y; i++ ) // Check that the new queen is not ( in vertical line || in right diagonal line || in left diagonal line ) // with the currently tested already placed queen if ( row[y - i] == x || row[y - i] == x - i || row[y - i] == x + i ) return false; return true; } // Recursive function (a function that call itself), get called for each new queen placement // int y == row to try to put a queen on void nQueens( int y ) { // Try each queen positions on current row for ( int x = 0; x < n; x++ ) // If the queen position is good if ( safe( row[y - 1] = x, y - 1 ) ) // If not the last row/queen if ( y < n ) // Try to put a queen on the next row nQueens( y + 1 ); // Else, last row/queen, we have a valid solution else { s++; //putBoard(); } // Ok, the function is over, but since it's recursive // it will go back to the row before this one // and continue to test queen positions // (Or return to the main if the row was the first one) } int main() { for ( n = 2; n <= nMax; n++ ) { clock_t init = clock(); // Put the number of solutions to zero s = 0; // Call queen placement with first row nQueens( 1 ); clock_t final = clock(); printf( "%10d # of solutions for %d x %d = %d\n", (int)( (final - init) * 1000 / CLOCKS_PER_SEC ), n, n, s ); } printf( "\nEnd\n" ); getchar(); return 0; }


Last edited by frenchfrog on Mon Aug 13, 2007 9:15 am, edited 4 times in total.

Top
Offline  
 Post subject:
PostPosted:Sun Aug 12, 2007 8:34 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
I'm back from vacation (I went to capecod nice place but I'm sunburned as hell.) Anyway I think I'm going to rewrite my algorithm to output in the manner Tycho wanted it.


Top
Offline  
 Post subject:
PostPosted:Mon Aug 13, 2007 8:49 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
French Frog, I was trying to run your code but for some reason I can't seem to get it to compile, I keep getting undeclared identifier errors for the clock. I'm sure I'm just being something stupid :oops: but could you try to help me out?


Top
Offline  
 Post subject:
PostPosted:Mon Aug 13, 2007 9:07 am 
Sagely Amphibian
User avatar
 

Joined:Sun Jun 18, 2006 3:06 pm
Posts:69
Gwanky, which compiler do you use? (Here I use MS Visual Studio 2005 sp1)

Try putting the following lines at the start of the program:

#include <stdlib.h>
#include <time.h>

EDIT: I edited my above post to include this modification.


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova