Quantcast

Maximum PC

It is currently Mon Jul 28, 2014 12:56 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Approaching Programming Problems
PostPosted: Fri Oct 29, 2004 11:05 am 
8086
8086

Joined: Thu Sep 30, 2004 10:22 pm
Posts: 79
Inspired by what Gadget pointed out in the "Learning C++ & Java" thread about building skills dealing with real-world programming problems, I thought this post would be an interesting helpful one for most of us. For you programmers out there, professional or not, do you have any certain steps or general guidelines that you always use or follow when you try to solve any real-world problems :?: If so, then please post them here that they may be of great help to those of us who are just starting to learn programming. So post away people. ;)


Top
  Profile  
 
 Post subject: Approaching Models
PostPosted: Fri Oct 29, 2004 12:01 pm 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Hi SeVeN,

This applies to only one type of real world problem.

and BTW - I am not what you would call a programmer

Keeping what Gadget said in mind, the first thing I do is to ignore my programming skills when approaching a problem. This isn't the best way to do something, but it allows me to get outside a language and focus on the problem at hand - not the programming language as just about any language can be used to solve a problem if the programmer is adept enough (not saying some aren't more appropriate than others).

The type of problems I generally have to solve are modeling ones.

Models can be very simple - such as "given a rock analysis, what type of rock was analized?"

This is a simple model with basically 2 dimensions (knobs). 1 - what is in the rock, 2- how much.

You have to know about rocks to do it which brings me to step 2 - If you can't at minimum answer the question in a broad manner without a computer or conceptualize how it would be done - you cannot program a solution.

In the example above, if you don't know about rocks, you can't do it. That doesn't mean you have to be a geologist - a simple field guide could tell you what you need to know. Then of course you would test it on real geologists and see that you need a third dimension called "texture" for it to really work - but the hard part you already did.

Now, for me, I start the process of programming after I have conceptualized how I would solve the problem on paper and turned that concept into pseudo code. And then I program the "engine" in sections.

Once the engine is finished I worry about looks and usability. Many folks do something I think is stupid, they program the look and feel before the functioanlity or at the same time. Get the thing to work first - then make it pretty IMO. If you develop the front end while making the engine, you will have issues when a change needs to be made - and you always have to make changes.

Reguarding models like the one above, if you have more than 6 "knobs", you are looking at serious development. The reason is simply none unique solutions - there are too many of them. The model talked about above is a reversable model. If you input a theoretical rock, its called a predictive or forward model. If you put in a real rock analysis, is a inverse or retrodictive model.

Anyways - I am not sure any of this is of use to you. It only applies to certain types of real world problems.

Manta's quote:
"If it can not be done, however impractically, dangerously, or difficultly, without a computer; it can not be done with one.

Manta


Top
  Profile  
 
 Post subject:
PostPosted: Fri Oct 29, 2004 8:45 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
For me, I generally end up working on three different types of problems or projects:

1.) Problems that I have seen before or I generally know the answer to already.
2.) Difficult problems that are going to take some time - I might need to pull out the algorithms book or a math book to get this one done.
3.) Projects that contain one or more problems and a user interface (either cli or gui).

The thing in common is that I generally spend anywhere from one or two minutes to 15 or more minutes making sure that I understand what is being asked. No points for solving the wrong problem! After I am sure that I understand the problem and I am fairly certain that I can work through it on paper, I will start putting it together in a sloppy pseudo-code... sort int[], fori 0 to arr.len, if arr.i == ??? kind of stuff if it is long, or just go straight to coding if it is shorter. The pseudo-code is so I can keep my train of thought going while coding the solution.

Something that I can seriously improve during this phase is identifying and jotting down corner cases / unit tests. Can that array be a null reference? Are you sure that all the ints will be positive, can they be zero, will they overflow, etc. In one of the TC comps, I successfully challenged 3 peoples easy problem (and it was a damn easy problem - given a distance, how long will it take type of problem) because they didn't pay attention to the constraints which stated that the input distance could be zero. It doesn't take very long to travel 0 miles! In the last TopCoder match, a division 1 competitor named TAG successfully challenged 14 peoples medium problem (everyone in his room)! Pay attention to the corner cases.

The thing that seperates #1 and #2 is that I am going to need a lot more scratch paper to make sure that I have all the possible cases, done the math right, or whatever. If the solution is recursive, I might walk through a short test case to make sure that I am ending at the right place and returning the right value.

What seperates #2 and #3 is that I generally have a good idea what I need to do in #2. It is a contest problem, homework assignment, etc. It is very clear what needs to be done and what I need to display. With a project, I'll do the normal software engineering approach of thinking about what I want my program to do from a customers perspective. I'll use some scratch paper on designing a gui, write down the use-cases, draw out the class structure if OOP, etc. I hate not having clear requirements. From there it is a matter of implementing each module... if you do #3 right, then all that is left is a bunch of #1 problems and generally a couple of #2 problems to implement.

