|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. 
Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college.
The good parts:
Your comments and logical structure make sense.
You are using loops correctly.
You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding)
The bad parts:
The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing.
Your comments are merely labeling parts of the code, not describing it
you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on.
I'm sick of this "grid[i+1][j-1] * grid[i][j] > product" comparison... If you copy and paste something, think about putting it into a function.
Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements:
Calculate the largest product of adjacent N numbers where they are all in a line
Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line)
Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number
Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example)
You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees.
Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0.
|
So I've been trying to break into some kind of low end position in web development and I'm getting mixed signals.
On one hand, people are saying you should have a bad ass portfolio with any amount of CSS/JS voodoo you can muster. Programming is often touted as a field with a ton of conviction about quality and if you don't have the same conviction/passion, you shouldn't be touching an IDE.
On the other hand, I'm having interviews where the seriously under-qualified are getting jobs. The last interview I had seriously said they've hired people -- as in given a living wage for this area -- who could not investigate problems on their own and barked for help at every turn. Now they obviously weren't kept around, but it still blows my mind that those hires got past the practical and initial interview.
I try to be honest with my ability and not misrepresent myself. I am only worth entry level. I can't tackle an entire corporate backend on day one, but I do have experience writing small stuff in Python/Django. Along with that comes basic HTML/CSS. I haven't done any responsive development, so stuff tends to look bad on a mobile browser. From the interviews I've been in, it seems like I have some entry-level skills that are worth a position (around here, anyway), but compared to the high and mighty talk on the forums I visit, I shouldn't be getting these interviews with this level of skill. I'm willing to learn new stuff, and I feel like I can learn any of the scripting/high-level languages fairly quickly. Since there are so many routes to take, and my free time is limited, I'd much prefer to study whatever language my next job will require (Is this a good or bad stance to take?).
Overall demand for developers is high, but does that demand extend down to the lower rungs? How useful are entry-level or junior positions?
Cheers.
|
On February 27 2013 09:20 RoyGBiv_13 wrote:Show nested quote +On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college. The good parts: Your comments and logical structure make sense. You are using loops correctly. You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding) The bad parts: The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing. Your comments are merely labeling parts of the code, not describing it you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on. I'm sick of this "grid[i+1][j-1] * grid[i][j] > product" comparison... If you copy and paste something, think about putting it into a function. Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements: Calculate the largest product of adjacent N numbers where they are all in a line Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line) Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example) You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees. Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0.
Okay, from what I understood from your and other guys' posts, I need to do the following:
A. Use a function that checks if (a * b) > product. Perhaps something like the suggested std::max()
B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid[i][j]? I always thought going through a grid is guaranteed O(n^2).
C. Have better comments perhaps which I usually do, but I keep them minimal before final implementation. It may be more time-consuming though.
There are probably more things to consider, but I'm tired, so I'll re-read posts again after I wake up.
Edit: You actually expect right. I'm 2nd year at university.
|
On February 27 2013 10:03 darkness wrote:B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid[i][j]? I always thought going through a grid is guaranteed O(n^2).
You don't need to perform reverse calculations. Evaluating grid[i][j] against grid [i][j + 1] is the same as evaluating grid[i][j] against grid[i][j - 1] in the next iteration where j is increased by one.
The same can be said for reverse vertical and reverse diagonal.
|
So I'm having trouble with this one perl script. here is the line:
my $pid = StartApp("E:\\Luxmark-win64-v2.0\\LuxMark-x64.exe");
(StartApp calls the basic X11::GUITest::StartApp() .... in rare cases it calls the perl CreateProcess... both cases I have the issue... so you can prolly ignore theis part)
If I manually just double click the exe... it runs fine.
However calling it from the perl script which is located in E:\ ... Luxmark-x64.exe can't find its render cfg file located in E:\Luxmark-win64-v2.0\scenes\sala\render.cfg
I'm assuming this has something to do with the current working directory being E:\ when I launch via the script instead of E:\Luxmark-win64-v2.0\ when I click the app......
Anyone know of a perl trick to fix this?
|
I'm going to be interviewing some college compsci/engineers tomorrow. Any advice?
Technical questions already been asked.
|
|
|
On February 27 2013 10:03 darkness wrote:Show nested quote +On February 27 2013 09:20 RoyGBiv_13 wrote:On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college. The good parts: Your comments and logical structure make sense. You are using loops correctly. You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding) The bad parts: The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing. Your comments are merely labeling parts of the code, not describing it you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on. I'm sick of this "grid[i+1][j-1] * grid[i][j] > product" comparison... If you copy and paste something, think about putting it into a function. Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements: Calculate the largest product of adjacent N numbers where they are all in a line Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line) Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example) You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees. Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0. Okay, from what I understood from your and other guys' posts, I need to do the following: A. Use a function that checks if (a * b) > product. Perhaps something like the suggested std::max() B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid[i][j]? I always thought going through a grid is guaranteed O(n^2). C. Have better comments perhaps which I usually do, but I keep them minimal before final implementation. It may be more time-consuming though. There are probably more things to consider, but I'm tired, so I'll re-read posts again after I wake up. Edit: You actually expect right. I'm 2nd year at university.
Your solution is very good. You have an idea of what you want to do, you know it works, and you've executed it, which is very important to begin with.
For a lot of questions, you want to try and think of exactly what is required before tackling it. You've done what is known as the brute force method. Like how the problem was described, you've implemented a procedure that does the description.
You iterate through all the numbers in the grid and then you check all the numbers adjacent to it. Simple, and effective, and just plain good code.
But while you can make optimizations to minutely improve the performance and readability, the general approach to the problem was still a simple brute-force, which most of the time will fail once you want to extend its functionality.
What you want to try to do is look at the bigger picture. What do you really need to solve the problem? Do you actually need to iterate through every number?
You should notice by now there's a lot of redundancy in your code. Let me index your grid to make things simpler.
1 2 3
4 5 6
7 8 9
If you go 1->2->3->...->9, then the following applies.
If you're on 1, you've done 5 out of bounds checks, and only 3 relevant multiplications. When you're on 2, you do 3 out of bounds checks, and only 4!! relevant multiplications, and 1 extraneous multiplication in that 1x2 and 2x1 are the same.
Looking at it this way, how could you reduce these redundancies?
The way you've described doesn't really have any way of doing that, does it?
So you should think of what other ways you could do this, and more importantly, what is the question really asking for, because there's usually something more elegant than brute-force.
We ask the "extend for the general case" questions in order to stretch your mind so you don't get stuck in this brute-force method. It's really fun to discover these answers.
+ Show Spoiler [a bit better] ++ Show Spoiler [srsly dont do it unless yer ready] ++ Show Spoiler [im serious] ++ Show Spoiler [fine you win] +If you want something super simple as described on the previous page, just iterate through every diagonal, every row and every column with a length greater than 2. Why does this work? Well, if you do this, then you've found all possible adjacent numbers without doing any extra work (for the computer I mean).
1 2 3
4 5 6
7 8 9
If you look at that, you only need to check the diagonals ( (2,4), (3,5,7), (6,8) ), the rows ( (1,2,3), (4,5,6), (7,8,9) ), and the columns ( (1,4,7), (2,5,8), (3,6,9) ). In each of those lists, you have to do (length(list) - 1) multiplications. In the case of (4,5,6), you only ever need to do 4x5 and 5x6, a total of 2 multiplications. Keep track of the highest product, and your code should be much more optimized. This method is also a tad better at extending for the general case.
|
Ok so I wonder if anyone here can give me some information with regards to an idea I have.
So I am currently going through some resource translations, essentially we have an .rc file which has dialogues / string tables eg:
/////////////////////////////////////////////////////////////////////////////
// English (United Kingdom) resources
#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENG)
LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_UK
/////////////////////////////////////////////////////////////////////////////
//
// Dialog
//
IDD_ABOUT DIALOG 0, 0, 186, 86
STYLE DS_SETFONT | DS_MODALFRAME | WS_POPUP | WS_CAPTION | WS_SYSMENU
CAPTION "About Software"
FONT 8, "MS Sans Serif"
BEGIN
DEFPUSHBUTTON "OK",IDOK,68,65,50,14
ICON IDI_DLG,IDC_STATIC,7,7,20,20
CTEXT "Copyright ©1997, 2012.",IDC_STATIC,30,32,126,8
CTEXT "Software",IDC_VERSION,30,15,126,8
CTEXT "License:",IDC_SERIAL,30,49,126,8
END
#endif // English (United Kingdom) resources
/////////////////////////////////////////////////////////////////////////////
Ok so the basic idea is I want to automate the implementation of string translation, we get the actual strings translated professionally but putting them into the resources is a pain, especially when things need changing like the size of the dialogue etc.
So my idea is to have something more like this:
/////////////////////////////////////////////////////////////////////////////
// English (United Kingdom) resources
#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENG)
LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_UK
/////////////////////////////////////////////////////////////////////////////
//
// Dialog
//
IDD_ABOUT DIALOG 0, 0, 186, 86
STYLE DS_SETFONT | DS_MODALFRAME | WS_POPUP | WS_CAPTION | WS_SYSMENU
CAPTION "LANG_ABOUTSOFTWARE"
FONT 8, "MS Sans Serif"
BEGIN
DEFPUSHBUTTON "LANG_OK",IDOK,68,65,50,14
ICON IDI_DLG,IDC_STATIC,7,7,20,20
CTEXT "LANG_COPYRIGHT",IDC_STATIC,30,32,126,8
CTEXT "LANG_SOFTWARE",IDC_VERSION,30,15,126,8
CTEXT "LANG_LICENCE:",IDC_SERIAL,30,49,126,8
END
#endif // English (United Kingdom) resources
/////////////////////////////////////////////////////////////////////////////
Where LANG_X indicates a tag to be replaced with a translation, but also as there is only 1 set of resources it also needs to add the new languages like:
/////////////////////////////////////////////////////////////////////////////
// English (United Kingdom) resources
#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENG)
LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_UK
/* STUFF*/
#endif // English (United Kingdom) resources
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
// Japanese resources
#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_JPN)
LANGUAGE LANG_JAPANESE, SUBLANG_NEUTRAL
/* STUFF IN JAPANESE */
#endif // Japanese resources
/////////////////////////////////////////////////////////////////////////////
etc etc
We already have Perl scripts (not written by me) which go through and replace a phrase with another phrase ( OEM_TAG -> Company or Product X, as we make stuff for OEM's ).
So the question I have is how complicated would it be to implement something to do what I would like in Perl? I have no experience in it, although some people here could give me tips. It would just need essentially copy the /* Stuff */ in the english and copy it to other languages. I guess I essentially need a parser, so would it be correct to parse the /* Stuff */ and store it in memory then simply print it out surrounded by each language definition with the appropriate translations for that language when it comes across a LANG_ tag during the printing.
This just means that instead of manually going through each language resource in the .rc file replacing the strings you simply make with only the english language version, then when it comes to building on our build server as part of the build you run this script on the .rc file with another file indicting what translates to what in which language. Meaning you'd have to copy / paste less translation, and all you would need to worry about when altering resources is the english one as the others are generated for you when a full build is run.
My 6 months 'probationary' period ends in April and while I've done good work so far I haven't had an opportunity to take my own initiative and fix / improve something without implicit instructions and if this is something relatively straight forward and beneficial in terms of improving my learning / understanding I feel I should look into it more and try to implement it.
Just for reference I am a physics grad working as a junior software engineer so forgive me if this is something basic that a CS grad should know.
Any info would be appreciated.
|
On February 27 2013 09:39 Lascero wrote:
So I've been trying to break into some kind of low end position in web development and I'm getting mixed signals.
On one hand, people are saying you should have a bad ass portfolio with any amount of CSS/JS voodoo you can muster. Programming is often touted as a field with a ton of conviction about quality and if you don't have the same conviction/passion, you shouldn't be touching an IDE.
On the other hand, I'm having interviews where the seriously under-qualified are getting jobs. The last interview I had seriously said they've hired people -- as in given a living wage for this area -- who could not investigate problems on their own and barked for help at every turn. Now they obviously weren't kept around, but it still blows my mind that those hires got past the practical and initial interview.
I try to be honest with my ability and not misrepresent myself. I am only worth entry level. I can't tackle an entire corporate backend on day one, but I do have experience writing small stuff in Python/Django. Along with that comes basic HTML/CSS. I haven't done any responsive development, so stuff tends to look bad on a mobile browser. From the interviews I've been in, it seems like I have some entry-level skills that are worth a position (around here, anyway), but compared to the high and mighty talk on the forums I visit, I shouldn't be getting these interviews with this level of skill. I'm willing to learn new stuff, and I feel like I can learn any of the scripting/high-level languages fairly quickly. Since there are so many routes to take, and my free time is limited, I'd much prefer to study whatever language my next job will require (Is this a good or bad stance to take?).
Overall demand for developers is high, but does that demand extend down to the lower rungs? How useful are entry-level or junior positions?
Cheers.
I would have to say it varies on the Company, and it varies as much as the high-end jobs do.
For example, i've seen Junior C# Developer jobs require a minimum of two years experience with knowledge of CSS,SQL etc as a requirement. Yet i've seen jobs that require no experience and 'just a willingness to learn'. (Obviously pay is a factor).
As long as you are actively working to improve yourself, and have a specific route you wish to take, that is good and you will eventually get what you are looking for. (If you know what that is)
With regards to what language you want to learn based on your next job: Turn it around, base your next job on the language you want to learn. Interested in the data side of things? SQL/SAS etc. Interested in Web Dev? PHP/HTML/CSS/ASP.NET etc
In my opinion it is best to do it this way, and then find a job in which you are comfortable based on your knowledge of the language.
|
On February 27 2013 13:14 Blisse wrote:Show nested quote +On February 27 2013 10:03 darkness wrote:On February 27 2013 09:20 RoyGBiv_13 wrote:On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college. The good parts: Your comments and logical structure make sense. You are using loops correctly. You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding) The bad parts: The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing. Your comments are merely labeling parts of the code, not describing it you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on. I'm sick of this "grid[i+1][j-1] * grid[i][j] > product" comparison... If you copy and paste something, think about putting it into a function. Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements: Calculate the largest product of adjacent N numbers where they are all in a line Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line) Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example) You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees. Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0. Okay, from what I understood from your and other guys' posts, I need to do the following: A. Use a function that checks if (a * b) > product. Perhaps something like the suggested std::max() B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid[i][j]? I always thought going through a grid is guaranteed O(n^2). C. Have better comments perhaps which I usually do, but I keep them minimal before final implementation. It may be more time-consuming though. There are probably more things to consider, but I'm tired, so I'll re-read posts again after I wake up. Edit: You actually expect right. I'm 2nd year at university. Your solution is very good. You have an idea of what you want to do, you know it works, and you've executed it, which is very important to begin with. For a lot of questions, you want to try and think of exactly what is required before tackling it. You've done what is known as the brute force method. Like how the problem was described, you've implemented a procedure that does the description. You iterate through all the numbers in the grid and then you check all the numbers adjacent to it. Simple, and effective, and just plain good code. But while you can make optimizations to minutely improve the performance and readability, the general approach to the problem was still a simple brute-force, which most of the time will fail once you want to extend its functionality. What you want to try to do is look at the bigger picture. What do you really need to solve the problem? Do you actually need to iterate through every number? You should notice by now there's a lot of redundancy in your code. Let me index your grid to make things simpler.
1 2 3
4 5 6
7 8 9
If you go 1->2->3->...->9, then the following applies. If you're on 1, you've done 5 out of bounds checks, and only 3 relevant multiplications. When you're on 2, you do 3 out of bounds checks, and only 4!! relevant multiplications, and 1 extraneous multiplication in that 1x2 and 2x1 are the same. Looking at it this way, how could you reduce these redundancies? The way you've described doesn't really have any way of doing that, does it? So you should think of what other ways you could do this, and more importantly, what is the question really asking for, because there's usually something more elegant than brute-force. We ask the "extend for the general case" questions in order to stretch your mind so you don't get stuck in this brute-force method. It's really fun to discover these answers. + Show Spoiler [a bit better] ++ Show Spoiler [srsly dont do it unless yer ready] ++ Show Spoiler [im serious] ++ Show Spoiler [fine you win] +If you want something super simple as described on the previous page, just iterate through every diagonal, every row and every column with a length greater than 2. Why does this work? Well, if you do this, then you've found all possible adjacent numbers without doing any extra work (for the computer I mean).
1 2 3
4 5 6
7 8 9
If you look at that, you only need to check the diagonals ( (2,4), (3,5,7), (6,8) ), the rows ( (1,2,3), (4,5,6), (7,8,9) ), and the columns ( (1,4,7), (2,5,8), (3,6,9) ). In each of those lists, you have to do (length(list) - 1) multiplications. In the case of (4,5,6), you only ever need to do 4x5 and 5x6, a total of 2 multiplications. Keep track of the highest product, and your code should be much more optimized. This method is also a tad better at extending for the general case.
Thanks everyone. This is what I've done so far:
1. I use max(a, b) comparison now.
2. I've added local variables for more readability (leftColumn, leftRow, etc)
3. I've revised the 2nd for loop to have less iterations.
Ok, current code:
+ Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 1; j < n; j += 2) {
/* in order to avoid magic numbers and to achieve
* more readability, there will be some local variables
* to have clearer checks for array boundaries
*/
int leftRow = i-1;
int rightRow = i+1;
int leftColumn = j-1;
int rightColumn = j+1;
/* left */
if (!(leftColumn < 0)) {
maxProduct = max(grid[i][leftColumn] * grid[i][j], maxProduct);
}
/* right */
if (!(rightColumn > arraySize)) {
maxProduct = max(grid[i][rightColumn] * grid[i][j], maxProduct);
}
/* up */
if (!(leftRow < 0)) {
maxProduct = max(grid[leftRow][j] * grid[i][j], maxProduct);
}
/* down */
if (!(rightRow > arraySize)) {
maxProduct = max(grid[rightRow][j] * grid[i][j], maxProduct);
}
/* diagonally */
/* top left */
if (!(leftRow < 0 || leftColumn < 0)) {
maxProduct = max(grid[leftRow][leftColumn] * grid[i][j], maxProduct);
}
/* top right */
if (!(leftRow < 0 || rightColumn > arraySize)) {
maxProduct = max(grid[leftRow][rightColumn] * grid[i][j], maxProduct);
}
/* bottom left */
if (!(rightRow > arraySize || leftColumn < 0)) {
maxProduct = max(grid[rightRow][leftColumn] * grid[i][j], maxProduct);
}
/* bottom right */
if (!(rightRow > arraySize || rightColumn > arraySize)) {
maxProduct = max(grid[rightRow][rightColumn] * grid[i][j], maxProduct);
}
}
}
Hopefully it looks a lot better now. Comments are still limited though, but that's an easy thing to add once implementation is done.
Edit: should it be j += 2? It doesn't always have to be 3x3 grid. It can be 4x4, 5x5, etc.
|
On February 28 2013 02:06 darkness wrote:Show nested quote +On February 27 2013 13:14 Blisse wrote:On February 27 2013 10:03 darkness wrote:On February 27 2013 09:20 RoyGBiv_13 wrote:On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college. The good parts: Your comments and logical structure make sense. You are using loops correctly. You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding) The bad parts: The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing. Your comments are merely labeling parts of the code, not describing it you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on. I'm sick of this "grid[i+1][j-1] * grid[i][j] > product" comparison... If you copy and paste something, think about putting it into a function. Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements: Calculate the largest product of adjacent N numbers where they are all in a line Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line) Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example) You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees. Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0. Okay, from what I understood from your and other guys' posts, I need to do the following: A. Use a function that checks if (a * b) > product. Perhaps something like the suggested std::max() B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid[i][j]? I always thought going through a grid is guaranteed O(n^2). C. Have better comments perhaps which I usually do, but I keep them minimal before final implementation. It may be more time-consuming though. There are probably more things to consider, but I'm tired, so I'll re-read posts again after I wake up. Edit: You actually expect right. I'm 2nd year at university. Your solution is very good. You have an idea of what you want to do, you know it works, and you've executed it, which is very important to begin with. For a lot of questions, you want to try and think of exactly what is required before tackling it. You've done what is known as the brute force method. Like how the problem was described, you've implemented a procedure that does the description. You iterate through all the numbers in the grid and then you check all the numbers adjacent to it. Simple, and effective, and just plain good code. But while you can make optimizations to minutely improve the performance and readability, the general approach to the problem was still a simple brute-force, which most of the time will fail once you want to extend its functionality. What you want to try to do is look at the bigger picture. What do you really need to solve the problem? Do you actually need to iterate through every number? You should notice by now there's a lot of redundancy in your code. Let me index your grid to make things simpler.
1 2 3
4 5 6
7 8 9
If you go 1->2->3->...->9, then the following applies. If you're on 1, you've done 5 out of bounds checks, and only 3 relevant multiplications. When you're on 2, you do 3 out of bounds checks, and only 4!! relevant multiplications, and 1 extraneous multiplication in that 1x2 and 2x1 are the same. Looking at it this way, how could you reduce these redundancies? The way you've described doesn't really have any way of doing that, does it? So you should think of what other ways you could do this, and more importantly, what is the question really asking for, because there's usually something more elegant than brute-force. We ask the "extend for the general case" questions in order to stretch your mind so you don't get stuck in this brute-force method. It's really fun to discover these answers. + Show Spoiler [a bit better] ++ Show Spoiler [srsly dont do it unless yer ready] ++ Show Spoiler [im serious] ++ Show Spoiler [fine you win] +If you want something super simple as described on the previous page, just iterate through every diagonal, every row and every column with a length greater than 2. Why does this work? Well, if you do this, then you've found all possible adjacent numbers without doing any extra work (for the computer I mean).
1 2 3
4 5 6
7 8 9
If you look at that, you only need to check the diagonals ( (2,4), (3,5,7), (6,8) ), the rows ( (1,2,3), (4,5,6), (7,8,9) ), and the columns ( (1,4,7), (2,5,8), (3,6,9) ). In each of those lists, you have to do (length(list) - 1) multiplications. In the case of (4,5,6), you only ever need to do 4x5 and 5x6, a total of 2 multiplications. Keep track of the highest product, and your code should be much more optimized. This method is also a tad better at extending for the general case. Thanks everyone. This is what I've done so far: 1. I use max(a, b) comparison now. 2. I've added local variables for more readability (leftColumn, leftRow, etc) 3. I've revised the 2nd for loop to have less iterations. Ok, current code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 1; j < n; j += 3) {
/* in order to avoid magic numbers and to achieve
* more readability, there will be some local variables
* to have clearer checks for array boundaries
*/
int leftRow = i-1;
int rightRow = i+1;
int leftColumn = j-1;
int rightColumn = j+1;
/* left */
if (!(leftColumn < 0)) {
maxProduct = max(grid[i][leftColumn] * grid[i][j], maxProduct);
}
/* right */
if (!(rightColumn > arraySize)) {
maxProduct = max(grid[i][rightColumn] * grid[i][j], maxProduct);
}
/* up */
if (!(leftRow < 0)) {
maxProduct = max(grid[leftRow][j] * grid[i][j], maxProduct);
}
/* down */
if (!(rightRow > arraySize)) {
maxProduct = max(grid[rightRow][j] * grid[i][j], maxProduct);
}
/* diagonally */
/* top left */
if (!(leftRow < 0 || leftColumn < 0)) {
maxProduct = max(grid[leftRow][leftColumn] * grid[i][j], maxProduct);
}
/* top right */
if (!(leftRow < 0 || rightColumn > arraySize)) {
maxProduct = max(grid[leftRow][rightColumn] * grid[i][j], maxProduct);
}
/* bottom left */
if (!(rightRow > arraySize || leftColumn < 0)) {
maxProduct = max(grid[rightRow][leftColumn] * grid[i][j], maxProduct);
}
/* bottom right */
if (!(rightRow > arraySize || rightColumn > arraySize)) {
maxProduct = max(grid[rightRow][rightColumn] * grid[i][j], maxProduct);
}
}
}
If I'm still missing something, it is because I either don't know how to implement it or I don't understand the idea. I'm aware there is extra multiplication in the case when j = 2 though. E.g. (2, 5), (5, 2), (5, 8), (8, 5). Hopefully it looks a lot better now. Comments are still limited though, but that's an easy thing to add once implementation is done. Edit: should it be j += 2 instead of 3? It doesn't always have to be 3x3 grid. It can be 4x4, 5x5, etc.
Yup, the code is a lot better in terms of readability, though there are definitely some things you could do to make it better, and there always will be.
My comment was more in regards to the limits of your current implementation. As in my previous reply, there is definitely an alternative approach to the question that provides a rather more elegant solution than what you have now. While you can definitely improve the readability of the solution, and maybe optimize some calculations, what my comment talks about is the overall approach to the problem.
(I am debating whether the optimal solution we're describing is within the limits of what you've learned so far since all you've learned is C, but it would be a good introduction to the topic, however randomly hard it might seem.)
Not sure why you have a j+=3 at all. Can you explain what your thought process is here?
How does that 3 relate to your 3x3, 4x4, NxN? Does it even relate?
|
This is a more theoretical and simple question, but I'd love some input, it's something I've been pondering since I learned OOP principles ages ago.
Let's say I'm making a console-based adventure game. I have a world class which handles command inputs from the user. The world class has a map (2d array of room objects), a player object and obviously lots of other stuff. Now let's say the user inputs the command "south". Thinking object-oriented, I go "Ok, so I want my player object to do a move method". At first, this makes sense because the player has a struct with an X and a Y position. However, obviously I need to make sure that the player doesn't walk outside of the map. The conundrum is, the player object doesn't know about the map, which the world object has.
The are two solutions I can think of, and I sort of dislike both:
1. Let the player know about the map, by sending in a pointer to it in the players constructor. Now, the player can check for himself if there's a room at the end of the Go command, else return that movement was impossible. Problem of course being the stronger coupling between the player class and the world class.
2. Don't let the player move, let the world have a MovePlayer method which does the map-checking etc and then updates the player objects position. Now the player is completely uncoupled from the world, but following this logic, the World class will become a BEAST which will have to implement pretty much everything done in the game. To use an OOP term, the cohesion for the world class will become very low if it has to handle every other object in the game.
How do you guys feel situations like this are best solved? It seems like it's impossible to hold to strict object-oriented guidelines without making pretty much every class know about every other class. If you want to take the example farther, let's say you have so many commands that you want some form of command-parser class... now, should suddenly the command-parser be coupled to all the other objects it needs to handle when dealing with commands?
|
On February 28 2013 03:32 Tobberoth wrote:
This is a more theoretical and simple question, but I'd love some input, it's something I've been pondering since I learned OOP principles ages ago.
Let's say I'm making a console-based adventure game. I have a world class which handles command inputs from the user. The world class has a map (2d array of room objects), a player object and obviously lots of other stuff. Now let's say the user inputs the command "south". Thinking object-oriented, I go "Ok, so I want my player object to do a move method". At first, this makes sense because the player has a struct with an X and a Y position. However, obviously I need to make sure that the player doesn't walk outside of the map. The conundrum is, the player object doesn't know about the map, which the world object has.
The are two solutions I can think of, and I sort of dislike both:
1. Let the player know about the map, by sending in a pointer to it in the players constructor. Now, the player can check for himself if there's a room at the end of the Go command, else return that movement was impossible. Problem of course being the stronger coupling between the player class and the world class.
2. Don't let the player move, let the world have a MovePlayer method which does the map-checking etc and then updates the player objects position. Now the player is completely uncoupled from the world, but following this logic, the World class will become a BEAST which will have to implement pretty much everything done in the game.
How do you guys feel situations like this are best solved? It seems like it's impossible to hold to strict object-oriented guidelines without making pretty much every class know about every other class.
In any OO system you're going to need to have a system of communication between objects. Your first option is the better of your two suggestions, but I think the weakness of it is that you're having the Player object read the Map object, both by literally having the Player check for an object in the Map's Rooms collection, but also by having the Player responsible for knowing what "north" "south" "east" and "west" mean. That's spatial relationship knowledge, and it's more at home in the Map than in the Player. It also unduly limits the Player in its ability to traverse the Map - what if your Player gets some Shoes of Teleportation? Now either the Player needs a new move function, or you have to delegate the move function to the shoes, making your structure even more complicated.
I would put all of your spatial information into the Map and Room. The Room can know what rooms it's connected to by making it a node in a multidimensional linked list, so it can implement functions like getNeighboringRoom(string rel) -- which makes you more flexible, as your Room can now connect to other Rooms via transporter panels, tunnels, or what have you, just by adding a new relationship type -- and getConnectedRooms() or getNeighborRoomRelationships() or getVerbsThatGetMeOutOfHere() to allow the Player to know which verbs can be used to get to another Room from the current one. The Map can get you a Room via coordinates or names, solving your Shoes of Teleportation problem.
Now navigating is simple. Your user types "go south", you call curRoom.getNeighboringRoom('south'). If your result is NULL, you reply "you bonk your head on the wall and take 5HP of damage, lol" and if it's not you call player.goToRoom(newRoom).
|
On February 28 2013 02:28 Blisse wrote:Show nested quote +On February 28 2013 02:06 darkness wrote:On February 27 2013 13:14 Blisse wrote:On February 27 2013 10:03 darkness wrote:On February 27 2013 09:20 RoyGBiv_13 wrote:On February 27 2013 08:50 darkness wrote:Edit: C languageI'm disgusted at how I've implemented my code to get the greatest product of 2 adjacent numbers. First off, an example of what I'm talking about (feel free to skip if you know what the goal is): You have an n x n grid (2D array). You're are asked to find the largest multiplication (product) of 2 adjacent (close to each other) numbers in any direction (left, right, down, up or diagonally). Example: 21 22 23 20 00 11 17 06 15 22 x 23 is the largest, so output would be 506. Now my implementation: Code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
/* check left */
if (!(j-1 < 0)) {
if (grid[i][j-1] * grid[i][j] > product) {
product = grid[i][j-1] * grid[i][j];
}
}
/* check right */
if (!(j+1 > n-1)) {
if (grid[i][j+1] * grid[i][j] > product) {
product = grid[i][j+1] * grid[i][j];
}
}
/* check up */
if (!(i-1 < 0)) {
if (grid[i-1][j] * grid[i][j] > product) {
product = grid[i-1][j] * grid[i][j];
}
}
/* check down */
if (!(i+1 > n-1)) {
if (grid[i+1][j] * grid[i][j] > product) {
product = grid[i+1][j] * grid[i][j];
}
}
/* check diagonally */
/* top left */
if (!(i-1 < 0 || j-1 < 0)) {
if (grid[i-1][j-1] * grid[i][j] > product) {
product = grid[i-1][j-1] * grid[i][j];
}
}
/* top right */
if (!(i-1 < 0 || j+1 > n-1)) {
if (grid[i-1][j+1] * grid[i][j] > product) {
product = grid[i-1][j+1] * grid[i][j];
}
}
/* bottom left */
if (!(i+1 > n-1 || j-1 < 0)) {
if (grid[i+1][j-1] * grid[i][j] > product) {
product = grid[i+1][j-1] * grid[i][j];
}
}
/* bottom right */
if (!(i+1 > n-1 || j+1 > n-1)) {
if (grid[i+1][j+1] * grid[i][j] > product) {
product = grid[i+1][j+1] * grid[i][j];
}
}
}
}
I'm honestly not pleased with how I wrote this. It doesn't seem clean to me. Any help/optimisation? What about 'x' adjacent numbers instead of only 2? Thanks. Edit: Possible step to make it more clean: I should perhaps have at the start of the 2nd loop something like this: leftColumn = j-1; rightColumn = j+1; rowAbove = i-1; etc Any feedback will be greatly appreciated. Honestly, if your goal for any code is that it works, then this is "good enough". To give you an idea of where you are at, I would expect this level of code quality from around a sophomore in a CS program in college. The good parts: Your comments and logical structure make sense. You are using loops correctly. You avoided unnecessary variables (though this isn't necessarily a good thing for the readability, it does show understanding) The bad parts: The code doesn't speak for itself in a lot of ways. Without knowledge of the problem, I would have no idea what this is doing. Your comments are merely labeling parts of the code, not describing it you only have the "given" variables, your input and output. Sometimes this is fine, but there is a lot of voodoo math going on. I'm sick of this "grid[i+1][j-1] * grid [j] > product" comparison... If you copy and paste something, think about putting it into a function.
Extending this to the general case (more than 2 adjacent numbers) can be very interesting based on the rules. Here are some example problem statements:
Calculate the largest product of adjacent N numbers where they are all in a line
Calculate the largest product of adjacent N numbers where they are touching (dont have to be in a line)
Calculate the largest product of adjacent N numbers where they are touching, This produce is based on traversing the matrix, and you can go backwards to a previous number
Calculate the largest product of adjacent N numbers where they are touching, but you can choose to not include a number if you don't want to (negative numbers, for example)
You can see how complicated this "simple" problem can get very quickly by adding in new problems. If there is extra credit on a problem, take it so that you will code for the more general case, and get used to doing so. This is probably the best way to clean up your code. In fact, if you have a minute and want to learn something, the third one down is a fantastic introduction to trees.
Finally, boundary checking is annoying. This is not the first time, nor the last you will encounter it, so its best if you spend some time thinking of possible ways to avoid boundary checking. For example, I would append a border of 0's around the given matrix, then iterate over i:1->N+1, so that when it calculates an edge, the product is 0. Okay, from what I understood from your and other guys' posts, I need to do the following: A. Use a function that checks if (a * b) > product. Perhaps something like the suggested std::max() B. Try to lower O(n^2) to O(n), but I'm not sure I fully understood the pseudo code. For example, how do you iterate i in grid [j]? I always thought going through a grid is guaranteed O(n^2).
C. Have better comments perhaps which I usually do, but I keep them minimal before final implementation. It may be more time-consuming though.
There are probably more things to consider, but I'm tired, so I'll re-read posts again after I wake up.
Edit: You actually expect right. I'm 2nd year at university.
Your solution is very good. You have an idea of what you want to do, you know it works, and you've executed it, which is very important to begin with. For a lot of questions, you want to try and think of exactly what is required before tackling it. You've done what is known as the brute force method. Like how the problem was described, you've implemented a procedure that does the description. You iterate through all the numbers in the grid and then you check all the numbers adjacent to it. Simple, and effective, and just plain good code. But while you can make optimizations to minutely improve the performance and readability, the general approach to the problem was still a simple brute-force, which most of the time will fail once you want to extend its functionality. What you want to try to do is look at the bigger picture. What do you really need to solve the problem? Do you actually need to iterate through every number? You should notice by now there's a lot of redundancy in your code. Let me index your grid to make things simpler.
1 2 3
4 5 6
7 8 9
If you go 1->2->3->...->9, then the following applies. If you're on 1, you've done 5 out of bounds checks, and only 3 relevant multiplications. When you're on 2, you do 3 out of bounds checks, and only 4!! relevant multiplications, and 1 extraneous multiplication in that 1x2 and 2x1 are the same. Looking at it this way, how could you reduce these redundancies? The way you've described doesn't really have any way of doing that, does it? So you should think of what other ways you could do this, and more importantly, what is the question really asking for, because there's usually something more elegant than brute-force. We ask the "extend for the general case" questions in order to stretch your mind so you don't get stuck in this brute-force method. It's really fun to discover these answers. + Show Spoiler [a bit better] ++ Show Spoiler [srsly dont do it unless yer ready] ++ Show Spoiler [im serious] ++ Show Spoiler [fine you win] +If you want something super simple as described on the previous page, just iterate through every diagonal, every row and every column with a length greater than 2. Why does this work? Well, if you do this, then you've found all possible adjacent numbers without doing any extra work (for the computer I mean).
1 2 3
4 5 6
7 8 9
If you look at that, you only need to check the diagonals ( (2,4), (3,5,7), (6,8) ), the rows ( (1,2,3), (4,5,6), (7,8,9) ), and the columns ( (1,4,7), (2,5,8), (3,6,9) ). In each of those lists, you have to do (length(list) - 1) multiplications. In the case of (4,5,6), you only ever need to do 4x5 and 5x6, a total of 2 multiplications. Keep track of the highest product, and your code should be much more optimized. This method is also a tad better at extending for the general case. Thanks everyone. This is what I've done so far: 1. I use max(a, b) comparison now. 2. I've added local variables for more readability (leftColumn, leftRow, etc) 3. I've revised the 2nd for loop to have less iterations. Ok, current code: + Show Spoiler +
for (i = 0; i < n; i++) {
for (j = 1; j < n; j += 3) {
/* in order to avoid magic numbers and to achieve
* more readability, there will be some local variables
* to have clearer checks for array boundaries
*/
int leftRow = i-1;
int rightRow = i+1;
int leftColumn = j-1;
int rightColumn = j+1;
/* left */
if (!(leftColumn < 0)) {
maxProduct = max(grid[i][leftColumn] * grid[i][j], maxProduct);
}
/* right */
if (!(rightColumn > arraySize)) {
maxProduct = max(grid[i][rightColumn] * grid[i][j], maxProduct);
}
/* up */
if (!(leftRow < 0)) {
maxProduct = max(grid[leftRow][j] * grid[i][j], maxProduct);
}
/* down */
if (!(rightRow > arraySize)) {
maxProduct = max(grid[rightRow][j] * grid[i][j], maxProduct);
}
/* diagonally */
/* top left */
if (!(leftRow < 0 || leftColumn < 0)) {
maxProduct = max(grid[leftRow][leftColumn] * grid[i][j], maxProduct);
}
/* top right */
if (!(leftRow < 0 || rightColumn > arraySize)) {
maxProduct = max(grid[leftRow][rightColumn] * grid[i][j], maxProduct);
}
/* bottom left */
if (!(rightRow > arraySize || leftColumn < 0)) {
maxProduct = max(grid[rightRow][leftColumn] * grid[i][j], maxProduct);
}
/* bottom right */
if (!(rightRow > arraySize || rightColumn > arraySize)) {
maxProduct = max(grid[rightRow][rightColumn] * grid[i][j], maxProduct);
}
}
}
If I'm still missing something, it is because I either don't know how to implement it or I don't understand the idea. I'm aware there is extra multiplication in the case when j = 2 though. E.g. (2, 5), (5, 2), (5, 8), (8, 5). Hopefully it looks a lot better now. Comments are still limited though, but that's an easy thing to add once implementation is done. Edit: should it be j += 2 instead of 3? It doesn't always have to be 3x3 grid. It can be 4x4, 5x5, etc. Yup, the code is a lot better in terms of readability, though there are definitely some things you could do to make it better, and there always will be. My comment was more in regards to the limits of your current implementation. As in my previous reply, there is definitely an alternative approach to the question that provides a rather more elegant solution than what you have now. While you can definitely improve the readability of the solution, and maybe optimize some calculations, what my comment talks about is the overall approach to the problem. (I am debating whether the optimal solution we're describing is within the limits of what you've learned so far since all you've learned is C, but it would be a good introduction to the topic, however randomly hard it might seem.) Not sure why you have a j+=3 at all. Can you explain what your thought process is here? How does that 3 relate to your 3x3, 4x4, NxN? Does it even relate?
Interesting, I'm guessing the j+=3 is so that he does not check the product of every number. Unfortunately this is an error as it will miss some products on the horizontal side, and additionally will miss a few diagonals and columns as well.
What Blisse said about the limitations of your brute force approach is correct. Look at the difference between these two implementations:
Brute Force
for(i:0>N)
for(j:0->N)
check_products(i,i)
Directional
for(i:0->N)
check_row(i)
check_column(i)
check_leftdiag(i)
check_rightdiag(i)
+ Show Spoiler +Though you may not understand this yet, its worth looking at. Bonus general case using recursion:
int product = 0;
check_products_then_recurse(0,0,)
...
check_products_then_recurse(int i, int j)
{
if invalid location
return 0
return max(check_products(i,j),check_products_then_recurse(i+1,j),check_products_then_recurse(i,j+1))
}
Also, one more nitpicky thing. The comment you added describes why you used the variables, but not what they do! It should be the other way around. In the real world, someone reading your code wont care [i]why you chose to do something that way, they will be reading it to try to understand [i]what you did
|
On February 28 2013 03:47 AmericanUmlaut wrote:Show nested quote +On February 28 2013 03:32 Tobberoth wrote:
This is a more theoretical and simple question, but I'd love some input, it's something I've been pondering since I learned OOP principles ages ago.
Let's say I'm making a console-based adventure game. I have a world class which handles command inputs from the user. The world class has a map (2d array of room objects), a player object and obviously lots of other stuff. Now let's say the user inputs the command "south". Thinking object-oriented, I go "Ok, so I want my player object to do a move method". At first, this makes sense because the player has a struct with an X and a Y position. However, obviously I need to make sure that the player doesn't walk outside of the map. The conundrum is, the player object doesn't know about the map, which the world object has.
The are two solutions I can think of, and I sort of dislike both:
1. Let the player know about the map, by sending in a pointer to it in the players constructor. Now, the player can check for himself if there's a room at the end of the Go command, else return that movement was impossible. Problem of course being the stronger coupling between the player class and the world class.
2. Don't let the player move, let the world have a MovePlayer method which does the map-checking etc and then updates the player objects position. Now the player is completely uncoupled from the world, but following this logic, the World class will become a BEAST which will have to implement pretty much everything done in the game.
How do you guys feel situations like this are best solved? It seems like it's impossible to hold to strict object-oriented guidelines without making pretty much every class know about every other class. In any OO system you're going to need to have a system of communication between objects. Your first option is the better of your two suggestions, but I think the weakness of it is that you're having the Player object read the Map object, both by literally having the Player check for an object in the Map's Rooms collection, but also by having the Player responsible for knowing what "north" "south" "east" and "west" mean. That's spatial relationship knowledge, and it's more at home in the Map than in the Player. It also unduly limits the Player in its ability to traverse the Map - what if your Player gets some Shoes of Teleportation? Now either the Player needs a new move function, or you have to delegate the move function to the shoes, making your structure even more complicated. I would put all of your spatial information into the Map and Room. The Room can know what rooms it's connected to by making it a node in a multidimensional linked list, so it can implement functions like getNeighboringRoom(string rel) -- which makes you more flexible, as your Room can now connect to other Rooms via transporter panels, tunnels, or what have you, just by adding a new relationship type -- and getConnectedRooms() or getNeighborRoomRelationships() or getVerbsThatGetMeOutOfHere() to allow the Player to know which verbs can be used to get to another Room from the current one. The Map can get you a Room via coordinates or names, solving your Shoes of Teleportation problem. Now navigating is simple. Your user types "go south", you call curRoom.getNeighboringRoom('south'). If your result is NULL, you reply "you bonk your head on the wall and take 5HP of damage, lol" and if it's not you call player.goToRoom(newRoom).
That is of course a nice other system of handling connections between rooms, but the eventual solution still means that the World object has to handle the "go south" command by asking the room for the spatial information and then tell the player to go south. In my simple system, that would be the same as if the world checked the coordinates in the map to see if there's a room there, and if there is, change the players coordinates to the new position.
But lets say we don't want the world to handle commands (which makes sense from a cohesion perspective) and we want a command parser to handle that. Now we have the same problem, because now we need to send the command object both the map (so it can check spatial information) and the player (so it can tell it to move). Of course, we could let the world have a MovePlayer method which we call from the command class.
The main problem here is that I usually find it very easy to put pure data into objects. A world has a map, a player has a position and a name, maybe an inventory. What I find difficult is when I need to give those objects actions, because that's when the dependencies really pile up. It seems logical the player should do the move command and a "pick up into inventory" command, but it can't since the world knows about the map/rooms and the items in the rooms. At the same time, having the world put the item in the inventory of the player seems weird, so the most decoupled way would be for the room to tell the player to put the item into the players inventory... which gives us ridiculously long chains of methods between objects.
|
On February 28 2013 04:04 Tobberoth wrote:
That is of course a nice other system of handling connections between rooms, but the eventual solution still means that the World object has to handle the "go south" command by asking the room for the spatial information and then tell the player to go south. In my simple system, that would be the same as if the world checked the coordinates in the map to see if there's a room there, and if there is, change the players coordinates to the new position.
No, the parser handles the command, asks the spatial model whether it's legal to execute it and then calls the appropriate function in response. Player in this model simply has a relationship to the Room he's in, which makes sense. Or you have a global "current Room" variable, which amounts to the same thing in a single player game. The Map doesn't communicate directly with the Room at all, the Map in my description is nothing more than a container for a collection of Rooms that are themselves a graph and capable of resolving their own neighbor relationships, and contains whatever functions you need to get at a Room instance beyond what any one Room knows.
But lets say we don't want the world to handle commands (which makes sense from a cohesion perspective) and we want a command parser to handle that. Now we have the same problem, because now we need to send the command object both the map (so it can check spatial information) and the player (so it can tell it to move).
Well you have a Player, a Map and a Room. They've either got to all be visible from where you want to manipulate them, or they've got to have a relationship to each other that they communicate through. I don't understand what you think is stylistically or logically a problem with having a command parser parse a command, determine whether it's spatially possible by consulting the object responsible for spatial relationships, then executing the command on the appropriate object. Have I misunderstood what your goal is?
Of course, we could let the world have a MovePlayer method which we call from the command class.
That doesn't make any sense, though. If you're in the command class and have gotten the information about where the Player should be put, why would you then move the Player via a method implemented by the Map? You know where the Player should go: Tell the Player and let it be responsible for dealing with that information.
The main problem here is that I usually find it very easy to put pure data into objects. A world has a map, a player has a position and a name, maybe an inventory. What I find difficult is when I need to give those objects actions, because that's when the dependencies really pile up. It seems logical the player should do the move command and a "pick up into inventory" command, but it can't since the world knows about the map/rooms and the items in the rooms. At the same time, having the world put the item in the inventory of the player seems weird, so the most decoupled way would be for the room to tell the player to put the item into the players inventory... which gives us ridiculously long chains of methods between objects.
All of the things you say make sense, except that you have some ideas about how classes should be restricted in their communication that seem very strange to me. You allow that a Player has a position, but you don't want it to have a pointer to a Room, which represents exactly that piece of information. You find it problematic for the Player to ask the Room what pickupable items it contains and then retrieve one of them, but the alternative you suggest is to have a tenuously related object (the Map) pluck an object from the Room and put it into the Player's Inventory collection, which doesn't make any sense in terms of separation of responsibilities.
I'm really not clear what your design goals are. When you have two objects, and one has information that the other requires to perform a task, the objects have to communicate. The Player wants to pick up an object, so it asks the Room for it. Or you have a global context that sees everything, and you pull from the Room and push to the Player from there. Or what exactly are you hoping to achieve?
|
On February 28 2013 04:54 AmericanUmlaut wrote:Show nested quote +On February 28 2013 04:04 Tobberoth wrote:
That is of course a nice other system of handling connections between rooms, but the eventual solution still means that the World object has to handle the "go south" command by asking the room for the spatial information and then tell the player to go south. In my simple system, that would be the same as if the world checked the coordinates in the map to see if there's a room there, and if there is, change the players coordinates to the new position.
No, the parser handles the command, asks the spatial model whether it's legal to execute it and then calls the appropriate function in response. Player in this model simply has a relationship to the Room he's in, which makes sense. Or you have a global "current Room" variable, which amounts to the same thing in a single player game. The Map doesn't communicate directly with the Room at all, the Map in my description is nothing more than a container for a collection of Rooms that are themselves a graph and capable of resolving their own neighbor relationships, and contains whatever functions you need to get at a Room instance beyond what any one Room knows. Show nested quote +But lets say we don't want the world to handle commands (which makes sense from a cohesion perspective) and we want a command parser to handle that. Now we have the same problem, because now we need to send the command object both the map (so it can check spatial information) and the player (so it can tell it to move). Well you have a Player, a Map and a Room. They've either got to all be visible from where you want to manipulate them, or they've got to have a relationship to each other that they communicate through. I don't understand what you think is stylistically or logically a problem with having a command parser parse a command, determine whether it's spatially possible by consulting the object responsible for spatial relationships, then executing the command on the appropriate object. Have I misunderstood what your goal is? Show nested quote +Of course, we could let the world have a MovePlayer method which we call from the command class. That doesn't make any sense, though. If you're in the command class and have gotten the information about where the Player should be put, why would you then move the Player via a method implemented by the Map? You know where the Player should go: Tell the Player and let it be responsible for dealing with that information. Show nested quote +The main problem here is that I usually find it very easy to put pure data into objects. A world has a map, a player has a position and a name, maybe an inventory. What I find difficult is when I need to give those objects actions, because that's when the dependencies really pile up. It seems logical the player should do the move command and a "pick up into inventory" command, but it can't since the world knows about the map/rooms and the items in the rooms. At the same time, having the world put the item in the inventory of the player seems weird, so the most decoupled way would be for the room to tell the player to put the item into the players inventory... which gives us ridiculously long chains of methods between objects. All of the things you say make sense, except that you have some ideas about how classes should be restricted in their communication that seem very strange to me. You allow that a Player has a position, but you don't want it to have a pointer to a Room, which represents exactly that piece of information. You find it problematic for the Player to ask the Room what pickupable items it contains and then retrieve one of them, but the alternative you suggest is to have a tenuously related object (the Map) pluck an object from the Room and put it into the Player's Inventory collection, which doesn't make any sense in terms of separation of responsibilities. I'm really not clear what your design goals are. When you have two objects, and one has information that the other requires to perform a task, the objects have to communicate. The Player wants to pick up an object, so it asks the Room for it. Or you have a global context that sees everything, and you pull from the Room and push to the Player from there. Or what exactly are you hoping to achieve?
A lot of your points make sense, but in this case, the player doesn't have a reference to a room. He only has coordinates, which only make sense when applied to the map in the World object. I agree that a lot of your logic makes sense when rooms work like your system, but this map system is far simpler since it's just a 2D Array, so a Room doesn't have any idea what rooms surrounds it, if any. All it has is, like the player, a 2-point coordinate.
I'm planning to rewrite the system to use something along the lines of what you're describing (currently writing a simple XML parser to read a map file), where you logic will make sense to implement. However, my problems with the current solution are still relevant though, since the same system is used in basic 2D tile engines. A tile generally has no idea what surrounds it, you only have coordinates which only make sense in a class of a higher order where your tiles are parts of a 2D array (at least in the tile engines I've seen). So when you move a player, you will generally not be able to go with the style of asking the player for its tile, and in turn asking that tile for surrounding tiles, you pretty much have to use an overarching map object, so we get the same situation: Does the player have a reference to the map object, or does the map object move the player instead, so to speak.
What I'm saying here is that your logic is sound, but you're calling the map (or rather world in my case) a "tenously related object", when it's in my system quite fundamental since it's the only object which has references to both the map and the player, since it instantiated both objects.
|
On February 28 2013 07:25 Tobberoth wrote:Show nested quote +On February 28 2013 04:54 AmericanUmlaut wrote:On February 28 2013 04:04 Tobberoth wrote:
That is of course a nice other system of handling connections between rooms, but the eventual solution still means that the World object has to handle the "go south" command by asking the room for the spatial information and then tell the player to go south. In my simple system, that would be the same as if the world checked the coordinates in the map to see if there's a room there, and if there is, change the players coordinates to the new position.
No, the parser handles the command, asks the spatial model whether it's legal to execute it and then calls the appropriate function in response. Player in this model simply has a relationship to the Room he's in, which makes sense. Or you have a global "current Room" variable, which amounts to the same thing in a single player game. The Map doesn't communicate directly with the Room at all, the Map in my description is nothing more than a container for a collection of Rooms that are themselves a graph and capable of resolving their own neighbor relationships, and contains whatever functions you need to get at a Room instance beyond what any one Room knows. But lets say we don't want the world to handle commands (which makes sense from a cohesion perspective) and we want a command parser to handle that. Now we have the same problem, because now we need to send the command object both the map (so it can check spatial information) and the player (so it can tell it to move). Well you have a Player, a Map and a Room. They've either got to all be visible from where you want to manipulate them, or they've got to have a relationship to each other that they communicate through. I don't understand what you think is stylistically or logically a problem with having a command parser parse a command, determine whether it's spatially possible by consulting the object responsible for spatial relationships, then executing the command on the appropriate object. Have I misunderstood what your goal is? Of course, we could let the world have a MovePlayer method which we call from the command class. That doesn't make any sense, though. If you're in the command class and have gotten the information about where the Player should be put, why would you then move the Player via a method implemented by the Map? You know where the Player should go: Tell the Player and let it be responsible for dealing with that information. The main problem here is that I usually find it very easy to put pure data into objects. A world has a map, a player has a position and a name, maybe an inventory. What I find difficult is when I need to give those objects actions, because that's when the dependencies really pile up. It seems logical the player should do the move command and a "pick up into inventory" command, but it can't since the world knows about the map/rooms and the items in the rooms. At the same time, having the world put the item in the inventory of the player seems weird, so the most decoupled way would be for the room to tell the player to put the item into the players inventory... which gives us ridiculously long chains of methods between objects. All of the things you say make sense, except that you have some ideas about how classes should be restricted in their communication that seem very strange to me. You allow that a Player has a position, but you don't want it to have a pointer to a Room, which represents exactly that piece of information. You find it problematic for the Player to ask the Room what pickupable items it contains and then retrieve one of them, but the alternative you suggest is to have a tenuously related object (the Map) pluck an object from the Room and put it into the Player's Inventory collection, which doesn't make any sense in terms of separation of responsibilities. I'm really not clear what your design goals are. When you have two objects, and one has information that the other requires to perform a task, the objects have to communicate. The Player wants to pick up an object, so it asks the Room for it. Or you have a global context that sees everything, and you pull from the Room and push to the Player from there. Or what exactly are you hoping to achieve? A lot of your points make sense, but in this case, the player doesn't have a reference to a room. He only has coordinates, which only make sense when applied to the map in the World object. I agree that a lot of your logic makes sense when rooms work like your system, but this map system is far simpler since it's just a 2D Array, so a Room doesn't have any idea what rooms surrounds it, if any. All it has is, like the player, a 2-point coordinate. I'm planning to rewrite the system to use something along the lines of what you're describing (currently writing a simple XML parser to read a map file), where you logic will make sense to implement. However, my problems with the current solution are still relevant though, since the same system is used in basic 2D tile engines. A tile generally has no idea what surrounds it, you only have coordinates which only make sense in a class of a higher order where your tiles are parts of a 2D array (at least in the tile engines I've seen). So when you move a player, you will generally not be able to go with the style of asking the player for its tile, and in turn asking that tile for surrounding tiles, you pretty much have to use an overarching map object, so we get the same situation: Does the player have a reference to the map object, or does the map object move the player instead, so to speak. What I'm saying here is that your logic is sound, but you're calling the map (or rather world in my case) a "tenously related object", when it's in my system quite fundamental since it's the only object which has references to both the map and the player, since it instantiated both objects.
Oh, you've already programmed this. I thought we were talking hypothetically about how you could use an object model to represent these relationships, not about cleaning up an already-existing implementation.
If you're going to start from the assumption that your map is a 2-dimensional grid, and all your player has are x and y values, then you can still get a reasonable separation of responsibilities. Your parser is responsible for understanding that "go south" means "attempt to increase the Y coordinate of the player's position by 1". The parser asks the map if that's allowed, the map says yes, the parser tells the player to move to the new coordinates. So the player is responsible for knowing where it is, the map is responsible for knowing what coordinates are legal, and the parser is responsible for determining the meaning of incoming user input.
|
On February 28 2013 19:43 AmericanUmlaut wrote:Show nested quote +On February 28 2013 07:25 Tobberoth wrote:On February 28 2013 04:54 AmericanUmlaut wrote:On February 28 2013 04:04 Tobberoth wrote:
That is of course a nice other system of handling connections between rooms, but the eventual solution still means that the World object has to handle the "go south" command by asking the room for the spatial information and then tell the player to go south. In my simple system, that would be the same as if the world checked the coordinates in the map to see if there's a room there, and if there is, change the players coordinates to the new position.
No, the parser handles the command, asks the spatial model whether it's legal to execute it and then calls the appropriate function in response. Player in this model simply has a relationship to the Room he's in, which makes sense. Or you have a global "current Room" variable, which amounts to the same thing in a single player game. The Map doesn't communicate directly with the Room at all, the Map in my description is nothing more than a container for a collection of Rooms that are themselves a graph and capable of resolving their own neighbor relationships, and contains whatever functions you need to get at a Room instance beyond what any one Room knows. But lets say we don't want the world to handle commands (which makes sense from a cohesion perspective) and we want a command parser to handle that. Now we have the same problem, because now we need to send the command object both the map (so it can check spatial information) and the player (so it can tell it to move). Well you have a Player, a Map and a Room. They've either got to all be visible from where you want to manipulate them, or they've got to have a relationship to each other that they communicate through. I don't understand what you think is stylistically or logically a problem with having a command parser parse a command, determine whether it's spatially possible by consulting the object responsible for spatial relationships, then executing the command on the appropriate object. Have I misunderstood what your goal is? Of course, we could let the world have a MovePlayer method which we call from the command class. That doesn't make any sense, though. If you're in the command class and have gotten the information about where the Player should be put, why would you then move the Player via a method implemented by the Map? You know where the Player should go: Tell the Player and let it be responsible for dealing with that information. The main problem here is that I usually find it very easy to put pure data into objects. A world has a map, a player has a position and a name, maybe an inventory. What I find difficult is when I need to give those objects actions, because that's when the dependencies really pile up. It seems logical the player should do the move command and a "pick up into inventory" command, but it can't since the world knows about the map/rooms and the items in the rooms. At the same time, having the world put the item in the inventory of the player seems weird, so the most decoupled way would be for the room to tell the player to put the item into the players inventory... which gives us ridiculously long chains of methods between objects. All of the things you say make sense, except that you have some ideas about how classes should be restricted in their communication that seem very strange to me. You allow that a Player has a position, but you don't want it to have a pointer to a Room, which represents exactly that piece of information. You find it problematic for the Player to ask the Room what pickupable items it contains and then retrieve one of them, but the alternative you suggest is to have a tenuously related object (the Map) pluck an object from the Room and put it into the Player's Inventory collection, which doesn't make any sense in terms of separation of responsibilities. I'm really not clear what your design goals are. When you have two objects, and one has information that the other requires to perform a task, the objects have to communicate. The Player wants to pick up an object, so it asks the Room for it. Or you have a global context that sees everything, and you pull from the Room and push to the Player from there. Or what exactly are you hoping to achieve? A lot of your points make sense, but in this case, the player doesn't have a reference to a room. He only has coordinates, which only make sense when applied to the map in the World object. I agree that a lot of your logic makes sense when rooms work like your system, but this map system is far simpler since it's just a 2D Array, so a Room doesn't have any idea what rooms surrounds it, if any. All it has is, like the player, a 2-point coordinate. I'm planning to rewrite the system to use something along the lines of what you're describing (currently writing a simple XML parser to read a map file), where you logic will make sense to implement. However, my problems with the current solution are still relevant though, since the same system is used in basic 2D tile engines. A tile generally has no idea what surrounds it, you only have coordinates which only make sense in a class of a higher order where your tiles are parts of a 2D array (at least in the tile engines I've seen). So when you move a player, you will generally not be able to go with the style of asking the player for its tile, and in turn asking that tile for surrounding tiles, you pretty much have to use an overarching map object, so we get the same situation: Does the player have a reference to the map object, or does the map object move the player instead, so to speak. What I'm saying here is that your logic is sound, but you're calling the map (or rather world in my case) a "tenously related object", when it's in my system quite fundamental since it's the only object which has references to both the map and the player, since it instantiated both objects. Oh, you've already programmed this. I thought we were talking hypothetically about how you could use an object model to represent these relationships, not about cleaning up an already-existing implementation. If you're going to start from the assumption that your map is a 2-dimensional grid, and all your player has are x and y values, then you can still get a reasonable separation of responsibilities. Your parser is responsible for understanding that "go south" means "attempt to increase the Y coordinate of the player's position by 1". The parser asks the map if that's allowed, the map says yes, the parser tells the player to move to the new coordinates. So the player is responsible for knowing where it is, the map is responsible for knowing what coordinates are legal, and the parser is responsible for determining the meaning of incoming user input.
Yeah, this sounds reasonable to me. So to make it more specific, let's go with a C++ example. Would you say it's reasonable that the CommandParser class #includes both Map.h and Player.h? I'm thinking maybe a "clean" but slightly unwieldy solution would be to go with a MVC style solution and have the CommandParser (being the controller) only include a World.h (being the Model, #including Map.h and Player.h), which in turn handles the commands as sent from the CommandParser. Now the CommandParser would only depend on the World interface and not on the implementation of specific objects. Obviously, the World object itself would be quite big to write... Hmm.
|
|
|
|
|
|
EPT
