|
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 25 2013 17:58 nunez wrote:Show nested quote +On February 25 2013 17:36 Arnstein wrote:
Yes, that's the line that is messing up! I don't know how to do this inside of a operator overload function, so I just copied some stuff from the header in the class, and also tried to copy something from the book. In the book you had leftHandSide and rightHandSide, but it didn't seem like these were declared. Then how does C++ know which one they mean? i am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question! you've got all the info you need to solve that exercise lined up in just the right order the institution you are attending deems best. i think you need to trace back a couple of exercises and make sure you understand what the words in the code you are compiling mean (in this context)!
Hmm, it seems like I've done it right all along, but that const messed it up for me! I just removed const, and everything was fine :D
I feel like a programming god, mohahaha!
|
Guys could you please tell me or show a link with an algorithm to find the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough.
Edit: within an n x n grid
|
On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find Show nested quote +the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid
You could just try doing it yourself - a special algorithm shouldn't really be necessary. If you have a number at position (x, y), you can find all eight adjacent numbers with (x-1, y) - if (0, 0) is the top-left, then this is the number directly to the left - and so on. Multiply each adjacent number with the number at (x, y), and you have the product between a number and its adjacent numbers.
Add in checks to make sure you aren't trying to multiply by a number that doesn't exist (e.g., there are no numbers to the left of (0, y)), and you should be good to go.
|
On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find Show nested quote +the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid
Write an O(n) search algorithm. Your operation would be a function like so:
int32 CheckIndex( uint32 i )
{
check left
right
up
down
diagonals
return largest
}
Call this operation on each index. Be sure to make sure you don't index out of the array on fringe elements. Then with the results just keep track of the largest returned value.
|
On February 26 2013 04:33 CecilSunkure wrote:Show nested quote +On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid Write an O(n) search algorithm. Your operation would be a function like so: int32 CheckIndex( uint32 i )
{
check left
right
up
down
diagonals
return largest
} Call this operation on each index. Be sure to make sure you don't index out of the array on fringe elements. Then with the results just keep track of the largest returned value.
This can be optimized with memoization since you would end up doing two multiplications per product by checking every index.
Alternatively, you can go through each direction (horizontal, vertical, diagonal left to right, and diagonal right to left, and multiply each pair one after another, saving the largest result. Compare the results from every direction, and choose the largest. If you need to know the index as well, then save that whenever you have a new maximum in a direction.
int arr[N][N];
for(i:0->N-1) {
for(j:0->N-1) {
horizontalMax = max(horizontalMax,arr[i][j]*arr[i][j+1];
verticalMax = max(verticalMax,arr[i][j]*arr[i+1][j];
//diagnonals....
}
}
//fix the edge cases as well
|
On February 26 2013 05:29 RoyGBiv_13 wrote:Show nested quote +On February 26 2013 04:33 CecilSunkure wrote:On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid Write an O(n) search algorithm. Your operation would be a function like so: int32 CheckIndex( uint32 i )
{
check left
right
up
down
diagonals
return largest
} Call this operation on each index. Be sure to make sure you don't index out of the array on fringe elements. Then with the results just keep track of the largest returned value. This can be optimized with memoization since you would end up doing two multiplications per product by checking every index. Alternatively, you can go through each direction (horizontal, vertical, diagonal left to right, and diagonal right to left, and multiply each pair one after another, saving the largest result. Compare the results from every direction, and choose the largest. If you need to know the index as well, then save that whenever you have a new maximum in a direction.
int arr[N][N];
for(i:0->N-1) {
for(j:0->N-1) {
horizontalMax = max(horizontalMax,arr[i][j]*arr[i][j+1];
verticalMax = max(verticalMax,arr[i][j]*arr[i+1][j];
//diagnonals....
}
}
//fix the edge cases as well
You mispelled memorization 
+ Show Spoiler +jkjk
How do you think of this? Does your brain just go like "huh, big numbers... how do I reduce?"
Albeit I don't think a simple multiplication is enough to warrant such steps.
|
On February 26 2013 08:32 obesechicken13 wrote:Show nested quote +On February 26 2013 05:29 RoyGBiv_13 wrote:On February 26 2013 04:33 CecilSunkure wrote:On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid Write an O(n) search algorithm. Your operation would be a function like so: int32 CheckIndex( uint32 i )
{
check left
right
up
down
diagonals
return largest
} Call this operation on each index. Be sure to make sure you don't index out of the array on fringe elements. Then with the results just keep track of the largest returned value. This can be optimized with memoization since you would end up doing two multiplications per product by checking every index. Alternatively, you can go through each direction (horizontal, vertical, diagonal left to right, and diagonal right to left, and multiply each pair one after another, saving the largest result. Compare the results from every direction, and choose the largest. If you need to know the index as well, then save that whenever you have a new maximum in a direction.
int arr[N][N];
for(i:0->N-1) {
for(j:0->N-1) {
horizontalMax = max(horizontalMax,arr[i][j]*arr[i][j+1];
verticalMax = max(verticalMax,arr[i][j]*arr[i+1][j];
//diagnonals....
}
}
//fix the edge cases as well
You mispelled memorization jkjk How do you think of this? Does your brain just go like "huh, big numbers... how do I reduce?" Albeit I don't think a simple multiplication is enough to warrant such steps.
Just to clarify, my solution doesn't involve memoization, it is an alternate algorithm which just doesn't need to compute it twice.
Memoizing would be taking the previously mentioned implementation, and skipping calculations that you have already done. When you take that code, and reduce it, it turns into the algorithm I mentioned. There is not a magic trick, I just don't like it when code repeats itself.
|
On February 26 2013 08:32 obesechicken13 wrote:Show nested quote +On February 26 2013 05:29 RoyGBiv_13 wrote:On February 26 2013 04:33 CecilSunkure wrote:On February 26 2013 04:15 darkness wrote:Guys could you please tell me or show a link with an algorithm to find the greatest product of two adjacent numbers in any direction (up, down, left, right, or diagonally) ? I've asked Google, but I didn't find something useful enough. Edit: within an n x n grid Write an O(n) search algorithm. Your operation would be a function like so: int32 CheckIndex( uint32 i )
{
check left
right
up
down
diagonals
return largest
} Call this operation on each index. Be sure to make sure you don't index out of the array on fringe elements. Then with the results just keep track of the largest returned value. This can be optimized with memoization since you would end up doing two multiplications per product by checking every index. Alternatively, you can go through each direction (horizontal, vertical, diagonal left to right, and diagonal right to left, and multiply each pair one after another, saving the largest result. Compare the results from every direction, and choose the largest. If you need to know the index as well, then save that whenever you have a new maximum in a direction.
int arr[N][N];
for(i:0->N-1) {
for(j:0->N-1) {
horizontalMax = max(horizontalMax,arr[i][j]*arr[i][j+1];
verticalMax = max(verticalMax,arr[i][j]*arr[i+1][j];
//diagnonals....
}
}
//fix the edge cases as well
You mispelled memorization + Show Spoiler +jkjk
How do you think of this? Does your brain just go like "huh, big numbers... how do I reduce?"
Albeit I don't think a simple multiplication is enough to warrant such steps.
Yeah it's pretty simple. Just realize that you'll do a lot of extra calculations. Then think of ways of how to avoid.
|
A simpler solution would be to, going from left to right for each row, take the current row/col number and multiply it by the number to the right, the number diagonally down and to the right, and the number directly below it. Save the highest product as you find it (and highest index combination, if you need it). You'll never do any more calculations then you need, and the code would be very simple to write.
|
Hey guys,
I'm a 3rd year CS student and I'm looking to get involved with the open source community; however I have no idea how to get started. Anyone want to point me in the right direction? I know that this is a super broad topic, sorry that I can't be more specific. If it helps at all, I would be really interested in getting involved with GNU type stuff.
|
On February 26 2013 18:13 Try wrote:
Hey guys,
I'm a 3rd year CS student and I'm looking to get involved with the open source community; however I have no idea how to get started. Anyone want to point me in the right direction? I know that this is a super broad topic, sorry that I can't be more specific. If it helps at all, I would be really interested in getting involved with GNU type stuff.
Find an open source project you like and contact people involved, go on message boards / mailing lists and ask questions and ask how you can help.
Also a quick google search can always help:
http://www.makeuseof.com/tag/the-10-best-open-source-projects-you-should-be-volunteering-to-help-with/
|
Hi everyone,
I hope this is the right thread. Im interested in learning to program, however I have to admit I have very basic knowledge of computers in general. Ive been (forced to) using Macs (i.e. every small part, script, etc is "hidden" for regular users) untill a couple of years ago and im not at all familiar with the underlying processes in a computer. Could anybody link me a comprehensive page on what makes computers work on certain levels, what processes are ongoing, etc. I feel I need to start at the very bottom, building my knowledge of computers from scratch. Then work towards more advanced subjects like programming, etc.
Much appreciated,
Peace
|
On February 26 2013 18:57 Aphasie wrote:
Hi everyone,
I hope this is the right thread. Im interested in learning to program, however I have to admit I have very basic knowledge of computers in general. Ive been (forced to) using Macs (i.e. every small part, script, etc is "hidden" for regular users) untill a couple of years ago and im not at all familiar with the underlying processes in a computer. Could anybody link me a comprehensive page on what makes computers work on certain levels, what processes are ongoing, etc. I feel I need to start at the very bottom, building my knowledge of computers from scratch. Then work towards more advanced subjects like programming, etc.
Much appreciated,
Peace
just read a good C book. you will learn how machines fundamentally work and get your feet wet programming at the same time. programming is actually more about logic than it is being familiar with an operating for example.
|
On February 26 2013 18:57 Aphasie wrote:
Hi everyone,
I hope this is the right thread. Im interested in learning to program, however I have to admit I have very basic knowledge of computers in general. Ive been (forced to) using Macs (i.e. every small part, script, etc is "hidden" for regular users) untill a couple of years ago and im not at all familiar with the underlying processes in a computer. Could anybody link me a comprehensive page on what makes computers work on certain levels, what processes are ongoing, etc. I feel I need to start at the very bottom, building my knowledge of computers from scratch. Then work towards more advanced subjects like programming, etc.
Much appreciated,
Peace
Code the Hidden Language of Computers by Charlez Petzhold. Modern C Programming 2nd Edition by K. N. King. http://www.randygaul.net/2011/11/16/i-want-to-learn-programming-but-i-know-nothing/
|
Edit: C language
I'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. 
|
Looks fine to me. You can clean things up a little by using some helper functions. You can also use std::max.
product = std::max( grid[i][j] * grid[i+1][j+1], product )
|
On February 27 2013 08:50 darkness wrote:I'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.
For this problem you're going to have to go through the whole grid.
Optimization 1) Don't calculate the reverse of a pair you've already calculated.
Optimization 2) Only need to go through the grid once, not twice (n ^ 2) as you're doing.
int maxProduct = 0;
int maxProductX1 = 0;
int maxProductY1 = 0;
int maxProductX2 = 0;
int maxProductY2 = 0;
int curProduct = 0;
int curX = 0;
int curY = 0;
void TestProduct(int x1, int y1, int x2, int y2)
{
int product = grid[x1][y1] * grid[x2][y2];
if(product > maxProduct) {
maxProduct = product;
maxProductX1 = x1;
maxProductX2 = x2;
maxProductY1 = y1;
maxProductY2 = y2;
}
}
for each element in grid {
// only ever need to test right and "down"
// note: not checking bounds as this is pseudocode
TestProduct(curX, curY, curX + 1, curY);
TestProduct(curX, curY, curX, curY + 1);
}
|
On February 27 2013 08:57 CecilSunkure wrote:Looks fine to me. You can clean things up a little by using some helper functions. You can also use std::max. product = std::max( grid[i][j] * grid[i+1][j+1], product )
Sorry, I forgot to mention it is C not C++. But yeah, I guess this would work in my case:
#ifndef max
#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif
#ifnef min
#define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
#endif
Erm, maybe not. I'm not aware what std::max actually does.
|
|
|
If you care about efficiency I'd imagine you'll want to make your own max function for C, so that your macros don't calculate a bunch of multiplications and array accesses redundantly.
int IntMax( int lhs, int rhs )
{
return lhs > rhs ? lhs : rhs;
}
std::max uses C++ templates:
namespace std
{
template <typename T>
bool max( T lhs, T rhs )
{
return lhs > rhs ? lhs : rhs;
}
}
There are of course other clever tricks using bit manipulations to perform min and max operations, although I wouldn't be surprised if more modern architectures have machine instructions for min and max that commonly replace std::max when std::max is used.
|
|
|
|
|
|
EPT