A great resource for learning how to solve problems is TopCoder. Open up an old practice problem, solve it and run the system tests to see if you got it right. Then go to the website and read the review for the problem(s) in that match that you just worked on and learn. Was your way the most direct implementation (better to checkmate in 8 than 36, right?). Was there a library function available that you didn't know about? Curious how solutions in different languages might differ... there you go. Here you can learn from some truly phenom-coders.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 30, 2004 6:48 am 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Corners?

Is that the programming term?

Just wondering. We call them end cases or end members. I was just wondering what the official term was. End member is a physical science term.

Thats a good point. Until last year I had never had to program something that someone might input endcase or nonsensical values into because the programs were for specific inputs or for myself - or for folks who would know better and understand why it "blewup". Now that I am looking at being more serious about it, its a real issue. One of the funny things about your basic proplem is that they should have considered it even if the problem didn't state they needed to IMO. But I realize those types of problems are very specific.

Manta - when I have more time - I will improve my skills more.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Oct 30, 2004 6:35 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:
Corners?

Is that the programming term?

Just wondering. We call them end cases or end members. I was just wondering what the official term was. End member is a physical science term.

I believe that what you're refering to as end cases and my corner cases are the same thing. It is just a difference in how you visualize the problem. In a nutshell, here is how corner cases were explained to me. Say we have a function that simply takes an int and returns an int that is 10 larger. Very simple.

Code:
public int add10(int i) {  return i + 10; }


Now visualize the input it as a mathematical function with the input i being a value on the x axis and the output a value on the y axis. So what are the acceptable values of x (not in terms of what will return a correct value, but what will the compiler allow me/you to pass to the function)? Anything greater than or equal to Integer.MIN and less than or equal to Integer.MAX, right? And for y it will be anything greater than Integer.MIN + 10 up to Integer.MAX. So now we have a square representing all possible combinations of input and output. Now the idea is that most errors are not going to be in the middle of this square, but around the edges and in the corners. So a good sequence of test inputs would probably be to start with 0, 1, 10, 1000, 1 million, -1 million to make sure things are working. Basic blackbox testing. Next jump to the far edges and see what happens when you try Integer.MAX - 2 which returns an incorrect result. We can grey out a small vertical strip along the rightmost edge that causes overflow. A more thorough testing would include the value of a corner and corner + 1 in every direction... same thing with the edges. A more difficult problem with two inputs and a return value has x,y inputs and a z return value with many more corners and edges to check.

BTW, you almost always want to test 0 and 1 because of their interesting math properties - screwing up something like 2^0 makes you feel pretty dumb! If it were a higher math problem, you would probably want to check e, pi, etc.

By end cases, do you mean when to terminate a loop? You can approach it similiarly. BTW, this is more formal than what I was suggesting previously. I like the extreme programming philosphy of writing unit tests before coding because it makes you think a bit harder about the problem and solution before wasting any time writing a bad implementation.


Top
  Profile  
 
 Post subject:
PostPosted: Sun Oct 31, 2004 6:09 am 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
[quote="Gadget"][/quote]

Basically you are on it. An end case is when all the weight of a problem is on one of its extremes. Example:

A ternary diagram is a triangle (very common in geoscience). Each end case sits on a corner. These can be applied to any problem with three components. In theory, each corner contributes to the solution - so a solution should sit inside the triangle. An end case would be when a solution sits on a corner - or even an edge. These represent your model space boundries - the edges of your universe. These are the places most likely for the model to fail.

And end member is the term used when the model is applied to a natural thing - like a rock, mineral, water type, etc.... - but its the same thing.

OK, corners, good to know.

Manta


Top
  Profile  
 
 Post subject: Re: Approaching Models
PostPosted: Sun Oct 31, 2004 7:42 am 
7yrs+11,000 Posts
7yrs+11,000 Posts
User avatar

Joined: Tue Jul 27, 2004 5:44 pm
Posts: 11242
Location: The kitten above is not on fire.
MantaBase wrote:
Hi SeVeN,

This applies to only one type of real world problem.

and BTW - I am not what you would call a programmer

Keeping what Gadget said in mind, the first thing I do is to ignore my programming skills when approaching a problem. This isn't the best way to do something, but it allows me to get outside a language and focus on the problem at hand - not the programming language as just about any language can be used to solve a problem if the programmer is adept enough (not saying some aren't more appropriate than others).

The type of problems I generally have to solve are modeling ones.

Models can be very simple - such as "given a rock analysis, what type of rock was analized?"

This is a simple model with basically 2 dimensions (knobs). 1 - what is in the rock, 2- how much.

You have to know about rocks to do it which brings me to step 2 - If you can't at minimum answer the question in a broad manner without a computer or conceptualize how it would be done - you cannot program a solution.

In the example above, if you don't know about rocks, you can't do it. That doesn't mean you have to be a geologist - a simple field guide could tell you what you need to know. Then of course you would test it on real geologists and see that you need a third dimension called "texture" for it to really work - but the hard part you already did.

Now, for me, I start the process of programming after I have conceptualized how I would solve the problem on paper and turned that concept into pseudo code. And then I program the "engine" in sections.

Once the engine is finished I worry about looks and usability. Many folks do something I think is stupid, they program the look and feel before the functioanlity or at the same time. Get the thing to work first - then make it pretty IMO. If you develop the front end while making the engine, you will have issues when a change needs to be made - and you always have to make changes.

