The first, and most basic, step to solving problems is to simplify them. Simplify. Simplify. Simplify. Many questions that you are posed will be insurmountable at first. If you wish to succeed in competitive programming or in the real world then you have to be able to take the parts of a question and piece them together in an easier fashion. This brings me to the first step when solving any coding problem. Take the convoluted topic and change it into something more familiar to you.
At a recent competition we were tasked to read in a degree plan, a series of pre-requisites for each class, and finally a course order and determine if the course plan was valid. At face value this seemed to be a very tough problem to crack; however, the problem could be changed into three basic steps and some simple logic with objects.
The question is as follows:
Step 1) This step is the most straightforward. It involves reading in the three lines of input and storing each of them in their respective String variables.
Step 2) This step is a little more daunting since this is where I created an object for each class and a HashMap to store each of these objects in accordance with their names. I started by iterating over the first line of input and adding each element to a HashMap of type String, Class. Each element of this HashMap was then used to manipulate these objects later in a way that they could be accessed easily. After I created the HashMap with each of the class names I then moved on to the second line of input. This line stores the pre-requisite requirements for each class by putting the name of the pre-requisite followed by a -> and then the class it is required for. Within the Class object, I created an ArrayList of type String with the name pres. This would be used to store the pre-requisite classes all in one place. I also created a method to retrieve the size of this ArrayList for later on in the solution. With the second line of input stored in a string, I iterated over it splitting at each comma to delimit different class dependencies. Within each of these strings, I stored the first and last section (being split at ->) as two different string values. These values could then be used to retrieve the dependent class from the HashMap and add the pre-requisite class to its pre ArrayList for manipulation later.
Step 3) Now that we have all information about each class stored in a HashMap we just have to decide whether the classpath requested is legal. To do this we capture the final line of input in a String so that we can iterate over it and progress down the classpath. At each class in the plan, we first test if the object for that class has an ArrayList of size zero. If the size of pre is greater than zero then we have not completed the required class so we can set solved to false and exit the for a loop. If the class does pass the required classes check then we iterate over all other classes in the HashMap and remove it from their pre ArrayList. This is continued for every class in the list until the final solution of whether the class path is legal or not is achieved.
When first read this problem can scare off many programmers, but by looking at the problem in a series of steps for its solution you are able to simplify it down into solving multiple smaller problems. The solution to the problem is not easy by any means to a beginner programmer, but the same thought process applies to all programs you are faced with. When asked to do something that seems insurmountable, take the first few minutes to ask yourself how you can simplify the problem into something feasible. Simplify. Simplify. Simplify.
You can find my solution and the input file on my GitHub here.
Comment (1) on "Basics of solving coding problems"