Critique my solution please.

Cinjection · **Posted:** Sat Feb 23, 2008 4:29 pm

Hey guys. In my quest to learn dynamic programming techniques, I've solved the S4 problem from the 2007 CCC. To my great pleasure, my solution seems to work and is fast. I'm happy with it, but I'm wondering if I'm doing something wrong. I'd appreciate if someone could look over my C++ solution and tell me if I'm doing something wrong or not doing something right.

Here's a link to the question:
http://cemc.uwaterloo.ca/ccc/2007/seniorEn.pdf

My C++ solution is below:

code:

#include <fstream>
#include <vector>

using namespace std;

vector<int> *nodes;

vector<int> nWays(1);

int calculateNWays(int nodeNum)
{
if (nodeNum == 1){
return nWays[1]; //One way to get to the first node.
}
else if (nWays[nodeNum] != 0)
{
return nWays[nodeNum];
}
else
{
int ways(0);

for(int i=0; i < nodes[nodeNum].size(); i++)
{
ways += calculateNWays( nodes[nodeNum][i] );
}

return ways;
}
}

int main()
{
ifstream in("S4.in");
ofstream out("S4.out");

int nNodes(0);
in>>nNodes;

nodes = new vector<int>[nNodes+1];
nWays.resize(nNodes+1);

//Init to zero
for (int i=0; i <= nNodes;i++)
{
nWays[i] = 0;
}

//Read connections
int nodeFrom(0);
int nodeTo(0);

in>>nodeFrom;
in>>nodeTo;

do
{
nodes[nodeTo].push_back(nodeFrom);

in>>nodeFrom;
in>>nodeTo;

} while (nodeFrom != 0 && nodeTo != 0);

nWays[1] = 1;

//Let's go do some dynamic programming!
for (int k=2; k <= nNodes; k++)
{
nWays[k] = calculateNWays(k);
}

out<<nWays[nNodes]<<endl;

delete [] nodes;
in.close();
out.close();

return 0;

}

Please critique my code any way you can, as it will help me for next time. Thanks in advance.

md · **Posted:** Sat Feb 23, 2008 7:00 pm

Your solution is short and ugly! It also dresses poorly! Wink

Actually I'm insanely far behind on some work; but a cursory glance seems to show it's good.

Got some problem files we can test it with too?

wtd · **Posted:** Sun Feb 24, 2008 12:19 am

Quick one:

code:

in>>nodeFrom;
in>>nodeTo;

code:

in >> nodeFrom >> nodeTo;

Cinjection · **Posted:** Sun Feb 24, 2008 12:49 pm

md @ Sat Feb 23, 2008 7:00 pm wrote:

Your solution is short and ugly! It also dresses poorly! Wink

Actually I'm insanely far behind on some work; but a cursory glance seems to show it's good.

Got some problem files we can it with too?

Thanks. I tested it with the test cases that CCC used, and it worked with all five.

cyberfish · **Posted:** Wed Mar 19, 2008 5:32 pm

Don't know about the coding, but the algorithm is exactly the same as the one I submitted.

http://access.mmhs.ca/ccc/2007/CCC2007S4WaterparkRecursion.txt

A.J · **Posted:** Wed Mar 19, 2008 5:56 pm

I had a MUCH faster method by recording the values (memoization) + DP

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members