Reguarding models like the one above, if you have more than 6 "knobs", you are looking at serious development. The reason is simply none unique solutions - there are too many of them. The model talked about above is a reversable model. If you input a theoretical rock, its called a predictive or forward model. If you put in a real rock analysis, is a inverse or retrodictive model.

Anyways - I am not sure any of this is of use to you. It only applies to certain types of real world problems.

Manta's quote:
"If it can not be done, however impractically, dangerously, or difficultly, without a computer; it can not be done with one.

Manta



Is writing your passion manta?


Top
  Profile  
 
 Post subject:
PostPosted: Sun Oct 31, 2004 8:38 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
How do I approach a problem? Sneakily, from the shadows, like a ninja. But, if I don't roll my Stealth skill ...

Gadget wrote:
I like the extreme programming philosphy of writing unit tests before coding because it makes you think a bit harder about the problem and solution before wasting any time writing a bad implementation.


This is the way that I approach my code as well.

(Lame RPG jokes go over well with a geek audience, right? I'm still pre-coffee this morning.)


Top
  Profile  
 
 Post subject:
PostPosted: Tue Nov 02, 2004 10:37 am 
8086
8086

Joined: Thu Sep 30, 2004 10:22 pm
Posts: 79
Thanks guys, I have to say that I find this to be helpful information indeed. I think it gives me a basic idea of what some of the problems that a programmer would face. I admit that I get a bit lost on the whole cornner/end casees issue. Is this is like part of an OOP design? Manta, I'd appreciate it if you can tell me some more about the ternary diagram. I assume this is something I'll come to know as I go deeper into programming, but it wouldn't hurt to ask to early, I guess.


Top
  Profile  
 
 Post subject:
PostPosted: Wed Nov 03, 2004 12:03 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
SeVeN wrote:
Thanks guys, I have to say that I find this to be helpful information indeed. I think it gives me a basic idea of what some of the problems that a programmer would face. I admit that I get a bit lost on the whole cornner/end casees issue. Is this is like part of an OOP design?

No. You might be thinking of use cases? Here is a link to an article on corner cases. It applies to any paradigm of programming that supports any degree of modularity (OK, I haven't verified that as a fact, but all of them that I can think of). In fact, it doesn't need to even be a module of code. For example, this java program takes to ints on the command line and prints the result.

Code:
public class Add {
  public static void main(String[] args) {
    int i = Integer.parseInt(args[0]);
    int j = Integer.parseInt(args[1]);
    System.out.println(i+j);
    System.exit(0);
  }
}


An example run would be "java Add 1 1" prints "2". Something like "java Add 3 A" is going to cause an exception which is different type of error. What we're looking to test is stuff at the extremes of the input and output possibilities. In this example, something like "java Add 3000000 0" is not going to print "300000000" (assuming it doesn't throw and exception... I'll have to check some day).

An example I found in a previous TC match concerned swimming times. Given a distance and speed how long would it take someone to swim the distance. Here people missed a distance of 0 which is a end case (or edge graphically).


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 07, 2004 4:59 am 
8086
8086

Joined: Thu Sep 30, 2004 10:22 pm
Posts: 79
OK Gadget, that article expailns a lot...made things much easier for me to understand what you guys are talking about in here. That Java example you gave also helped clarifying things more. Thanks man. :)


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 07, 2004 7:52 am 
I'd rather be modding!
I'd rather be modding!
User avatar

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
SeVeN wrote:
Thanks guys, I have to say that I find this to be helpful information indeed. I think it gives me a basic idea of what some of the problems that a programmer would face. I admit that I get a bit lost on the whole cornner/end casees issue. Is this is like part of an OOP design? Manta, I'd appreciate it if you can tell me some more about the ternary diagram. I assume this is something I'll come to know as I go deeper into programming, but it wouldn't hurt to ask to early, I guess.


Sorry SeVeN, I didn't mean to confuse by talkin' with Gadget.

Unless you will be programming for chemists, geologist, hydrologists, biologists, material engineers, or planetary science folks, you don't need to worry about them. Here is a geoscience example of an applet:

http://home.earthlink.net/%7Ebaedke/triplot/

The point was, that at the "corners" and edges of this diagram is where a good number of null inputs occur (or can) in the original data program.

A simple example - division by zero could crash a model. Its most likely to occur when you are at one of the "corners". You want to look for cases like this when you program and ensure they are delt with.

As for learning about ternary plots, I think you should not waste your time unless you are just board. If you need them you can learn about them when the time comes.

Manta


Top
  Profile  
 
 Post subject:
PostPosted: Thu Nov 18, 2004 11:39 pm 
8086
8086

Joined: Thu Sep 30, 2004 10:22 pm
Posts: 79
err...sorry for my late reply manta. Thanks for your help though...I guess I'll look up some info about the ternary diagram whenever I got the time. It's honestly been very hectic for me during the last month...I barely had the time to even come here & check on the forums. I'll come back for more questions if I ever had any. ;) I appreciate all your help, all the info you gave was helpful indeed. So thanks again. :D


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 4 guests


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

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group